Sparse-access oracle construction

What it fills

• Block-encode a matrix

  Wrap an operator $A$ inside a larger unitary $U$ so that $A/α$ sits in $U$'s top-left block, giving every routine above it one uniform way to touch the matrix. The subnormalization $α$ and the ancilla count are outputs of this layer, not free parameters.

When it applies

Needs $A$ to be $s_r$-row-sparse and $s_c$-column-sparse with $|a_ij| ≤ 1$ after rescaling, and needs the sparsity-pattern oracles $O_r$ and $O_c$ to be efficiently implementable. That is an assumption about structure, and it is separate from the question of whether it holds for a given application.

Requires

Every step this method names moves its route along, so there is nothing it needs alongside them.

Example

given  A, s_r-row-sparse and s_c-column-sparse, with |a_ij| <= 1 after rescaling,
       the row and column index oracles O_r and O_c,
       and the entry oracle O_A

# O_r and O_c must be efficiently implementable. That is an assumption about
# structure, separate from whether it holds for a given application

prepare uniform superpositions over the sparsity pattern

rotate an ancilla by arcsin of each entry

swap registers

# A is left in the flagged block: that is the block-encoding

# Gilyen, Su, Low and Wiebe Lemma 48 gives a (sqrt(s_r*s_c), w+3, epsilon)-
# block-encoding of A, from a single use of O_r, a single use of O_c, two uses
# of O_A, plus O(w + log^2.5(s_r*s_c/epsilon)) one- and two-qubit gates
# -- the record does not say which of the stages above each use falls in

# Lemma 48 assumes |a_ij| <= 1 and states alpha = sqrt(s_r*s_c) flat. The
# alpha = sqrt(s_r*s_c)*||A||_max form usually quoted is the standard
# rescaling, not what the lemma says, so it is not written here

# and that count is in queries, not gates. Zhang and Yuan open the oracle: for
# general matrices, even including sparse ones, they prove that sparse-access
# input models and block-encoding both require nearly linear circuit
# complexities relative to the matrix dimension. A routine that is logarithmic
# in queries to an oracle whose own circuit is linear in N is a linear-cost
# routine

Cost, as the source states it

Gilyén, Su, Low and Wiebe (arXiv:1806.01838) Lemma 48 gives a $(\sqrt(s_r·s_c), w+3, \varepsilon)$-block-encoding of $A$, using a single use of $O_r$, a single use of $O_c$, two uses of $O_A$, plus $O(w + \log^{2.5}(s_r·s_c/\varepsilon))$ one- and two-qubit gates. Lemma 48 assumes $|a_ij| \leq 1$ and states $\alpha = \sqrt(s_r·s_c)$ flat; the $\alpha = \sqrt(s_r·s_c)·||A||_max$ form usually quoted is the standard rescaling, not what the lemma says.

Implementations

