Simple Algorithm
Quantum Computing · Excited State · 24 min

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 kk-local Hamiltonians and identify which of their terms commute.
  • Derive the Lie–Trotter product formula and its error bound t2∥[A,B]∥/(2r)t^2\norm{\comm{A}{B}}/(2r).
  • Compile e−iθZ⊗Ze^{-i\theta Z\otimes Z}, 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 nn-qubit state has 2n2^n complex amplitudes. Storing each in double precision takes 16 bytes, and evolving the state means applying e−iHte^{-iHt}, the solution of the Schrödinger equation (we set ℏ=1\hbar = 1), a 2n×2n2^n\times 2^n matrix. Memory and time both double with every added particle.

Predict before you look

At 16 bytes per amplitude, what is the smallest number of qubits whose state vector no longer fits in one terabyte (101210^{12} bytes)?

Show the answer

36 qubits

16×235≈0.55×101216\times 2^{35} \approx 0.55\times10^{12} bytes still fits; 16×236≈1.1×101216\times 2^{36}\approx 1.1\times 10^{12} 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 2n2^n 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 kk-local if

H=∑j=1mHj,H = \sum_{j=1}^{m} H_j,

where each Hermitian term HjH_j acts non-trivially on at most kk qubits and the number of terms mm is polynomial in nn. Two workhorses of condensed-matter physics are 2-local:

HTFIM=−J∑iZiZi+1−h∑iXi,HHeis=J∑i(XiXi+1+YiYi+1+ZiZi+1).H_{\mathrm{TFIM}} = -J\sum_{i} Z_iZ_{i+1} - h\sum_i X_i, \qquad H_{\mathrm{Heis}} = J\sum_i \big(X_iX_{i+1}+Y_iY_{i+1}+Z_iZ_{i+1}\big).

Molecules become sums of polynomially many Pauli strings after a fermion-to-qubit mapping (see Fermion-to-Qubit Mappings).

Each e−iHjte^{-iH_jt} acts on at most kk qubits, so it is a cheap gate. If all terms commuted, e−iHt=∏je−iHjte^{-iHt} = \prod_j e^{-iH_jt} and we would be done. They do not, and eA+B≠eAeBe^{A+B} \neq e^Ae^B in general. Non-commutativity is the only obstacle, and the next step shows how to tame it.

Check your understanding

Which pair of terms from the transverse-field Ising model does not commute?

  1. Z1Z2Z_1Z_2 and Z2Z3Z_2Z_3
  2. X1X_1 and X2X_2
  3. Z1Z2Z_1Z_2 and X2X_2
  4. X1X_1 and Z2Z3Z_2Z_3
Show the answer

C. Z1Z2Z_1Z_2 and X2X_2

X2X_2 anticommutes with Z2Z_2 and commutes with Z1Z_1, so Z1Z2X2=−X2Z1Z2Z_1Z_2X_2 = -X_2Z_1Z_2 and [Z1Z2,X2]=2Z1Z2X2≠0\comm{Z_1Z_2}{X_2} = 2Z_1Z_2X_2 \neq 0. Pauli strings commute exactly when they differ by an even number of anticommuting positions.

The Lie–Trotter product formula

Slice the evolution into rr short steps and alternate the two parts: e−i(A+B)t=lim⁡r→∞(e−iAt/re−iBt/r)re^{-i(A+B)t} = \lim_{r\to\infty}\big(e^{-iAt/r}e^{-iBt/r}\big)^r (Lie; Trotter 1959). This is trotterization. For finite rr the error is controlled by the commutator.

