Simple Algorithm
Quantum Computing · Rydberg State · 30 min

Trotter–Suzuki Product Formulas

Splitting e^{-i(A+B)t} and bounding the error.

Product formulas are the oldest way to simulate quantum dynamics and still the most practical: no ancillas, no oracles, just exponentials of the terms you already have. This lesson builds Suzuki's formulas of every even order from one symmetry argument and proves the commutator-scaling bounds that let them compete with asymptotically optimal algorithms.

What you’ll learn

  • Define the order of a product formula and prove that time-symmetric formulas have even order.
  • Derive Suzuki's recursion and its coefficient uk=1/(4−41/(2k−1))u_k = 1/(4-4^{1/(2k-1)}), and explain why negative time steps are unavoidable beyond order two.
  • State the commutator-scaling theorem of Childs, Su, Tran, Wiebe & Zhu and sketch its proof.
  • Derive the gate count O((nt)1+1/pε−1/p)\order{(nt)^{1+1/p}\varepsilon^{-1/p}} for lattice Hamiltonians and compare product formulas with post-Trotter methods.

Product formulas and their order

The Lie–Trotter formula S1(t)=e−itH1⋯e−itHΓS_1(t) = e^{-itH_1}\cdots e^{-itH_\Gamma} has order 1. The symmetric Strang formula

S2(t)=e−itH1/2⋯e−itHΓ−1/2 e−itHΓ e−itHΓ−1/2⋯e−itH1/2S_2(t) = e^{-itH_1/2}\cdots e^{-itH_{\Gamma-1}/2}\,e^{-itH_\Gamma}\,e^{-itH_{\Gamma-1}/2}\cdots e^{-itH_1/2}

has order 2. You could verify that with the Baker–Campbell–Hausdorff formula, but there is a slicker argument that works at every order.

DerivationProof
  1. S(t)=exp⁡(−itH+∑j≥2tjEj)S(t) = \exp\Big(-itH + \sum_{j\ge2} t^jE_j\Big)

    For small tt, BCH writes any product of exponentials as one exponential of a power series. First-order consistency (∑υa(υ,γ)=1\sum_\upsilon a_{(\upsilon,\gamma)} = 1 for each γ\gamma) fixes the linear term.

  2. S(−t)=exp⁡(itH+∑j≥2(−1)jtjEj),S(t)−1=exp⁡(itH−∑j≥2tjEj)S(-t) = \exp\Big(itH + \sum_{j\ge2}(-1)^jt^jE_j\Big), \qquad S(t)^{-1} = \exp\Big(itH - \sum_{j\ge2}t^jE_j\Big)

    Substitute −t-t; invert by negating the exponent.

  3. S(−t)=S(t)−1 ⟹ (−1)jEj=−Ej ⟹ Ej=0  for all even jS(-t) = S(t)^{-1}\ \Longrightarrow\ (-1)^jE_j = -E_j\ \Longrightarrow\ E_j = 0\ \text{ for all even } j

    Near the identity the logarithm is unique, so the exponents agree term by term. The first surviving error is at an odd power t2k+1t^{2k+1}: the order 2k2k is even. ■\blacksquare

Check your understanding

Which of these is a second-order approximation of e−i(A+B)te^{-i(A+B)t} for non-commuting AA, BB?

  1. e−iAt/2e−iBt/2e−iAt/2e−iBt/2e^{-iAt/2}e^{-iBt/2}e^{-iAt/2}e^{-iBt/2}
  2. e−iBt/2 e−iAt e−iBt/2e^{-iBt/2}\,e^{-iAt}\,e^{-iBt/2}
  3. e−iAt/3 e−iBt e−2iAt/3e^{-iAt/3}\,e^{-iBt}\,e^{-2iAt/3}
  4. e−iAt e−iBte^{-iAt}\,e^{-iBt}
Show the answer

B. e−iBt/2 e−iAt e−iBt/2e^{-iBt/2}\,e^{-iAt}\,e^{-iBt/2}

It is first-order consistent and palindromic, so S(t)S(−t)=IS(t)S(-t) = \id and the symmetry theorem forces order 2. Which operator gets split does not matter.

Suzuki's fractal recursion

Suzuki (1990, 1991) raised the order two at a time with a palindrome of five copies of the previous formula:

