- Physical Review Journals
All JournalsPhysics Magazine

Physical Review X

Reuse & Permissions

It is not necessary to obtain permission to reuse this article or its components as it is available under the terms of the Creative Commons Attribution 4.0 International license. This license permits unrestricted use, distribution, and reproduction in any medium, provided attribution to the author(s) and the published article's title, journal citation, and DOI are maintained. Please note that some figures may have been included with permission from other third parties. It is your responsibility to obtain the proper permission from the rights holder directly for these figures.

Export citation

Export citation

Choose format for download:

Download Citation
  • Open Access

Theory of Trotter Error with Commutator Scaling

Andrew M. Childs1,2,3, Yuan Su1,2,3, Minh C. Tran3,4, Nathan Wiebe5,6,7, and Shuchen Zhu8

  • 1Department of Computer Science, University of Maryland, College Park, Maryland 20742, USA
  • 2Institute for Advanced Computer Studies, University of Maryland, College Park, Maryland 20742, USA
  • 3Joint Center for Quantum Information and Computer Science, University of Maryland, College Park, Maryland 20742, USA
  • 4Joint Quantum Institute, University of Maryland, College Park, Maryland 20742, USA
  • 5Department of Physics, University of Washington, Seattle, Washington 98195, USA
  • 6Pacific Northwest National Laboratory, Richland, Washington 99354, USA
  • 7Google Inc., Venice, California 90291, USA
  • 8Department of Computer Science, Georgetown University, Washington, DC 20057, USA

PDF

Phys. Rev. X 11, 011020 – Published 1 February, 2021

DOI: https://doi.org/10.1103/PhysRevX.11.011020

Abstract

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 by-product. 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 it is close to tight for power-law interactions and other orderings of terms. This result suggests that our theory can accurately characterize Trotter error in terms of both asymptotic scaling and constant prefactor.

View figure in article

Physics Subject Headings (PhySH)

Popular Summary

Quantum computers hold the promise of simulating quantum systems much more efficiently than their classical counterparts, enabling potential development of new pharmaceuticals, catalysts, and materials. Among all known quantum simulation algorithms, product formulas provide the simplest approach, making them popular for experimental realizations. Furthermore, evidence suggests that product formulas perform well in practice. Here, we develop a theory for bounding the error of product formulas.

Until now, the error scaling of product formulas has been poorly understood, leaving a dramatic gap between their provable performance and actual behavior. This gap has made it hard to identify the fastest simulation algorithm and to find optimized implementations for near-term applications of quantum computers.

Our theory allows us to provide a host of improved algorithms for quantum simulation, including various systems of practical relevance. This analysis puts the product-formula algorithm on a rigorous foundation, in many cases justifying its superiority over the best previous algorithms. We also connect our result to classical simulation of quantum systems and to the speed of information propagation in physical systems.

This work represents significant progress toward a precise characterization of the product-formula error. Whereas recent studies have favored more advanced simulation algorithms that are easier to analyze but harder to implement, our result demonstrates that product formulas can outperform these sophisticated algorithms. Our findings thus reemphasize the role of product formulas in quantum simulation, which we hope will bridge the gap between theoretical investigation and near-term experimental realization of quantum computing.

Article Text