• Qualtran's `SparseMatrix` block-encoding bloq

  • Expressing and Analyzing Quantum Algorithms with Qualtran

  Qualtran's paper defines a block encoding the same way this method's sibling entries quote it: "the (s + a)-qubit unitary B[A] is a (α, a, ϵ)-block encoding of A if" $\lVert A - \alpha(\langle 0|^{\otimes a} \otimes I)\mathcal{B}[A](|0\rangle^{\otimes a} \otimes I)\rVert \le \epsilon$. Of the three primitive routes it lists — "unitaries, LCU SELECT/PREPARE oracles, and sparse access matrices" — this is the third: "Third, Qualtran's SparseMatrix bloq constructs a block encoding for a sparse matrix A with at most m non-zero entries in each row or column, given oracles" $O_r|i\rangle|k\rangle = |i\rangle|r_{ik}\rangle$, $O_c|j\rangle|\ell\rangle = |c_{j\ell}\rangle|\ell\rangle$ "to compute the index $r_{ij}$ or $c_{ji}$ of the j-th nonzero entry in the i-th row or column respectively of A, and" $O_A|i\rangle|j\rangle|0\rangle = |i\rangle|j\rangle|A_{ij}\rangle$ "to compute the matrix entry $A_{ij}$" — the same three-oracle interface this method's own hop names. The paper's own citation for that oracle set is not Gilyén, Su, Low and Wiebe (cited elsewhere in the same paper for the singular value transformation) but Dalzell, Clader, Salton, Berta, Lin, Bader, Stamatopoulos, Schuetz, Brandão, Katzgraber and Zeng, "End-to-end resource analysis for quantum interior-point methods and portfolio optimization", PRX Quantum 4 (2023).

  The bloq lives in a file whose own docstrings cite a third source again: `RowColumnOracle`, `EntryOracle` and `SparseMatrix` each list "References: [Lecture Notes on Quantum Algorithms for Scientific Computation](https://arxiv.org/abs/2201.08309). Lin Lin (2022). Ch. 6.5", not the Qualtran paper's own citation. `SparseMatrix.__attrs_post_init__` raises "Unequal row and column sparsities are not supported" whenever `row_oracle.num_nonzero != col_oracle.num_nonzero`, so the class only implements the equal-sparsity case $s_r=s_c=s$ of this method's oracle set, not the fully general $s_r \neq s_c$ case its own hop's theory states. `build_composite_bloq` composes, in order, a `diffusion` step (`PrepareUniformSuperposition(n=row_oracle.num_nonzero)` wrapped in `AutoPartition`, not a bare Hadamard layer), `col_oracle`, `entry_oracle`, a `Swap`, `row_oracle.adjoint()`, then `diffusion.adjoint()` — the class's own ASCII circuit diagram draws exactly that sequence. `alpha` returns `row_oracle.num_nonzero` directly — the flat sparsity count, not a square root — and `ancilla_bitsize` is `system_bitsize + 1`, matching the docstring's stated $(s, n+1, \epsilon)$-block encoding.

  No matrix is downloaded or measured; sparsity pattern and entries come from the caller's choice of oracle. Two `RowColumnOracle`s ship built in: `TopLeftRowColumnOracle`, whose implementation comment reads "the l-th non-zero entry is at position l, so do nothing", and `SymmetricBandedRowColumnOracle`, parameterised by a `bandsize`. Two `EntryOracle`s ship built in: `UniformEntryOracle`, a single `Ry(2*arccos(entry))`, and `ExplicitEntryOracle`, which loads `arccos` of a supplied NumPy array from `QROM` and applies it as controlled `Ry` rotations bit by bit. The test file's `test_vlasov_explicit` builds an $8\times8$ ($n=3$) Vlasov-equation Hamiltonian from its own `gen_vlasov_hamiltonian(n, alpha, m)` helper and block-encodes it with `SymmetricBandedRowColumnOracle(n, bandsize=1)` plus `ExplicitEntryOracle`.

  `qualtran/bloqs/block_encoding/sparse_matrix.py` in https://github.com/quantumlib/Qualtran — Python, Apache License 2.0, header "Copyright 2024 Google LLC"; 500 lines as read on 2026-08-27 (most recent commit to the file aa47606, 2026-03-09), latest tag v0.7.0. The block-encoding class is `SparseMatrix(row_oracle, col_oracle, entry_oracle, eps)`, an `attrs.frozen` subclass of `BlockEncoding` from `qualtran.bloqs.block_encoding.block_encoding_base`; its oracle arguments are typed `RowColumnOracle` and `EntryOracle`, both `abc.ABC` subclasses of `Bloq` defined in the same file. A sibling file in the same directory, `sparse_matrix_hermitian.py`, defines a Hermitian-restricted variant not covered here.

  The file's own `sparse_matrix_test.py` is the only source of numbers. `test_sparse_matrix_params` asserts `bloq.alpha == 4`, `bloq.epsilon == 0` and `bloq.ancilla_bitsize == 2 + 1` for a 2-qubit example (`TopLeftRowColumnOracle(system_bitsize=2)`, all $2^2=4$ entries nonzero), and `bloq.alpha == 2**n` symbolically for general `system_bitsize=n`. `test_call_graph` counts `sigma[Hadamard()] == 4` for the concrete example and `6 * n` symbolically. `test_sparse_matrix_tensors` reconstructs the matrix as `bloq.tensor_contract() * alpha` and checks it against `np.full((4, 4), 0.3)`; `test_vlasov_explicit` does the same for the $8\times8$ Vlasov Hamiltonian at `atol=0.02`. `tensor_contract` is Qualtran's own classical tensor-network contraction, built on quimb (`import quimb.tensor as qtn` in `qualtran/simulation/tensor/_quimb.py`) — none of these checks run on a quantum simulator or hardware backend.