S2k(t)=S2k−2(ukt)2  S2k−2((1−4uk)t)  S2k−2(ukt)2.S_{2k}(t) = S_{2k-2}(u_kt)^2\;S_{2k-2}\big((1-4u_k)t\big)\;S_{2k-2}(u_kt)^2.
DerivationWhere u_k comes from
  1. S2k−2(s)=exp⁡(−isH+s2k−1E+O(s2k+1))S_{2k-2}(s) = \exp\Big(-isH + s^{2k-1}E + \order{s^{2k+1}}\Big)

    By the symmetry theorem the leading error of the symmetric formula S2k−2S_{2k-2} sits at the odd power 2k−12k-1.

  2. ∏i=15S2k−2(cit)=exp⁡(−itH∑ici+t2k−1E∑ici2k−1+O(t2k))\prod_{i=1}^{5}S_{2k-2}(c_it) = \exp\Big(-itH\sum_i c_i + t^{2k-1}E\sum_i c_i^{2k-1} + \order{t^{2k}}\Big)

    The leading exponents are all multiples of the same HH, so they commute; the error terms add at leading order, since their commutators with tHtH only enter at order t2kt^{2k}.

  3. ∑ici=4u+(1−4u)=1,∑ici2k−1=4u2k−1+(1−4u)2k−1=0\sum_i c_i = 4u + (1-4u) = 1,\qquad \sum_i c_i^{2k-1} = 4u^{2k-1} + (1-4u)^{2k-1} = 0

    Consistency is automatic; the second equation kills the t2k−1t^{2k-1} error.

  4. 41/(2k−1) u=4u−1⟹uk=14−41/(2k−1)4^{1/(2k-1)}\,u = 4u-1 \quad\Longrightarrow\quad u_k = \frac{1}{4-4^{1/(2k-1)}}

    Take real (2k−1)(2k-1)-th roots of 4u2k−1=(4u−1)2k−14u^{2k-1} = (4u-1)^{2k-1}.

  5. The arrangement (u,u,1−4u,u,u)(u, u, 1-4u, u, u) is palindromic, so S2kS_{2k} is again symmetric, and the t2kt^{2k} term vanishes too. Hence S2kS_{2k} has order 2k2k. ■\blacksquare

Predict before you look

For the fourth-order formula (k=2k = 2), compute the time coefficient 1−4u21-4u_2 of the middle stage.

Show the answer

-0.66

u2=1/(4−41/3)≈1/2.4126≈0.4145u_2 = 1/(4-4^{1/3}) \approx 1/2.4126 \approx 0.4145, so 1−4u2≈−0.6581-4u_2\approx -0.658. The middle stage runs time backwards. (Numerically, halving tt shrinks the error of S4(t)S_4(t) by a factor ≈32=25\approx 32 = 2^5, confirming order 4.)

The price of the recursion is exponential in kk: S2kS_{2k} contains 5k−15^{k-1} copies of S2S_2, about 2⋅5k−1Γ2\cdot5^{k-1}\Gamma exponentials per step. That factor is why practitioners rarely go beyond order 4 or 6.

Commutator scaling

Early analyses (Lloyd 1996; Berry, Ahokas, Cleve & Sanders 2007) bounded the per-step error by powers of ∑γ∥Hγ∥ t\sum_\gamma\norm{H_\gamma}\,t. That is wasteful: in a lattice most pairs of terms commute, and commuting terms contribute no error at all. The right currency is nested commutators.

DerivationProof sketch
  1. ddtS(t)=−iH S(t)+R(t)⟹S(t)−e−itH=∫0te−i(t−τ)H R(τ) dτ\frac{d}{dt}S(t) = -iH\,S(t) + \mathcal{R}(t)\quad\Longrightarrow\quad S(t)-e^{-itH} = \int_0^t e^{-i(t-\tau)H}\,\mathcal{R}(\tau)\,d\tau

    Variation of parameters (Duhamel). It suffices to bound ∥R(τ)∥\norm{\mathcal{R}(\tau)}.

  2. R(τ)=(∑m(−iam) U<m(τ) Hγm U<m(τ)†+iH)S(τ)\mathcal{R}(\tau) = \Big(\sum_{m}(-ia_m)\,\mathcal{U}_{<m}(\tau)\,H_{\gamma_m}\,\mathcal{U}_{<m}(\tau)^\dagger + iH\Big)S(\tau)

    Flatten SS into exponentials e−iτamHγme^{-i\tau a_mH_{\gamma_m}}. Differentiating puts HγmH_{\gamma_m} where its exponential sits; moving it to the front conjugates it by the product U<m\mathcal{U}_{<m} of the exponentials to its left.

  3. e−isA X eisA=∑j=0q−1(−is)jj!ad⁡Aj(X)+∫0s(s−u)q−1(q−1)! e−iuA (−i)qad⁡Aq(X) eiuA due^{-isA}\,X\,e^{isA} = \sum_{j=0}^{q-1}\frac{(-is)^j}{j!}\operatorname{ad}_A^j(X) + \int_0^s\frac{(s-u)^{q-1}}{(q-1)!}\,e^{-iuA}\,(-i)^q\operatorname{ad}_A^q(X)\,e^{iuA}\,du

    Expand each conjugation in nested commutators ad⁡A(X)=[A,X]\operatorname{ad}_A(X) = \comm{A}{X}, with an exact integral remainder.

  4. order p ⟹ all terms of degree<p in τ cancel ⟹ ∥R(τ)∥=O(α~comm τp)\text{order } p\ \Longrightarrow\ \text{all terms of degree} < p \text{ in } \tau \text{ cancel}\ \Longrightarrow\ \norm{\mathcal{R}(\tau)} = \order{\tilde\alpha_{\mathrm{comm}}\,\tau^{p}}

    The order conditions are exactly the statement that the polynomial part cancels up to degree p−1p-1. Only remainders survive, and each is bounded by norms of nested commutators of p+1p+1 terms.

  5. ∥S(t)−e−itH∥≤∫0t∥R(τ)∥ dτ=O(α~comm tp+1)\norm{S(t)-e^{-itH}} \le \int_0^t\norm{\mathcal{R}(\tau)}\,d\tau = \order{\tilde\alpha_{\mathrm{comm}}\,t^{p+1}}

    Integrate. For p=1p = 1 this reproduces the Excited State bound with explicit constant: ∥S1(t)−e−itH∥≤t22∑γ1∥[∑γ2>γ1Hγ2,Hγ1]∥\norm{S_1(t)-e^{-itH}} \le \frac{t^2}{2}\sum_{\gamma_1}\big\lVert\big[\sum_{\gamma_2>\gamma_1}H_{\gamma_2},H_{\gamma_1}\big]\big\rVert.

