PaperlayerView exact revision on arXiv

Source-linked AI summary

The Trotter Step Size Required for Accurate Quantum Simulation of Quantum Chemistry

David Poulin, M. B. Hastings, Dave Wecker, Nathan Wiebe, Andrew C. Doherty, Matthias Troyer

arXiv:1406.4920v1quant-ph

TL;DR

The paper revisits the cost of Trotterized quantum chemistry simulation, addressing whether prior N^8–N^9 scaling reflects real molecules. Using an efficiently computable upper bound and alternative Hamiltonian decompositions, it finds more favorable scaling for studied real molecules and molecule-dependent opportunities for further savings.

  • Problem

    Prior analyses predicted N^8–N^9 gate-count scaling and relied on random ensembles or costly exact simulations, limiting efficient assessment for real molecules.

  • Method

    The paper efficiently evaluates an upper bound on Trotter-simulation error and examines alternative Hamiltonian decompositions, including coalescing, for real and artificial molecules.

  • Results

    Worst-case scaling for studied real molecules is N^5.5–N^6.5, while the required inverse Trotter step scales as O(N^1.5−2.5) for constant accuracy.

  • Takeaways & Limitations

    Random artificial molecules do not accurately reproduce real molecules’ statistical properties, and alternative decompositions or coalescing can sometimes substantially reduce simulation cost depending on the molecule.

  • Takeaways & Limitations

    Firm conclusions require evaluating the error bound on more molecules and understanding whether error terms add absolutely or with random signs.

Abstract

from arXiv · show

The simulation of molecules is a widely anticipated application of quantum computers. However, recent studies \cite{WBCH13a,HWBT14a} have cast a shadow on this hope by revealing that the complexity in gate count of such simulations increases with the number of spin orbitals $N$ as $N^8$, which becomes prohibitive even for molecules of modest size $N\sim 100$. This study was partly based on a scaling analysis of the Trotter step required for an ensemble of random artificial molecules. Here, we revisit this analysis and find instead that the scaling is closer to $N^6$ in worst case for real model molecules we have studied, indicating that the random ensemble fails to accurately capture the statistical properties of real-world molecules. Actual scaling may be significantly better than this due to averaging effects. We then present an alternative simulation scheme and show that it can sometimes outperform existing schemes, but that this possibility depends crucially on the details of the simulated molecule. We obtain further improvements using a version of the coalescing scheme of \cite{WBCH13a}; this scheme is based on using different Trotter steps for different terms. The method we use to bound the complexity of simulating a given molecule is efficient, in contrast to the approach of \cite{WBCH13a,HWBT14a} which relied on exponentially costly classical exact simulation.

I. INTRODUCTION

Quantum simulation of molecules is promising but faces severe time-resource costs because molecular Hamiltonians contain many terms and Trotter errors force small time steps. This paper reassesses those costs for real molecules and introduces alternative decompositions.

  • Motivation: Classical high-precision simulations are limited to molecules with at most 50-70 spin orbitals, while roughly 100 logical qubits could store otherwise classically intractable simulations.A spin orbital specifies both orbital and spin quantum numbers.
  • Problem: Molecular Coulomb interactions produce O(N^4) distinct fermionic terms, imposing at least ∼N^4 gates per infinitesimal Trotter step.Each term can require a constant number of gates on average under the stated gate set.
  • Problem: Previous analyses estimated quantum-simulation complexity at O(N^8), making simulations with N ∼100 spin orbitals prohibitively costly.The estimate combined quartic Hamiltonian-term counts with Trotter-step requirements scaling as O(N^4−5).
  • Approach: The paper evaluates an efficient upper bound for real molecules up to N ∼100 instead of relying on costly exact classical simulations.The bound is intended to assess simulations that are too large for classical simulation.
  • Alternative schemes: The study also considers coalescing, which uses different Trotter steps for different terms to obtain further time-complexity improvements.The paper counts gates as work, while circuit depth may be reduced through parallelization.
  • Alternative schemes: An alternative Hamiltonian decomposition uses m = O(N^2) terms, each implementable with O(N^2) gates, and can sometimes enable larger Trotter steps.Its performance depends strongly on the details of the molecule.