DerivationProof
  1. U(s):=e−i(A+B)s,V(s):=e−iAse−iBs:dds[U(δ−s) V(s)]=U(δ−s)  i [B,e−iAs] e−iBsU(s) := e^{-i(A+B)s},\quad V(s) := e^{-iAs}e^{-iBs}:\qquad \frac{d}{ds}\Big[U(\delta-s)\,V(s)\Big] = U(\delta-s)\; i\,\comm{B}{e^{-iAs}}\,e^{-iBs}

    Interpolate between exact evolution and one Trotter step of length δ=t/r\delta = t/r. Differentiating, the A+BA+B terms cancel and only a commutator survives.

  2. V(δ)−U(δ)=∫0δU(δ−s) i [B,e−iAs] e−iBs ds⟹∥V(δ)−U(δ)∥≤∫0δ∥[B,e−iAs]∥ dsV(\delta) - U(\delta) = \int_0^\delta U(\delta-s)\, i\,\comm{B}{e^{-iAs}}\, e^{-iBs}\,ds \quad\Longrightarrow\quad \norm{V(\delta)-U(\delta)} \le \int_0^\delta \norm{\comm{B}{e^{-iAs}}}\,ds

    Integrate from 00 to δ\delta; the unitaries on either side have norm 11.

  3. ∥[B,e−iAs]∥=∥eiAsBe−iAs−B∥=∥∫0seiAu i[A,B] e−iAu du∥≤s ∥[A,B]∥\norm{\comm{B}{e^{-iAs}}} = \norm{e^{iAs}Be^{-iAs} - B} = \Big\lVert \int_0^s e^{iAu}\, i\comm{A}{B}\,e^{-iAu}\,du\Big\rVert \le s\,\norm{\comm{A}{B}}

    Factor out e−iAse^{-iAs}, and use ddu(eiAuBe−iAu)=eiAu i[A,B] e−iAu\frac{d}{du}\big(e^{iAu}Be^{-iAu}\big) = e^{iAu}\,i\comm{A}{B}\,e^{-iAu}.

  4. ∥V(δ)−U(δ)∥≤∫0δs ∥[A,B]∥ ds=δ22∥[A,B]∥\norm{V(\delta) - U(\delta)} \le \int_0^\delta s\,\norm{\comm{A}{B}}\,ds = \frac{\delta^2}{2}\norm{\comm{A}{B}}

    One slice errs by O(δ2)\order{\delta^2}.

  5. ∥Vr−Ur∥=∥∑k=0r−1Vr−1−k(V−U) Uk∥≤r ∥V−U∥≤r⋅t22r2∥[A,B]∥=t22r∥[A,B]∥■\norm{V^r - U^r} = \Big\lVert\sum_{k=0}^{r-1} V^{r-1-k}(V-U)\,U^k\Big\rVert \le r\,\norm{V-U} \le r\cdot\frac{t^2}{2r^2}\norm{\comm{A}{B}} = \frac{t^2}{2r}\norm{\comm{A}{B}}\qquad\blacksquare

    Telescoping: for unitaries, the errors of the rr slices at most add.

So r=⌈t2∥[A,B]∥/(2ε)⌉r = \big\lceil t^2\norm{\comm{A}{B}}/(2\varepsilon)\big\rceil steps suffice: doubling the time quadruples the work, and halving the error doubles it. For H=∑j=1LHjH = \sum_{j=1}^{L} H_j applied in order, the same proof gives error at most t22r∑j<k∥[Hj,Hk]∥\frac{t^2}{2r}\sum_{j<k}\norm{\comm{H_j}{H_k}}, and commuting terms cost nothing.

Predict before you look

At the default time t=1.2t = 1.2, read the first-order infidelity at r=10r = 10. By what factor does it drop when you double to r=20r = 20?

Show the answer

4 ×

The state error scales like t2/rt^2/r and halves; the infidelity is quadratic in that error and drops about 4-fold (the widget shows 3.7×10−3→9.2×10−43.7\times10^{-3}\to 9.2\times10^{-4}, a factor of 4.14.1). For the second-order formula the same doubling gives about 1616.

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

S2(δ)=e−iAδ/2 e−iBδ e−iAδ/2,log⁡S2(δ)=−i(A+B)δ+iδ312[B,[B,A]]−iδ324[A,[A,B]]+O(δ5).S_2(\delta) = e^{-iA\delta/2}\,e^{-iB\delta}\,e^{-iA\delta/2},\qquad \log S_2(\delta) = -i(A+B)\delta + \tfrac{i\delta^3}{12}\comm{B}{\comm{B}{A}} - \tfrac{i\delta^3}{24}\comm{A}{\comm{A}{B}} + \order{\delta^5}.

The error per step is O(δ3)\order{\delta^3}, so the total error after rr steps is O(t3/r2)\order{t^3/r^2}; quantitatively it is at most t3r2(112∥[B,[B,A]]∥+124∥[A,[A,B]]∥)\frac{t^3}{r^2}\big(\tfrac{1}{12}\norm{\comm{B}{\comm{B}{A}}} + \tfrac{1}{24}\norm{\comm{A}{\comm{A}{B}}}\big) (Childs, Su, Tran, Wiebe & Zhu 2021).

It costs almost nothing extra: adjacent half-steps of consecutive slices merge, S2(δ)r=e−iAδ/2(e−iBδe−iAδ)r−1e−iBδe−iAδ/2S_2(\delta)^r = e^{-iA\delta/2}\big(e^{-iB\delta}e^{-iA\delta}\big)^{r-1}e^{-iB\delta}e^{-iA\delta/2}, which is just one exponential more than first order. That is why the widget reports 2r+12r+1 gates.

Think first Why does the symmetric arrangement cancel the δ2\delta^2 error term?

Because S2(δ) S2(−δ)=IS_2(\delta)\,S_2(-\delta) = \id: the formula is time-reversal symmetric. Then log⁡S2(−δ)=−log⁡S2(δ)\log S_2(-\delta) = -\log S_2(\delta), so the exponent contains only odd powers of δ\delta. The linear term is already correct, so the first error is δ3\delta^3. The Rydberg State lesson uses the same argument to build formulas of every even order.

FormulaError bound for HTFIMH_{\mathrm{TFIM}} (J=h=1J = h = 1)Steps rrCNOTs
First ordert22r∥[A,B]∥\frac{t^2}{2r}\norm{\comm{A}{B}} with ∥[A,B]∥≤4(n−1)=196\norm{\comm{A}{B}}\le 4(n-1) = 196≈1×107\approx 1\times10^{7}≈1×109\approx 1\times10^{9}
Second ordert3r2(16(n−1)12+16n24)≈98.7 t3r2\frac{t^3}{r^2}\big(\frac{16(n-1)}{12}+\frac{16n}{24}\big)\approx 98.7\,\frac{t^3}{r^2}≈1×104\approx 1\times10^{4}≈1×106\approx 1\times10^{6}
A worked estimate for n=50n = 50 spins, time t=10t = 10, accuracy ε=10−3\varepsilon = 10^{-3}, with AA the ZZZZ part and BB the field part. Each step needs 2(n−1)=982(n-1) = 98 CNOTs. The commutator norms come from the triangle inequality, bond by bond. Rigorous bounds are usually pessimistic, but the lesson stands: at high precision, higher order wins by orders of magnitude.

Compiling a Trotter step into gates

Every slice needs exponentials e−iθPe^{-i\theta P} of Pauli strings PP. The key case is Z⊗ZZ\otimes Z, the Ising interaction. The trick: let a CNOT compute the parity of the two qubits, rotate by that parity, and uncompute.

DerivationTwo CNOTs and one rotation
  1. CNOT∣a,b⟩=∣a, a⊕b⟩\mathrm{CNOT}\ket{a,b} = \ket{a,\ a\oplus b}

    The target now holds the parity of the two bits.

  2. RZ(2θ)∣c⟩=e−iθZ∣c⟩=e−iθ(−1)c∣c⟩R_Z(2\theta)\ket{c} = e^{-i\theta Z}\ket{c} = e^{-i\theta(-1)^c}\ket{c}

    With RZ(φ)=e−iφZ/2R_Z(\varphi) = e^{-i\varphi Z/2}, the angle must be doubled.

  3. CNOT (I⊗RZ(2θ)) CNOT∣a,b⟩=e−iθ(−1)a⊕b∣a,b⟩\mathrm{CNOT}\,\big(\id\otimes R_Z(2\theta)\big)\,\mathrm{CNOT}\ket{a,b} = e^{-i\theta(-1)^{a\oplus b}}\ket{a,b}

    The second CNOT restores ∣a,b⟩\ket{a,b}, leaving only a parity-dependent phase.

  4. (−1)a⊕b=⟨a,b∣Z⊗Z∣a,b⟩ ⟹ CNOT (I⊗RZ(2θ)) CNOT=e−iθ Z⊗Z(-1)^{a\oplus b} = \bra{a,b}Z\otimes Z\ket{a,b}\ \Longrightarrow\ \mathrm{CNOT}\,\big(\id\otimes R_Z(2\theta)\big)\,\mathrm{CNOT} = e^{-i\theta\,Z\otimes Z}

    Both sides are diagonal in the computational basis with the same entries.

Any Pauli string reduces to this case. Rotate each XX or YY to ZZ with X=HZHX = HZH and Y=(SH) Z (SH)†Y = (SH)\,Z\,(SH)^\dagger, compute the parity of all kk qubits into one with a ladder of k−1k-1 CNOTs, apply RZ(2θ)R_Z(2\theta), and undo everything:

e−iθX⊗X=(H⊗H) e−iθZ⊗Z (H⊗H),cost of e−iθP for weight k: 2(k−1) CNOTs.e^{-i\theta X\otimes X} = (H\otimes H)\,e^{-i\theta Z\otimes Z}\,(H\otimes H), \qquad \text{cost of } e^{-i\theta P}\text{ for weight } k:\ 2(k-1)\text{ CNOTs}.
Think first How many CNOTs does one first-order Trotter step of the nn-spin transverse-field Ising chain need?

2(n−1)2(n-1): two for each of the n−1n-1 bonds eiJδZiZi+1e^{iJ\delta Z_iZ_{i+1}}. The field terms eihδXi=RX(−2hδ)e^{ih\delta X_i} = R_X(-2h\delta) are single-qubit rotations. Bonds on even and odd links commute, so a step has depth O(1)\order{1} in the number of spins.

What simulation buys, and what comes next

With e−iHte^{-iHt} in hand you can:

  • Follow dynamics: quenches, transport, and correlation functions ⟨A(t)B⟩\expval{A(t)B} (via a Hadamard test with controlled evolutions).
  • Measure spectra: phase estimation applied to e−iHte^{-iHt} 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).

MethodCost for time tt, error ε\varepsilonNotes
First-order TrotterO(t2/ε)\order{t^2/\varepsilon} stepssimplest; no ancillas
Order-2k2k Trotter–SuzukiO(t1+1/2k/ε1/2k)\order{t^{1+1/2k}/\varepsilon^{1/2k}} stepsstage count grows like 5k5^{k}
LCU + truncated Taylor seriesO(αt log⁡(αt/ε)log⁡log⁡(αt/ε))\order{\alpha t\,\frac{\log(\alpha t/\varepsilon)}{\log\log(\alpha t/\varepsilon)}}block encodings, ancillas
Quantum signal processing / qubitizationO(αt+log⁡(1/ε)log⁡log⁡(1/ε))\order{\alpha t + \frac{\log(1/\varepsilon)}{\log\log(1/\varepsilon)}}optimal query complexity
α\alpha is the sum of the absolute values of the coefficients when HH is written as a combination of Pauli strings. Product-formula step counts also scale with nested commutators of the terms.

Key takeaways

  • Classical state-vector simulation needs 2n2^n amplitudes; a quantum simulator needs nn qubits (Feynman 1982, Lloyd 1996).
  • Physical Hamiltonians are sums of kk-local terms whose exponentials are cheap; non-commutativity is the only obstacle.
  • First-order Trotter: error at most t2∥[A,B]∥/(2r)t^2\norm{\comm{A}{B}}/(2r), so r=O(t2/ε)r = \order{t^2/\varepsilon}. The symmetric second-order formula has error O(t3/r2)\order{t^3/r^2} at almost the same cost.
  • e−iθZ⊗Z=CNOT (I⊗RZ(2θ)) CNOTe^{-i\theta Z\otimes Z} = \mathrm{CNOT}\,(\id\otimes R_Z(2\theta))\,\mathrm{CNOT}; any weight-kk Pauli exponential costs 2(k−1)2(k-1) CNOTs plus basis changes.
  • Post-Trotter methods (LCU, QSP/QSVT) reach O(αt+log⁡(1/ε))\order{\alpha t + \log(1/\varepsilon)} scaling, up to a log⁡log⁡\log\log factor.

