PaperlayerView exact revision on arXiv

Source-linked AI summary

A Theory of Trotter Error

Andrew M. Childs, Yuan Su, Minh C. Tran, Nathan Wiebe, Shuchen Zhu

arXiv:1912.08854v3quant-phcond-mat.str-elcs.DScs.NAmath.NAphysics.chem-ph

TL;DR

Product-formula error scaling remains poorly understood, with prior bounds often far above observed errors. This paper develops a general commutativity-based theory that yields tighter bounds and supports simulation algorithms that nearly match or outperform state-of-the-art results.

  • Problem

    Product-formula error scaling remains poorly understood, while existing bounds can exceed observed errors by several orders of magnitude, even for relatively small systems.

    Source: §1 · p. 3

  • Method

    The theory directly exploits commutativity of operator summands to derive tighter Trotter-error bounds for arbitrary finite-dimensional operators and real- and imaginary-time evolution.

    Source: §1 · p. 3, §6 · p. 42

  • Results

    Across numerous quantum-simulation examples, product formulas nearly match or outperform state-of-the-art results, and numerical calculations suggest nearly tight constant prefactors.

    Source: §1 · p. 3

  • Takeaways & Limitations

    The theory covers quantum dynamics, local observables, and quantum Monte Carlo, without restricting systems to geometric locality or Lie-algebraic structure.

    Source: §1 · p. 3, §6 · p. 42

    The analysis assumes a prior operator decomposition, applies the triangle inequality across Trotter steps, and treats an idealized setting without noise.

    Source: §6 · p. 44

Abstract

from arXiv · show

The Lie-Trotter formula, together with its higher-order generalizations, provides a direct approach to decomposing the exponential of a sum of operators. Despite significant effort, the error scaling of such product formulas remains poorly understood. We develop a theory of Trotter error that overcomes the limitations of prior approaches based on truncating the Baker-Campbell-Hausdorff expansion. Our analysis directly exploits the commutativity of operator summands, producing tighter error bounds for both real- and imaginary-time evolutions. Whereas previous work achieves similar goals for systems with geometric locality or Lie-algebraic structure, our approach holds in general. We give a host of improved algorithms for digital quantum simulation and quantum Monte Carlo methods, including simulations of second-quantized plane-wave electronic structure, $k$-local Hamiltonians, rapidly decaying power-law interactions, clustered Hamiltonians, the transverse field Ising model, and quantum ferromagnets, nearly matching or even outperforming the best previous results. We obtain further speedups using the fact that product formulas can preserve the locality of the simulated system. Specifically, we show that local observables can be simulated with complexity independent of the system size for power-law interacting systems, which implies a Lieb-Robinson bound as a byproduct. Our analysis reproduces known tight bounds for first- and second-order formulas. Our higher-order bound overestimates the complexity of simulating a one-dimensional Heisenberg model with an even-odd ordering of terms by only a factor of $5$, and is close to tight for power-law interactions and other orderings of terms. This suggests that our theory can accurately characterize Trotter error in terms of both asymptotic scaling and constant prefactor.

1 Introduction

The paper develops a general theory of Trotter error that exploits commutativity to tighten bounds, covering real-time digital quantum simulation and imaginary-time quantum Monte Carlo. It applies the theory to applications including local-observable simulations and numerical tests of bound tightness.

1 Introduction

  • The theory addresses poorly understood product-formula error scaling with commutativity-based bounds, and shows that product formulas can nearly match or outperform state-of-the-art simulation results.The authors argue that product formulas can outperform more advanced post-Trotter methods for many quantum systems.Source: §1 · p. 3

1.1 Simulating quantum systems by product formulas

  • Product formulas decompose Hamiltonian evolution into implementable steps, require no ancilla qubits, and can preserve locality for local-observable simulation; the results also extend to quantum Monte Carlo.The paper emphasizes that its analysis applies to general product formulas, not just specific formulas.Source: §1.1 · pp. 3–4

1.2 Previous analyses of Trotter error

  • Earlier analyses could miss dominant higher-order errors or ignore commutativity, while locality- and Lie-algebra-based improvements do not apply to all systems.Bounds based on lowest-order Taylor terms can fail at fixed time steps; some alternatives reduce to worst-case bounds without the relevant structure.Source: §1.2 · pp. 4–5