B. Simulating time evolution

The simulation decomposes total evolution into repeated infinitesimal steps and approximates each step with a second- or higher-order Trotter-Suzuki product. Free-fermion evolution can be exact, while interaction terms dominate gate complexity.

  • Trotter-Suzuki construction: The total evolution UH(1) is written as [UH(∆t)]^1/∆t, then each infinitesimal step is approximated by a higher-order Trotter-Suzuki decomposition.The product applies term evolutions in a symmetric sequence for the second-order formula.
  • Trotter-Suzuki construction: For the molecular Hamiltonian, the Trotter decomposition ranges over orbital pairs and quartets, giving m ∼N^4 terms.The quartet terms correspond to interaction contributions.
  • Free evolution: Any free Hamiltonian can be implemented exactly with O(N^2) gates by decomposing its orbital unitary into two-mode transformations.The two-mode operators require a constant number of gates on average after canceling Jordan-Wigner strings.
  • Interaction evolution: Interaction terms require constant gates per term on average, so their much larger count makes the single-step gate cost approximately ∼N^4.Interaction terms therefore set the overall circuit complexity.
  • Term ordering: Interleaving free terms with selected interaction terms can exploit cancellations in a Hartree-Fock basis and reduce Trotter error.This is presented as a practical alternative to simulating all free terms exactly in isolation.

C. Error per infinitesimal time-step

Trotter error is governed by nested commutators among Hamiltonian terms, and its bound determines the time step needed for a target precision. BCH analysis provides a tighter small-step estimate and supports the bound’s scaling.

  • Error bound: The Trotter-Suzuki error bound is built from nested commutators among Hamiltonian terms and scales with powers of ∆t.The bound organizes contributions according to terms that commute or fail to commute.
  • Error bound: Only noncommuting term combinations contribute, reducing the relevant count from the full O(N^12) triple set to combinations controlled by K = O(N^3).For a given term, K bounds the number of terms with which it does not commute.
  • Precision requirement: ∆t = O(N^-5) is sufficient for constant precision under the rigorous upper bound derived previously.The resulting step requirement follows from translating Trotter-evolution error into ground-state-energy error.
  • BCH comparison: The BCH expansion gives a small-∆t error estimate within a constant factor of the rigorous bound, indicating that the bound is close to optimal.The rigorous bound remains applicable beyond the small-step regime where BCH is tightest.
  • BCH comparison: The leading-order formulas predict simulation errors accurately as ∆t approaches zero, while the triangle-inequality bound is comparable within roughly a factor of 12 after neglecting O(∆t^3) terms.This comparison applies in the regime where error scales proportionally to ∆t^2.

D. Random ensemble

The paper replaces exponentially costly exact simulation with efficiently computable error bounds and tests scaling on real and random molecular models. The results show that random ensembles can misrepresent real-molecule statistics and that alternative decompositions may reduce cost.

  • Random-ensemble motivation: Earlier numerical scaling studies used artificial molecules because exact simulations were feasible only for modest molecular sizes and few interesting real molecules were available.The artificial ensemble was intended to reproduce real-molecule statistical properties.
  • Random-ensemble construction: The random ensemble assigns nonzero values to only a fraction F ≈0.8% of Hamiltonian coefficients, with random signs and prescribed magnitudes.The study also considers the ensemble with F = 1.
  • Random-ensemble results: ∆t ∼N^-4.32-N^-5.08 was observed for the random ensemble, depending on the electronic filling factor.These values came from prior exact numerical simulations of the ensemble.
  • Efficient error evaluation: The improved bound restricts sums to noncommuting terms and can be evaluated from molecular coefficients with complexity linear in m for the standard term representation.For m ∼N^4, direct evaluation can still become demanding for N ≫100; the alternative approach scales as N^9.
  • Efficient error evaluation: Monte Carlo sampling estimates the error bound with about 1% relative error or less using M = 10^5 samples in the cases where sampling is required.Sampling is used only for the alternative simulation approach.