References (86)

  1. R. P. Feynman, Simulating Physics with Computers, Int. J. Theor. Phys. 21, 467 (1982).
  2. S. Lloyd, Universal Quantum Simulators, Science 273, 1073 (1996).
  3. D. Aharonov and A. Ta-Shma, Adiabatic Quantum State Generation and Statistical Zero Knowledge, in Proceedings of the 35th ACM Symposium on Theory of Computing (Association for Computing Machinery, New York, 2003), pp. 20–29, 10.1145/780542.780546.
  4. D. W. Berry, G. Ahokas, R. Cleve, and B. C. Sanders, Efficient Quantum Algorithms for Simulating Sparse Hamiltonians, Commun. Math. Phys. 270, 359 (2007).
  5. D. W. Berry, A. M. Childs, R. Cleve, R. Kothari, and R. D. Somma, Exponential Improvement in Precision for Simulating Sparse Hamiltonians, in Proceedings of the 46th Annual ACM Symposium on Theory of Computing (Association for Computing Machinery, New York, 2014), pp. 283–292, 10.1145/2591796.2591854.
  6. D. W. Berry, A. M. Childs, and R. Kothari, Hamiltonian Simulation with Nearly Optimal Dependence on All Parameters, in Proceedings of the 56th IEEE Symposium on Foundations of Computer Science (IEEE Computer Society, Washington, DC, 2015), pp. 792–809, 10.1109/FOCS.2015.54.
  7. G. H. Low and I. L. Chuang, Optimal Hamiltonian Simulation by Quantum Signal Processing, Phys. Rev. Lett. 118, 010501 (2017).
  8. G. H. Low, Hamiltonian Simulation with Nearly Optimal Dependence on Spectral Norm, in Proceedings of the 51th ACM Symposium on Theory of Computing (Association for Computing Machinery, New York, 2019), pp. 491–502, 10.1145/3313276.3316386.
  9. D. Wecker, B. Bauer, B. K. Clark, M. B. Hastings, and M. Troyer, Gate Count Estimates for Performing Quantum Chemistry on Small Quantum Computers, Phys. Rev. A 90, 022305 (2014).
  10. D. Poulin, M. B. Hastings, D. Wecker, N. Wiebe, A. C. Doherty, and M. Troyer, The Trotter Step Size Required for Accurate Quantum Simulation of Quantum Chemistry, Quantum Inf. Comput. 15, 361 (2015).
  11. R. Babbush, N. Wiebe, J. McClean, J. McClain, H. Neven, and G. K.-L. Chan, Low-Depth Quantum Simulation of Materials, Phys. Rev. X 8, 011044 (2018).
  12. S. McArdle, S. Endo, A. Aspuru-Guzik, S. C. Benjamin, and X. Yuan, Quantum Computational Chemistry, Rev. Mod. Phys. 92, 015003 (2020).
  13. S. P. Jordan, K. S. M. Lee, and J. Preskill, Quantum Algorithms for Quantum Field Theories, Science 336, 1130 (2012).
  14. B. P. Lanyon, J. D. Whitfield, G. G. Gillett, M. E. Goggin, M. P. Almeida, I. Kassal, J. D. Biamonte, M. Mohseni, B. J. Powell, M. Barbieri et al., Towards Quantum Chemistry on a Quantum Computer, Nat. Chem. 2, 106 (2010).
  15. Y. Cao, J. Romero, J. P. Olson, M. Degroote, P. D. Johnson, M. Kieferová, I. D. Kivlichan, T. Menke, B. Peropadre, N. P. D. Sawaya, S. Sim, L. Veis, and A. Aspuru-Guzik, Quantum Chemistry in the Age of Quantum Computing, Chem. Rev. 119, 10856 (2019).
  16. A. W. Harrow, A. Hassidim, and S. Lloyd, Quantum Algorithm for Linear Systems of Equations, Phys. Rev. Lett. 103, 150502 (2009).
  17. F. G. S. L. Brandao and K. M. Svore, Quantum Speed-ups for Solving Semidefinite Programs, in Proceedings of the 58th IEEE Symposium on Foundations of Computer Science (IEEE Computer Society, Washington, DC, 2017), pp. 415–426, 10.1109/FOCS.2017.45.
  18. E. Farhi, J. Goldstone, and S. Gutmann, A Quantum Algorithm for the Hamiltonian NAND Tree, Theory Comput. 4, 169 (2008).
  19. A. M. Childs, R. Cleve, E. Deotto, E. Farhi, S. Gutmann, and D. A. Spielman, Exponential Algorithmic Speedup by a Quantum Walk, in Proceedings of the 35th ACM Symposium on Theory of Computing (Association for Computing Machinery, New York, 2003), pp. 59–68, 10.1145/780542.780552.
  20. D. W. Berry, High-Order Quantum Algorithm for Solving Linear Differential Equations, J. Phys. A 47, 105301 (2014).
  21. M. Suzuki, General Theory of Fractal Path Integrals with Applications to Many-Body Theories and Statistical Physics, J. Math. Phys. (N.Y.) 32, 400 (1991).
  22. S. Blanes and F. Casas, A Concise Introduction to Geometric Numerical Integration (Chapman and Hall/CRC, London, 2016)10.1201/b21563.
  23. D. W. Berry, A. M. Childs, R. Cleve, R. Kothari, and R. D. Somma, Simulating Hamiltonian Dynamics with a Truncated Taylor Series, Phys. Rev. Lett. 114, 090502 (2015).
  24. G. H. Low and I. L. Chuang, Hamiltonian Simulation by Qubitization, Quantum 3, 163 (2019).
  25. G. H. Low and N. Wiebe, Hamiltonian Simulation in the Interaction Picture, arXiv:1805.00675.
  26. S. Hadfield and A. Papageorgiou, Divide and Conquer Approach to Quantum Hamiltonian Simulation, New J. Phys. 20, 043003 (2018).
  27. A. M. Childs, A. Ostrander, and Y. Su, Faster Quantum Simulation by Randomization, Quantum 3, 182 (2019).
  28. G. H. Low, V. Kliuchnikov, and N. Wiebe, Well-Conditioned Multiproduct Hamiltonian Simulation, arXiv:1907.11679.
  29. Y. Ouyang, D. R. White, and E. Campbell, Compilation by Stochastic Hamiltonian Sparsification, Quantum 4, 235 (2020).
  30. E. Campbell, Random Compiler for Fast Hamiltonian Simulation, Phys. Rev. Lett. 123, 070503 (2019).
  31. A. M. Childs, D. Maslov, Y. Nam, N. J. Ross, and Y. Su, Toward the First Quantum Simulation with Quantum Speedup,” Proc. Natl. Acad. Sci. U.S.A. 115, 9456 (2018).
  32. M. Reiher, N. Wiebe, K. M. Svore, D. Wecker, and M. Troyer, Elucidating Reaction Mechanisms on Quantum Computers, Proc. Natl. Acad. Sci. U.S.A. 114, 7555 (2017).
  33. R. Babbush, J. McClean, D. Wecker, A. Aspuru-Guzik, and N. Wiebe, Chemical Basis of Trotter-Suzuki Errors in Quantum Chemistry Simulation, Phys. Rev. A 91, 022311 (2015).
  34. D. Wecker, M. B. Hastings, N. Wiebe, B. K. Clark, C. Nayak, and M. Troyer, Solving Strongly Correlated Electron Models on a Quantum Computer, Phys. Rev. A 92, 062318 (2015).
  35. A. M. Childs and Y. Su, Nearly Optimal Lattice Simulation by Product Formulas, Phys. Rev. Lett. 123, 050503 (2019).
  36. M. Troyer, N. Pearson, and D. Poulin, Trotter Error Scaling with System Size in Quantum Simulations, in APS Meeting Abstracts (2019).
  37. M. Kliesch, C. Gogolin, and J. Eisert, Lieb-Robinson Bounds and the Simulation of Time-Evolution of Local Observables in Lattice Systems, in Many-Electron Approaches in Physics, Chemistry and Mathematics (Springer, New York, 2014), pp. 301–318, 10.1007/978-3-319-06379-9_17.
  38. S. Bravyi, Monte Carlo Simulation of Stoquastic Hamiltonians, Quantum Inf. Comput. 15, 1122 (2015).
  39. S. Bravyi and D. Gosset, Polynomial-Time Classical Simulation of Quantum Ferromagnets, Phys. Rev. Lett. 119, 100503 (2017).
  40. M. Suzuki, Decomposition Formulas of Exponential Operators and Lie Exponentials with Some Applications to Quantum Mechanics and Statistical Physics, J. Math. Phys. (N.Y.) 26, 601 (1985).
  41. J. Huyghebaert and H. De Raedt, Product Formula Methods for Time-Dependent Schrödinger Problems, J. Phys. A 23, 5777 (1990).
  42. S. Descombes and M. Thalhammer, An Exact Local Error Representation of Exponential Operator Splitting Methods for Evolutionary Problems and Applications to Linear Schrödinger Equations in the Semi-classical Regime, BIT 50, 729 (2010).
  43. I. D. Kivlichan, C. Gidney, D. W. Berry, N. Wiebe, J. McClean, W. Sun, Z. Jiang, N. Rubin, A. Fowler, A. Aspuru-Guzik, H. Neven, and R. Babbush, Improved Fault-Tolerant Quantum Simulation of Condensed-Phase Correlated Electrons via Trotterization, Quantum 4, 296 (2020).
  44. R. D. Somma, A Trotter-Suzuki Approximation for Lie Groups with Applications to Hamiltonian Simulation, J. Math. Phys. (N.Y.) 57, 062202 (2016).
  45. M. Thalhammer, High-Order Exponential Operator Splitting Methods for Time-Dependent Schrödinger Equations, SIAM J. Numer. Anal. 46, 2022 (2008).
  46. T. Jahnke and C. Lubich, Error Bounds for Exponential Operator Splittings, BIT 40, 735 (2000).
  47. M. Thalhammer, Convergence Analysis of High-Order Time-Splitting Pseudospectral Methods for Nonlinear Schrödinger Equations, SIAM J. Numer. Anal. 50, 3231 (2012).
  48. R. I. McLachlan and G. R. W. Quispel, Splitting Methods, Acta Numer. 11, 341 (2002).
  49. R. I. McLachlan, On the Numerical Integration of Ordinary Differential Equations by Symmetric Composition Methods, SIAM J. Sci. Comput. 16, 151 (1995).
  50. E. Hairer, G. Wanner, and C. Lubich, Geometric Numerical Integration: Structure-Preserving Algorithms for Ordinary Differential Equations (Springer Science & Business Media, New York, 2006), Vol. 31, 10.1007/978-3-662-05018-7.

  51. The 1-norm ‖H‖1 and the induced 1-norm |‖H|‖1 are formally defined in Sec. 2a. For now, it suffices to know that |‖H|‖1≤‖H‖1 and that the gap can be significant for many k-local Hamiltonians.

  52. M. C. Tran, A. Y. Guo, Y. Su, J. R. Garrison, Z. Eldredge, M. Foss-Feig, A. M. Childs, and A. V. Gorshkov, Locality and Digital Quantum Simulation of Power-Law Interactions, Phys. Rev. X 9, 031006 (2019).
  53. T. Peng, A. Harrow, M. Ozols, and X. Wu, Simulating Large Quantum Circuits on a Small Quantum Computer, Phys. Rev. Lett. 125, 150504 (2020).
  54. R. A. Horn and C. R. Johnson, Matrix Analysis (Cambridge University Press, Cambridge, England, 2012), 10.1017/CBO9781139020411.
  55. J. D. Dollard and C. N. Friedman, Product Integration with Application to Differential Equations (Cambridge University Press, Cambridge, England, 1984), http://dx.doi.org/10.1017/CBO9781107340701.

  56. Alternatively, we may define a time-ordered exponential by its Dyson series or by a convergent sequence of products of ordinary matrix exponentials, and verify that this alternative definition satisfies a certain differential equation. We prefer the differential-equation definition since it is more versatile for the analysis in this paper.

  57. N. Wiebe, D. Berry, P. Høyer, and B. C. Sanders, Higher Order Decompositions of Ordered Operator Exponentials, J. Phys. A 43, 065203 (2010).
  58. W. Auzinger and W. Herfort, Local Error Structures and Order Conditions in Terms of Lie Elements for Exponential Splitting Schemes, Opusc. Math. 34, 243 (2014).
  59. W. Auzinger, O. Koch, and M. Thalhammer, Defect-Based Local Error Estimators for Splitting Methods, with Application to Schrödinger Equations, Part II. Higher-Order Methods for Linear Problems, J. Comput. Appl. Math. 255, 384 (2014).
  60. R. Babbush, C. Gidney, D. W. Berry, N. Wiebe, J. McClean, A. Paler, A. Fowler, and H. Neven, Encoding Electronic Spectra in Quantum Circuits with Linear T Complexity, Phys. Rev. X 8, 041015 (2018).
  61. A. J. Ferris, Fourier Transform for Fermionic Systems and the Spectral Tensor Network, Phys. Rev. Lett. 113, 010401 (2014).

  62. For Hamiltonians that are supported on finite lattices, we simply add trivial terms supported outside the lattices.

  63. E. H. Lieb and D. W. Robinson, The Finite Group Velocity of Quantum Spin Systems, Commun. Math. Phys. 28, 251 (1972).
  64. M. B. Hastings and T. Koma, Spectral Gap and Exponential Decay of Correlations, Commun. Math. Phys. 265, 781 (2006).
  65. B. Nachtergaele, Y. Ogata, and R. Sims, Propagation of Correlations in Quantum Lattice Systems, J. Stat. Phys. 124, 1 (2006).
  66. B. Nachtergaele and R. Sims, Lieb-Robinson Bounds and the Exponential Clustering Theorem, Commun. Math. Phys. 265, 119 (2006).
  67. Z.-X. Gong, M. Foss-Feig, S. Michalakis, and A. V. Gorshkov, Persistence of Locality in Systems with Power-Law Interactions, Phys. Rev. Lett. 113, 030602 (2014).
  68. M. Foss-Feig, Z.-X. Gong, C. W. Clark, and A. V. Gorshkov, Nearly Linear Light Cones in Long-Range Interacting Quantum Systems, Phys. Rev. Lett. 114, 157201 (2015).
  69. D.-M. Storch, M. Van Den Worm, and M. Kastner, Interplay of Soundcone and Supersonic Propagation in Lattice Models with Power Law Interactions, New J. Phys. 17, 063021 (2015).
  70. C.-F. Chen and A. Lucas, Finite Speed of quantum scrambling with long range interactions, Phys. Rev. Lett. 123, 250605 (2019).
  71. J. Haah, M. B. Hastings, R. Kothari, and G. H. Low, Quantum Algorithm for Simulating Real Time Evolution of Lattice Hamiltonians, in Proceedings of the 59th IEEE Symposium on Foundations of Computer Science (IEEE Computer Society, Washington, DC, 2018), pp. 350–360, 10.1109/FOCS.2018.00041.

  72. More recent bounds [70, 73] provide tighter light cones than in Tran et al. [52] for α>2d+1.

  73. T. Kuwahara and K. Saito, Strictly Linear Light Cones in Long-Range Interacting Systems of Arbitrary Dimensions, Phys. Rev. X 10, 031010 (2020).
  74. D. J. Luitz, N. Laflorencie, and F. Alet, Many-Body Localization Edge in the Random-Field Heisenberg Chain, Phys. Rev. B 91, 081103(R) (2015).
  75. Y. Atia and D. Aharonov, Fast-Forwarding of Hamiltonians and Exponentially Precise Measurements, Nat. Commun. 8, 1572 (2017).
  76. I. D. Kivlichan, J. McClean, N. Wiebe, C. Gidney, A. Aspuru-Guzik, G. Kin-Lic Chan, and R. Babbush, Quantum Simulation of Electronic Structure with Linear Depth and Connectivity, Phys. Rev. Lett. 120, 110501 (2018).
  77. D. Poulin, A. Qarry, R. D. Somma, and F. Verstraete, Quantum Simulation of Time-Dependent Hamiltonians and the Convenient Illusion of Hilbert Space, Phys. Rev. Lett. 106, 170501 (2011).
  78. M. Kieferová, A. Scherer, and D. W. Berry, Simulating the Dynamics of Time-Dependent Hamiltonians with a Truncated Dyson Series, Phys. Rev. A 99, 042314 (2019).
  79. D. W. Berry, A. M. Childs, Y. Su, X. Wang, and N. Wiebe, Time-Dependent Hamiltonian Simulation with L1-Norm Scaling, Quantum 4, 254 (2020).
  80. M. Heyl, Philipp. Hauke, and P. Zoller, Quantum Localization Bounds Trotter Errors in Digital Quantum Simulation, Sci. Adv. 5, eaau8342 (2019).
  81. L. M. Sieberer, T. Olsacher, A. Elben, M. Heyl, P. Hauke, F. Haake, and P. Zoller, Digital Quantum Simulation, Trotter Errors, and Quantum Chaos of the Kicked Top, npj Quantum Inf. 5, 78 (2019).
  82. S. McArdle, X. Yuan, and S. Benjamin, Error-Mitigated Digital Quantum Simulation, Phys. Rev. Lett. 122, 180501 (2019).
  83. A. W. Knapp, Basic Real Analysis, Digital 2nd ed. (Birkhëuser, Boston, 2005), http://dx.doi.org/10.3792/euclid/9781429799997.
  84. T. Helgaker, P. Jørgensen, and J. Olsen, Molecular Electronic-Structure Theory (John Wiley & Sons, New York, 2014), 10.1002/9781119019572.
  85. S. C. Eisenstat and I. C. F. Ipsen, Relative Perturbation Techniques for Singular Value Problems, SIAM J. Numer. Anal. 32, 1972 (1995).
  86. I. C. F. Ipsen, Relative Perturbation Results for Matrix Eigenvalues and Singular Values, Acta Numer. 7, 151 (1998).

Outline

Information

Phys. Rev. X 11, 011020– Published 1 February, 2021
  • Received 21 January 2020
  • Revised 7 July 2020
  • Accepted 4 November 2020
Crossmark - Check for updates button
Creative Commons Logo

Published by the American Physical Society under the terms of the Creative Commons Attribution 4.0 International license. Further distribution of this work must maintain attribution to the author(s) and the published article’s title, journal citation, and DOI.

Published by the American Physical Society

Sign In to Your Journals Account

Filter

Filter

Article Lookup

Enter a citation