quantum-computing

Direct Analysis of Zero-Noise Extrapolation: Polynomial Methods, Error Bounds, and Simultaneous Physical-Algorithmic Error Mitigation

Pegah Mohammadipour and Xiantao Li

15 min read

0 likes

⚡ Quantum Brief

Pegah Mohammadipour and Xiantao Li published a rigorous analysis of zero-noise extrapolation (ZNE), a key quantum error mitigation technique, revealing fundamental limitations in Richardson extrapolation’s polynomial interpolation approach. Their study quantifies bias and variance bounds for ZNE, exposing how non-polynomial noise behavior and measurement errors degrade accuracy, while providing sample complexity estimates for any target precision ε. The authors propose polynomial least squares extrapolation as a robust alternative, reducing overfitting and measurement noise amplification compared to traditional Richardson methods. A novel joint mitigation strategy scales both noise levels and Trotter-Suzuki time steps, simultaneously addressing physical circuit errors and algorithmic inaccuracies in Hamiltonian simulations. Numerical experiments validate the theoretical framework, offering practical tools to improve near-term quantum computation reliability on noisy intermediate-scale devices.

AI Audio Summary

0:00 / 0:00

Click to play

Unsplash · Validated Fallback

Understand this faster with AI

Ask ChatGPT

Research with Perplexity

Explain with Claude

Discuss on Grok