Lattices. For a nearest-neighbor chain of nn sites with ∥hj,j+1∥≤1\norm{h_{j,j+1}}\le1, a nested commutator is nonzero only if its terms form a connected cluster, so α~comm=O(n)\tilde\alpha_{\mathrm{comm}} = \order{n} for fixed pp, versus O(np+1)\order{n^{p+1}} for the norm-based bound. Hence

r=O(n1/p t1+1/pε1/p),gates=O(n r)=O((nt)1+1/pε1/p),r = \order{\frac{n^{1/p}\,t^{1+1/p}}{\varepsilon^{1/p}}},\qquad \text{gates} = \order{n\,r} = \order{\frac{(nt)^{1+1/p}}{\varepsilon^{1/p}}},

almost linear in the space-time volume ntnt. Haah, Hastings, Kothari & Low (2018) reached O(nt polylog⁡(nt/ε))\order{nt\,\operatorname{polylog}(nt/\varepsilon)} with a different decomposition and showed this is optimal up to polylogarithmic factors.

Check your understanding

A nearest-neighbor chain of nn qubits is simulated for time t=nt = n at fixed precision with a fourth-order formula. Using commutator scaling, how does the total gate count scale?

  1. O(n2)\order{n^{2}}
  2. O(n2.5)\order{n^{2.5}}
  3. O(n3.5)\order{n^{3.5}}
  4. O(n1.25)\order{n^{1.25}}
Show the answer

B. O(n2.5)\order{n^{2.5}}

Gates =O((nt)1+1/p)= \order{(nt)^{1+1/p}} with p=4p = 4 and nt=n2nt = n^2: (n2)5/4=n2.5(n^2)^{5/4} = n^{2.5}.

Practice and frontier

Asymptotically, product formulas lose to post-Trotter methods: their cost grows like ε−1/p\varepsilon^{-1/p} rather than log⁡(1/ε)\log(1/\varepsilon). In practice they often win. They need no ancillas, their constants are small, commutator scaling exploits locality, and the actual error is often far below the bounds. Childs, Maslov, Nam, Ross & Su (2018) compiled concrete Heisenberg-chain simulations and found product formulas, especially with empirically estimated error, needed fewer gates than the asymptotically superior algorithms at the sizes of interest.

MethodSteps or queries for time tt, error ε\varepsilonKey feature
Lie–Trotter (p=1p = 1)O(α~comm t2/ε)\order{\tilde\alpha_{\mathrm{comm}}\,t^2/\varepsilon}simplest
Suzuki, order p=2kp = 2kO(α~comm1/p t1+1/p/ε1/p)\order{\tilde\alpha_{\mathrm{comm}}^{1/p}\,t^{1+1/p}/\varepsilon^{1/p}}2⋅5k−1Γ2\cdot5^{k-1}\Gamma exponentials per step
qDRIFT (Campbell 2019)O(λ2t2/ε)\order{\lambda^2t^2/\varepsilon} exponentials, λ=∑γ∥Hγ∥\lambda = \sum_\gamma\norm{H_\gamma}independent of the number of terms Γ\Gamma
Truncated Taylor series (LCU)O(αt log⁡(αt/ε)log⁡log⁡(αt/ε))\order{\alpha t\,\frac{\log(\alpha t/\varepsilon)}{\log\log(\alpha t/\varepsilon)}}block encodings, ancillas
QSP / qubitizationO(αt+log⁡(1/ε)log⁡log⁡(1/ε))\order{\alpha t + \frac{\log(1/\varepsilon)}{\log\log(1/\varepsilon)}}optimal query complexity
qDRIFT samples term γ\gamma with probability ∥Hγ∥/λ\norm{H_\gamma}/\lambda and applies e−iλtHγ/(N∥Hγ∥)e^{-i\lambda tH_\gamma/(N\norm{H_\gamma})}; it shines for Hamiltonians with very many small terms, as in chemistry.

