Foundation lesson · do not skip this if you are new
A quantum algorithm is not given a NumPy array for free. Before discussing speedups, we must say how classical data, matrix entries, or a linear operator become quantum operations. State preparation, query oracles, and block encodings are three different access contracts.
Contract. Build a circuit P that creates the input quantum state you actually want to use.
Why it matters. Algorithms that start from amplitude-encoded data need this state before any later quantum subroutine can help. Preparation cost is therefore part of the end-to-end algorithm, not decorative preprocessing.
The Pauli-X and Hadamard cases show the smallest exact examples.
Contract. Ask a reversible black box for a matrix entry encoded in a work register.
Why it matters. Query-complexity theorems often count how many times the oracle is called, but a real fault-tolerant implementation must also build the arithmetic and memory circuit hidden inside that call.
The GHL Robin paper explicitly contrasts this model with its gate-level construction.
Contract. Embed a possibly non-unitary matrix A as the clean ancilla block of a larger unitary U_A.
Why it matters. Quantum hardware applies unitary gates. Block encoding is the interface that lets algorithms such as QSVT and Hamiltonian simulation manipulate a general structured matrix through a unitary circuit.
BE Case 1, the cubic diagonal family, and the Robin case all certify this contract.
How to read a quantum circuit
wireA horizontal wire is one qubit/register. Time flows from left to right.|0>A ket at the left fixes the input state of that wire.H, X, RYA box is a gate. Its matrix acts when the state reaches that box.controlA control dot means another gate acts only when the control condition is satisfied.daggerU† means the inverse/conjugate-transpose circuit; it often uncomputes temporary information.ancillaAn ancilla is workspace. A clean block-encoding proof normally requires selected ancillas to start and end in |0>.measurementMeasurement converts quantum amplitudes into classical outcomes; it is different from the coherent unitary part of the circuit.The H-plus-CNOT circuit above prepares the Bell state \((|00\rangle+|11\rangle)/\sqrt2\). The same visual grammar is used in the case studies; larger diagrams only add named registers and uncomputation.
“quantum state vectors are unit vectors with respect to the Euclidean norm.”Quantum circuitsIBM Quantum Learning / John Watrous
“The flow of information along the wires goes from left to right”Lecture Notes on Quantum Algorithms for Scientific ComputationLin Lin
“A more general input model, as will be discussed in this chapter, is called ‘block encoding’.”
New to quantum computing? Start here.
A classical program updates bits. In the circuit model used here, a quantum program applies reversible linear transformations to complex amplitude vectors and reads classical outcomes through measurement.
Textbook / teaching anchor
Standard textbook reference for quantum mechanics, qubits, gates, and the circuit model.
Textbook / teaching anchor
Circuit-first computer-science viewpoint on qubits and quantum information.
Textbook / teaching anchor
Beginner-friendly state-vector, measurement, multi-system, and circuit explanations.
Textbook / teaching anchor
Foundations, entanglement, circuits, algorithms, and error correction.
Guided reading
Part I develops State Preparation after the shared finite-matrix and circuit foundations. Part II develops Block Encoding on exactly those same lower nodes. The intended inclusion-like curriculum direction is Part I → Part II: a verified PREPARE is a reusable subproblem inside many block-encoding constructions. A block can also be consumed for state preparation, but that is a different downstream theorem requiring input, accepted-branch, normalization and success-cost obligations.
Reading map
The graph makes State Preparation a reusable subproblem of the broader Block Encoding toolchain without identifying their certificate types. Reverse block-to-state consumption remains a separately typed path.
flowchart TB F["Shared foundations<br/>finite matrices, basis states, circuits"] F --> S1["State preparation"] S1 --> S2["State action and<br/>first-column certificates"] S2 --> S3["Prepared-state routes<br/>and reusable PREPARE components"] F --> B1["Block encoding"] B1 --> B2["Ancillas, register order,<br/>normalization and projection"] B2 --> B3["Composition, dilation,<br/>LCU and QSVT interfaces"] S3 -. "nested PREPARE layer + SELECT + unprepare" .-> B3 B3 -. "downstream consumer only: input + branch + normalization/amplification" .-> S3 S3 --> H["ASPBE search,<br/>verification and exports"] B3 --> H classDef shared fill:#f8f5ee,stroke:#826a32,color:#222222,stroke-width:1.5px; classDef state fill:#edf5f1,stroke:#2f7355,color:#18382b,stroke-width:1.5px; classDef block fill:#eef3f7,stroke:#49677d,color:#1f2e39,stroke-width:1.5px; classDef system fill:#ffffff,stroke:#64747a,color:#222222,stroke-width:1.25px; class F shared; class S1,S2,S3 state; class B1,B2,B3 block; class H system;
Current chapters
Chapters 1–2 are shared foundations authored once and reused by Block Encoding; Chapters 3–4 specialize them to preparation certificates.
Block Encoding reuses the same finite-matrix and circuit nodes, then adds projected-block, composition, resource and proof-gated construction obligations.
Planned curriculum · not current theorem status
New chapters must reuse compatible lower graph nodes and pass the same source, semantic, Lean, integration, exposition and independent-review gates. A source listed here is a curriculum anchor, not a claim of formalization.
flowchart TB
CORE["Shared Lean graph<br/>finite linear algebra · tensors · registers · unitaries<br/>states/density operators · channels · norms/distances · resources"]
subgraph CURRENT["Current textbook"]
SP["Part I · State Preparation<br/>U|0^n⟩ = |ψ⟩"]
BE["Part II · Block Encoding<br/>‖A - αΠUΠ†‖ ≤ ε"]
end
QIT["Planned Part III · Quantum Information<br/>Leditzky: symmetry · Schur–Weyl · de Finetti<br/>cloning · spectrum estimation"]
SCI["Planned Part IV · Quantum Scientific Computing<br/>Lin–Wiebe: QSP/QSVT · simulation · QPE<br/>walks · linear systems/ODEs · open systems"]
EXT["Attributed external Lean references<br/>Mathlib · quantum-computing-lean · Lean-QuantumInfo<br/>lean-quantum · Lean-QuantumAlg-Bench · Lean-QIT-Bench"]
CORE --> SP
CORE --> BE
CORE --> QIT
CORE --> SCI
SP -. "nested preparation layer + SELECT + unprepare" .-> BE
BE -. "downstream consumer (not inclusion): input + branch + normalization/amplification" .-> SP
BE --> SCI
QIT --> SCI
EXT -. "reviewed reuse / narrow adapters only" .-> CORE
NOTE["Conceptual curriculum graph only.<br/>Dashed arrows are conditional transports, not Lean implications."]
NOTE -.-> CURRENT
NOTE -.-> QIT
NOTE -.-> SCI
classDef core fill:#f8f5ee,stroke:#826a32,color:#222222,stroke-width:1.5px;
classDef state fill:#edf5f1,stroke:#2f7355,color:#18382b,stroke-width:1.5px;
classDef block fill:#eef3f7,stroke:#49677d,color:#1f2e39,stroke-width:1.5px;
classDef future fill:#f7f4fb,stroke:#735a8f,color:#2f2440,stroke-width:1.5px;
classDef external fill:#ffffff,stroke:#64747a,color:#222222,stroke-width:1.25px;
class CORE core;
class SP state;
class BE block;
class QIT,SCI future;
class EXT,NOTE external;
Planned Part III
Leditzky's representation-theoretic QIT notes anchor density operators/measurements, composite systems and entanglement, representation theory, Schur–Weyl duality, invariant states, de Finetti, cloning and spectrum-estimation routes.
Planned Part IV
Lin–Wiebe, 29 April 2026 anchors channels/distances, query models, perturbation/statistics, qubitization/QSP/QSVT, simulation, phase estimation, walks, linear systems, differential equations and open systems. Its Block Encoding chapter reuses Part II rather than creating a second API.