• QCLAB scripts for explicit sparse block-encoding circuits

  • Explicit Quantum Circuits for Block Encodings of Certain Sparse Matrices

  The abstract states the goal plainly: "we give a few examples on how efficient quantum circuits can be explicitly constructed for some well structured sparse matrices, and discuss a few strategies used in these constructions. We also provide implementations of these quantum circuits in MATLAB." Its base result, Theorem 4.1, is presented as "a variant of [Gilyén et al., 2019, Lemma 48 (in the full version)]": given a unitary $O_c$ with $O_c|\ell\rangle|j\rangle = |\ell\rangle|c(j,\ell)\rangle$ and a unitary $O_A$ with $O_A|0\rangle|\ell\rangle|j\rangle = (A_{c(j,\ell),j}|0\rangle + \sqrt{1-|A_{c(j,\ell),j}|^2}|1\rangle)|\ell\rangle|j\rangle$, then $U_A = (I_2 \otimes D_s \otimes I_N)(I_2 \otimes O_c)\,O_A\,(I_2 \otimes D_s \otimes I_N)$ "block encodes A/s" for an s-sparse A — using only a column oracle and an entry oracle, no separate row oracle. The paper's own concluding remarks name that omission as a limitation, not an oversight: "it may be difficult to find an efficient $O_c$ if the sparsity pattern of A is somewhat arbitrary. In some cases, a more general block encoding scheme that includes an additional $O_r$ unitary that encodes the row sparsity separately from the column sparsity may be needed" — the row oracle this method's own hop uses throughout is, in this paper, an extension the released scripts do not implement.

  Three matrix families are released as QCLAB `.m` functions returning `[circuit, OA, OC, D]`, each built in the order $D \to O_A \to O_C \to D$ — the right-to-left reading of Theorem 4.1's $U_A$: a real symmetric $2\times2$ matrix (`realsym2_simple.m`), a banded circulant/tridiagonal matrix with periodic or non-periodic boundary conditions (`tridiag.m` and three variants), and the adjacency matrix of a weighted extended binary tree on $2^n$ nodes (`extbintree.m`). `realsym2_simple.m` is the direct Theorem-4.1 construction: `theta1 = 2*acos(alpha1)`, `theta2 = 2*acos(alpha2)`, applied as two `CRotationY` gates for $O_A$ and a single `CNOT(0,1)` for $O_C$ — matching the paper's own worked example, credited there as "using the following two lines QCLAB code". A separate, non-oracle script for the same $2\times2$ matrix, `realsym2.m`, instead factors the block encoding as the seven-unitary product $U_A = U_6U_5U_4U_3U_2U_1U_0$ of equation (4.1); the paper notes this circuit "requires 2 ancilla qubits in addition to the n = 1 system qubit required to match the dimension of A", making the resulting unitary "of dimension $2^3$, which is twice the dimension of the block encoding given by" equation (3.4) — the earlier, explicitly impractical square-root construction from section 3 of the paper (rejected there because it requires computing the square root of $A^\dagger A$), not a comparison against the $O_A$/$O_C$ oracle construction of Theorem 4.1 that `realsym2_simple.m` implements. `tridiag.m` builds $O_A$ from three angles `theta0/1/2 = 2*acos(alpha - 1 / beta / gamma)` as multi-controlled `MCRotationY` gates and $O_C$ from the file's own `leftshift`/`rightshift` helpers; `extbintree.m` builds a four-angle $O_A$ and an $O_C$ composed from `mul2`/`div2`/`leftshift`/`rightshift`. None of the three families constructs a separate row oracle.

  No dataset: each script's input is a handful of scalars fixing the matrix's own entries — `alpha1, alpha2` for the $2\times2$ case; `alpha, beta, gamma` (diagonal, sub- and super-diagonal) for the tridiagonal case, checked in-code by `assert(0 <= alpha); assert(alpha <= 2); assert(abs(beta) <= 1); assert(abs(gamma) <= 1)`; and `n, alpha, beta, gamma` for the extended binary tree. Every `test_*.m` script builds the dense matrix `A` directly in MATLAB from those same scalars for comparison.

  https://github.com/QuantumComputingLab/explicit-block-encodings — MATLAB, 21 files under `explicit-block-encodings/`, no license file (the GitHub API reports `license: null`). The repository's most recent commit is dated 2022-12-14 (`pushed_at: 2022-12-14T23:49:12Z`), unchanged since. The README states "This repository contains a collection of MATLAB scripts to generate explicit quantum circuits for block encodings of certain sparse matrices in QCLAB" and depends on the separate `QuantumComputingLab/qclab` toolbox. Function signatures read directly off the files: `[circuit,OA,OC,D] = tridiag(n,alpha,beta,gamma)`, `[circuit,A,OA,OC,D] = realsym2_simple(alpha1,alpha2)`, `[circuit,OA,OC,D] = extbintree(n,alpha,beta,gamma)`.

  No hardware or simulator is named: every `test_*.m` script instead builds the circuit's dense unitary classically via QCLAB's `circuit.matrix` property and checks it against the target matrix. `test_tridiag.m` sets `n=3, a=0.3, b=0.5, c=0.7`, forms `M = 4*U(1:2^n,1:2^n)`, and asserts `norm(A - M) < 1e-14` and `norm(U'*U - eye(size(U))) < 1e-14`; `test_realsym2_simple.m` runs the same pattern with `M = 2*U(1:2,1:2)`; `test_extbintree.m` with `M = 8*U(1:2^n,1:2^n)`. The scaling factors 2, 4 and 8 are each script's own sparsity count rounded up to a power of 2, matching Theorem 4.1's A/s.

What it needs

Nobody has taken this apart yet. That is a gap in this graph, not a claim that the method has no parts.

Other ways to fill the same slot

Different approaches

• Block-encoding from a Pauli decomposition

  Write $A = Σ_j c_j P_j$ over Pauli strings; PREPARE loads amplitudes proportional to $sqrt(|c_j|)$ into an ancilla register, SELECT applies the controlled Pauli strings, and PREPARE$†$ unprepares, leaving $A/||c||_1$ in the block flagged by the all-zeros ancilla. This is the input model chemistry and lattice Hamiltonians supply for free.

• FABLE approximate circuit construction

  Build the block-encoding directly from uniformly controlled Ry (magnitude) and Rz (phase) rotations between Hadamards and a SWAP, with no oracle assumption at all, then threshold the rotation angles and cancel the resulting CNOT chains to compress the circuit.

• Tensor hypercontraction block encoding

  Factorize the chemistry Hamiltonian's two-electron integrals into a product of much smaller matrices first, then build the block-encoding of the factorized form. The saving is not in the encoding technique but in what is being encoded — a tensor with far fewer independent entries than the one the basis handed you.

In the Atlas

No record in the Atlas covers this yet. The catalogue is circuits and primitives; this part of the literature is not in it.

Sources

• Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics↗András Gilyén, Yuan Su, Guang Hao Low, Nathan Wiebe · 2018theory yes · simulation no · hardware no
• Circuit complexity of quantum access models for encoding classical data↗Xiao-Ming Zhang, Xiao Yuan · 2023theory yes · simulation ? · hardware no