Many Variations of QROAM

[fdmalone]

I was a little confused about the expected QROM costs when implementing something for THC.

There are at least four possible expected (Toffoli) costs:

1. No dirty ancilla [1] : d / k + M * (k-1) (this is used for THC prepare)
2. Dirty Ancilla [1]: 2 d / k + 4 * M * (k - 1)
3. No dirty ancilla [2] : d / k + 2 * M * k
4. Dirty ancilla [2] : 2 d / k + 8 M * k

d = data size, k = block size, M = number of bits of output.

[1] https://quantum-journal.org/papers/q-2019-12-02-208/pdf/ (page 9)
[2] https://arxiv.org/pdf/1812.00954.pdf Table II, rows 3 and 4, 4th column

[fdmalone]

Relevant Screenshot from [1]

[fdmalone]

Some code

from qualtran.cirq_interop import CirqGateAsBloq
from cirq_ft.algos.select_swap_qrom import SelectSwapQROM
num_bits = 15
data_size = 230
num_blocks = 2
sel_swap = SelectSwapQROM(
        (10,)*data_size,
        target_bitsizes=(15,),
        block_size=2**num_blocks,
    )
qroam = CirqGateAsBloq(
    sel_swap
)
print(qroam.t_complexity())
cost_1 = int(np.ceil(data_size/2**num_blocks))
cost_2 = num_bits * (2**num_blocks - 1)
print(f"THC cost (no dirty ancilla) = {4*(cost_1 + cost_2)}")
print(f"THC cost (dirty ancilla) = {4*(2* cost_1 + 4*cost_2)}")
cost_1 = int(np.ceil(data_size/2**num_blocks))
cost_2 = num_bits * (2**num_blocks)
print(f"Select Swap QROM (no dirty ancilla) = {4*(cost_1 + 2 * cost_2)}")
cost_2 = num_bits * (2**num_blocks)
print(f"Select Swap QROM (dirty ancilla) = {4*(2 * cost_1 + 8 * cost_2)}")

58 4 (15,)
T-count:   744
Rotations: 0
Cliffords: 4150

T-count:   744
Rotations: 0
Cliffords: 4366

THC cost (no dirty ancilla) = 412
THC cost (dirty ancilla) = 1184
Select Swap QROM (no dirty ancilla) = 712
Select Swap QROM (dirty ancilla) = 2384

[fdmalone]

I'm a little concerned that our Tcounts are quite different than what I might expect (option 4) but I imagine there's some leeway with the parameters. cc @tanujkhattar

[fdmalone]

We also need to account for cheaper inversion which has cost:

[fdmalone]

Also QROAM on two registers