1.3 Trotter error with commutator scaling

  • The new bound uses finitely many pure nested commutators rather than BCH truncation, and its asymptotic scaling is independent of summand ordering.Ordering still matters for local-observable simulation and for tight constant prefactors.Source: §1.3 · pp. 5–6

1.4 Overview of results

  • Applications include electronic-structure, k-local, power-law, and clustered Hamiltonians, as well as improved quantum Monte Carlo simulations of transverse-field Ising models and quantum ferromagnets.The paper also reports that local-observable simulation for power-law systems can have complexity independent of system size.Source: §1.3 · p. 6, §1.4 · p. 7
  • For a one-dimensional Heisenberg model, the bound overestimates by about a factor of 5; the paper also reports a nearly tight bound for power-law interactions.For two-term Hamiltonians, the analysis recovers known tight analyses of the Lie-Trotter and second-order Suzuki formulas.Source: §1.4 · p. 7
  • The framework defines additive, multiplicative, and exponentiated errors, gives order conditions for cancelling low-order terms, and represents error with finitely many nested-commutator terms.The three error types are equivalent for digital quantum simulation, while multiplicative and exponentiated errors also support quantum Monte Carlo analysis.Source: §1.4 · p. 8
  • The overview says the theory handles real-time digital quantum simulation and imaginary-time quantum Monte Carlo evolutions; Section 2 gives background, and Section 6 concludes with results and open questions.Source: §1.4 · p. 9

2 Preliminaries

The preliminaries establish notation and time-evolution tools, then define general product formulas and a norm-based error bound whose neglect of commutativity motivates the paper’s theory. The analysis assumes finite-dimensional operator spaces and applies to real- and imaginary-time evolutions. [p28, p29, p40, p74, p81]

2.1 Notation and terminology

  • Notation assumes a finite-dimensional Hilbert space, organizes scalars into vectors and tensors, and specifies spectral and tensor norms and asymptotic conventions.The authors restrict the analysis to finite dimensions as most relevant to digital quantum and quantum Monte Carlo simulation, while noting possible generalization.Source: §2.1 · pp. 9–10

2.2 Time-ordered evolutions

  • For continuous operator-valued generators, time-ordered evolution is defined by an initial-value differential equation and covers real- and imaginary-time analysis.The preliminaries also give variation-of-parameters and interaction-picture tools for treating evolutions with an added term or split generator.Source: §2.2 · pp. 10–11

2.3 Product formulas

  • The framework covers general product formulas, with stages, real coefficients, and permutations specifying the ordering of summands within each stage.The number of stages is denoted Υ; coefficients are assumed bounded in absolute value by 1.Source: §2.3 · pp. 12–13
  • The 1-norm-scaled bound uses only summand norms, so it can be arbitrarily large even when all summands commute and the error is zero.The paper identifies this gap as motivation for bounds that use commutation information.Source: §2.3 · p. 14
  • The paper’s theory exploits commutativity of operator summands, reducing to known bounds for low-order formulas and special systems while revealing new speedups.Its central concepts are Trotter-error types, order conditions, and representations.Source: §2.3 · p. 15

3 Theory

The theory uses order conditions and operator commutativity to express Trotter error through nested commutators, developing distinct error forms and a framework for bounds in general systems and product formulas of arbitrary order. It distinguishes an asymptotic bound from a concrete error operator and reports evidence of tight low-order bounds and promise for higher-order formulas.

3.1 Example of the Lie-Trotter formula

  • The Lie-Trotter example shows how additive, multiplicative, and exponentiated errors arise, and that each error operator converges to zero as time approaches zero.The three forms are equivalent for digital quantum simulation and local observables, while multiplicative and exponentiated errors also suit quantum Monte Carlo.Source: §3.1 · p. 16

3.2 Error types

  • Three error forms—additive, multiplicative, and exponentiated—are equivalent for quantum-dynamics and local-observable complexity, while the latter two are more versatile for quantum Monte Carlo.For a general product formula, the additive form follows from variation of parameters, the exponentiated form from differentiation and time-ordered evolution, and the multiplicative form from the interaction picture.Source: §3.2 · p. 17