IV. ALTERNATIVE DECOMPOSITION

The paper introduces an alternative decomposition that expresses the interacting Hamiltonian using sums of squares of free Hamiltonians, enabling efficient accuracy evaluation. Its implementation uses O(N^2) terms and O(N^2) gates per term, retaining O(N^4) cost per infinitesimal time step.

  • Alternative decomposition: The alternative scheme expresses the interacting Hamiltonian as sums of squares of free Hamiltonians plus additional free terms.This is achieved by completing the squares after diagonalizing the interaction tensor.
  • Alternative decomposition: The resulting Hamiltonian contains a free component H0 together with squared free-fermion operators and commutator-generated free terms.The commutators of the Hermitian and skew-Hermitian components produce free Hamiltonians.
  • Simulation: The second-order Trotter-Suzuki decomposition uses m = 2N^2 + 1 terms in the alternative scheme.This reduces the decomposition from the many individual interaction terms used by the standard approach.
  • Simulation: Each squared term is implemented by diagonalizing it through an orbital basis change, followed by free-fermion evolution requiring O(N) gates in the diagonal basis.The basis change dominates the cost because it requires O(N^2) gates.
  • Simulation: The alternative scheme therefore has O(N^4) complexity per infinitesimal time evolution, matching the scaling of the existing method.There are O(N^2) terms, each requiring O(N^2) gates because of the orbital basis change.

C. Error per infinitesimal time-step

The paper evaluates error bounds for two simulation schemes and converts single-step error into the total Trotter-step count needed for constant accuracy. The comparison covers real molecules and sparse and full artificial ensembles.

  • Numerical comparison: Figure 1 compares standard and alternative schemes using circles and squares, respectively, across real-world, sparse-ensemble, and full-ensemble molecules.The artificial ensembles use F = 0.008 for sparse Hamiltonians and F = 1 for full Hamiltonians.
  • Error evaluation: The alternative error bound uses norms of free-fermion operators and can be evaluated efficiently through their single-particle spectra.Computing one such norm has complexity O(N^3), while evaluating Eq. (21) directly has overall complexity O(N^9).
  • Step-count conversion: 1/∆t = Γ time-steps are required for constant accuracy when the single-step error has the stated cubic dependence on ∆t.Figure 1 reports the numerical bounds as total Trotter-step counts 1/∆t.

A. Artificial molecules

Artificial molecules show complexity near N^4.5-N^5, largely insensitive to coefficient sparsity, while real and artificial molecules display a clear scaling discrepancy. Alternative decompositions and averaging can improve error estimates, but performance and tightness remain molecule- and size-dependent.

  • Artificial-molecule scaling: N^4.5-N^5 complexity is observed for artificial molecules, with little scaling impact from the fraction F of non-zero Hpqrs coefficients.Both simulation schemes show this behavior, consistent with earlier full numerical simulations.
  • Artificial-molecule scaling: The random ensemble strongly affects the constant prefactor because denser Hamiltonians have higher norms and larger Trotter–Suzuki error bounds.The two simulation schemes are not affected equally by Hamiltonian density.
  • Artificial-molecule scaling: N^1.5-N^2.5 scaling is suggested for real molecules instead of the N^4-N^5 behavior found for artificial molecules, although scattered data prevent a firm scheme comparison.A case-by-case approach is considered most appropriate at this stage.
  • Alternative decomposition: Fewer, more complex Hamiltonian terms can significantly reduce Trotter–Suzuki error, but the gain may partly reflect a tighter upper bound rather than lower actual error.This observation is made for the artificial ensemble with F = 1.
  • Averaging and bounds: Triangle-inequality bounds are likely loose: an O(N^8) estimate improves on O(N^10), while observed error can decrease with larger N for studied molecules.The O(N^8) estimate ignores commutation constraints and may still overestimate the error.
  • Averaging and bounds: Randomizing Hpqrs term order produces decorrelated signs in many commutator contributions, supporting averaging effects in Trotter error.For H2O, 1000 randomized instances at Δt = 1/8 yielded an approximately Gaussian error distribution with a non-zero mean.
  • Averaging and bounds: Higher-order analysis is left open, with expected averaging effects not yet extended to all orders.The current treatment addresses terms order-by-order rather than providing an all-orders averaging estimate.
  • Applications: Accurate barrier heights in ozone are a useful quantum benchmark because classical calculations face large-basis and truncated-basis errors.The relevant transition separates a shallow van der Waals minimum from the ground state.

