Quantum Information & Computation
Volume 25, Issue 1
RESEARCH ARTICLE Open access

Selection and Improvement of Product Formulae for Best Performance of Quantum Simulation

Mauro E. S. Morales, Pedro C. S. Costa, Giacomo Pantaleoni, Daniel K. Burgarth, Yuval R. Sanders, Dominic W. Berry

Author affiliations
  1. Centre for Quantum Computation and Communication Technology, University of Technology Sydney, Sydney, NSW, Australia; Centre for Quantum Software and Information, University of Technology Sydney, Sydney, NSW, Australia; Joint Center for Quantum Information and Computer Science (QuICS), University of Maryland, College Park, Maryland, USA
  2. School of Mathematical and Physical Sciences, Macquarie University, Sydney, NSW, Australia; Quantum for New South Wales, Sydney, NSW, Australia
  3. School of Mathematical and Physical Sciences, Macquarie University, Sydney, NSW, Australia
  4. School of Mathematical and Physical Sciences, Macquarie University, Sydney, NSW, Australia; Department Physik, Friedrich-Alexander-Universität Erlangen-Nürnberg, Staudtstraße 7, Erlangen, Germany
  5. Centre for Quantum Software and Information, University of Technology Sydney, Sydney, NSW, Australia; School of Mathematical and Physical Sciences, Macquarie University, Sydney, NSW, Australia

pp. 1-35 · 10.2478/qic-2025-0001

Read PDF View on Reference Global
On this page

Abstract

Quantum algorithms for simulation of Hamiltonian evolution are often based on product formulae. The fractal methods give a systematic way to find arbitrarily high-order product formulae, but result in a large number of exponentials. On the other hand, product formulae with fewer exponentials can be found by numerical solution of simultaneous non-linear equations. It is also possible to reduce the cost of long-time simulations by processing, where a kernel is repeated and a processor need only be applied at the beginning and end of the simulation. In this work, we found thousands of new product formulae, and numerically tested these formulae, together with many formulae from prior literature. We provide methods to fairly compare product formulae of different lengths and different orders. For the case of 8th order, we have found new product formulae with exceptional performance, about two orders of magnitude better accuracy than prior work, both in the processed and non-processed cases. The processed product formula provides the best performance due to being shorter than the non-processed product formula. It outperforms all other tested product formulae over a range of many orders of magnitude in system parameters T(time) and ε(allowable error). That includes reasonable combinations of parameters to be used in quantum algorithms, where the size of the simulation is large enough to be classically intractable, but not so large it takes an impractically long time on a quantum computer.
Open accessCC BY-NC-ND 4.0

Keywords

  • quantum algorithm
  • quantum simulation
  • product formula
  • symplectic integrator
  • Trotter formula

Suggested citation

Mauro E. S. Morales, Pedro C. S. Costa, Giacomo Pantaleoni, Daniel K. Burgarth, Yuval R. Sanders, Dominic W. Berry (2025). Selection and Improvement of Product Formulae for Best Performance of Quantum Simulation. Quantum Information & Computation, 25(1), 1-35. https://doi.org/10.2478/qic-2025-0001

Download BibTeX