3.3 Order conditions

  • Order conditions describe how quickly an operator-valued function vanishes near zero; an indirect approach uses known product-formula accuracy to derive them for general formulas.The resulting conditions enable cancellation of low-order error terms in the commutator representation.Source: §3.3 · p. 18

3.4 Error representations

  • The theory represents error as a finite series of nested commutators, overcoming prior approaches that can be loose generally or apply only to special systems.Order conditions cancel terms below order p, leaving the higher-order remainder for the error bound.Source: §3.4 · pp. 19, 21, 22
  • Theorem 11 bounds additive and multiplicative errors of pth-order product formulas using commutator scaling, with a further bound when summands are anti-Hermitian.Corollary 12 uses this scaling to bound the Trotter number needed for a target accuracy.Source: §3.4 · p. 22
  • The bound is applied to quantum dynamics, local observables, and quantum Monte Carlo methods.The text notes these applications can often be handled by induction.Source: §3.4 · p. 22
  • Theorem 11 establishes correct asymptotic scaling, but its constant prefactor is unevaluated and may be loose because the proof uses inequality zooming.For practical implementation, the text recommends Theorem 10, which gives a concrete expression for the error operator.Source: §3.4 · p. 22
  • The bound reduces to previous Lie-Trotter and second-order Suzuki bounds, which are known to be tight up to the triangle inequality.The cited prior bounds are Lie-Trotter and second-order Suzuki [52] [90].Source: §3.4 · p. 23
  • Numerical evidence suggests the bound also has a small prefactor for higher-order formulas.The text points to a general methodology for obtaining bounds with small constant factors in Appendix J.Source: §3.4 · p. 23

4 Applications

Section 4 applies commutator-based product-formula error bounds to digital quantum simulation, local-observable simulation, and quantum Monte Carlo. The applications include system-size-independent gate complexity for simulating local observables in power-law interacting systems and improved quantum Monte Carlo methods for two spin systems.

4.1 Applications to digital quantum simulation

  • Higher-order product formulas simulate second-quantized plane-wave electronic structure with gate complexity n^2+o(1)t^1+o(1), confirming a numerical observation for the second-order formula [52].Source: §4.1 · p. 24
  • Product formulas improve on qubitization’s n-dependence for power-law interactions and offer an improved alternative for general k-local Hamiltonians [62].Source: §4.1 · pp. 24–26
  • An improved approach using product formulas has gate complexity (nt)^(1+d/(α−d))+o(1); the quasilocal result is asymptotically the same as a recent result for nearest-neighbor Hamiltonians [25].Source: §4.1 · p. 26
  • The analysis improves [73] for the first-order formula and extends to higher orders; the hybrid simulator runs in 2O(r·cc(g)), where r is the Trotter number and cc(g) the interaction-graph contraction complexity.Source: §4.1 · p. 27

4.2 Applications to simulating local observables

  • Using product formulas, the paper simulates short-time evolution of local observables with gate complexity independent of system size and proves a power-law-Hamiltonian Lieb–Robinson-type bound nearly matching Tran et al. [87].It directly approximates the evolved observable using a Hamiltonian supported within a light cone originating from the observable.Source: §4.2 · p. 28
  • For power-law Hamiltonians with α > 2d, local observables can be simulated with gate complexity independent of system size by restricting evolution to a light cone.The construction uses a reduced product formula and a Hamiltonian truncated to terms within the light cone.Source: §4.2 · pp. 30–31
  • A special ordering of product-formula terms preserves locality and reduces error when simulating local observables.The resulting decomposition also implies a Lieb-Robinson-type bound for power-law Hamiltonians, with a light-cone scaling approaching ρ^(α−d).Source: §4.2 · pp. 31–32

4.3 Applications to quantum Monte Carlo simulation

  • The tightened analysis exploits commutativity to improve second-order Suzuki decompositions for quantum Monte Carlo, including the transverse field Ising model and quantum ferromagnets.These applications target partition-function approximation rather than full dynamics.Source: §4.3 · pp. 32–33
  • The transverse field Ising application yields an improved fully polynomial randomized approximation scheme, with running time better than the previous complexity [17].The analysis bounds multiplicative error in the partition-function approximation.Source: §4.3 · pp. 34–35
  • For ferromagnetic quantum spin systems, the resulting randomized approximation scheme improves the runtime of the original Bravyi-Gosset algorithm [18].The method also estimates error for partial product-formula sequences.Source: §4.3 · p. 37