D. Cauchy–Schwarz bounds and decay of |hpqrs|2

Cauchy–Schwarz bounds provide an efficiently computable route to estimating Trotter error through RMS Hamiltonian norms and contributing term triplets. For studied molecules, the resulting scaling is substantially improved, while ground-state structure can reduce it further.

  • Cauchy–Schwarz bounds: Cauchy–Schwarz bounds estimate simulation error using RMS values of ∥Hα∥ over Hamiltonian triplets that contribute non-vanishingly.The indicator W(x) excludes zero commutators and can also exclude symmetry-vanishing ground-state contributions at the chosen order.
  • Cauchy–Schwarz bounds: The RMS-based bound is easy to compute directly or by Monte Carlo sampling and naturally handles constraints.This makes it suitable for large values of n.
  • Scaling consequences: O(N)-O(N^2.5) Trotter steps and O(N^5)-... gate complexity follow empirically from RMS norm scaling and O(N^4) Hamiltonian terms.The supplied passage gives the step scaling explicitly and begins the corresponding gate-count range.
  • Scaling consequences: If only O(N^6) terms affect the ground-state energy, gate complexity drops to O(N^5.5)-O(N^4), making ground-state properties relevant to tighter bounds.This condition holds when Hartree–Fock approximation error is small.

VI. COALESCING

The paper develops coalescing, a multiresolution Trotterization that applies different Hamiltonian terms at different frequencies. It prioritizes terms using an importance estimate tied to their second-order ground-state energy response.

  • VI. COALESCING: Coalescing assigns each Hamiltonian term its own application interval instead of enforcing one Trotter step for all terms.Terms are applied every n_α-th step with strength proportional to 1/n_α.
  • VI. COALESCING: The method uses powers-of-two intervals and applies coalescing only to H_pqrs terms, while other terms retain n_α = 1.The simpler first-order scheme is used, with terms executed on steps 1, n_α + 1, 2n_α + 1, … .
  • VI. COALESCING: The first-order coalescing scheme is exact for commuting terms and gives the correct first-order ground-state energy shift for any n_α.For H_α = εT, the shift is ε⟨ψ_0|T|ψ_0⟩ + O(ε^2), regardless of n_α.
  • A. Prioritizing Terms: The paper chooses n_α using an importance measure I_α that estimates a term’s second-order response, rather than relying only on coefficient magnitude.Terms with larger I_α receive smaller n_α, even when their coefficients are small because their energy denominators are small.
  • A. Prioritizing Terms: The importance distribution separates a few highly important terms from many low-importance terms, with relatively few terms of intermediate importance.This separation becomes more pronounced as molecules grow larger, reducing the need for detailed occupancy-based rules.

B. Numerical Results

