Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2208.09178 · Physical Review Letters

Universal Sampling Lower Bounds for Quantum Error Mitigation

Ryuji Takagi, Hiroyasu Tajima, Mile Gu

Published Nov 22, 2023• 58 citations
arXivHTMLPDF

Abstract

Numerous quantum error-mitigation protocols have been proposed, motivated by the critical need to suppress noise effects on intermediate-scale quantum devices. Yet, their general potential and limitations remain elusive. In particular, to understand the ultimate feasibility of quantum error mitigation, it is crucial to characterize the fundamental sampling cost-how many times an arbitrary mitigation protocol must run a noisy quantum device. Here, we establish universal lower bounds on the sampling cost for quantum error mitigation to achieve the desired accuracy with high probability. Our bounds apply to general mitigation protocols, including the ones involving nonlinear postprocessing and those yet to be discovered. The results imply that the sampling cost required for a wide class of protocols to mitigate errors must grow exponentially with the circuit depth for various noise models, revealing the fundamental obstacles in the scalability of useful noisy near-term quantum devices.

DOI
10.1103/physrevlett.131.210602

Related papers

Fundamental limits of quantum error mitigation

Ryuji Takagi, Suguru Endo, Shintaro Minagawa +1 more

Abstract The inevitable accumulation of errors in near-future quantum devices represents a key obstacle in delivering practical quantum advantages, motivating the development of various quantum error-mitigation methods. Here, we derive fundamental bounds concerning how error-mitigation algorithms can reduce the computation error as a function of their sampling overhead. Our bounds place universal performance limits on a general error-mitigation protocol class. We use them to show (1) that the sampling overhead that ensures a certain computational accuracy for mitigating local depolarizing noise in layered circuits scales exponentially with the circuit depth for general error-mitigation protocols and (2) the optimality of probabilistic error cancellation among a wide class of strategies in mitigating the local dephasing noise on an arbitrary number of qubits. Our results provide a means to identify when a given quantum error-mitigation strategy is optimal and when there is potential room for improvement.

arXiv:2109.04457•npj Quantum Information•Sep 22, 2022•161 citations

Universal Cost Bound of Quantum Error Mitigation Based on Quantum Estimation Theory

Kento Tsubouchi, Takahiro Sagawa, Nobuyuki Yoshioka

We present a unified approach to analyzing the cost of various quantum error mitigation methods on the basis of quantum estimation theory. By analyzing the quantum Fisher information matrix of a virtual quantum circuit that effectively represents the operations of quantum error mitigation methods, we derive for a generic layered quantum circuit under a wide class of Markovian noise that, unbiased estimation of an observable encounters an exponential growth with the circuit depth in the lower bound on the measurement cost. Under the global depolarizing noise, we in particular find that the bound can be asymptotically saturated by merely rescaling the measurement results. Moreover, we prove for random circuits with local noise that the cost grows exponentially also with the qubit count. Our numerical simulations support the observation that, even if the circuit has only linear connectivity, such as the brick-wall structure, each noise channel converges to the global depolarizing channel with its strength growing exponentially with the qubit count. This not only implies the exponential growth of cost both with the depth and qubit count, but also validates the rescaling technique for sufficiently deep quantum circuits. Our results contribute to the understanding of the physical limitations of quantum error mitigation and offer a new criterion for evaluating the performance of quantum error mitigation techniques.

arXiv:2208.09385•Physical Review Letters•Nov 22, 2023•53 citations

Error-Mitigated Hamiltonian Simulation: Complexity Analysis and Optimization for Near-Term and Early-Fault-Tolerant Quantum Computers

Keisuke Murota, Synge Todo, Suguru Endo