5 Error bounds with small prefactors

This section develops small-prefactor error bounds for first-, second-, and higher-order product formulas. Numerical benchmarks show tightened bounds for nearest-neighbor and power-law Heisenberg models, with tightness depending on the setting.

5.1 First- and second-order error bounds

  • The first- and second-order analyses bootstrap two-term error bounds to general Hamiltonians, yielding bounds that match the lowest-order BCH term up to the triangle inequality.The section reports reproducing previous tight bounds for both formula orders.Source: §5.1 · p. 37, §5 · p. 37

5.2 Higher-order error bounds

  • For higher-order formulas, heuristic analysis tightens large-prefactor bounds by exploiting commutation within even-odd and X-Y-Z groupings.The asymptotic bounds hold irrespective of term ordering, but their prefactors depend on the ordering; these choices maximize commutativity.Source: §5.2 · pp. 39–40
  • At n = 10, the higher-order bound overestimates the empirical Trotter number by factors of 5.1 for even-odd ordering and 7.2 for X-Y-Z ordering.The new bounds match empirical asymptotic scaling up to finite-size effects; competing bounds are less competitive for the stated reasons.Source: §5.2 · p. 41
  • At n = 10, the power-law bound is 10.2 times looser for α = 0 and 6.9 times looser for α = 4 than empirical Trotter numbers.The empirical values are 552 ± 45 and 129 ± 6, while the bounds are 5609 ± 3 and 885 ± 32, respectively; more triangle-inequality applications partly explain the weaker performance at small α.Source: §5.2 · p. 42
  • For power-law interactions, the bound captures the observed decrease in Trotter-number scaling exponent as α increases, approaching the nearest-neighbor exponent at large α.The analytic bound's exponent is loose and independent of α; empirical scaling exponents are based on simulations only up to n = 11.Source: §5.2 · p. 42

6 Discussion

The discussion presents a general Trotter-error framework and its applications, while identifying scope boundaries and possible extensions. It also reports that product formulas can be advantageous for local observables and several system classes.

6 Discussion

  • The theory applies to arbitrary finite-dimensional operators and real- or imaginary-time evolution, representing additive, multiplicative, and exponentiated errors through nested commutators.Its applications include quantum dynamics, local observables, and quantum Monte Carlo methods.Source: §6 · p. 42
  • For power-law interactions with α > 2d, product formulas can scale better than the Lieb-Robinson-based approach when p ≥ (α − d)/d.The threshold can be small for dipole-dipole interactions (α = 3) and van der Waals interactions (α = 6); product formulas also remain advantageous for small systems in some cases without matching asymptotic scaling.Source: §6 · p. 43
  • The analysis assumes a time-independent Hamiltonian and a prior operator decomposition; it also uses the triangle inequality across Trotter steps and an idealized noise-free setting.The discussion identifies time-dependent evolution and noise as directions for future study.Source: §6 · p. 44
  • The framework improves generalized product-formula analyses by expressing their q_kth-order error in terms of nested commutators.The paper presents this as improving understanding of these formulas and justifying their potential utility in quantum simulation.Source: §6 · p. 44
  • The paper notes that its spectral-norm error bound may be overly pessimistic for low-energy initial states.It suggests changing the error metric to avoid worst-case error propagation.Source: §6 · p. 44

A Error types

The appendix expresses product-formula error in additive, exponentiated, and multiplicative forms. These representations support different analyses, including quantum Monte Carlo simulation.

A Error types

  • The appendix establishes three representations of Trotter error: additive, exponentiated, and multiplicative.It states that these are equivalent for complexity analysis of quantum dynamics and local observables.Source: A Error types · pp. 45, 47
  • The exponentiated and multiplicative error forms are more versatile for quantum Monte Carlo simulation than the additive form.The multiplicative representation writes the product formula as the ideal evolution times a correction factor.Source: A Error types · pp. 45, 47
  • The additive error is represented as an integral of the product-formula residual propagated by the ideal evolution.This follows from the variation-of-parameters formula.Source: A Error types · pp. 46–47

B Order conditions

The appendix formalizes order conditions for Trotter error and gives rules for deriving them. These conditions let the analysis cancel lower-order terms before expressing error through nested commutators.

