Select-Swap QROM data loading¶

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)[source]¶

Bases: object

Resource-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

to_dict()[source]¶

Structured dictionary for gallery and backend reports.

Returns:: Flat dictionary of the resource counts and width fields.
Return type:: dict[str, int]

oracq.algorithms.input_model.data_loading.qrom_cost(n_addresses, data_bits, partitions=1)[source]¶

Purely classical resource estimation for Select-Swap QROM: T count/depth about 4(N/λ + λ·b), with λ being partitions.

Parameters:

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).

Returns:

Snapshot of the Toffoli/T counts and ancilla-qubit estimates for this configuration.

Return type:

QromCost

oracq.algorithms.input_model.data_loading.qrom_lookup(table, *, data_bits=None, name=None)[source]¶

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.

Parameters:

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.

Returns:

Unary-iteration database view annotated with qrom_cost.

Return type:

XorDatabase

oracq.algorithms.input_model.data_loading.select_swap_qrom(table, *, partitions, data_bits=None, name=None)[source]¶

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 on y == 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.

Parameters:

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.

Returns:

Select-Swap database view annotated with qrom_cost.

Return type:

XorDatabase