Simulating real-time dynamics under a Hamiltonian is a central goal of quantum information science. While numerous Hamiltonian-simulation quantum algorithms have been proposed, the effects of physical noise have rarely been incorporated into their performance analysis, despite the non-negligible noise levels of quantum devices. We present an end-to-end complexity analysis of noisy Hamiltonian simulation combined with quantum error mitigation (QEM) to answer how many circuit runs are required to reach a given target accuracy. Because the QEM sampling overhead grows exponentially with the circuit depth while the algorithmic error decreases with it, the circuit depth becomes an optimization variable, and we derive an analytic depth-selection rule for two algorithm families. For the order-$k$ Suzuki--Trotter formula, the optimized cost exhibits a critical error $ε_c$, below which the required number of circuit runs grows exponentially. QEM improves the noise dependence of $ε_c$ from sublinear to $k$th-power scaling, an exponent improvement by a factor of $k+1$. For randomized-LCU-based simulation, optimizing the repetition number yields a square-root improvement in the simulation-time dependence of the sampling-overhead exponent over the standard parameter choice. We further quantify the noise-characterization cost required for error mitigation via gate set tomography and the recently proposed space-time noise inversion method, showing that the latter can significantly reduce this cost.

quant-pharXiv:2603.11527•Mar 13, 2026•0 citations

Optimal resource cost for error mitigation

Ryuji Takagi

One of the central problems for near-term quantum devices is to understand their ultimate potential and limitations. We address this problem in terms of quantum error mitigation by introducing a framework taking into account the full expressibility of near-term devices, in which the optimal resource cost for the probabilistic error cancellation method can be formalized. We provide a general methodology for evaluating the optimal cost by connecting it to a resource-theoretic quantifier defined with respect to the noisy operations that devices can implement. We employ our methods to estimate the optimal cost in mitigating a general class of noise, where we obtain an achievable cost that has a generic advantage over previous evaluations, as well as a fundamental lower bound applicable to a broad class of noisy implementable operations. We improve our bounds for several noise models, where we give the exact optimal costs for the depolarizing and dephasing noise, precisely characterizing the overhead cost while offering an operational meaning to the resource measure in terms of error mitigation. Our result particularly implies that the heuristic approach presented by Temme et al. [K. Temme, S. Bravyi, and J. M. Gambetta, Phys. Rev. Lett. 119, 180509 (2017)] is optimal even in our extended framework, putting fundamental limitations on the advantage provided by the extra degrees of freedom inherent in near-term devices for this noise model.

arXiv:2006.12509•Physical Review Research•Aug 20, 2021•61 citations

Sample-efficient quantum error mitigation via classical learning surrogates

Wei-You Liao, Ge Yan, Yujin Song +5 more

The pursuit of practical quantum utility on near-term quantum processors is critically challenged by their inherent noise. Quantum error mitigation (QEM) techniques are leading solutions to improve computation fidelity with relatively low qubit-overhead, while full-scale quantum error correction remains a distant goal. However, QEM techniques incur substantial measurement overheads, especially when applied to families of quantum circuits parameterized by classical inputs. Focusing on zero-noise extrapolation (ZNE), a widely adopted QEM technique, here we devise the surrogate-enabled ZNE (S-ZNE), which leverages classical learning surrogates to perform ZNE entirely on the classical side. Unlike conventional ZNE, whose measurement cost scales linearly with the number of circuits, S-ZNE requires only constant measurement overhead for an entire family of quantum circuits, offering superior scalability. Theoretical analysis indicates that S-ZNE achieves accuracy comparable to conventional ZNE in many practical scenarios, and numerical experiments on up to 100-qubit ground-state energy and quantum metrology tasks confirm its effectiveness. Our approach provides a template that can be effectively extended to other quantum error mitigation protocols, opening a promising path toward scalable error mitigation.

quant-pharXiv:2511.07092•Communications Physics•Nov 11, 2025•1 citation

Exponentially tighter bounds on limitations of quantum error mitigation

Yihui Quek, Daniel Stilck França, Sumeet Khatri +2 more

