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 the 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. They also impact other near-term applications, 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.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 the 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. They also impact other near-term applications, 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.

arXiv:2210.11505Oct 20, 202210 citations

Quantum Techniques in Machine Learning (QTML conference 2023)

Yihui Quek

What can we quantum-learn in the age of noisy quantum computation? Both more and less than you think. Noise limits our ability to error-mitigate, a term that refers to near-term schemes where errors that arise in a quantum computation are dealt with in classical pre-processing. I present a unifying framework for error mitigation and an analysis that strongly limits the degree to which quantum noise can be effectively `undone' for larger system sizes, and shows that current error mitigation schemes are more or less as good as they can be. After presenting this negative result, I'll switch to discussing how noise can be a friendly foe: non-unital noise, unlike its unital counterparts, surprisingly results in absence of barren plateaus in quantum machine learning.What can we quantum-learn in the age of noisy quantum computation? Both more and less than you think. Noise limits our ability to error-mitigate, a term that refers to near-term schemes where errors that arise in a quantum computation are dealt with in classical pre-processing. I present a unifying framework for error mitigation and an analysis that strongly limits the degree to which quantum noise can be effectively `undone' for larger system sizes, and shows that current error mitigation schemes are more or less as good as they can be. After presenting this negative result, I'll switch to discussing how noise can be a friendly foe: non-unital noise, unlike its unital counterparts, surprisingly results in absence of barren plateaus in quantum machine learning.

Jan 1, 20230 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.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.11527Mar 13, 20260 citations

Noise-induced shallow circuits and the absence of barren plateaus

Antonio Anna Mele, Armando Angrisani, Soumik Ghosh +4 more

Without a successful implementation of fault-tolerant quantum error correction, calculations on quantum computers are subject to noise that limits their capabilities. Here, motivated by realistic near-term hardware considerations, we study the impact of uncorrected local noise on logical quantum circuits. We first show that, in the task of estimating observable expectation values, any noise effectively truncates most quantum circuits to logarithmic depth. We then prove that quantum circuits under any non-unital noise do not exhibit barren plateaus for cost functions composed of local observables. However, by using the effective shallowness, we also design an efficient classical algorithm to estimate observable expectation values within any constant additive accuracy, with high probability over the choice of the circuit, in any circuit architecture. Taken together, our results establish that, unless we carefully engineer quantum circuits to take advantage of the noise, noisy quantum circuits are unlikely to offer an advantage over shallow ones for algorithms that output observable expectation value estimates, such as many variational quantum machine learning proposals.Without a successful implementation of fault-tolerant quantum error correction, calculations on quantum computers are subject to noise that limits their capabilities. Here, motivated by realistic near-term hardware considerations, we study the impact of uncorrected local noise on logical quantum circuits. We first show that, in the task of estimating observable expectation values, any noise effectively truncates most quantum circuits to logarithmic depth. We then prove that quantum circuits under any non-unital noise do not exhibit barren plateaus for cost functions composed of local observables. However, by using the effective shallowness, we also design an efficient classical algorithm to estimate observable expectation values within any constant additive accuracy, with high probability over the choice of the circuit, in any circuit architecture. Taken together, our results establish that, unless we carefully engineer quantum circuits to take advantage of the noise, noisy quantum circuits are unlikely to offer an advantage over shallow ones for algorithms that output observable expectation value estimates, such as many variational quantum machine learning proposals.

arXiv:2403.13927Nature PhysicsApr 2, 202612 citations

Error Mitigation for Short-Depth Quantum Circuits

Kristan Temme, Sergey B. Bravyi, Jay Gambetta

Two schemes are presented that mitigate the effect of errors and decoherence in short-depth quantum circuits. The size of the circuits for which these techniques can be applied is limited by the rate at which the errors in the computation are introduced. Near-term applications of early quantum devices, such as quantum simulations, rely on accurate estimates of expectation values to become relevant. Decoherence and gate errors lead to wrong estimates of the expectation values of observables used to evaluate the noisy circuit. The two schemes we discuss are deliberately simple and do not require additional qubit resources, so to be as practically relevant in current experiments as possible. The first method, extrapolation to the zero noise limit, subsequently cancels powers of the noise perturbations by an application of Richardson's deferred approach to the limit. The second method cancels errors by resampling randomized circuits according to a quasiprobability distribution.Two schemes are presented that mitigate the effect of errors and decoherence in short-depth quantum circuits. The size of the circuits for which these techniques can be applied is limited by the rate at which the errors in the computation are introduced. Near-term applications of early quantum devices, such as quantum simulations, rely on accurate estimates of expectation values to become relevant. Decoherence and gate errors lead to wrong estimates of the expectation values of observables used to evaluate the noisy circuit. The two schemes we discuss are deliberately simple and do not require additional qubit resources, so to be as practically relevant in current experiments as possible. The first method, extrapolation to the zero noise limit, subsequently cancels powers of the noise perturbations by an application of Richardson's deferred approach to the limit. The second method cancels errors by resampling randomized circuits according to a quasiprobability distribution.

arXiv:1612.02058Physical Review LettersNov 3, 20171,379 citations

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.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.04457npj Quantum InformationSep 22, 2022161 citations

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.