Quantum Linear Algebra
A toolkit of primitives - block encoding, linear combination of unitaries, and singular value transformation - for manipulating matrices as quantum operations.
Matrices as operators
Classical linear algebra runs on arrays of numbers. Quantum linear algebra instead treats a matrix A as an operation embedded inside a larger unitary, then transforms it using quantum circuits. The central abstractions are block encoding, the linear combination of unitaries (LCU), and the quantum singular value transformation (QSVT), which together unify many quantum algorithms.
Block encoding
A unitary U block-encodes a matrix A (suitably normalized) if A appears as the top-left block of U: applying U and post-selecting ancillas on |0> effectively applies A to the data register. This lets non-unitary matrices act on quantum states. See block encoding for details.
Linear combination of unitaries
Any matrix can be written as a weighted sum A = sum_k c_k U_k of unitaries. LCU implements this sum by preparing an ancilla in a state proportional to sqrt(c_k), applying the U_k conditioned on the ancilla, then unpreparing the ancilla. Post-selecting the ancilla on |0> applies A up to normalization. LCU is a workhorse for Hamiltonian simulation and matrix functions.
What the toolkit builds
- Hamiltonian simulation exp(-iHt) via LCU or QSVT.
- Matrix inversion A^-1 (the heart of linear-system solvers).
- Matrix functions like sign, exponential, and projectors via polynomial approximation.
- Amplitude amplification and phase estimation as special cases.
QSVT as the unifier
QSVT applies a polynomial transformation to the singular values of a block-encoded matrix. Choosing the polynomial gives inversion (approximating 1/x), exponentiation, thresholding, and more, all from the same circuit template with different phase angles. Many separately discovered algorithms are now understood as QSVT with a particular polynomial, giving the field a common language.
The data-access caveat
These primitives assume efficient block encoding of the input matrix and efficient preparation of input states. When those hold (structured, sparse, or quantum-native data) the speedups can be exponential; when data must be loaded from scratch, loading cost can dominate. This caveat governs the practical reach of the entire toolkit.