References (55)

  1. M. Creutz and A. Gocksch (1989). “Higher-order hybrid Monte Carlo algorithms”. Physical Review Letters, 63, 9. https://doi.org/10.1103/PhysRevLett.63.9.DOI: 10.1103/PhysRevLett.63.9Google Scholar
  2. M. Suzuki (1990). “Fractal decomposition of exponential operators with applications to many-body theories and Monte Carlo simulations”. Physical Letters A, 146, 319 https://doi.org/10.1016/0375-9601(90)90962-N.DOI: 10.1016/0375-9601(90)90962-NGoogle Scholar
  3. H. Yoshida, (1990). “Construction of higher order symplectic integrators”. Physics Letters A, 150, 262 https://doi.org/10.1016/0375-9601(90)90092-3.DOI: 10.1016/0375-9601(90)90092-3Google Scholar
  4. M. Suzuki (1991). “General theory of fractal path integrals with applications to many-body theories and statistical physics.” Journal of Mathematical Physics, 32, 400. https://doi.org/10.1063/1.529425.DOI: 10.1063/1.529425Google Scholar
  5. D. W. Berry, G. Ahokas, R. Cleve, and B. C. Sanders (2007). “Efficient quantum algorithms for simulating sparse Hamiltonians”. Communications in Mathematical Physics, 270, 359. https://doi.org/10.1007/s00220-006-0150-x.DOI: 10.1007/s00220-006-0150-xGoogle Scholar
  6. S. Lloyd (1996). “Universal quantum simulators”. Science, 273, 1073. https://doi.org/10.1126/science.273.5278.1073.DOI: 10.1126/science.273.5278.1073Google Scholar
  7. D. Aharonov and A. Ta-Shma (2003). “Adiabatic quantum state generation and statistical zero knowledge”, in Proceedings of the Thirty-Fifth Annual ACM Symposium on Theory of Computing, STOC '03. New York: Association for Computing Machinery, pp. 20–29. https://doi.org/10.1145/780542.780546.DOI: 10.1145/780542.780546Google Scholar
  8. D. W. Berry and A. M. Childs (2012). “Black-box Hamiltonian simulation and unitary implementation”. Quantum Information and Computation, 12, 29–62. https://doi.org/10.26421/QIC12.1-2-4.DOI: 10.26421/QIC12.1-2-4Google Scholar
  9. D. W. Berry, A. M. Childs, R. Cleve, R. Kothari, and R. D. Somma (2014). “Exponential improvement in precision for simulating sparse Hamiltonians”, in Proceedings of the Forty-Sixth Annual ACM Symposium on Theory of Computing, STOC '14. New York: Association for Computing Machinery, pp. 283–292. https://doi.org/10.1145/2591796.2591854.DOI: 10.1145/2591796.2591854Google Scholar
  10. D. W. Berry, A. M. Childs, and R. Kothari (2015). “Hamiltonian simulation with nearly optimal dependence on all parameters”, in 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, pp. 792–809. https://doi.org/10.1109/FOCS.2015.54.DOI: 10.1109/FOCS.2015.54Google Scholar
  11. G. H. Low (2019) “Hamiltonian simulation with nearly optimal dependence on spectral norm”, in Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (STOC 2019). New York: Association for Computing Machinery, pp. 491–502. https://doi.org/10.1145/3313276.3316386.DOI: 10.1145/3313276.3316386Google Scholar
  12. A. M. Childs, Y. Su, M. C. Tran, N. Wiebe, and S. Zhu (2021) “Theory of Trotter error with commutator scaling”. Physical Review X, 11, 011020. https://doi.org/10.1103/PhysRevX.11.011020.DOI: 10.1103/PhysRevX.11.011020Google Scholar
  13. A. M. Childs and N. Wiebe (2012) “Hamiltonian simulation using linear combinations of unitary operations”. Quantum Information and Computation, 12, 901–924. https://doi.org/10.26421/QIC12.11-12-1.DOI: 10.26421/QIC12.11-12-1Google Scholar
  14. D. W. Berry, A. M. Childs, R. Cleve, R. Kothari, and R. D. Somma (2015), Simulating Hamiltonian dynamics with a truncated Taylor Series”. Physical Review Letters, 114, 090502. https://doi.org/10.1103/PhysRevLett.114.090502.DOI: 10.1103/PhysRevLett.114.090502Google Scholar
  15. G. H. Low and I. L. Chuang (2017). “Optimal Hamiltonian simulation by quantum signal processing”. Physical Review Letters, 118, 010501. https://doi.org/10.1103/PhysRevLett.118.010501.DOI: 10.1103/PhysRevLett.118.010501Google Scholar
  16. R. Babbush, J. McClean, D. Wecker, A. Aspuru-Guzik, and N. Wiebe (2015) “Chemical basis of Trotter-Suzuki errors in quantum chemistry simulation”. Physical Review A, 91, 022311. https://doi.org/10.1103/PhysRevA.91.022311.DOI: 10.1103/PhysRevA.91.022311Google Scholar
  17. A. M. Childs, D. Maslov, Y. Nam, N. J. Ross, and Y. Su (2018) “Toward the first quantum simulation with quantum speedup”. Proceedings of the National Academy of Sciences, 115, 9456. https://doi.org/10.1073/pnas.1801723115.DOI: 10.1073/pnas.1801723115Google Scholar
  18. Y. Su, H.-Y. Huang, and E. T. Campbell (2021) “Nearly tight Trotterization of interacting electrons”. Quantum, 5, 495. https://doi.org/10.22331/q-2021-07-05-495.DOI: 10.22331/q-2021-07-05-495Google Scholar
  19. C. Zhang (2012). “Randomized algorithms for Hamiltonian simulation”, in L. Plaskota and H. Woźniakowski, (eds), Monte Carlo and Quasi-Monte Carlo Methods 2010. Berlin, Heidelberg: Springer, pp. 709–719. https://doi.org/10.1007/978-3-642-27440-4_42.DOI: 10.1007/978-3-642-27440-4_42Google Scholar
  20. E. Campbell (2019). “Random compiler for fast Hamiltonian simulation”. Physical Review Letters, 123, 070503. https://doi.org/10.1103/PhysRevLett.123.070503.DOI: 10.1103/PhysRevLett.123.070503Google Scholar
  21. A. M. Childs, A. Ostrander, and Y. Su (2019). “Faster quantum simulation by randomization”. Quantum, 3, 182. https://doi.org/10.22331/q-2019-09-02-182.DOI: 10.22331/q-2019-09-02-182Google Scholar
  22. M. P. Calvo and J. M. Sanz-Serna (1993). “High-order symplectic Runge–Kutta–Nyström methods”. SIAM Journal on Scientific Computing, 14, 1237. https://doi.org/10.1137/0914073.DOI: 10.1137/0914073Google Scholar
  23. M. Suzuki and K. Umeno (1993). “Higher-order decomposition theory of exponential operators and its applications to QMC and nonlinear dynamics”, in D. P. Landau, K. K. Mon, and H.-B. Schüttler (eds), Computer Simulation Studies in Condensed-Matter Physics VI. Berlin, Heidelberg: Springer, pp. 74–86.DOI: 10.1007/978-3-642-78448-4_7Google Scholar
  24. R. I. McLachlan (1995). “On the numerical integration of ordinary differential equations by symmetric composition methods”. SIAM Journal on Scientific Computing, 16, 151. https://doi.org/10.1137/0916010.DOI: 10.1137/0916010Google Scholar
  25. W. Kahan and R.-C. Li (1997). “Composition constants for raising the orders of unconventional schemes for ordinary differential equations”. Mathematics of Computation, 66, 1089–1099. https://doi.org/10.1090/S0025-5718-97-00873-9.DOI: 10.1090/S0025-5718-97-00873-9Google Scholar
  26. C. Tsitouras (1999). “A tenth order symplectic Runge–Kutta–Nyström Method”. Celestial Mechanics and Dynamical Astronomy, 74, 223–230. https://doi.org/10.1023/a:1008346516048.DOI: 10.1023/A:1008346516048Google Scholar
  27. R. I. McLachlan (2002). “Families of high-order composition methods”. Numerical Algorithms, 31, 233–246. https://doi.org/10.1023/a:1021195019574.DOI: 10.1023/A:1021195019574Google Scholar
  28. E. Hairer, G. Wanner, and C. Lubich (2006). Geometric Numerical Integration: Structure-Preserving Algorithms for Ordinary Differential Equations. Springer-Verlag. https://doi.org/10.1007/3-540-30666-8.DOI: 10.1007/3-540-30666-8Google Scholar
  29. M. Sofroniou and G. Spaletta (2005). “Derivation of symmetric composition constants for symmetric integrators”. Optimization Methods and Software, 20, 597. https://doi.org/10.1080/10556780500140664.DOI: 10.1080/10556780500140664Google Scholar
  30. S. Blanes, F. Casas, and A. Murua (2008). “Splitting and composition methods in the numerical integration of differential equations”. Boletín de la Sociedad Española de Matemática Aplicada, 45, 89, Available at: https://www.sema.org.es/Documentos/Fotos/1/0/2/5/pagina_fichero_1025-ficheros-1644772684-01752300-68691.pdf (Accessed on 6 December 2024).Google Scholar
  31. S. Blanes, F. Casas, and A. Murua (2006). “Composition methods for differential equations with processing”. SIAM Journal on Scientific Computing, 27, 1817. https://doi.org/10.1137/030601223.DOI: 10.1137/030601223Google Scholar
  32. S. Blanes, F. Casas, P. Chartier, and A. Murua (2013). “Optimized high-order splitting methods for some classes of parabolic equations”. Mathematics of Computation, 82, 1559. Available at: http://www.jstor.org/stable/42002709 (Accessed on 6 December 2024).DOI: 10.1090/S0025-5718-2012-02657-3Google Scholar
  33. S. Blanes, F. Casas, and A. Murua (2024). “Splitting methods for differential equations”. Acta Numerica, 33, 1–161. https://doi.org/10.1017/S0962492923000077.DOI: 10.1017/S0962492923000077Google Scholar
  34. M. A. Lopez-Marcos, R. D. Skeel, and J. M. Sanz-Serna (1996). “Cheap enhancement of symplectic integrators”, in Numerical Analysis, Longman Scientific and Technical, pp. 107–122.Google Scholar
  35. J. Butcher and J. Sanz-Serna (1996). “The number of conditions for a Runge-Kutta method to have effective order p”. Applied Numerical Mathematics, 22, 103. https://doi.org/10.1016/S0168-9274(96)00028-1.DOI: 10.1016/S0168-9274(96)00028-1Google Scholar
  36. R. I. McLachlan (1996). “More on symplectic correctors”. Integration Algorithms and Classical Mechanics, 10, 141.DOI: 10.1090/fic/010/09Google Scholar
  37. J. Wisdom, M. Holman, and J. Touma (1996). “Symplectic correctors”. Integration Algorithms and Classical Mechanics, 10, 217.DOI: 10.1090/fic/010/14Google Scholar
  38. S. Blanes, F. Casas, and J. Ros (1999). “Symplectic integration with processing: A general study”. SIAM Journal on Scientific Computing, 21, 711. https://doi.org/10.1137/S1064827598332497.DOI: 10.1137/S1064827598332497Google Scholar
  39. S. Blanes (2001). “High order numerical integrators for differential equations using composition and processing of low order methods”. Applied Numerical Mathematics, 37, 289. https://doi.org/10.1016/S0168-9274(00)00044-1.DOI: 10.1016/S0168-9274(00)00044-1Google Scholar
  40. S. Blanes, F. Casas, and A. Escorihuela-Tomàs (2024). “Families of efficient low order processed composition methods”. Applied Numerical Mathematics, 204, 86. https://doi.org/10.1016/j.apnum.2024.06.002.DOI: 10.1016/j.apnum.2024.06.002Google Scholar
  41. S. Blanes and F. Casas (2004). “On the convergence and optimization of the Baker–Campbell–Hausdorff formula”. Linear Algebra and its Applications, 378, 135. https://doi.org/10.1016/j.laa.2003.09.010.DOI: 10.1016/j.laa.2003.09.010Google Scholar
  42. E. Forest and R. D. Ruth (1990). “Fourth-order symplectic integration”. Physica D: Nonlinear Phenomena, 43, 105. https://doi.org/10.1016/0167-2789(90)90019-L.DOI: 10.1016/0167-2789(90)90019-LGoogle Scholar
  43. M. Campostrini and P. Rossi (1990). “A comparison of numerical algorithms for dynamical fermions”. Nuclear Physics B, 329, 753. https://doi.org/10.1016/0550-3213(90)90081-N.DOI: 10.1016/0550-3213(90)90081-NGoogle Scholar
  44. E. Forest (2006). “Geometric integration for particle accelerators”. Journal of Physics A: Mathematical and General, 39, 5321. https://doi.org/10.1088/0305-4470/39/19/S03.DOI: 10.1088/0305-4470/39/19/S03Google Scholar
  45. R. Babbush, C. Gidney, D. W. Berry, N. Wiebe, J. McClean, A. Paler, A. Fowler, and H. Neven (2018). “Encoding electronic spectra in quantum circuits with linear T complexity”. Physical Review X, 8, 041015 https://doi.org/10.1103/PhysRevX.8.041015.DOI: 10.1103/PhysRevX.8.041015Google Scholar
  46. J. Ostmeyer (2023). “Optimised Trotter decompositions for classical and quantum computing”. Journal of Physics A: Mathematical and Theoretical, 56, 285303. https://doi.org/10.1088/1751-8121/acde7a.DOI: 10.1088/1751-8121/acde7aGoogle Scholar
  47. S. Blanes and P. Moan (2002). “Practical symplectic partitioned Runge–Kutta and Runge–Kutta–Nyström methods”. Journal of Computational and Applied Mathematics, 142, 313–324. https://doi.org/10.1016/S0377-0427(01)00492-7.DOI: 10.1016/S0377-0427(01)00492-7Google Scholar
  48. E. Alberdi, M. Antoñana, J. Makazaga, and A. Murua (2019). “An algorithm based on continuation techniques for minimization problems with highly non-linear equality constraints”. arXiv, arXiv:1909.07263.Google Scholar
  49. C. Gidney and M. Ekerå (2021). “How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits”. Quantum, 5, 433. https://doi.org/10.22331/q-2021-04-15-433.DOI: 10.22331/q-2021-04-15-433Google Scholar
  50. G. H. Low, Y. Su, Y. Tong, and M. C. Tran (2023). “Complexity of implementing Trotter steps”. PRX Quantum, 4, 020323. https://doi.org/10.1103/PRXQuantum.4.020323.DOI: 10.1103/PRXQuantum.4.020323Google Scholar
  51. N. C. Rubin, D. W. Berry, A. Kononov, F. D. Malone, T. Khattar, A. White, J. Lee, H. Neven, R. Babbush, and A. D. Baczewski (2024), “Quantum computation of stopping power for inertial fusion target design”. Proceedings of the National Academy of Sciences, 121, e2317772121. https://doi.org/10.1073/pnas.2317772121.DOI: 10.1073/pnas.2317772121Google Scholar
  52. Y. Su, D. W. Berry, N. Wiebe, N. Rubin, and R. Babbush (2021). “Fault-tolerant quantum simulations of chemistry in first quantization”. PRX Quantum, 2, 040332. https://doi.org/10.1103/PRXQuantum.2.040332.DOI: 10.1103/PRXQuantum.2.040332Google Scholar
  53. C.-H. Cho, D. W. Berry, and M.-H. Hsieh (2024). “Doubling the order of approximation via the randomized product formula”. Physical Review A, 109, 062431. https://doi.org/10.1103/PhysRevA.109.062431.DOI: 10.1103/PhysRevA.109.062431Google Scholar
  54. A. Van-Brunt and M. Visser (2016). “Simplifying the Reinsch algorithm for the Baker–Campbell–Hausdorff series”. Journal of Mathematical Physics, 57, 023507. https://doi.org/10.1063/1.4939929.DOI: 10.1063/1.4939929Google Scholar
  55. I. Duleba and I. Karcz-Duleba, (2020). “Algorithm to express lie monomials in Ph. Hall basis and its practical applications”, in R. Moreno-Díaz, F. Pichler, and A. Quesada-Arencibia (eds), Computer Aided Systems Theory – EUROCAST 2019, Cham: Springer International Publishing, pp. 465–473. https://doi.org/10.1007/978-3-030-45093-9_56.DOI: 10.1007/978-3-030-45093-9_56Google Scholar