Improved Accuracy for Trotter Simulations Using Chebyshev Interpolation
1Zapata Computing Inc., Boston, MA 02110, USA
2Facility for Rare Isotope Beams, Michigan State University, East Lansing, MI 48824, USA
3Department of Computer Science, University of Toronto, Toronto, ON M5S 2E4, Canada
4Pacific Northwest National Laboratory, Richland, WA 99352, USA
| Published: | 2024-02-26, volume 8, page 1266 |
| Eprint: | arXiv:2212.14144v4 |
| Doi: | https://doi.org/10.22331/q-2024-02-26-1266 |
| Citation: | Quantum 8, 1266 (2024). |
Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.
Abstract
Quantum metrology allows for measuring properties of a quantum system at the optimal Heisenberg limit. However, when the relevant quantum states are prepared using digital Hamiltonian simulation, the accrued algorithmic errors will cause deviations from this fundamental limit. In this work, we show how algorithmic errors due to Trotterized time evolution can be mitigated through the use of standard polynomial interpolation techniques. Our approach is to extrapolate to zero Trotter step size, akin to zero-noise extrapolation techniques for mitigating hardware errors. We perform a rigorous error analysis of the interpolation approach for estimating eigenvalues and time-evolved expectation values, and show that the Heisenberg limit is achieved up to polylogarithmic factors in the error. Our work suggests that accuracies approaching those of state-of-the-art simulation algorithms may be achieved using Trotter and classical resources alone for a number of relevant algorithmic tasks.
Featured image: The first five Chebyshev polynomials. Interpolation at the Chebyshev zeros serves as a robust scheme for Trotter error mitigation.
Popular summary
To mitigate errors in Trotter simulations without increasing the quantum processing time, we use polynomials to learn the relationship between error and step size. By collecting data for different choices of step size, we can interpolate, i.e. thread, the data with a polynomial, then estimate the expected behavior for very small step sizes. We prove mathematically that our approach yields asymptotic accuracy improvements over standard Trotter for two fundamental tasks: estimating eigenvalues and estimating expectation values.
Our method is simple and practical, requiring only standard techniques in quantum and classical computation. We believe our work provides a strong theoretical foothold for further investigations of algorithmic error mitigation. Extensions of this work could occur in several directions, from eliminating artificial assumptions in our analysis to demonstrating improved quantum simulations.
► BibTeX data
► References
[1] S. Lloyd, Universal quantum simulators, Science 273 (1996) 1073.
https://doi.org/10.1126/science.273.5278.1073
[2] M. Reiher, N. Wiebe, K.M. Svore, D. Wecker and M. Troyer, Elucidating reaction mechanisms on quantum computers, Proceedings of the National Academy of Sciences 114 (2017) 7555.
https://doi.org/10.1073/pnas.161915211
[3] J.D. Whitfield, J. Biamonte and A. Aspuru-Guzik, Simulation of electronic structure hamiltonians using quantum computers, Molecular Physics 109 (2011) 735.
https://doi.org/10.1080/00268976.2011.552441
[4] J. Lee, D.W. Berry, C. Gidney, W.J. Huggins, J.R. McClean, N. Wiebe et al., Even more efficient quantum computations of chemistry through tensor hypercontraction, PRX Quantum 2 (2021) 030305.
https://doi.org/10.1103/PRXQuantum.2.030305
[5] V. von Burg, G.H. Low, T. Häner, D.S. Steiger, M. Reiher, M. Roetteler et al., Quantum computing enhanced computational catalysis, Physical Review Research 3 (2021) 033055.
https://doi.org/10.1103/PhysRevResearch.3.033055
[6] S.P. Jordan, K.S. Lee and J. Preskill, Quantum algorithms for quantum field theories, Science 336 (2012) 1130.
https://doi.org/10.1126/science.1217069
[7] A.F. Shaw, P. Lougovski, J.R. Stryker and N. Wiebe, Quantum algorithms for simulating the lattice schwinger model, Quantum 4 (2020) 306.
https://doi.org/10.22331/q-2020-08-10-306
[8] N. Klco, M.J. Savage and J.R. Stryker, Su (2) non-abelian gauge field theory in one dimension on digital quantum computers, Physical Review D 101 (2020) 074512.
https://doi.org/10.1103/PhysRevD.101.074512
[9] A.M. Childs and N. Wiebe, Hamiltonian simulation using linear combinations of unitary operations, Quantum Info. Comput. 12 (2012) 901–924.
https://doi.org/10.26421/QIC12.11-12-1
[10] G.H. Low, V. Kliuchnikov and N. Wiebe, Well-conditioned multiproduct hamiltonian simulation, arXiv:1907.11679 (2019).
https://doi.org/10.48550/arXiv.1907.11679
arXiv:1907.11679
[11] D.W. Berry, A.M. Childs, R. Cleve, R. Kothari and R.D. Somma, Simulating hamiltonian dynamics with a truncated taylor series, Physical review letters 114 (2015) 090502.
https://doi.org/10.1103/PhysRevLett.114.090502
[12] G.H. Low and N. Wiebe, Hamiltonian simulation in the interaction picture, arXiv:1805.00675 (2018).
https://doi.org/10.48550/arXiv.1805.00675
arXiv:1805.00675
[13] M. Kieferová, A. Scherer and D.W. Berry, Simulating the dynamics of time-dependent hamiltonians with a truncated dyson series, Physical Review A 99 (2019) 042314.
https://doi.org/10.1103/PhysRevA.99.042314
[14] G.H. Low and I.L. Chuang, Hamiltonian Simulation by Qubitization, Quantum 3 (2019) 163.
https://doi.org/10.22331/q-2019-07-12-163
[15] R. Babbush, C. Gidney, D.W. Berry, N. Wiebe, J. McClean, A. Paler et al., Encoding electronic spectra in quantum circuits with linear t complexity, Physical Review X 8 (2018) 041015.
https://doi.org/10.1103/PhysRevX.8.041015
[16] D.W. Berry, G. Ahokas, R. Cleve and B.C. Sanders, Efficient quantum algorithms for simulating sparse hamiltonians, Communications in Mathematical Physics 270 (2006) 359–371.
https://doi.org/10.1007/s00220-006-0150-x
[17] N. Wiebe, D.W. Berry, P. Høyer and B.C. Sanders, Simulating quantum dynamics on a quantum computer, Journal of Physics A: Mathematical and Theoretical 44 (2011) 445308.
https://doi.org/10.1088/1751-8113/44/44/445308
[18] A.M. Childs, Y. Su, M.C. Tran, N. Wiebe and S. Zhu, Theory of trotter error with commutator scaling, Physical Review X 11 (2021) 011020.
https://doi.org/10.1103/PhysRevX.11.011020
[19] J. Haah, M.B. Hastings, R. Kothari and G.H. Low, Quantum algorithm for simulating real time evolution of lattice hamiltonians, SIAM Journal on Computing (2021) FOCS18.
https://doi.org/10.1137/18M12315
[20] M. Hagan and N. Wiebe, Composite quantum simulations, arXiv:2206.06409 (2022).
https://doi.org/10.22331/q-2023-11-14-1181
arXiv:2206.06409
[21] G.H. Low, Y. Su, Y. Tong and M.C. Tran, On the complexity of implementing trotter steps, arXiv:2211.09133 (2022).
https://doi.org/10.1103/PRXQuantum.4.020323
arXiv:2211.09133
[22] G.H. Low and I.L. Chuang, Optimal hamiltonian simulation by quantum signal processing, Physical Review Letters 118 (2017).
https://doi.org/10.1103/physrevlett.118.010501
[23] S. Endo, Q. Zhao, Y. Li, S. Benjamin and X. Yuan, Mitigating algorithmic errors in a hamiltonian simulation, Phys. Rev. A 99 (2019) 012334.
https://doi.org/10.1103/PhysRevA.99.012334
[24] A.C. Vazquez, R. Hiptmair and S. Woerner, Enhancing the quantum linear systems algorithm using richardson extrapolation, ACM Transactions on Quantum Computing 3 (2022).
https://doi.org/10.1145/3490631
[25] A.C. Vazquez, D.J. Egger, D. Ochsner and S. Woerner, Well-conditioned multi-product formulas for hardware-friendly hamiltonian simulation, Quantum 7 (2023) 1067.
https://doi.org/10.22331/q-2023-07-25-1067
[26] M. Suzuki, General theory of fractal path integrals with applications to many‐body theories and statistical physics, Journal of Mathematical Physics 32 (1991) 400.
https://doi.org/10.1063/1.529425
[27] A. Gilyén, Y. Su, G.H. Low and N. Wiebe, Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics, in Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, pp. 193–204, 2019, DOI.
https://doi.org/10.1145/3313276.3316366
[28] C. Yi and E. Crosson, Spectral analysis of product formulas for quantum simulation, npj Quantum Information 8 (2022) 37.
https://doi.org/10.1038/s41534-022-00548-w
[29] A. Quarteroni, R. Sacco and F. Saleri, Numerical mathematics, vol. 37, Springer Science & Business Media (2010), 10.1007/b98885.
https://doi.org/10.1007/b98885
[30] F. Piazzon and M. Vianello, Stability inequalities for lebesgue constants via markov-like inequalities, Dolomites Research Notes on Approximation 11 (2018).
[31] A.P. de Camargo, On the numerical stability of newton’s formula for lagrange interpolation, Journal of Computational and Applied Mathematics 365 (2020) 112369.
https://doi.org/10.1016/j.cam.2019.112369
[32] L. Trefethen, Six myths of polynomial interpolation and quadrature, (2011).
[33] W. Gautschi, How (un)stable are vandermonde systems? asymptotic and computational analysis, in Lecture Notes in Pure and Applied Mathematics, pp. 193–210, Marcel Dekker, Inc, 1990.
[34] N.J. Higham, The numerical stability of barycentric lagrange interpolation, IMA Journal of Numerical Analysis 24 (2004) 547.
https://doi.org/10.1093/imanum/24.4.547
[35] J.C. Mason and D.C. Handscomb, Chebyshev polynomials, CRC press (2002), 10.1201/9781420036114.
https://doi.org/10.1201/9781420036114
[36] G. Rendon, T. Izubuchi and Y. Kikuchi, Effects of cosine tapering window on quantum phase estimation, Physical Review D 106 (2022) 034503.
https://doi.org/10.1103/PhysRevD.106.034503
[37] L.N. Trefethen, Approximation Theory and Approximation Practice, Extended Edition, SIAM (2019), 10.1137/1.9781611975949.
https://doi.org/10.1137/1.9781611975949
[38] F.L. Bauer and C.T. Fike, Norms and exclusion theorems, Numer. Math. 2 (1960) 137–141.
https://doi.org/10.1007/BF01386217
[39] S. Blanes, F. Casas, J.-A. Oteo and J. Ros, The magnus expansion and some of its applications, Physics reports 470 (2009) 151.
https://doi.org/10.1016/j.physrep.2008.11.001
[40] N. Klco and M.J. Savage, Minimally entangled state preparation of localized wave functions on quantum computers, Physical Review A 102 (2020).
https://doi.org/10.1103/physreva.102.012612
[41] J.J. García-Ripoll, Quantum-inspired algorithms for multivariate analysis: from interpolation to partial differential equations, Quantum 5 (2021) 431.
https://doi.org/10.22331/q-2021-04-15-431
[42] W. Górecki, R. Demkowicz-Dobrzański, H.M. Wiseman and D.W. Berry, $\pi$-corrected heisenberg limit, Physical review letters 124 (2020) 030501.
https://doi.org/10.1103/PhysRevLett.124.030501
[43] D. Grinko, J. Gacon, C. Zoufal and S. Woerner, Iterative quantum amplitude estimation, npj Quantum Information 7 (2021) 52 [1912.05559].
https://doi.org/10.1038/s41534-021-00379-1
arXiv:1912.05559
[44] N. Wiebe, D. Berry, P. Høyer and B.C. Sanders, Higher order decompositions of ordered operator exponentials, Journal of Physics A: Mathematical and Theoretical 43 (2010) 065203.
https://doi.org/10.1088/1751-8113/43/6/065203
[45] R.A. Horn and C.R. Johnson, Matrix analysis, Cambridge university press (2012), 10.1017/CBO9780511810817.
https://doi.org/10.1017/CBO9780511810817
[46] M. Chiani, D. Dardari and M.K. Simon, New exponential bounds and approximations for the computation of error probability in fading channels, IEEE Transactions on Wireless Communications 2 (2003) 840.
https://doi.org/10.1109/TWC.2003.814350
[47] J.M. Borwein and P.B. Borwein, Pi and the AGM: a study in the analytic number theory and computational complexity, Wiley-Interscience (1987).
[48] B.L. Higgins, D.W. Berry, S.D. Bartlett, H.M. Wiseman and G.J. Pryde, Entanglement-free Heisenberg-limited phase estimation, Nature 450 (2007) 393.
https://doi.org/10.1038/nature06257
[49] R.B. Griffiths and C.-S. Niu, Semiclassical Fourier Transform for Quantum Computation, Physical Review Letters 76 (1996) 3228.
https://doi.org/10.1103/PhysRevLett.76.3228
[50] A.Y. Kitaev, Quantum measurements and the abelian stabilizer problem, quant-ph/9511026 (1995).
https://doi.org/10.48550/arXiv.quant-ph/9511026
arXiv:quant-ph/9511026
[51] D.S. Abrams and S. Lloyd, Quantum Algorithm Providing Exponential Speed Increase for Finding Eigenvalues and Eigenvectors, Physical Review Letters 83 (1999) 5162.
https://doi.org/10.1103/PhysRevLett.83.5162
[52] J. Watkins, N. Wiebe, A. Roggero and D. Lee, Time-dependent hamiltonian simulation using discrete clock constructions, arXiv:2203.11353 (2022).
https://doi.org/10.48550/arXiv.2203.11353
arXiv:2203.11353
[53] T.D. Ahle, Sharp and simple bounds for the raw moments of the binomial and poisson distributions, Statistics & Probability Letters 182 (2022) 109306.
https://doi.org/10.1016/j.spl.2021.109306
[54] T. Rivlin, Chebyshev Polynomials, Dover Books on Mathematics, Dover Publications (2020).
Cited by
[1] Sergiy Zhuk, Niall F. Robertson, and Sergey Bravyi, "Trotter error bounds and dynamic multi-product formulas for Hamiltonian simulation", Physical Review Research 6 3, 033309 (2024).
[2] Jinzhao Sun, Pei Zeng, Tom Gur, and M. S. Kim, "High-precision and low-depth quantum algorithm design for eigenstate problems", Science Advances 12 3, eaeb1622 (2026).
[3] Zhi-Cheng He and Zheng-Yuan Xue, "High-fidelity initialization of a logical qubit with multiple injections", Physical Review A 111 5, 052419 (2025).
[4] Patrick Cook, Danny Jammooa, Morten Hjorth-Jensen, Daniel D. Lee, and Dean Lee, "Parametric matrix models", Nature Communications 16 1, 5929 (2025).
[5] Pegah Mohammadipour and Xiantao Li, "Direct Analysis of Zero-Noise Extrapolation: Polynomial Methods, Error Bounds, and Simultaneous Physical-Algorithmic Error Mitigation", Quantum 9, 1909 (2025).
[6] Gumaro Rendón, "Function extraction via Chebyshev interpolation of quantum integral estimates", Physical Review Research 8 2, 023095 (2026).
[7] Jakob Günther, Freek Witteveen, Alexander Schmidhuber, Marek Miller, Matthias Christandl, and Aram W. Harrow, "Phase Estimation with Partially Randomized Time Evolution", PRX Quantum 7 2, 020332 (2026).
[8] Jacob Watkins, Nathan Wiebe, Alessandro Roggero, and Dean Lee, "Time-Dependent Hamiltonian Simulation Using Discrete-Clock Constructions", PRX Quantum 5 4, 040316 (2024).
[9] Shah Ishmam Mohtashim, Manas Sajjan, and Sabre Kais, "Continuous-Time Quantum-Walk Centrality for Protein Residue Interaction Networks", Journal of the American Chemical Society 148 27, 29206 (2026).
[10] Tatsuhiko N. Ikeda, Hideki Kono, and Keisuke Fujii, "Measuring Trotter error and its application to precision-guaranteed Hamiltonian simulations", Physical Review Research 6 3, 033285 (2024).
[11] Hirad Alipanah, Feng Zhang, Yong-Xin Yao, Richard Thompson, Nam Nguyen, Junyu Liu, Peyman Givi, Brian J. McDermott, and Juan José Mendoza-Arenas, "Quantum dynamics simulation of the advection-diffusion equation", Physical Review Research 7 4, 043318 (2025).
[12] Guo Qiu Wang and Wei Liang, "Non-orthogonal interpolation on closed interval and convergence", Journal of Computational and Applied Mathematics 484, 117454 (2026).
[13] Pegah Mohammadipour and Xiantao Li, "Reducing circuit depth in Lindblad simulations via step-size extrapolation", Physical Review A 112 6, 062206 (2025).
[14] Kaoru Mizuta, "On the commutator scaling in Hamiltonian simulation with multi-product formulas", Quantum 10, 1974 (2026).
[15] Bence Bakó, Tenzan Araki, and Bálint Koczor, "Exponential Distillation of Dominant Eigenproperties", PRX Quantum 7 1, 010334 (2026).
[16] Shreyas Malpathak, Sangeeth Das Kallullathil, and Artur F. Izmaylov, "Simulating Vibrational Dynamics on Bosonic Quantum Devices", The Journal of Physical Chemistry Letters 16 8, 1855 (2025).
[17] Davide Cugini, Francesco Ghisoni, Angela Rosy Morgillo, and Francesco Scala, "Spectral gap estimation via adiabatic preparation", Physica Scripta 101 24, 245109 (2026).
[18] Pedro H. Alvarez, Farhan T. Chowdhury, Luke D. Smith, Trevor J. Brokowski, Clarice D. Aiello, Daniel R. Kattnig, and Marcos C. de Oliveira, "Simulating spin biology using a digital quantum computer: Prospects on a near-term quantum hardware emulator", APL Quantum 1 3, 036114 (2024).
[19] Hans Hon Sang Chan, Richard Meister, Matthew L. Goh, and Bálint Koczor, "Algorithmic Shadow Spectroscopy", PRX Quantum 6 1, 010352 (2025).
[20] James D. Watson and Jacob Watkins, "Exponentially Reduced Circuit Depths Using Trotter Error Mitigation", PRX Quantum 6 3, 030325 (2025).
[21] Niall F. Robertson, Bibek Pokharel, Bryce Fuller, Eric Switzer, Oles Shtanko, Mirko Amico, Adam Byrne, Andrea D'Urbano, Salome Hayes-Shuptar, Albert Akhriev, Nathan Keenan, Sergey Bravyi, and Sergiy Zhuk, "Tensor Network Enhanced Dynamic Multiproduct Formulas", PRX Quantum 6 2, 020360 (2025).
[22] Zhicheng Zhang, Qisheng Wang, and Mingsheng Ying, "Parallel Quantum Algorithm for Hamiltonian Simulation", Quantum 8, 1228 (2024).
[23] Shantanav Chakraborty, Soumyabrata Hazra, Tongyang Li, Changpeng Shao, Xinzhao Wang, and Yuxin Zhang, "Quantum singular value transformation without block encodings: Near-optimal complexity with minimal ancilla", arXiv:2504.02385, (2025).
[24] Gregory Boyd, "Low-Overhead Parallelisation of LCU via Commuting Operators", arXiv:2312.00696, (2023).
[25] Gumaro Rendon, "All you need is Trotter", arXiv:2311.01533, (2023).
[26] Sergiy Zhuk, Niall Robertson, and Sergey Bravyi, "Trotter error bounds and dynamic multi-product formulas for Hamiltonian simulation", arXiv:2306.12569, (2023).
[27] Yan Wang, Sarah Chehade, and Eugene Dumitrescu, "Semicoherent symmetric quantum processes: Theory and applications", AVS Quantum Science 6 3, 033805 (2024).
[28] Gumaro Rendon and Peter D. Johnson, "Low-depth Gaussian State Energy Estimation", arXiv:2309.16790, (2023).
[29] Dean Lee, "Quantum techniques for eigenvalue problems", European Physical Journal A 59 11, 275 (2023).
[30] Lea M. Trenkwalder, Eleanor Scerri, Thomas E. O'Brien, and Vedran Dunjko, "Compilation of product-formula Hamiltonian simulation via reinforcement learning", arXiv:2311.04285, (2023).
[31] Gumaro Rendon and Stepan Smid, "Preconditioned Multivariate Quantum Solution Extraction", arXiv:2601.05077, (2026).
[32] Chan Bin Bark, Sangjin Lee, Kwang Jun Ahn, Sangmo Cheon, Moon Jip Park, and Youngseok Kim, "Constant-Depth Multi-Product Formula for Trotter Error Mitigation in Near-Term Digital Quantum Simulation", arXiv:2607.12225, (2026).
The above citations are from Crossref's cited-by service (last updated successfully 2026-08-19 14:11:23) and SAO/NASA ADS (last updated successfully 2026-08-19 14:11:24). The list may be incomplete as not all publishers provide suitable and complete citation data.
This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions.