Quantum Simulation
Simulating nature with nature: Hamiltonian simulation.
In a 1981 lecture Richard Feynman asked a blunt question: if a classical computer needs exponentially many numbers just to write down the state of a quantum system, why not simulate quantum systems with quantum hardware? Hamiltonian simulation is the answer, and it is the application most likely to pay off first.
What you’ll learn
- Explain why classical state-vector simulation scales exponentially, and state the Hamiltonian simulation problem precisely.
- Describe -local Hamiltonians and identify which of their terms commute.
- Derive the Lie–Trotter product formula and its error bound .
- Compile , and any Pauli-string exponential, into CNOTs and single-qubit rotations.
- Estimate Trotter-step and gate counts for a spin chain, and compare first- and second-order formulas.
Feynman's exponential wall
An -qubit state has complex amplitudes. Storing each in double precision takes 16 bytes, and evolving the state means applying , the solution of the Schrödinger equation (we set ), a matrix. Memory and time both double with every added particle.
At 16 bytes per amplitude, what is the smallest number of qubits whose state vector no longer fits in one terabyte ( bytes)?
Show the answer
36 qubits
bytes still fits; does not. Fifty qubits would need about 18 petabytes, and 300 qubits more bytes than there are atoms in the observable universe.
Note what the quantum simulator does not give you: the amplitudes. You learn about the evolved state by measuring observables (magnetizations, correlation functions, energies), each estimated from repeated runs. That is exactly what experiments on real materials and molecules measure too.
Local Hamiltonians
Physical interactions involve few particles at a time. A Hamiltonian is -local if
where each Hermitian term acts non-trivially on at most qubits and the number of terms is polynomial in . Two workhorses of condensed-matter physics are 2-local:
Molecules become sums of polynomially many Pauli strings after a fermion-to-qubit mapping (see Fermion-to-Qubit Mappings).
Each acts on at most qubits, so it is a cheap gate. If all terms commuted, and we would be done. They do not, and in general. Non-commutativity is the only obstacle, and the next step shows how to tame it.
Which pair of terms from the transverse-field Ising model does not commute?
- and
- and
- and
- and
Show the answer
C. and
anticommutes with and commutes with , so and . Pauli strings commute exactly when they differ by an even number of anticommuting positions.
The Lie–Trotter product formula
Slice the evolution into short steps and alternate the two parts: (Lie; Trotter 1959). This is trotterization. For finite the error is controlled by the commutator.
Interpolate between exact evolution and one Trotter step of length . Differentiating, the terms cancel and only a commutator survives.
Integrate from to ; the unitaries on either side have norm .
Factor out , and use .
One slice errs by .
Telescoping: for unitaries, the errors of the slices at most add.
So steps suffice: doubling the time quadruples the work, and halving the error doubles it. For applied in order, the same proof gives error at most , and commuting terms cost nothing.
At the default time , read the first-order infidelity at . By what factor does it drop when you double to ?
Show the answer
4 ×
The state error scales like and halves; the infidelity is quadratic in that error and drops about 4-fold (the widget shows , a factor of ). For the second-order formula the same doubling gives about .
Symmetrize: the second-order formula
Splitting one of the exponentials in half and placing the halves symmetrically gives the Strang (second-order Trotter–Suzuki) formula
The error per step is , so the total error after steps is ; quantitatively it is at most (Childs, Su, Tran, Wiebe & Zhu 2021).
It costs almost nothing extra: adjacent half-steps of consecutive slices merge, , which is just one exponential more than first order. That is why the widget reports gates.
Think first Why does the symmetric arrangement cancel the error term?
Because : the formula is time-reversal symmetric. Then , so the exponent contains only odd powers of . The linear term is already correct, so the first error is . The Rydberg State lesson uses the same argument to build formulas of every even order.
| Formula | Error bound for () | Steps | CNOTs |
|---|---|---|---|
| First order | with | ||
| Second order |
Compiling a Trotter step into gates
Every slice needs exponentials of Pauli strings . The key case is , the Ising interaction. The trick: let a CNOT compute the parity of the two qubits, rotate by that parity, and uncompute.
The target now holds the parity of the two bits.
With , the angle must be doubled.
The second CNOT restores , leaving only a parity-dependent phase.
Both sides are diagonal in the computational basis with the same entries.
Any Pauli string reduces to this case. Rotate each or to with and , compute the parity of all qubits into one with a ladder of CNOTs, apply , and undo everything:
Think first How many CNOTs does one first-order Trotter step of the -spin transverse-field Ising chain need?
: two for each of the bonds . The field terms are single-qubit rotations. Bonds on even and odd links commute, so a step has depth in the number of spins.
What simulation buys, and what comes next
With in hand you can:
- Follow dynamics: quenches, transport, and correlation functions (via a Hadamard test with controlled evolutions).
- Measure spectra: phase estimation applied to reads out energy eigenvalues (see Phase Estimation: Error Analysis), the route to chemistry and materials applications.
- Prepare states: adiabatic evolution and filtering.
One caveat matters: phase estimation projects onto an eigenstate with probability equal to the squared overlap of your trial state with it. Finding ground states of local Hamiltonians is hard in the worst case even for quantum computers (QMA-hard; see Quantum Complexity: BQP & Beyond).
| Method | Cost for time , error | Notes |
|---|---|---|
| First-order Trotter | steps | simplest; no ancillas |
| Order- Trotter–Suzuki | steps | stage count grows like |
| LCU + truncated Taylor series | block encodings, ancillas | |
| Quantum signal processing / qubitization | optimal query complexity |
Key takeaways
- Classical state-vector simulation needs amplitudes; a quantum simulator needs qubits (Feynman 1982, Lloyd 1996).
- Physical Hamiltonians are sums of -local terms whose exponentials are cheap; non-commutativity is the only obstacle.
- First-order Trotter: error at most , so . The symmetric second-order formula has error at almost the same cost.
- ; any weight- Pauli exponential costs CNOTs plus basis changes.
- Post-Trotter methods (LCU, QSP/QSVT) reach scaling, up to a factor.
Check yourself
In the interactive lesson these are scored with your confidence, and what you miss comes back for review.
Using the first-order bound, you need error for evolution time . If you double and keep fixed, by what factor must the number of steps grow?
Show the answer
C.
grows like , so doubling quadruples .
Which circuit implements (with )?
- CNOT, then on the target, then CNOT
- CNOT, then on the target, then CNOT
- on each qubit, no CNOTs
- CNOT, then on the control, then CNOT
Show the answer
A. CNOT, then on the target, then CNOT
The CNOT stores the parity on the target, applies , and the second CNOT uncomputes the parity.
For which Hamiltonian is the first-order product formula exact for every number of steps ?
Show the answer
D.
All three terms commute (the terms share only 's, and acts on a different qubit), so factorizes exactly and makes the error bound vanish.
What is the fundamental obstacle to simulating 100 interacting qubits by storing and updating their state vector on a classical computer?
- Measuring the state would collapse it
- Floating-point round-off makes unitary evolution unstable
- The Hamiltonian of 100 qubits cannot be written down efficiently
- The state has amplitudes, far beyond any memory
Show the answer
D. The state has amplitudes, far beyond any memory
The number of amplitudes doubles with each qubit. A local Hamiltonian has only polynomially many terms and is easy to write down; the state is what explodes.
What does an operator-norm guarantee tell you?
- Only that the final state is close for the input
- For every input state and every measurement, outcome probabilities differ by at most
- That the circuit uses at most gates
- That the error grows linearly with at fixed step count
Show the answer
B. For every input state and every measurement, outcome probabilities differ by at most
The operator norm is a worst case over input states, and for every projector .
Go deeper
- Trotter–Suzuki Product Formulas · Splitting e^{-i(A+B)t} and bounding the error.
- LCU & Block Encodings · Implementing non-unitary matrices inside unitaries.
- Quantum Signal Processing & QSVT · A grand unification of quantum algorithms.
Further reading
- R. P. Feynman, "Simulating physics with computers", International Journal of Theoretical Physics 21, 467 (1982).
- S. Lloyd, "Universal quantum simulators", Science 273, 1073 (1996).
- M. A. Nielsen & I. L. Chuang, Quantum Computation and Quantum Information, §4.7 (Cambridge, 10th anniv. ed., 2010).
- A. M. Childs, Y. Su, M. C. Tran, N. Wiebe & S. Zhu, "Theory of Trotter error with commutator scaling", Physical Review X 11, 011020 (2021).