Block Encoding
Embedding an arbitrary matrix as a sub-block of a larger unitary so it can act on quantum states.
The problem it solves
Quantum gates are unitary, but the matrices we want to apply (Hamiltonians, covariance matrices, general operators) usually are not. Block encoding resolves this by placing the target matrix A, scaled by a normalization factor alpha, inside the top-left corner of a unitary U acting on the data register plus some ancilla qubits.
Definition
U is an (alpha, m, epsilon) block encoding of A if, using m ancilla qubits, the top-left block satisfies || A - alpha (<0|^ancilla tensor I) U (|0>^ancilla tensor I) || <= epsilon. In words: prepare the ancillas in |0>, apply U, and post-select the ancillas back on |0>; the data register then experiences A/alpha up to error epsilon. The normalization alpha must be at least the spectral norm of A.
How encodings arise
- Sparse matrices: oracles for the positions and values of nonzero entries give an efficient block encoding.
- LCU: a sum of unitaries A = sum c_k U_k yields a block encoding with alpha = sum |c_k|.
- Density matrices: purifications provide natural block encodings.
- Products and sums of block-encoded matrices compose into new block encodings.
Why it matters
Block encoding is the input model for modern quantum linear algebra. Once A is block-encoded, the quantum singular value transformation applies polynomials to its singular values, delivering matrix inversion, Hamiltonian simulation, and filtering from a single framework. The quality of the encoding (its normalization alpha and ancilla count) directly sets the cost and success probability of everything built on top.
Cost accounting
The subnormalization alpha appears in the query complexity: routines using the encoding typically scale with alpha, so tighter encodings (smaller alpha) are better. Amplitude amplification boosts the post-selection success probability from 1/alpha^2 toward order one. Constructing efficient, low-alpha block encodings for a given matrix is often the central engineering challenge in applying quantum linear algebra.