Numerical tests apply importance-based coalescing to molecules of different sizes and compare work against fixed-interval baselines. The general rule reduces or preserves error and may yield larger runtime gains for larger molecules, though larger-size behavior is extrapolative.

  • B. Numerical Results: The scheme combines four-fermion terms sharing spin orbitals because the same circuits execute them, using the minimum associated energy denominator.The combined terms are represented through four strengths spanning eight basis directions, with the maximum magnitude used as representative.
  • B. Numerical Results: The coalescing rule groups four-fermion terms by importance, retaining high-importance terms every step while assigning lower-importance terms intervals of 16, 32, or 64 steps.Intermediate terms receive n_α = 1 or 16 according to whether they annihilate the Hartree-Fock ground state.
  • B. Numerical Results: Across the tested molecules, the cutoff rule did not increase error and often decreased it relative to simulations without coalescing.The cutoffs use the mean of log(I_α) plus 3 standard deviations for C_U and plus 1.2 standard deviations for C_L.
  • B. Numerical Results: The current approach is close to the middle asymptote between executing all terms every 16 steps and every 32 steps at Trotter number 64.Figure 6 compares work for various molecules against the fixed-interval asymptotes.
  • B. Numerical Results: The larger-molecule speedup projection is conditional because the authors could not simulate larger molecules directly.The extrapolation assumes that the coalescing scheme continues to work beyond the studied sizes.
  • B. Numerical Results: As N increases, the front porch disappears and the most important terms become more prominent relative to the mean.This suggests that larger molecules may permit coalescing nearly all terms except a few highly important ones, potentially increasing runtime gains.

VII. DISCUSSION AND CONCLUSION

For real-world molecules, Trotter-simulation scaling is more favorable than earlier random-ensemble analyses suggested, and alternative decompositions and coalescing can provide further molecule-dependent improvements.

  • VII. DISCUSSION AND CONCLUSION: The random ensemble appears statistically unlike real molecules: Σ_pqrs |h_pqrs| scales as N^2 for real molecules but as N^4 by design in the ensemble.This discrepancy helps explain why random-ensemble scaling analyses can misrepresent real-molecule behavior.
  • VII. DISCUSSION AND CONCLUSION: An alternative Hamiltonian decomposition can yield significant savings, although its performance depends strongly on the simulated molecule.The decomposition uses terms designed to reduce Trotter error and permit larger time steps.
  • VII. DISCUSSION AND CONCLUSION: The decomposition used is no sparser than the full Hamiltonian, so sparsity alone is insufficient as a guide for finding improved decompositions.The authors therefore identify a need for other criteria to guide decomposition choices.
  • VII. DISCUSSION AND CONCLUSION: The proposed coalescing technique shows large gains for small molecules and may enable further gains for larger molecules.Combining coalescing with the improved scaling suggests simulations with hundreds of spin orbitals may be more practical than previously indicated.
  • VII. DISCUSSION AND CONCLUSION: Random-walk and continuous-query approaches remain difficult to compare with Trotter methods because their quantum-oracle implementations may require substantial gates or QRAM space.Their performance could nevertheless be competitive because their upper bounds may not reflect actual behavior.

Appendix A: Estimate for Norm of Random Hamiltonian

The appendix examines the norm of a random Hamiltonian and uses a trace-method argument to establish a weaker bound when the expected O(N^2) bound is difficult to prove.

  • Appendix A: Estimate for Norm of Random Hamiltonian: The physically expected Hamiltonian norm bound is ||H_α|| ≤ O(N^2), motivated by the O(N^2) norm of electron-electron interactions.The appendix asks how much of this bound can be proved for a random ensemble.
  • Appendix A: Estimate for Norm of Random Hamiltonian: A trace-method argument can prove the weaker bound ||H_α|| ≤ O(N^5/2).The argument considers averaged traces of powers of the random Hamiltonian.
  • Appendix A: Estimate for Norm of Random Hamiltonian: For constant n, expanding the averaged trace leaves only index sequences in which each Hamiltonian term is repeated an even number of times.This reduces the potentially m^n terms to at most (mn)^(n/2) non-vanishing terms.
Loading 1406.4920v1…