Select-Swap QROM

English · 简体中文

Category C5 · Module oracq.algorithms.input_model.data_loading · Stage V4

Overview

Select-Swap QROM is the resource-optimized implementation of QROM lookup (Low–Kliuchnikov–Schaeffer 2018; Babbush et al. 2018, cited in the module docstring): the address is split into the high part h (k bits) and the low part y (l bits), \(\lambda = 2^l\) window partitions share the high address bits and load the sub-tables \(T[h\cdot\lambda + i]\) in parallel, then merge through controlled swaps keyed on \(y = i\), trading query depth against ancilla qubits at a T count of about \(4(2^k + \lambda b)\) (b is the data bit width) (QRAM in the input-model vocabulary).

Interface and input model

select_swap_qrom(table, *, partitions, data_bits=None, name=None)
qrom_cost(n_addresses, data_bits, partitions=1)

API entry points: select_swap_qrom, qrom_cost

• table: a sequence of words or a sparse dictionary; missing addresses are treated as 0.

• partitions: the partition count λ; it must be a power of two and no more than the number of addresses \(2^{\lceil\log_2 N\rceil}\).

• data_bits: the data bit width; by default the bit width of the largest table word.

Returns XorDatabase (implementation="select_swap"); the external interface is still the two bits registers address / data, with XOR semantics exactly matching the baseline. Module attributes carry the qrom_cost estimate (field table in QROM lookup), where work_qubits = λ·b counts the window registers and fanout_qubits = (λ-1)·l the low-bit fanout copies (usable as dirty qubits).

Implementation notes

Three phases: select — each of the λ clean local window registers window_i performs its sub-table query window_i ^= T[h·λ+i]; all windows share the high address bits, so the unary iteration is paid only once: \(2^k - 1\) (for k = 0 the sub-table is constant and it degenerates to X gates); merge — controlled on y == i, the compound swap–xor–swap is applied to (window_i, data), with net effect a controlled data ^= window_i, preserving XOR semantics for arbitrary data initial values without destroying the window contents; uncompute — an adjoint replay of the sub-queries uncomputes all windows back to zero.

For the test baseline (N = 16, b = 3), the trade-off curve given by qrom_cost:

λ	select	swap	t_count	t_depth	work	fanout	ancilla qubits
1	15	0	60	15	3	0	3
2	7	3	40	8	6	1	7
4	3	9	48	6	12	6	18
8	1	21	88	8	24	21	45
16	0	45	180	15	48	60	108

t_count reaches its valley at λ = 4 (the two inequalities asserted by the test test_cost_model_matches_formulas_and_tradeoff_curve), and t_depth is likewise minimal at intermediate partitions; at λ = 16 the high bits are exhausted and the select phase degenerates into pure swaps. Applicability boundary: increasing λ lowers the T depth but linearly increases ancilla qubits; the optimal λ depends on the hardware’s qubit / depth exchange rate.

Validation approach

Category C5 (data-access layer; acceptance criteria in ../development/validation-plan.md §2). Three layers of evidence in tests/core/test_data_loading.py:DataLoadingTests (16-address table TABLE16, b = 3):

• Structural: test_generated_operations_carry_cost_attributes — attributes such as select_toffoli / swap_toffoli / t_count / work_qubits / dirty_fanout_qubits agree item by item with qrom_cost(16, 3, 4).

• Numerical: test_select_swap_matches_gate_database_per_address — for λ ∈ {1, 2, 4, 8, 16}, the readouts of all 16 addresses equal the gate_database baseline pointwise; test_xor_semantics_with_nonzero_data_register (with data initial value 5 the output is T[a] XOR 5); test_superposition_query_restores_clean_work (after a query on a uniform address superposition the marginal distribution is uniform, places = 12; the windows are forced clean by LocalExit); test_cost_model_matches_formulas_and_tradeoff_curve — λ = 4 sits at the bottom of the curve (curve[4] < curve[1] = 4·15 and < curve[16] = 4·45), and the curve is asserted to agree pointwise with the closed form \(4(N/\lambda - 1 + b(\lambda - 1))\).

• Binding: the gate / QRAM bindings are covered indirectly by test_result_invariant_across_partitions_and_qrom_lookup_baseline (results do not change with partitions or implementations); three-binding consistency parameterization is pending for V4.

• Negative cases: test_invalid_inputs_fail_at_generation — partitions not a power of two / out of range, empty tables, negative values, out-of-range word widths, etc. raise ValidationError at generation time.

Known gaps and planned stages

Three-binding parameterization (V4): unified parameterized cross-checks of the gate / QRAM bindings of the same declaration are not rolled out; validation-plan §5 additionally suggests bringing qrom_cost into catalog-report attributes. Consistent with the data_loading.py row of validation-coverage.md.

Related links

• Source: src/oracq/algorithms/input_model/data_loading.py

• Same-group pages: QROM lookup, XOR database

• API reference: Select-Swap QROM data loading

• Concepts: Oracles and operator representations

• Validation matrix: Validation coverage matrix

Numerical validation

Paper-level numerical validation script: tests/verification/verify_blockencoding.py (executed on real backends, no mocks, no skips; as of 2026-09-16 all 73 cases pass), artifact out/verification/blockencoding.json. This page corresponds to 6 cases: select-swap-lambda{1,2,4,8,16} and select-swap-as-sparse-entry.

Experiment design: 16 addresses, 3-bit random data words (fixed seed), with the partition count λ scanned over {1, 2, 4, 8, 16}; for each λ, all 16 addresses × two data initial values (0 and the nonzero 5, checking XOR semantics) are read out per basis state and cross-checked amplitude by amplitude against the gate_database truth-table baseline (reference path). End-to-end case: select_swap (λ = 2) serves as the element database of the CKS sparse block encoding, assembling the \(T^\dagger S T\) block encoding of a 2×2 signed sparse matrix, whose zero-signal block, after multiplying by α, is cross-checked element by element against the classical matrix (see the numerical validation section of sparse matrix block encoding).

Case	Scale	Backend paths	Metric	Value
select-swap-lambda1	16 addresses × 2 initial values	reference	max deviation from baseline	0
select-swap-lambda2	ditto	reference	ditto	0
select-swap-lambda4	ditto	reference	ditto	0
select-swap-lambda8	ditto	reference	ditto	0
select-swap-lambda16	ditto	reference	ditto	0
select-swap-as-sparse-entry	dim 2, s=2, α=3.0	reference	sparse BE block max_error	4.4e-16

Reproduction command:

PYTHONPATH=src /path/to/backend/python tests/verification/verify_blockencoding.py

Artifact: out/verification/blockencoding.json.