Key takeaways

  • A pp-th order product formula errs by O(α~commtp+1)\order{\tilde\alpha_{\mathrm{comm}}t^{p+1}} per step, so r=O(α~comm1/pt1+1/pε−1/p)r = \order{\tilde\alpha_{\mathrm{comm}}^{1/p}t^{1+1/p}\varepsilon^{-1/p}} steps suffice (Childs, Su, Tran, Wiebe & Zhu 2021).
  • Time-symmetric formulas have even order; Suzuki's palindrome with uk=1/(4−41/(2k−1))u_k = 1/(4-4^{1/(2k-1)}) raises the order by two at five times the cost.
  • Beyond order two, negative time steps are unavoidable (Sheng–Suzuki).
  • Commutator scaling makes lattice simulation nearly linear in the space-time volume, and in practice product formulas often beat asymptotically optimal methods.

Check yourself

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

Question 1

A product formula satisfies S(t)S(−t)=IS(t)S(-t) = \id and S(t)=e−itH+O(t2)S(t) = e^{-itH}+\order{t^2}. What can you conclude?

  1. It is first order
  2. It is exact
  3. It is at least second order
  4. It is fourth order
Show the answer

C. It is at least second order

Time-reversal symmetry kills every even power in log⁡S(t)\log S(t), including t2t^2, so the first error is at least t3t^3. It need not be fourth order: Strang's formula is symmetric and has a nonzero t3t^3 term.

Question 2

Why does Suzuki's fourth-order formula contain a backward time step?

  1. Every product formula of order ≥3\ge3 must contain a negative coefficient; here 1−4u2≈−0.6581-4u_2\approx-0.658
  2. To undo decoherence accumulated in the forward steps
  3. Because HH must be made traceless first
  4. It does not; all five stages run forward in time
Show the answer

A. Every product formula of order ≥3\ge3 must contain a negative coefficient; here 1−4u2≈−0.6581-4u_2\approx-0.658

Cancelling the t3t^3 error requires 4u3+(1−4u)3=04u^3 + (1-4u)^3 = 0, which forces 1−4u<01-4u<0. More generally, the Sheng–Suzuki theorem says no all-positive splitting exceeds order two.

Question 3

Why are product formulas beyond order 4–6 rarely used?

  1. Higher orders are not more accurate for small steps
  2. Negative time steps make them non-unitary
  3. Commutator scaling fails beyond order 6
  4. The number of stages grows like 5k−15^{k-1}, which outweighs the better scaling t1+1/2k/ε1/2kt^{1+1/2k}/\varepsilon^{1/2k} at realistic precisions
Show the answer

D. The number of stages grows like 5k−15^{k-1}, which outweighs the better scaling t1+1/2k/ε1/2kt^{1+1/2k}/\varepsilon^{1/2k} at realistic precisions

Each order increase multiplies the exponentials per step by 5. The exponent of 1/ε1/\varepsilon only improves from 1/(2k)1/(2k) to 1/(2k+2)1/(2k+2), which pays off only at extreme precision or very long times.

Question 4

For a nearest-neighbor chain of nn sites with bounded terms, how does α~comm\tilde\alpha_{\mathrm{comm}} scale with nn at fixed order pp?

  1. O(np+1)\order{n^{p+1}}
  2. O(n)\order{n}
  3. O(1)\order{1}
  4. O(2n)\order{2^n}
Show the answer

B. O(n)\order{n}

A nested commutator of p+1p+1 terms vanishes unless the terms form a connected cluster. There are O(n)\order{n} starting positions and O(1)\order{1} clusters of bounded size at each, so the sum is O(n)\order{n}.

Further reading

  • H. F. Trotter, "On the product of semi-groups of operators", Proceedings of the American Mathematical Society 10, 545 (1959).
  • M. Suzuki, "General theory of fractal path integrals with applications to many-body theories and statistical physics", Journal of Mathematical Physics 32, 400 (1991).
  • D. W. Berry, G. Ahokas, R. Cleve & B. C. Sanders, "Efficient quantum algorithms for simulating sparse Hamiltonians", Communications in Mathematical Physics 270, 359 (2007).
  • 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).
  • A. M. Childs, D. Maslov, Y. Nam, N. J. Ross & Y. Su, "Toward the first quantum simulation with quantum speedup", PNAS 115, 9456 (2018).