Block-encode a matrix

Why this is a layer

Downstream query counts are linear in $\alpha$, so the same matrix encoded two different ways can differ in end-to-end cost by orders of magnitude: $\alpha = 1$ for a purified density operator, $||c||_1$ for a Pauli LCU, $sqrt(s_r·s_c)$ for sparse access under $|a_ij| \leq 1$, and $2^n$ for FABLE. Comparing two block-encodings without comparing their $\alpha$ says nothing. This is also where an exponential advantage most often dies quietly, because a construction that needs $\Omega(N)$ gates to build $U$ erases whatever the solver above it saves — and most results at this layer are stated in queries to an oracle rather than in gates.

Records for what it handles

The catalogue's own entries for the objects on either side of this contract.

Ways to do this

4 methods recorded

• Sparse-access oracle construction

  Given row and column index oracles $O_r$, $O_c$ and an entry oracle $O_A$, prepare uniform superpositions over the sparsity pattern, rotate an ancilla by arcsin of each entry, and swap registers to leave $A$ in the flagged block. This is the standard construction behind the sparse-Hamiltonian line, formalized as a block-encoding by Gilyén, Su, Low and Wiebe.

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

Routes that skip this layer

These do not fill the slot. They replace the span it belongs to, so this layer is not on their path at all.

• Product-formula (Trotter-Suzuki) simulation

  Split $H$ into terms that can each be exponentiated directly and alternate short evolutions of them — the Lie-Trotter formula and its higher-order generalizations. No block-encoding is built and there is no all-zeros flag to amplify.

This is a step inside

• QSVT matrix inversion

  Block-encode $A$, apply the quantum singular value transformation with an odd polynomial approximating a scaled $1/x$ away from the origin, then amplify. Because it acts on singular values, $A$ need not be Hermitian or sparse — only block-encodable.

• Discrete adiabatic inversion

  Encode the solution as the null eigenstate of a Hamiltonian path built from $A$ and $|b>$, follow that path with a sequence of qubitization walk operators to fixed precision, then finish with an eigenstate filter implemented as a linear combination of walk operators rather than by quantum signal processing. Costa and co-authors prove an adiabatic theorem for intrinsically discrete-time evolutions, which removes the residual $\log(κ)$ that continuous adiabatic treatments carried.

• Eigenstate filtering inversion

  Construct the minimax-optimal polynomial that is 1 at a target eigenvalue and uniformly small outside a spectral gap, and apply it through quantum signal processing. For a linear system $|x>$ is the null eigenstate of a Hamiltonian built from $A$ and $|b>$, so one application of the filter solves it once a starting state with non-trivial overlap is supplied.

• Quantum singular value transformation

  Interleave the block-encoding $U$, its inverse, and projector-controlled phase shifts $e^{iφ(2Π-I)}$ so that the designated block becomes $P$ applied to the singular values of $A$. The phase sequence is the compiled form of the polynomial, and a single ancilla qubit carries the phase shifts.

• Chebyshev series by linear combination of unitaries

  Write the target function as a Chebyshev series, then implement that series as a linear combination of walk-operator powers using a PREPARE/SELECT pair on an ancilla register, and post-select. No phase factors are computed — the polynomial enters through the coefficients of the combination instead.

• Truncated-Taylor LCU simulation

  Truncate the Taylor series of $e^{-iHt}$ over short segments and implement the truncated sum as a linear combination of unitaries — PREPARE loads the coefficients, SELECT applies the terms, PREPARE$†$ unprepares — with the all-zeros ancilla flag amplified.

• Qubitization walk simulation

  From a block-encoding pair $(U, |G⟩)$ with $H = (⟨G|⊗I)U(|G⟩⊗I)$, build a walk operator $W$ that splits the Hilbert space into invariant two-dimensional $SU(2)$ subspaces, one per eigenvalue of $H$, with eigenvalues $e^{±i·arccos(H/α)}$. Quantum signal processing phases applied to $W$ then produce $e^{-iHt}$.

Routes that run this slot many times

For these routes this slot is inside a loop, so its cost is multiplied rather than paid once. That multiplier is usually the largest single term in what the route costs.

• QSVT matrix inversion runs m = O((1/δ) log(1/ε)) applications of U and U†

  The loop stays coherent: nothing is measured between turns. The preparation may still be reapplied every turn — what the loop never pays is a readout and a restart from classical data. The price is depth, and a success probability that multiplies down the chain.

• Quantum singular value transformation runs n uses of U and n of U†, for a degree-n transform

  The loop stays coherent: nothing is measured between turns. The preparation may still be reapplied every turn — what the loop never pays is a readout and a restart from classical data. The price is depth, and a success probability that multiplies down the chain.

No multiplicity recorded

These routes take this step and no source we have read says how often. That is an absence, not a claim that they take it once.

• Discrete adiabatic inversion

  Encode the solution as the null eigenstate of a Hamiltonian path built from $A$ and $|b>$, follow that path with a sequence of qubitization walk operators to fixed precision, then finish with an eigenstate filter implemented as a linear combination of walk operators rather than by quantum signal processing. Costa and co-authors prove an adiabatic theorem for intrinsically discrete-time evolutions, which removes the residual $\log(κ)$ that continuous adiabatic treatments carried.

• Eigenstate filtering inversion

  Construct the minimax-optimal polynomial that is 1 at a target eigenvalue and uniformly small outside a spectral gap, and apply it through quantum signal processing. For a linear system $|x>$ is the null eigenstate of a Hamiltonian built from $A$ and $|b>$, so one application of the filter solves it once a starting state with non-trivial overlap is supplied.

• Chebyshev series by linear combination of unitaries

  Write the target function as a Chebyshev series, then implement that series as a linear combination of walk-operator powers using a PREPARE/SELECT pair on an ancilla register, and post-select. No phase factors are computed — the polynomial enters through the coefficients of the combination instead.

• Truncated-Taylor LCU simulation

  Truncate the Taylor series of $e^{-iHt}$ over short segments and implement the truncated sum as a linear combination of unitaries — PREPARE loads the coefficients, SELECT applies the terms, PREPARE$†$ unprepares — with the all-zeros ancilla flag amplified.

• Qubitization walk simulation

  From a block-encoding pair $(U, |G⟩)$ with $H = (⟨G|⊗I)U(|G⟩⊗I)$, build a walk operator $W$ that splits the Hilbert space into invariant two-dimensional $SU(2)$ subspaces, one per eigenvalue of $H$, with eigenvalues $e^{±i·arccos(H/α)}$. Quantum signal processing phases applied to $W$ then produce $e^{-iHt}$.

In the Atlas

• Encoding of linear kinetic plasma problems in quantum circuits via data compression

  Encode a linear kinetic plasma problem — modeling electrostatic linear waves, driven by a spatially localized external current, in a one-dimensional Maxwellian electron plasma — into a quantum circuit that solves the resulting linear system.