Sparse Access

English · 简体中文

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

Overview

The sparse matrix oracle (SO in the input-model vocabulary) follows the CKS position / entry separation convention and is organized as a bundle of two query operations rather than a fictitious total unitary:

• Position \(P_A^{(1)}\) (paradigm sparse_location_inplace, in place): \(|\text{column}, i\rangle \mapsto |\text{column}, \nu(\text{column}, i)\rangle\), where \(\nu\) enumerates the nonzero rows of the column;

• Entry \(P_A^{(2)}\) (paradigm sparse_entry_xor): \(|\text{row}, \text{column}, d\rangle \mapsto |\text{row}, \text{column}, d \oplus A[\text{row},\text{column}]\rangle\), any row and column can be queried.

The gate implementation requires a full permutation extension per column (the partial permutation over the nonzero rows is completed into a permutation on \([0, 2^w)\)), while the QRAM implementation uses a forward and an inverse lookup table.

Interface and input model

abstract_sparse_access(name, width, value_width, sparsity, work_width=None)
sparse_location_gate(width, permutations, *, work_width=None, name=None)
sparse_location_qram(width)
sparse_entry(database, width)

API entry points: abstract_sparse_access, sparse_location_gate, sparse_location_qram, sparse_entry

• abstract_sparse_access: an open declaration producing the two operations name_position / name_entry; the position operation carries the sparsity and full_permutation_extension=True attributes; work_width defaults to width.

• sparse_location_gate: permutations gives the full \(2^w \times 2^w\) permutation table per column.

• sparse_location_qram: declares the two QRAM(2*width, width) tables forward / inverse.

• sparse_entry: adapted from XorDatabase, requires address_width == 2*width (row|column concatenated addressing).

SparseAccess(location, entry, width, value_width, sparsity) is a frozen dataclass constraining \(1 \le \text{width} \le 64\), \(1 \le \text{value\_width} \le 64\), \(1 \le \text{sparsity} \le 2^{\text{width}}\), with position signature ("column", "index", "work") and entry signature ("row", "column", "data"). Attributes:

Attribute	Meaning
location / entry	the two underlying Operation objects
width / value_width / sparsity	dimension bits, value word width, sparsity
describe()	OracleSpec (type cks_sparse, anc_qubit=None, position / entry component descriptions, sparsity parameter)

Implementation notes

The gate position implementation executes the permutation column by column under control: each cycle is decomposed along a single-bit-difference path into transpositions, and each transposition is further realized as a forward path of controlled X plus a return path, with the intermediate basis states restored. The gate count explodes with \(2^w\); the implementation only suits witnessing on small instances.

The QRAM position implementation performs the in-place permutation in three steps: work ^= forward[column, index], swap(index, work), work ^= inverse[column, index] — the last step cleans work back to zero while index holds the new value. In the catalog cases the forward and inverse tables are bound after resource renaming (forward / inverse).

SparseAccess is a bundle, not a unitary: as a whole anc_qubit=None, which avoids disguising the two query operations as one unitary. Downstream it is consumed by qlss.SparseSystem (the sparse input model of the CKS Chebyshev / Costa walk solvers) and can also be turned into a block encoding via the sparse→BE adaptation in sparse.py; applications/catalog.py and examples/ode_input_models.py give assembly examples.

Validation approach

Category C5 (data-access layer; acceptance criteria in ../development/validation-plan.md §2). Three layers of evidence:

• Structure: tests/core/test_contracts.py:OracleContractTests.test_sparse_is_a_bundle_not_a_fictitious_unitary — type == "cks_sparse", anc_qubit is None, and the component descriptions and sparsity parameter are correct.

• Numerical: tests/core/test_qlss_input_models.py:QLSSInputTests.test_signed_sparse_encoding_and_chebyshev — after sparse_location_gate + sparse_entry(gate_database(...)) assembles a 2×2 symmetric sparse system, the (0,0) block of the sparse→BE adaptation is cross-checked element by element against the dense matrix (places = 11, α = 2); test_matrix_probe_recovers_scalar_system_norm reuses the same entry query as a norm probe (places = 10). The real-backend side is consumed by tests/integration/test_qfvm_input_models.py:QfvmInputNativeTests (the integrity of the location permutation and the raw QRAM fields).

• Binding: the paradigm capability restrictions are witnessed by OracleContractTests.test_capability_restrictions_survive_annotation_and_wrapping; the QRAM position implementation enters the catalog cases (the closure and serialization checks of tests/core/test_workloads.py:WorkloadTests.test_every_catalog_case_has_a_closed_description).

Known gaps and planned stages

Three-binding consistency parameterization (to be rolled out in V4): a unified parameterized cross-check of the gate / QRAM position implementations against the abstract declaration is not rolled out; the existing evidence is scattered across the downstream witnesses. Consistent with the oracles.py row of validation-coverage.md.

Related links

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

• Same-group pages: XOR database

• API reference: Oracle declarations and implementations

• Concepts: Oracles and operator representations

• Validation matrix: Validation coverage matrix

Numerical validation

Paper-grade numerical validation script: tests/verification/verify_blockencoding.py (real-backend execution, no mock substitutes, no skips; all 73 cases passed on 2026-09-16), artifact out/verification/blockencoding.json. This page corresponds to sparse-access-layer plus sparse-lookup-helpers, sparse-boolean-helpers, and sparse-rotation-helpers, 4 cases in total (for the end-to-end behavior of the access layer inside a block encoding see the numerical validation section of Sparse matrix block encoding).

Experiment design (dim = 4, tridiagonal structural positions, fixed-point format 3.1 signed):

1. Position oracle sparse_location_gate: all 16 (column, index) basis-state inputs are read out one by one against the classical permutation table, and work must be cleaned back to 0;

2. Entry oracle sparse_entry: all 16 (row, column) × two initial data values (0 and the nonzero value 5) verify the XOR semantics \(d \oplus A_{rc}\);

3. QRAM position implementation sparse_location_qram: the forward/inverse tables are bound as memory data, the clean-up semantics are verified basis state by basis state, and the reference and rir-pysparq backends agree amplitude by amplitude;

4. Access-layer helpers: reversible_lookup with fused address/data views over 128 input groups, batch_lookup with three concurrent lookups, compare_words (eq/lt, exhaustive over all inputs for bit widths 1–4), value_transposition (all 512 input groups at 3 bits), prefix_state uniform prefix superposition, and the analytic probability semantics of word_rotation / magnitude_rotation.

Case	Scale	Paths	Metric	Value
sparse-access-layer (gate position)	dim 4, 16 basis states	reference	permutation mismatch count	0
ditto (entry XOR)	16 × 2 groups	reference	mismatch count	0
ditto (QRAM position)	16 basis states	reference + rir	mismatch count / backend deviation	0 / 0
sparse-lookup-helpers	128 groups of fused views + batching	reference	mismatch count	0
sparse-boolean-helpers	eq/lt exhaustive + transposition 512 groups	reference	mismatch count / prefix uniformity error	0 / 1.1e-16
sparse-rotation-helpers	bit widths 2–4 / format 4.1	reference + rir	probability semantics error	5.6e-16 / 1.1e-16

Reproduction command:

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

Artifacts: out/verification/blockencoding.json.