Linear Algebra for Quantum Algorithms

Quantum algorithms derive their computational advantage from the mathematical structure of complex vector spaces. This entry provides a rigorous yet accessible foundation in the linear algebra concepts essential for understanding qubit state spaces, unitary transformations, measurement postulates, and multi-qubit entanglement. It serves as a prerequisite reference for Grover’s search, Shor’s factoring, and variational quantum eigensolvers (VQE).

1. Introduction

Classical computation operates on bits represented as elements of the field $𝔽₂$ , but quantum computation generalizes this framework to complex Hilbert spaces. Every quantum algorithm—whether amplitude amplification, phase estimation, or quantum machine learning—relies fundamentally on linear algebra. Mastery of vector spaces, inner products, matrix transformations, and spectral decomposition is not merely advantageous; it is strictly necessary for deriving, analyzing, and implementing quantum protocols.

This entry systematically bridges abstract linear algebra with quantum mechanical formalism, emphasizing computational interpretations over physical derivations.

2. Vector Spaces & Hilbert Spaces

A single qubit resides in a two-dimensional complex vector space $ℂ²$ . Unlike classical bits, a qubit state $|ψ⟩$ is a normalized vector:

|ψ⟩ = α|0⟩ + β|1⟩, where α, β \in ℂ and |α|² + |β|² = 1

The space equipped with an inner product $⟨φ|ψ⟩$ is a Hilbert space. Key properties include:

Conjugate Symmetry: ⟨φ|ψ⟩ = ⟨ψ|φ⟩*
Linearity: ⟨φ| (a|ψ⟩ + b|χ⟩) = a⟨φ|ψ⟩ + b⟨φ|χ⟩
Positivity: ⟨ψ|ψ⟩ ≥ 0, with equality iff |ψ⟩ = |0⟩

💡 Computational Note

Normalization ensures probabilities sum to unity. The Born rule dictates that measuring $|ψ⟩$ in the computational basis yields $|0⟩$ with probability $|α|²$ and $|1⟩$ with $|β|²$ .

3. Operators & Matrix Representations

Quantum operations are linear operators acting on Hilbert space. In matrix form, an operator $Â$ on $ℂⁿ$ is an $n\timesn$ complex matrix. Two classes dominate quantum computing:

Hermitian Operators (Â = Â†): Represent observables. Eigenvalues are real.
Unitary Operators (Û†Û = I): Represent time evolution and quantum gates. Preserve inner products and norm.

Matrix multiplication dictates algorithmic composition: applying gate $A$ then $B$ corresponds to the matrix product $BA$ acting on the state vector from the left.

4. Eigenvalues, Spectral Theorem & Measurement

The spectral theorem guarantees that any Hermitian operator can be diagonalized:

Â = Σᵢ λᵢ |λᵢ⟩⟨λᵢ|, where Â|λᵢ⟩ = λᵢ|λᵢ⟩ and ⟨λᵢ|λⱼ⟩ = δᵢⱼ

In quantum mechanics, measurement collapses the state onto an eigenspace. The probability of obtaining eigenvalue $λᵢ$ when measuring $|ψ⟩$ is $|⟨λᵢ|ψ⟩|²$ . This projection postulate is the linear-algebraic foundation of quantum randomness and algorithmic output extraction.

5. Tensor Products & Multi-Qubit Systems

Composite systems are modeled via the tensor product $\otimes$ . An $n$ -qubit state lives in $(ℂ²)\otimesⁿ ≅ ℂ²ⁿ$ . The Kronecker product constructs basis states:

|00⟩ = |0⟩\otimes|0⟩ = [1, 0, 0, 0]ᵀ |01⟩ = |0⟩\otimes|1⟩ = [0, 1, 0, 0]ᵀ ...

6. Unitary Evolution & Quantum Gates

Quantum circuits are sequences of unitary matrices. Fundamental single-qubit gates include:

Pauli-X: $[[0,1],[1,0]]$ (bit flip)
Pauli-Z: $[[1,0],[0,-1]]$ (phase flip)
Hadamard (H): $(1/\sqrt2)[[1,1],[1,-1]]$ (superposition)

Two-qubit gates like CNOT and SWAP introduce entanglement. Universality theorems prove that {H, T, CNOT} can approximate any unitary to arbitrary precision, forming the basis of quantum compilation.

7. Applications in Quantum Algorithms

Linear algebra structures directly enable quantum speedups:

Grover’s Algorithm: Geometric interpretation as rotation in a 2D subspace spanned by $|ω⟩$ and $|s⟩$ . Amplitude amplification uses reflections to rotate toward the solution.
Shor’s Algorithm: Relies on eigenphase estimation of the unitary operator $U|x⟩ = |aˣ mod N⟩$ . Period finding reduces to extracting eigenvalues via the Quantum Fourier Transform (QFT), which is a change-of-basis matrix.
VQE & QAOA: Optimize expectation values $⟨ψ(θ)|Ĥ|ψ(θ)⟩$ where $Ĥ$ is a Hamiltonian (Hermitian operator). Gradient-based updates operate in parameterized unitary spaces.

8. References & Further Reading

Nielsen, M. A., & Chuang, I. L. (2010). Quantum Computation and Quantum Information. Cambridge University Press.
Preskill, J. (2018). Quantum Computing in the NISQ era and beyond. arXiv:1801.00862
Gribble, P. (2021). Linear Algebra for Quantum Computing. Springer.
Aaronson, S. (2013). Quantum Computing since Democritus. Cambridge University Press.
Qiskit Textbook. (2024). Mathematics of Quantum Computing. IBM. qiskit.org