Quantum error mitigation has been proposed as a means to combat unwanted and unavoidable errors in near-term quantum computing without the heavy resource overheads required by fault-tolerant schemes. Recently, error mitigation has been successfully applied to reduce noise in near-term applications. In this work, however, we identify strong limitations to the degree to which quantum noise can be effectively 'undone' for larger system sizes. Our framework rigorously captures large classes of error-mitigation schemes in use today. By relating error mitigation to a statistical inference problem, we show that even at shallow circuit depths comparable to those of current experiments, a superpolynomial number of samples is needed in the worst case to estimate the expectation values of noiseless observables, the principal task of error mitigation. Notably, our construction implies that scrambling due to noise can kick in at exponentially smaller depths than previously thought. Noise also impacts other near-term applications by constraining kernel estimation in quantum machine learning, causing an earlier emergence of noise-induced barren plateaus in variational quantum algorithms and ruling out exponential quantum speed-ups in estimating expectation values in the presence of noise or preparing the ground state of a Hamiltonian.

Nature Physics•Jul 25, 2024•91 citations
Numerous quantum error-mitigation protocols have been proposed, motivated by the critical need to suppress noise effects on intermediate-scale quantum devices. Yet, their general potential and limitations remain elusive. In particular, to understand the ultimate feasibility of quantum error mitigation, it is crucial to characterize the fundamental sampling cost-how many times an arbitrary mitigation protocol must run a noisy quantum device. Here, we establish universal lower bounds on the sampling cost for quantum error mitigation to achieve the desired accuracy with high probability. Our bounds apply to general mitigation protocols, including the ones involving nonlinear postprocessing and those yet to be discovered. The results imply that the sampling cost required for a wide class of protocols to mitigate errors must grow exponentially with the circuit depth for various noise models, revealing the fundamental obstacles in the scalability of useful noisy near-term quantum devices.
Abstract The inevitable accumulation of errors in near-future quantum devices represents a key obstacle in delivering practical quantum advantages, motivating the development of various quantum error-mitigation methods. Here, we derive fundamental bounds concerning how error-mitigation algorithms can reduce the computation error as a function of their sampling overhead. Our bounds place universal performance limits on a general error-mitigation protocol class. We use them to show (1) that the sampling overhead that ensures a certain computational accuracy for mitigating local depolarizing noise in layered circuits scales exponentially with the circuit depth for general error-mitigation protocols and (2) the optimality of probabilistic error cancellation among a wide class of strategies in mitigating the local dephasing noise on an arbitrary number of qubits. Our results provide a means to identify when a given quantum error-mitigation strategy is optimal and when there is potential room for improvement.
We present a unified approach to analyzing the cost of various quantum error mitigation methods on the basis of quantum estimation theory. By analyzing the quantum Fisher information matrix of a virtual quantum circuit that effectively represents the operations of quantum error mitigation methods, we derive for a generic layered quantum circuit under a wide class of Markovian noise that, unbiased estimation of an observable encounters an exponential growth with the circuit depth in the lower bound on the measurement cost. Under the global depolarizing noise, we in particular find that the bound can be asymptotically saturated by merely rescaling the measurement results. Moreover, we prove for random circuits with local noise that the cost grows exponentially also with the qubit count. Our numerical simulations support the observation that, even if the circuit has only linear connectivity, such as the brick-wall structure, each noise channel converges to the global depolarizing channel with its strength growing exponentially with the qubit count. This not only implies the exponential growth of cost both with the depth and qubit count, but also validates the rescaling technique for sufficiently deep quantum circuits. Our results contribute to the understanding of the physical limitations of quantum error mitigation and offer a new criterion for evaluating the performance of quantum error mitigation techniques.
Simulating real-time dynamics under a Hamiltonian is a central goal of quantum information science. While numerous Hamiltonian-simulation quantum algorithms have been proposed, the effects of physical noise have rarely been incorporated into their performance analysis, despite the non-negligible noise levels of quantum devices. We present an end-to-end complexity analysis of noisy Hamiltonian simulation combined with quantum error mitigation (QEM) to answer how many circuit runs are required to reach a given target accuracy. Because the QEM sampling overhead grows exponentially with the circuit depth while the algorithmic error decreases with it, the circuit depth becomes an optimization variable, and we derive an analytic depth-selection rule for two algorithm families. For the order-kkk Suzuki--Trotter formula, the optimized cost exhibits a critical error εcε_cεc​, below which the required number of circuit runs grows exponentially. QEM improves the noise dependence of εcε_cεc​ from sublinear to kkkth-power scaling, an exponent improvement by a factor of k+1k+1k+1. For randomized-LCU-based simulation, optimizing the repetition number yields a square-root improvement in the simulation-time dependence of the sampling-overhead exponent over the standard parameter choice. We further quantify the noise-characterization cost required for error mitigation via gate set tomography and the recently proposed space-time noise inversion method, showing that the latter can significantly reduce this cost.
One of the central problems for near-term quantum devices is to understand their ultimate potential and limitations. We address this problem in terms of quantum error mitigation by introducing a framework taking into account the full expressibility of near-term devices, in which the optimal resource cost for the probabilistic error cancellation method can be formalized. We provide a general methodology for evaluating the optimal cost by connecting it to a resource-theoretic quantifier defined with respect to the noisy operations that devices can implement. We employ our methods to estimate the optimal cost in mitigating a general class of noise, where we obtain an achievable cost that has a generic advantage over previous evaluations, as well as a fundamental lower bound applicable to a broad class of noisy implementable operations. We improve our bounds for several noise models, where we give the exact optimal costs for the depolarizing and dephasing noise, precisely characterizing the overhead cost while offering an operational meaning to the resource measure in terms of error mitigation. Our result particularly implies that the heuristic approach presented by Temme et al. [K. Temme, S. Bravyi, and J. M. Gambetta, Phys. Rev. Lett. 119, 180509 (2017)] is optimal even in our extended framework, putting fundamental limitations on the advantage provided by the extra degrees of freedom inherent in near-term devices for this noise model.
The pursuit of practical quantum utility on near-term quantum processors is critically challenged by their inherent noise. Quantum error mitigation (QEM) techniques are leading solutions to improve computation fidelity with relatively low qubit-overhead, while full-scale quantum error correction remains a distant goal. However, QEM techniques incur substantial measurement overheads, especially when applied to families of quantum circuits parameterized by classical inputs. Focusing on zero-noise extrapolation (ZNE), a widely adopted QEM technique, here we devise the surrogate-enabled ZNE (S-ZNE), which leverages classical learning surrogates to perform ZNE entirely on the classical side. Unlike conventional ZNE, whose measurement cost scales linearly with the number of circuits, S-ZNE requires only constant measurement overhead for an entire family of quantum circuits, offering superior scalability. Theoretical analysis indicates that S-ZNE achieves accuracy comparable to conventional ZNE in many practical scenarios, and numerical experiments on up to 100-qubit ground-state energy and quantum metrology tasks confirm its effectiveness. Our approach provides a template that can be effectively extended to other quantum error mitigation protocols, opening a promising path toward scalable error mitigation.
Quantum error mitigation has been proposed as a means to combat unwanted and unavoidable errors in near-term quantum computing without the heavy resource overheads required by fault-tolerant schemes. Recently, error mitigation has been successfully applied to reduce noise in near-term applications. In this work, however, we identify strong limitations to the degree to which quantum noise can be effectively 'undone' for larger system sizes. Our framework rigorously captures large classes of error-mitigation schemes in use today. By relating error mitigation to a statistical inference problem, we show that even at shallow circuit depths comparable to those of current experiments, a superpolynomial number of samples is needed in the worst case to estimate the expectation values of noiseless observables, the principal task of error mitigation. Notably, our construction implies that scrambling due to noise can kick in at exponentially smaller depths than previously thought. Noise also impacts other near-term applications by constraining kernel estimation in quantum machine learning, causing an earlier emergence of noise-induced barren plateaus in variational quantum algorithms and ruling out exponential quantum speed-ups in estimating expectation values in the presence of noise or preparing the ground state of a Hamiltonian.