B Order conditions

  • Theorem 9 relates order conditions for additive, multiplicative, and exponentiated Trotter error, enabling lower-order terms to be canceled.The paper applies these conditions to establish commutator scaling.Source: B Order conditions · pp. 47, 48, 50
  • Order conditions characterize how quickly an operator-valued function approaches zero and can be checked by vanishing derivatives at zero.For a function with p continuous derivatives, the first p derivatives, from order zero through p − 1, must vanish.Source: B Order conditions · p. 48
  • The appendix proves rules for order conditions under addition, multiplication, differentiation, and exponentiation.These rules support indirect derivation when direct calculation is inefficient for high-order Suzuki formulas.Source: B Order conditions · p. 49

C Error representations

The section derives Trotter-error bounds by expanding the product-formula error in nested commutators. It treats additive and multiplicative errors and distinguishes general bounds from tighter bounds for anti-Hermitian summands.

C Error representations

  • The error expansion keeps terms of order O(τ^p), since lower-order terms vanish under the product formula's order condition.Theorem 9 supplies the order condition used in the expansion.Source: C Error representations · p. 51
  • A more careful expansion improves the exponent prefactor from 4 to 2 without invoking the triangle inequality.This improvement follows after canceling low-order terms.Source: C Error representations · p. 52
  • An order-independent asymptotic bound removes dependence on the ordering of operator summands, though its constant prefactor is not tight.The ordering-dependent analysis is retained for bounds that track the product formula's stages.Source: C Error representations · p. 54
  • Theorem 11 bounds additive and multiplicative Trotter errors with commutator scaling for a pth-order product formula.The theorem also gives a bound for anti-Hermitian summands.Source: C Error representations · p. 54

D Simulating second-quantized electronic structure

This section analyzes product-formula simulation of second-quantized plane-wave electronic structure. It tracks nested commutators using a layer measure for operators and gives resulting error and gate-complexity bounds.

D Simulating second-quantized electronic structure

  • The stated Hamiltonian setting assumes constant density, n/ω = O(1), and total nuclear charge magnitude Σι|ζι| = O(n).These are conditions attached to the plane-wave electronic-structure Hamiltonian described in the passage.Source: D Simulating second-quantized… · p. 55
  • The layer of a second-quantized operator W is the largest count of creation-annihilation pairs and number operators in a summand.The commutator analysis uses this measure to track operator structure.Source: D Simulating second-quantized… · pp. 55–56
  • Theorem D.5 gives a Trotter-error scaling for product-formula simulation of second-quantized plane-wave electronic-structure Hamiltonians.The Hamiltonian is written as H = T + U + V.Source: D Simulating second-quantized… · pp. 54, 58
  • The analysis derives gate complexity for constant-accuracy simulation by choosing sufficiently large formula order and implementing each Trotter step as specified.The cited step implementation is from [34] [64].Source: D Simulating second-quantized… · p. 58

E Simulating k-local Hamiltonians

This section applies product formulas to k-local Hamiltonians by controlling the support and norm of nested commutators. It gives corresponding Trotter-error and gate-complexity bounds.

E Simulating k-local Hamiltonians

  • A p-level nested commutator is supported on at most k + p(k − 1) qubits.The support bound follows by induction using overlap between local terms and the existing commutator support.Source: E Simulating k-local Hamiltonians · pp. 58–59
  • Theorem E.1 gives a Trotter-error scaling for product-formula simulation of k-local Hamiltonians on n qubits.The theorem applies to a pth-order product formula.Source: E Simulating k-local Hamiltonians · p. 59
  • For constant accuracy and sufficiently large formula order, the section derives gate complexity by implementing each Trotter step with the stated gate cost.The supplied passage does not specify the resulting complexity expression.Source: E Simulating k-local Hamiltonians · p. 59

F Simulating power-law interactions

This section bounds product-formula simulation costs for power-law and quasilocal interactions. It also treats faster-decaying interactions by truncating distant terms before simulation.

