Algorithm Zoo · Primitives
Block Encoding
First described: Low, Chuang (concept); Gilyén et al. (framework), 2017
The problem
Encode an arbitrary matrix A into the top-left block of a unitary U.
A block encoding is a unitary U such that A/α = (⟨0|⊗I) U (|0⟩⊗I) for some scaling α ≥ ||A||. Block encodings are the input model for QSVT, qubitization, and modern HHL — they replace 'sparse matrix oracle' as the dominant abstraction.
Best classical
n/a (this is an input model, not an algorithm)
Quantum complexity
Depends on construction. For s-sparse N×N matrices with row-oracle access: 2 row queries plus O(log N) gates.
Our verdict
The right input model for the 2026 era. If you're writing a new quantum algorithm and you're not thinking in block encodings, you're thinking in 2010. Construction cost is the real bottleneck — getting the block encoding cheap is the engineering work.
When to use it
- Always, if you're designing a quantum algorithm that touches a matrix in 2026.
- When you need to apply f(A) for some polynomial f — block encoding plus QSVT does this efficiently.
When not to use it
- When sparse-matrix oracle access has tighter known constants for your particular problem.
Classical baseline
n/a
Hardware cost
1-2 ancilla qubits per block encoding. Linear combinations of block encodings (LCBE) compose at additive ancilla cost.
Key papers
- Quantum Singular Value Transformation and Beyond ↗
Gilyén, Su, Low, Wiebe · 2019 · STOC
Deep-dive tutorials
Last verified: 2026-05-24