AbstractZero-noise extrapolation (ZNE) is a widely used quantum error mitigation technique that artificially amplifies circuit noise and then extrapolates the results to the noise-free circuit. A common ZNE approach is Richardson extrapolation, which relies on polynomial interpolation. Despite its simplicity, efficient implementations of Richardson extrapolation face several challenges, including approximation errors from the non-polynomial behavior of noise channels, overfitting due to polynomial interpolation, and exponentially amplified measurement noise. This paper provides a comprehensive analysis of these challenges, presenting bias and variance bounds that quantify approximation errors. Additionally, for any precision $\varepsilon$, our results offer an estimate of the necessary sample complexity. We further extend the analysis to polynomial least squares-based extrapolation, which mitigates measurement noise and avoids overfitting. Finally, we propose a strategy for simultaneously mitigating circuit and algorithmic errors in the Trotter-Suzuki algorithm by jointly scaling the time step size and the noise level. This strategy provides a practical tool to enhance the reliability of near-term quantum computations. We support our theoretical findings with numerical experiments.Popular summaryZero-noise extrapolation (ZNE) is a widely used quantum error mitigation technique that artificially amplifies circuit noise and then extrapolates the results to the noise-free circuit. A common ZNE approach is Richardson extrapolation, which relies on polynomial interpolation. Despite its simplicity, robust implementations of Richardson extrapolation face several challenges, including approximation errors from the non-polynomial behavior of noise channels, overfitting due to polynomial interpolation, and exponentially amplified measurement noise. This paper provides a comprehensive analysis of these challenges, quantifying the bias and statistical error arising from ZNE.► BibTeX data@article{Mohammadipour2025directanalysisof, doi = {10.22331/q-2025-11-14-1909}, url = {https://doi.org/10.22331/q-2025-11-14-1909}, title = {Direct {A}nalysis of {Z}ero-{N}oise {E}xtrapolation: {P}olynomial {M}ethods, {E}rror {B}ounds, and {S}imultaneous {P}hysical-{A}lgorithmic {E}rror {M}itigation}, author = {Mohammadipour, Pegah and Li, Xiantao}, journal = {{Quantum}}, issn = {2521-327X}, publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, volume = {9}, pages = {1909}, month = nov, year = {2025} }► References [1] John Preskill. ``Quantum computing in the nisq era and beyond''. Quantum 2, 79 (2018). https://doi.org/10.22331/q-2018-08-06-79 [2] Ying Li and Simon C Benjamin. ``Efficient variational quantum simulator incorporating active error minimization''. Physical Review X 7, 021050 (2017). https://doi.org/10.1103/PhysRevX.7.021050 [3] Kristan Temme, Sergey Bravyi, and Jay M Gambetta. ``Error mitigation for short-depth quantum circuits''. Physical review letters 119, 180509 (2017). https://doi.org/10.1103/PhysRevLett.119.180509 [4] Austin G Fowler, Matteo Mariantoni, John M Martinis, and Andrew N Cleland. ``Surface codes: Towards practical large-scale quantum computation''. Physical Review A—Atomic, Molecular, and Optical Physics 86, 032324 (2012). https://doi.org/10.1103/PhysRevA.86.032324 [5] Goran Lindblad. ``On the generators of quantum dynamical semigroups''. Communications in mathematical physics 48, 119–130 (1976). https://doi.org/10.1007/BF01608499 [6] Vittorio Gorini, Andrzej Kossakowski, and Ennackal Chandy George Sudarshan. ``Completely positive dynamical semigroups of n-level systems''. Journal of Mathematical Physics 17, 821–825 (1976). [7] Heinz-Peter Breuer and Francesco Petruccione. ``The theory of open quantum systems''. OUP Oxford. (2002). https://doi.org/10.1093/acprof:oso/9780199213900.001.0001 [8] Evan Borras and Milad Marvian. ``A quantum algorithm to simulate lindblad master equations''. arXiv preprint arXiv:2406.12748 (2024). https://doi.org/10.48550/arXiv.2406.12748 arXiv:2406.12748 [9] Suguru Endo, Simon C Benjamin, and Ying Li. ``Practical quantum error mitigation for near-future applications''. Physical Review X 8, 031027 (2018). https://doi.org/10.1103/PhysRevX.8.031027 [10] Suguru Endo, Qi Zhao, Ying Li, Simon Benjamin, and Xiao Yuan. ``Mitigating algorithmic errors in a hamiltonian simulation''. Phys. Rev. A 99, 012334 (2019). https://doi.org/10.1103/PhysRevA.99.012334 [11] Tomochika Kurita, Hammam Qassim, Masatoshi Ishii, Hirotaka Oshima, Shintaro Sato, and Joseph Emerson. ``Synergetic quantum error mitigation by randomized compiling and zero-noise extrapolation for the variational quantum eigensolver''. Quantum 7, 1184 (2023). https://doi.org/10.22331/q-2023-11-20-1184 [12] Almudena Carrera Vazquez, Ralf Hiptmair, and Stefan Woerner. ``Enhancing the quantum linear systems algorithm using richardson extrapolation''. ACM Transactions on Quantum Computing 3, 1–37 (2022). https://doi.org/10.48550/arXiv.2009.04484 [13] Almudena Carrera Vazquez. ``Extrapolation methods in quantum computing''. PhD thesis. ETH Zurich. (2022). https://doi.org/10.3929/ethz-b-000586831 [14] Trevor Hastie, Robert Tibshirani, Jerome H Friedman, and Jerome H Friedman. ``The elements of statistical learning: data mining, inference, and prediction''. Volume 2. Springer. (2009). https://doi.org/10.1007/978-0-387-84858-7 [15] Walter Gautschi and Gabriele Inglese. ``Lower bounds for the condition number of vandermonde matrices''. Numerische Mathematik 52, 241–250 (1987). https://doi.org/10.1007/BF01398878 [16] Ren-Cang Li. ``Lower bounds for the condition number of a real confluent vandermonde matrix''. Mathematics of computation 75, 1987–1995 (2006). https://doi.org/10.1090/S0025-5718-06-01856-4 [17] Tudor Giurgica-Tiron, Yousef Hindy, Ryan LaRose, Andrea Mari, and William J. Zeng. ``Digital zero noise extrapolation for quantum error mitigation''. In 2020 IEEE International Conference on Quantum Computing and Engineering (QCE). Pages 306–316. (2020). https://doi.org/10.1109/QCE49297.2020.00045 [18] Michael Krebsbach, Björn Trauzettel, and Alessio Calzona. ``Optimization of richardson extrapolation for quantum error mitigation''. Phys. Rev. A 106, 062436 (2022). https://doi.org/10.1103/PhysRevA.106.062436 [19] Lloyd N. Trefethen. ``Approximation theory and approximation practice, extended edition''. Society for Industrial and Applied Mathematics. Philadelphia, PA (2019). https://doi.org/10.1137/1.9781611975949 [20] Andrew M. Childs, Yuan Su, Minh C. Tran, Nathan Wiebe, and Shuchen Zhu. ``Theory of trotter error with commutator scaling''. Phys. Rev. X 11, 011020 (2021). https://doi.org/10.1103/PhysRevX.11.011020 [21] Gumaro Rendon, Jacob Watkins, and Nathan Wiebe. ``Improved accuracy for trotter simulations using chebyshev interpolation''. Quantum Journal 8, 1266 (2024). https://doi.org/10.22331/q-2024-02-26-1266 [22] James D. Watson and Jacob Watkins. ``Exponentially reduced circuit depths using trotter error mitigation''. PRX Quantum 6, 030325 (2025). https://doi.org/10.1103/kw39-yxq5 [23] Ryuji Takagi, Hiroyasu Tajima, and Mile Gu. ``Universal sampling lower bounds for quantum error mitigation''. Phys. Rev. Lett. 131, 210602 (2023). https://doi.org/10.1103/PhysRevLett.131.210602 [24] Ryuji Takagi, Suguru Endo, Shintaro Minagawa, and Mile Gu. ``Fundamental limits of quantum error mitigation''. npj Quantum Information 8, 114 (2022). https://doi.org/10.1038/s41534-022-00618-z [25] Yihui Quek, Daniel Stilck França, Khatri Sumeet, Johannes Jacob Meyer, and Jens Eisert. ``Exponentially tighter bounds on limitations of quantum error mitigation''. Nature Physics 20, 1648–1658 (2024). https://doi.org/10.1038/s41567-024-02536-7 [26] Ryan LaRose, Andrea Mari, Sarah Kaiser, Peter J Karalekas, Andre A Alves, Piotr Czarnik, Mohamed El Mandouh, Max H Gordon, Yousef Hindy, Aaron Robertson, et al. ``Mitiq: A software package for error mitigation on noisy quantum computers''. Quantum 6, 774 (2022). https://doi.org/10.22331/q-2022-08-11-774 [27] Lewis Fry Richardson. ``Ix. the approximate arithmetical solution by finite differences of physical problems involving differential equations, with an application to the stresses in a masonry dam''. Philosophical Transactions of the Royal Society of London. Series A, containing papers of a mathematical or physical character 210, 307–357 (1911). https://doi.org/10.1098/rsta.1911.0009 [28] Lewis Fry Richardson and J Arthur Gaunt. ``Viii. the deferred approach to the limit''. Philosophical Transactions of the Royal Society of London. Series A, containing papers of a mathematical or physical character 226, 299–361 (1927). https://doi.org/10.1098/rsta.1927.0008 [29] Avram Sidi. ``Practical extrapolation methods: Theory and applications''.

Cambridge University Press. (2003). https://doi.org/10.1017/CBO9780511546815 [30] Kendall Atkinson. ``An introduction to numerical analysis''. John wiley & sons. (1991). [31] Carl Runge. ``Über empirische funktionen und die interpolation zwischen äquidistanten ordinaten''. Zeitschrift für Mathematik und Physik, vol. 46, pp. 224–243 (1901). [32] Laurent Demanet and Alex Townsend. ``Stable extrapolation of analytic functions''. Foundation of Computational Mathematics 19, 297–331 (2016). https://doi.org/10.1007/s10208-018-9384-1 [33] Laurent Demanet and Lexing Ying. ``On chebyshev interpolation of analytic functions''. preprint (2010). url: https://math.mit.edu/icg/papers/cheb-interp.pdf. https://math.mit.edu/icg/papers/cheb-interp.pdf [34] Zhenyu Cai. ``Multi-exponential error extrapolation and combining error mitigation techniques for nisq applications''. npj Quantum Information 7, 80 (2021). https://doi.org/10.1038/s41534-021-00404-3 [35] J.C. Mason and D.C. Handscomb. ``Chebyshev polynomials (1st ed.)''. Chapman and Hall/CRC. (2002). https://doi.org/10.1201/9781420036114 [36] John P Boyd. ``Chebyshev and fourier spectral methods''. Courier Corporation. (2001). url: https://link.springer.com/book/9783540514879. https://link.springer.com/book/9783540514879 [37] Ernst Hairer, Marlis Hochbruck, Arieh Iserles, and Christian Lubich. ``Geometric numerical integration''. Oberwolfach Reports 3, 805–882 (2006). https://doi.org/10.14760/OWR-2006-14 [38] James D Watson. ``Randomly compiled quantum simulation with exponentially reduced circuit depths'' (2024). arXiv:2411.04240. arXiv:2411.04240 [39] Ali Javadi-Abhari, Matthew Treinish, Kevin Krsulich, Christopher J. Wood, Jake Lishman, Julien Gacon, Simon Martiel, Paul D. Nation, Lev S. Bishop, Andrew W. Cross, Blake R. Johnson, and Jay M. Gambetta. ``Quantum computing with qiskit'' (2024). arXiv:2405.08810. arXiv:2405.08810 [40] Shigeo Hakkaku, Yasunari Suzuki, Yuuki Tokunaga, and Suguru Endo. ``Data-efficient error mitigation for physical and algorithmic errors in a hamiltonian simulation'' (2025). arXiv:2503.05052. arXiv:2503.05052 [41] Abdolhossein Hoorfar and Mehdi Hassani. ``Inequalities on the lambert function and hyperpower function.''. JIPAM. Journal of Inequalities in Pure & Applied Mathematics [electronic only] 9, Paper No. 51, 5 p., electronic only–Paper No. 51, 5 p., electronic only (2008). [42] Neal L Carothers. ``A short course on approximation theory''.

Bowling Green State University, Bowling Green, OH 38 (1998). url: https://fourier.math.uoc.gr/ mk/approx1011/carothers.pdf. https://fourier.math.uoc.gr/~mk/approx1011/carothers.pdf [43] Wassily Hoeffding. ``Probability inequalities for sums of bounded random variables''. Journal of the American statistical association 58, 13–30 (1963). https://doi.org/10.2307/2282952Cited byCould not fetch Crossref cited-by data during last attempt 2025-11-14 13:03:03: Could not fetch cited-by data for 10.22331/q-2025-11-14-1909 from Crossref. This is normal if the DOI was registered recently. Could not fetch ADS cited-by data during last attempt 2025-11-14 13:03:03: No response from ADS or unable to decode the received json data when getting the list of citing works.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. AbstractZero-noise extrapolation (ZNE) is a widely used quantum error mitigation technique that artificially amplifies circuit noise and then extrapolates the results to the noise-free circuit. A common ZNE approach is Richardson extrapolation, which relies on polynomial interpolation. Despite its simplicity, efficient implementations of Richardson extrapolation face several challenges, including approximation errors from the non-polynomial behavior of noise channels, overfitting due to polynomial interpolation, and exponentially amplified measurement noise. This paper provides a comprehensive analysis of these challenges, presenting bias and variance bounds that quantify approximation errors. Additionally, for any precision $\varepsilon$, our results offer an estimate of the necessary sample complexity. We further extend the analysis to polynomial least squares-based extrapolation, which mitigates measurement noise and avoids overfitting. Finally, we propose a strategy for simultaneously mitigating circuit and algorithmic errors in the Trotter-Suzuki algorithm by jointly scaling the time step size and the noise level. This strategy provides a practical tool to enhance the reliability of near-term quantum computations. We support our theoretical findings with numerical experiments.Popular summaryZero-noise extrapolation (ZNE) is a widely used quantum error mitigation technique that artificially amplifies circuit noise and then extrapolates the results to the noise-free circuit. A common ZNE approach is Richardson extrapolation, which relies on polynomial interpolation. Despite its simplicity, robust implementations of Richardson extrapolation face several challenges, including approximation errors from the non-polynomial behavior of noise channels, overfitting due to polynomial interpolation, and exponentially amplified measurement noise. This paper provides a comprehensive analysis of these challenges, quantifying the bias and statistical error arising from ZNE.► BibTeX data@article{Mohammadipour2025directanalysisof, doi = {10.22331/q-2025-11-14-1909}, url = {https://doi.org/10.22331/q-2025-11-14-1909}, title = {Direct {A}nalysis of {Z}ero-{N}oise {E}xtrapolation: {P}olynomial {M}ethods, {E}rror {B}ounds, and {S}imultaneous {P}hysical-{A}lgorithmic {E}rror {M}itigation}, author = {Mohammadipour, Pegah and Li, Xiantao}, journal = {{Quantum}}, issn = {2521-327X}, publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, volume = {9}, pages = {1909}, month = nov, year = {2025} }► References [1] John Preskill. ``Quantum computing in the nisq era and beyond''. Quantum 2, 79 (2018). https://doi.org/10.22331/q-2018-08-06-79 [2] Ying Li and Simon C Benjamin. ``Efficient variational quantum simulator incorporating active error minimization''. Physical Review X 7, 021050 (2017). https://doi.org/10.1103/PhysRevX.7.021050 [3] Kristan Temme, Sergey Bravyi, and Jay M Gambetta. ``Error mitigation for short-depth quantum circuits''. Physical review letters 119, 180509 (2017). https://doi.org/10.1103/PhysRevLett.119.180509 [4] Austin G Fowler, Matteo Mariantoni, John M Martinis, and Andrew N Cleland. ``Surface codes: Towards practical large-scale quantum computation''. Physical Review A—Atomic, Molecular, and Optical Physics 86, 032324 (2012). https://doi.org/10.1103/PhysRevA.86.032324 [5] Goran Lindblad. ``On the generators of quantum dynamical semigroups''. Communications in mathematical physics 48, 119–130 (1976). https://doi.org/10.1007/BF01608499 [6] Vittorio Gorini, Andrzej Kossakowski, and Ennackal Chandy George Sudarshan. ``Completely positive dynamical semigroups of n-level systems''. Journal of Mathematical Physics 17, 821–825 (1976). [7] Heinz-Peter Breuer and Francesco Petruccione. ``The theory of open quantum systems''. OUP Oxford. (2002). https://doi.org/10.1093/acprof:oso/9780199213900.001.0001 [8] Evan Borras and Milad Marvian. ``A quantum algorithm to simulate lindblad master equations''. arXiv preprint arXiv:2406.12748 (2024). https://doi.org/10.48550/arXiv.2406.12748 arXiv:2406.12748 [9] Suguru Endo, Simon C Benjamin, and Ying Li. ``Practical quantum error mitigation for near-future applications''. Physical Review X 8, 031027 (2018). https://doi.org/10.1103/PhysRevX.8.031027 [10] Suguru Endo, Qi Zhao, Ying Li, Simon Benjamin, and Xiao Yuan. ``Mitigating algorithmic errors in a hamiltonian simulation''. Phys. Rev. A 99, 012334 (2019). https://doi.org/10.1103/PhysRevA.99.012334 [11] Tomochika Kurita, Hammam Qassim, Masatoshi Ishii, Hirotaka Oshima, Shintaro Sato, and Joseph Emerson. ``Synergetic quantum error mitigation by randomized compiling and zero-noise extrapolation for the variational quantum eigensolver''. Quantum 7, 1184 (2023). https://doi.org/10.22331/q-2023-11-20-1184 [12] Almudena Carrera Vazquez, Ralf Hiptmair, and Stefan Woerner. ``Enhancing the quantum linear systems algorithm using richardson extrapolation''. ACM Transactions on Quantum Computing 3, 1–37 (2022). https://doi.org/10.48550/arXiv.2009.04484 [13] Almudena Carrera Vazquez. ``Extrapolation methods in quantum computing''. PhD thesis. ETH Zurich. (2022). https://doi.org/10.3929/ethz-b-000586831 [14] Trevor Hastie, Robert Tibshirani, Jerome H Friedman, and Jerome H Friedman. ``The elements of statistical learning: data mining, inference, and prediction''. Volume 2. Springer. (2009). https://doi.org/10.1007/978-0-387-84858-7 [15] Walter Gautschi and Gabriele Inglese. ``Lower bounds for the condition number of vandermonde matrices''. Numerische Mathematik 52, 241–250 (1987). https://doi.org/10.1007/BF01398878 [16] Ren-Cang Li. ``Lower bounds for the condition number of a real confluent vandermonde matrix''. Mathematics of computation 75, 1987–1995 (2006). https://doi.org/10.1090/S0025-5718-06-01856-4 [17] Tudor Giurgica-Tiron, Yousef Hindy, Ryan LaRose, Andrea Mari, and William J. Zeng. ``Digital zero noise extrapolation for quantum error mitigation''. In 2020 IEEE International Conference on Quantum Computing and Engineering (QCE). Pages 306–316. (2020). https://doi.org/10.1109/QCE49297.2020.00045 [18] Michael Krebsbach, Björn Trauzettel, and Alessio Calzona. ``Optimization of richardson extrapolation for quantum error mitigation''. Phys. Rev. A 106, 062436 (2022). https://doi.org/10.1103/PhysRevA.106.062436 [19] Lloyd N. Trefethen. ``Approximation theory and approximation practice, extended edition''. Society for Industrial and Applied Mathematics. Philadelphia, PA (2019). https://doi.org/10.1137/1.9781611975949 [20] Andrew M. Childs, Yuan Su, Minh C. Tran, Nathan Wiebe, and Shuchen Zhu. ``Theory of trotter error with commutator scaling''. Phys. Rev. X 11, 011020 (2021). https://doi.org/10.1103/PhysRevX.11.011020 [21] Gumaro Rendon, Jacob Watkins, and Nathan Wiebe. ``Improved accuracy for trotter simulations using chebyshev interpolation''. Quantum Journal 8, 1266 (2024). https://doi.org/10.22331/q-2024-02-26-1266 [22] James D. Watson and Jacob Watkins. ``Exponentially reduced circuit depths using trotter error mitigation''. PRX Quantum 6, 030325 (2025). https://doi.org/10.1103/kw39-yxq5 [23] Ryuji Takagi, Hiroyasu Tajima, and Mile Gu. ``Universal sampling lower bounds for quantum error mitigation''. Phys. Rev. Lett. 131, 210602 (2023). https://doi.org/10.1103/PhysRevLett.131.210602 [24] Ryuji Takagi, Suguru Endo, Shintaro Minagawa, and Mile Gu. ``Fundamental limits of quantum error mitigation''. npj Quantum Information 8, 114 (2022). https://doi.org/10.1038/s41534-022-00618-z [25] Yihui Quek, Daniel Stilck França, Khatri Sumeet, Johannes Jacob Meyer, and Jens Eisert. ``Exponentially tighter bounds on limitations of quantum error mitigation''. Nature Physics 20, 1648–1658 (2024). https://doi.org/10.1038/s41567-024-02536-7 [26] Ryan LaRose, Andrea Mari, Sarah Kaiser, Peter J Karalekas, Andre A Alves, Piotr Czarnik, Mohamed El Mandouh, Max H Gordon, Yousef Hindy, Aaron Robertson, et al. ``Mitiq: A software package for error mitigation on noisy quantum computers''. Quantum 6, 774 (2022). https://doi.org/10.22331/q-2022-08-11-774 [27] Lewis Fry Richardson. ``Ix. the approximate arithmetical solution by finite differences of physical problems involving differential equations, with an application to the stresses in a masonry dam''. Philosophical Transactions of the Royal Society of London. Series A, containing papers of a mathematical or physical character 210, 307–357 (1911). https://doi.org/10.1098/rsta.1911.0009 [28] Lewis Fry Richardson and J Arthur Gaunt. ``Viii. the deferred approach to the limit''. Philosophical Transactions of the Royal Society of London. Series A, containing papers of a mathematical or physical character 226, 299–361 (1927). https://doi.org/10.1098/rsta.1927.0008 [29] Avram Sidi. ``Practical extrapolation methods: Theory and applications''.

Read Original

Source Information

Source: Quantum Science and Technology (arXiv overlay)

Website: https://quantum-journal.org/feed

Discussion

0 professional contributions

Be the first to add a constructive contribution.

Direct Analysis of Zero-Noise Extrapolation: Polynomial Methods, Error Bounds, and Simultaneous Physical-Algorithmic Error Mitigation

Tags

Source Information