118
Part Three · B · Algorithms

Hamiltonian simulation: Trotter, qDRIFT, LCU, qubitization

In 1981, at a conference at MIT, Richard Feynman pointed out that simulating quantum physics on a classical computer seems to need resources that grow exponentially with the number of particles, while nature does it effortlessly. “Nature isn’t classical, dammit,” he said, “and if you want to make a simulation of nature, you’d better make it quantum mechanical.” Simulating how a quantum system evolves in time, e−iHte^{-iHt}, was the first reason to build a quantum computer, and it remains the most convincing one.

On the plate: the error of splitting a time evolution into short steps, against the number of steps.

Trotter splitting

Physical Hamiltonians are sums of simple pieces, H=∑jHjH = \sum_jH_j, each easy to exponentiate on its own. If they commuted, e−iHt=∏je−iHjte^{-iHt} = \prod_je^{-iH_jt} exactly. They don’t, but over a short time the error is small, so split tt into rr steps:

e−i(A+B)t≈(e−iAt/re−iBt/r)re^{-i(A+B)t} \approx \left(e^{-iAt/r}e^{-iBt/r}\right)^r

Seth Lloyd showed in 1996 that this makes any local Hamiltonian efficiently simulable. The first-order error is about t22r∥[A,B]∥\frac{t^2}{2r}\|[A, B]\|: halve the step, halve the error. The symmetric second-order formula e−iAt/2re−iBt/re−iAt/2re^{-iAt/2r}e^{-iBt/r}e^{-iAt/2r} has error falling as 1/r21/r^2. Set the steps to 4 for H=X+ZH = X + Z on one qubit and t=1t = 1. Established

Tighter bounds

Old error bounds used the size of each term and badly overestimated costs. Andrew Childs and colleagues showed in 2021 that the true error depends on nested commutators of the terms, which for local Hamiltonians are much smaller: for a chain of nn spins, the number of Trotter steps needed grows far more slowly than the old bounds suggested. This alone cut resource estimates for some chemistry and materials problems by orders of magnitude.

Randomized and exact-in-principle methods

qDRIFT (Earl Campbell, 2019): instead of cycling through every term, pick terms at random with probability proportional to their size. The cost depends on the total weight of the terms, not their number, which suits Hamiltonians with many small terms, as in chemistry. Linear combinations of unitaries (Andrew Childs and Nathan Wiebe, 2012; Dominic Berry and colleagues, 2015): write HH as a weighted sum of unitaries, prepare the weights in an ancilla register, and apply a truncated Taylor series of e−iHte^{-iHt}, with error falling exponentially in the work done. Qubitization (Guang Hao Low and Isaac Chuang, 2019) builds a walk operator whose eigenphases encode HH’s eigenvalues and reaches the optimal cost, linear in tt plus logarithmic in 1/ε1/\varepsilon. Choose a method: to see how its cost scales with accuracy.

Which to use

There is no single winner. Trotter formulas need no ancillas and are simple, which suits early fault-tolerant machines. Qubitization has the best asymptotic scaling but needs ancillas and an expensive “prepare” step. qDRIFT shines for many-term Hamiltonians at modest accuracy. Alexander Dalzell and colleagues’ survey of end-to-end costs (2023, published as a book in 2025) finds that for chemistry and materials the best choice depends on the specific Hamiltonian and target accuracy, and that simulation remains the most credible route to useful quantum advantage. Established as scalings; the practical ranking is problem-dependent.

What you now have

Feynman’s motivation, Trotter–Suzuki splitting and its first- and second-order errors, commutator scaling, qDRIFT, linear combinations of unitaries, qubitization, and how to choose among them.

· · ·

Three questions to carry with you.

How does first-order Trotter error scale with the number of steps?tap
As 1/r, proportional to the commutator [A, B].
When is qDRIFT attractive?tap
For Hamiltonians with very many small terms, at moderate accuracy.
What does qubitization achieve?tap
Optimal scaling: linear in t plus logarithmic in 1/ε, at the cost of ancillas.

And one to work out. A first-order Trotter simulation has error 0.02 with 10 steps. About what error with 40 steps?

error ≈

Sources: R. P. Feynman, Int. J. Theor. Phys. 21, 467 (1982). S. Lloyd, Science 273, 1073 (1996). A. M. Childs et al., Phys. Rev. X 11, 011020 (2021). E. Campbell, Phys. Rev. Lett. 123, 070503 (2019). A. M. Childs and N. Wiebe, Quantum Inf. Comput. 12, 901 (2012). D. W. Berry et al., Phys. Rev. Lett. 114, 090502 (2015). G. H. Low and I. L. Chuang, Quantum 3, 163 (2019). A. M. Dalzell et al., Quantum Algorithms: A Survey of Applications and End-to-End Complexities (CUP 2025). Checked by code (H = X + Z, t = 1): first-order error 0.799, 0.362, 0.176, 0.088, 0.044 for r = 1…16; second-order 0.314, 0.071, 0.017, 0.0043, 0.0011.

Next · Chapter 119
Quantum signal processing and QSVT

One algorithm contains Grover, Hamiltonian simulation and linear solvers as special cases.

Turn the page