Check yourself

In the interactive lesson these are scored with your confidence, and what you miss comes back for review.

Question 1

Using the first-order bound, you need error ε\varepsilon for evolution time tt. If you double tt and keep ε\varepsilon fixed, by what factor must the number of steps rr grow?

  1. 22
  2. 2\sqrt2
  3. 44
  4. 88
Show the answer

C. 44

r≥t2∥[A,B]∥/(2ε)r \ge t^2\norm{\comm{A}{B}}/(2\varepsilon) grows like t2t^2, so doubling tt quadruples rr.

Question 2

Which circuit implements e−iθ Z⊗Ze^{-i\theta\,Z\otimes Z} (with RZ(φ)=e−iφZ/2R_Z(\varphi) = e^{-i\varphi Z/2})?

  1. CNOT, then RZ(2θ)R_Z(2\theta) on the target, then CNOT
  2. CNOT, then RZ(θ)R_Z(\theta) on the target, then CNOT
  3. RZ(2θ)R_Z(2\theta) on each qubit, no CNOTs
  4. CNOT, then RZ(2θ)R_Z(2\theta) on the control, then CNOT
Show the answer

A. CNOT, then RZ(2θ)R_Z(2\theta) on the target, then CNOT

The CNOT stores the parity a⊕ba\oplus b on the target, RZ(2θ)=e−iθZR_Z(2\theta) = e^{-i\theta Z} applies e−iθ(−1)a⊕be^{-i\theta(-1)^{a\oplus b}}, and the second CNOT uncomputes the parity.

Question 3

For which Hamiltonian is the first-order product formula exact for every number of steps rr?

  1. X+ZX + Z
  2. X1X2+Z1X_1X_2 + Z_1
  3. Z1Z2+X2Z_1Z_2 + X_2
  4. Z1Z2+Z2Z3+X4Z_1Z_2 + Z_2Z_3 + X_4
Show the answer

D. Z1Z2+Z2Z3+X4Z_1Z_2 + Z_2Z_3 + X_4

All three terms commute (the ZZZZ terms share only ZZ's, and X4X_4 acts on a different qubit), so e−iHte^{-iHt} factorizes exactly and [Hj,Hk]=0\comm{H_j}{H_k} = 0 makes the error bound vanish.

Question 4

What is the fundamental obstacle to simulating 100 interacting qubits by storing and updating their state vector on a classical computer?

  1. Measuring the state would collapse it
  2. Floating-point round-off makes unitary evolution unstable
  3. The Hamiltonian of 100 qubits cannot be written down efficiently
  4. The state has 2100≈10302^{100}\approx10^{30} amplitudes, far beyond any memory
Show the answer

D. The state has 2100≈10302^{100}\approx10^{30} 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.

Question 5

What does an operator-norm guarantee ∥U−e−iHt∥≤ε\norm{U - e^{-iHt}} \le \varepsilon tell you?

  1. Only that the final state is close for the input ∣0⋯0⟩\ket{0\cdots0}
  2. For every input state and every measurement, outcome probabilities differ by at most 2ε2\varepsilon
  3. That the circuit uses at most 1/ε1/\varepsilon gates
  4. That the error grows linearly with tt at fixed step count
Show the answer

B. For every input state and every measurement, outcome probabilities differ by at most 2ε2\varepsilon

The operator norm is a worst case over input states, and ∣⟨ψ∣U†PU∣ψ⟩−⟨ψ∣V†PV∣ψ⟩∣≤2∥U−V∥\abs{\bra{\psi}U^\dagger PU\ket\psi - \bra{\psi}V^\dagger PV\ket\psi} \le 2\norm{U-V} for every projector PP.

Go deeper

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).