The Hamiltonian Simulation Problem
Given a Hamiltonian H, a time t, and an error budget, produce a quantum circuit that approximates the evolution operator e^(-iHt).
Statement of the problem
Time evolution in quantum mechanics is governed by the Schrodinger equation. For a time-independent Hamiltonian H, a state evolves as |psi(t)> = U(t)|psi(0)> with U(t) = e^(-iHt) (setting hbar = 1). The Hamiltonian simulation problem asks for a quantum circuit that implements a unitary V such that the operator distance ||V - e^(-iHt)|| is below a chosen error epsilon.
Why it is hard classically
e^(-iHt) is a 2^n by 2^n matrix for an n-qubit system. Exponentiating it directly, or even storing it, is exponentially expensive. Yet on a quantum computer the same operator can often be built from a number of gates that scales polynomially in n, t, and log(1/epsilon), which is the central promise of the field.
Structure you can exploit
Real Hamiltonians are rarely arbitrary. Most physically relevant H are local or sparse: they decompose into a sum H = sum_j H_j of terms that each act on a few qubits or have few nonzero entries per row. This structure is what algorithms convert into efficient circuits.
- k-local Hamiltonians: each term touches at most k qubits.
- Sparse Hamiltonians: at most d nonzero entries per row, with an oracle giving their positions and values.
- Linear combinations: H = sum_j a_j P_j over Pauli strings, common in chemistry.
Families of algorithms
Product formulas (Trotter-Suzuki) split e^(-iHt) into a sequence of easy exponentials. Linear-combination-of-unitaries and Taylor-series methods build the propagator from weighted sums of unitaries. Qubitization and quantum signal processing achieve near-optimal scaling by manipulating the spectrum of a block-encoded H.
The quality of an algorithm is judged by gate count, ancilla count, and dependence on t and epsilon. The best modern methods scale as O(t + log(1/epsilon)), matching known lower bounds. This underpins downstream tasks such as phase estimation for eigenvalues and dynamics for spectroscopy.