F Simulating power-law interactions

  • Theorem F.2 gives Trotter-error and gate-complexity bounds for power-law Hamiltonians on a d-dimensional lattice, with separate regimes at α = d.The supplied theorem passages do not expose the complete error or complexity expressions.Source: F Simulating power-law interactions · p. 60
  • For rapidly decaying power-law interactions with α > d, the analysis simulates a truncated Hamiltonian that removes terms beyond distance ℓ.The theorem gives Trotter-error and gate-complexity bounds for this truncated setting.Source: F Simulating power-law interactions · p. 61
  • For rapidly decaying interactions, the proof bounds the difference between the original and truncated Hamiltonians to account for truncation error.It combines this truncation control with the product-formula analysis.Source: F Simulating power-law interactions · p. 61
  • For quasilocal interactions with constant β > 0, the cutoff ℓ = Θ(log(nt/ϵ)) controls truncation before product-formula simulation.The section also gives a resulting gate-complexity bound.Source: F Simulating power-law interactions · p. 62

G Simulating clustered Hamiltonians

The section applies the paper’s Trotter error bound to the product-formula decomposition used in hybrid simulation of clustered Hamiltonians. It reports a more efficient decomposition, extending the earlier analysis to higher-order formulas.

G Simulating clustered Hamiltonians

  • The new bound gives a more efficient product-formula decomposition and thereby a faster hybrid simulation of clustered Hamiltonians.The Hamiltonian is split into terms acting within parties and between parties.Source: G Simulating clustered Hamiltonians · p. 62
  • The analysis improves the earlier hybrid-simulation result for p = 1 and extends it to pth-order product formulas.The earlier algorithm decomposes the Hamiltonian using the first-order Lie-Trotter formula.Source: G Simulating clustered Hamiltonians · pp. 62–63
  • Theorem G.1 gives a Trotter-error scaling for clustered Hamiltonians, which the section uses to obtain a hybrid-simulator runtime improvement.The supplied passages do not state the complete scaling or runtime expressions.Source: G Simulating clustered Hamiltonians · p. 63

H Simulating local observables

The section studies product-formula simulation of local observables under power-law interactions by truncating the Hamiltonian and exploiting locality. It gives an error analysis and constructs a local Hamiltonian whose evolution approximates the observable’s evolution.

H Simulating local observables

  • The approach truncates the Hamiltonian to a finite number of shells around the observable’s support before simulating its evolution.It then uses product-formula locality to cancel exponentials outside the reduced region when evolving the observable.Source: H Simulating local observables · pp. 64–66
  • The truncation error is bounded by scaling with the boundary area of the truncated region and the interaction decay, under the lemma’s stated assumptions.The truncation lemma assumes α > d and Γ = O(1).Source: H Simulating local observables · pp. 64–65
  • For power-law Hamiltonians with α > 2d, the construction yields a local Hamiltonian supported within radius x0 + rΓℓ for approximating a constant-radius observable.Here Γ is constant, and the construction uses pth-order product formulas.Source: H Simulating local observables · p. 66
  • The section derives a gate-count expression for simulating the local observable with constant accuracy, but the supplied passage does not include its complete scaling.The construction chooses the truncation parameter to minimize error and requires α > 2d.Source: H Simulating local observables · pp. 66–67

I Quantum Monte Carlo simulation

The section applies the commutativity-aware Trotter bound to quantum Monte Carlo simulations. It reports improved performance for the transverse-field Ising model and ferromagnetic quantum spin systems, while restricting the analysis to second-order Suzuki formulas.

I Quantum Monte Carlo simulation

  • For the transverse-field Ising simulation, the algorithm decomposes evolution with a second-order Suzuki formula whose summands within each group commute.Consequently, the analysis focuses on the Trotter error between the two groups.Source: I Quantum Monte Carlo simulation · p. 67
  • The commutativity-exploiting bound improves the asymptotic performance of quantum Monte Carlo simulation for the transverse-field Ising model.The comparison is with the previous bound in [17, Lemma 3].Source: I Quantum Monte Carlo simulation · p. 68
  • The same Trotter-error approach gives improved quantum Monte Carlo simulation for ferromagnetic quantum spin systems.The section considers approximating their partition function.Source: I Quantum Monte Carlo simulation · pp. 68, 70

J Higher-order error bounds with small prefactors

The section develops fourth-order Trotter-error bounds with small prefactors and illustrates bounds for two- and three-summand Hamiltonians. Numerical results suggest close tightness in selected systems, but tightness is not rigorously established for higher-order bounds.

J Higher-order error bounds with small prefactors

Related papers

Loading 1912.08854v3…