Select-Swap QROM 数据加载¶
oracq.algorithms.input_model.data_loading
Select-Swap QROM data loading (Low–Kliuchnikov–Schaeffer 2018; Babbush et al. 2018).
A QROM lookup realizes a classical table T as the XOR database
|address, data> -> |address, data XOR T[address]>. The baseline
qrom_lookup is a unary iteration of per-address controlled XOR;
select_swap_qrom splits the address into high bits h (k bits) and low
bits y (l bits); λ = partitions = 2^l window partitions share the high
address and load the sub-tables T[h·λ + i] in parallel, then merge by
controlled swaps keyed on y == i, trading query depth against ancilla
qubits at a T count of about 4(2^k + λ·b). Like gate_database, the data
table is expanded into gate-level sub-databases at generation time and does not
enter the IR JSON; resource estimation is given purely classically by
qrom_cost.
- class oracq.algorithms.input_model.data_loading.QromCost(n_addresses, data_bits, partitions, address_bits, select_toffoli, swap_toffoli, work_qubits, fanout_qubits)[源代码]¶
基类：
objectResource-estimation snapshot for Select-Swap QROM; the Toffoli/T counts are for a single compute pass.
- n_addresses¶
- data_bits¶
- partitions¶
- address_bits¶
- select_toffoli¶
- swap_toffoli¶
- work_qubits¶
- fanout_qubits¶
- property t_count¶
T count of a single compute pass, estimated at 4 T per Toffoli.
- property t_depth¶
with partitioned parallel loading the select segment is a serial unary iteration and the swap segment merges level by level per partition.
- Type:
T depth
- property round_trip_t_count¶
Round-trip T count for coherent uncomputation (compute plus adjoint uncompute); measurement-based uncomputation can drop the uncompute.
- property ancilla_qubits¶
the λ data windows plus the low-bit fanout copies (the latter may use dirty qubits).
- Type:
Total ancilla qubits
- oracq.algorithms.input_model.data_loading.qrom_cost(n_addresses, data_bits, partitions=1)[源代码]¶
Purely classical resource estimation for Select-Swap QROM: T count/depth about
4(N/λ + λ·b), with λ being partitions.- 参数:
n_addresses -- Number N of words in the lookup table.
data_bits -- Data word bit width b.
partitions -- Partition count λ; must be a power of two not exceeding
2^ceil(log2 N).
- 返回:
Snapshot of the Toffoli/T counts and ancilla-qubit estimates for this configuration.
- 返回类型:
- oracq.algorithms.input_model.data_loading.qrom_lookup(table, *, data_bits=None, name=None)[源代码]¶
QROM baseline: a unary iteration of per-address controlled XOR (i.e. Select-Swap with partitions=1).
Same structure as gate_database but annotated qrom_unary_iteration and carrying a qrom_cost estimate, serving as the λ=1 endpoint of the Select-Swap trade-off curve.
- 参数:
table -- Sequence of words or a sparse dict; missing addresses are treated as 0.
data_bits -- Data bit width; defaults to the width of the largest table word.
name -- Module name; generated from the table content when omitted.
- 返回:
Unary-iteration database view annotated with qrom_cost.
- 返回类型:
- oracq.algorithms.input_model.data_loading.select_swap_qrom(table, *, partitions, data_bits=None, name=None)[源代码]¶
Select-Swap QROM: partitioned parallel loading sharing the high address bits, merged by low-bit controlled swaps.
The λ window registers (clean local registers) each perform the sub-table query
window_i ^= T[h·λ + i]; all windows share the high address h, so the select segment pays for only one 2^k unary iteration. Then, keyed ony == i, the controlled swap–xor–swap composite is applied to(window_i, data)(preserving the database_xor XOR semantics under arbitrary initial data values without destroying the window contents), and finally the sub-queries are replayed adjointly to uncompute all windows. The fanout copies of the low bits y (which may use dirty qubits and are counted in qrom_cost's fanout_qubits) are implied by the Control primitive in the RIR and left for expansion during backend lowering.- 参数:
table -- Sequence of words or a sparse dict; missing addresses are treated as 0.
partitions -- Partition count λ; must be a power of two not exceeding the number of addresses.
data_bits -- Data bit width; defaults to the width of the largest table word.
name -- Module name; generated from the table content when omitted.
- 返回:
Select-Swap database view annotated with qrom_cost.
- 返回类型: