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.

An access model for $A$ — sparse-access oracles, a Pauli or LCU decomposition, a purification, or an explicit arithmetic description — plus a target precision $\varepsilon$.

1. Matrix you can query → Block-encodingsuperpose the indices, rotate by the entry

   The encoding is a Gram-matrix sandwich $U = U_{L}^{\dagger}U_{R}$. With $D_{s}$ preparing $|0\rangle \mapsto \sum_{k=1}^{s}|k\rangle/\sqrt{s}$, the two halves are $V_{L} := O_{r}(I_{w+2} \otimes D_{s_{r}})\mathrm{SWAP}_{w+1}$ and $V_{R} := O_{c}(D_{s_{c}} \otimes I_{w+1})$, so that $V_{L}$ spreads a row index over its $s_{r}$ nonzero positions and $V_{R}$ does the same down a column. Their overlap is a pure indicator: $\langle 0|^{w+2}\langle i|V_{L}^{\dagger}V_{R}|0\rangle^{w+2}|j\rangle = 1/\sqrt{s_{r}s_{c}}$ if $a_{ij} \ne 0$ and $0$ otherwise. assumption: that identity says only that an entry is nonzero, so it rests entirely on $O_{r}$ and $O_{c}$ returning the true index of each row's and column's $k$-th nonzero, padded out past the sparsity bound. The value itself arrives separately: $U_{R}$ queries $O_{A}$ on the surviving pair and rotates one qubit to $a_{ij}|0\rangle + \sqrt{1-|a_{ij}|^{2}}|1\rangle$, then calls $O_{A}$ again to uncompute the query register. approximation: that rotation is implemented "with precision $O(\mathrm{poly}(s_{r}s_{c}/\varepsilon))$" — an exact rotation through the arcsine of a queried value would take unboundedly many gates.

   approximationassumption

A unitary $U$ on $s+a$ qubits, its subnormalization $\alpha$, and its ancilla/flag count $a$. Because $\lVert U\rVert = 1$, Gilyén, Su, Low and Wiebe's Definition 43 forces $\lVert A\rVert \le \alpha + \varepsilon$.

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

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.

The Lemma 48 count is in queries, not gates. Zhang and Yuan open the oracle: "For general matrices (even including sparse ones), we 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.

• Qualtran's `SparseMatrix` block-encoding bloq

  • Expressing and Analyzing Quantum Algorithms with Qualtran

    Matthew P. Harrigan, Tanuj Khattar, Charles Yuan, Anurudh Peduri, Noureldin Yosri, Fionn D. Malone, Ryan Babbush, Nicholas C. Rubin · 2024

  About

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

  Methods

  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.

  Data

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

  Code

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

  Results

  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

    Daan Camps, Lin Lin, Roel Van Beeumen, Chao Yang · 2022

  About

  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.

  Methods

  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.

  Data

  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.

  Code

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

  Results

  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.