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.09385 · Physical Review Letters

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

Kento Tsubouchi, Takahiro Sagawa, Nobuyuki Yoshioka

Published Nov 22, 2023• 53 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1103/physrevlett.131.210601

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 Sampling Lower Bounds for Quantum Error Mitigation

Ryuji Takagi, Hiroyasu Tajima, Mile Gu

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.

arXiv:2208.09178•Physical Review Letters•Nov 22, 2023•58 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

Unified multivariate trace estimation and quantum error mitigation

Jin‐Min Liang, Qiao-Qiao Lv, Zhi‐Xi Wang +1 more

Calculating the trace of the product of $m\phantom{\rule{4pt}{0ex}}n$-qubit density matrices (multivariate trace) is a crucial subroutine in quantum error mitigation and information measure estimation. We propose a unified multivariate trace estimation (UMT) which conceptually unifies the previous qubit-optimal and depth-optimal approaches with tunable quantum circuit depth and number of qubits. The constructed circuits have $\ensuremath{\lceil}(m\ensuremath{-}1)/s\ensuremath{\rceil}$ or $n\ensuremath{\lceil}(m\ensuremath{-}1)/s\ensuremath{\rceil}$ depth corresponding to $(s+m)n$ or $s+mn$ qubits for $s\ensuremath{\in}{1,\ensuremath{\cdots},\ensuremath{\lfloor}m/2\ensuremath{\rfloor}}$, respectively. Such flexible circuit structures enable people to choose suitable circuits for different hardware devices. We apply UMT to virtual distillation to achieve exponential error suppression and design a family of concrete circuits to calculate the trace of the product of eight and nine $n$-qubit density matrices. A numerical example shows that the additional circuits still mitigate the noise expectation value under the global depolarizing channel.

arXiv:2301.12358•Physical Review A•Jan 10, 2023•9 citations

Statistical Signal Processing for Quantum Error Mitigation

Kausthubh Chandramouli, Kelly Mae Allen, Christopher Mori +2 more

In the noisy intermediate-scale quantum (NISQ) era, quantum error mitigation (QEM) is essential for producing reliable outputs from quantum circuits. We present a statistical signal processing approach to QEM that estimates the most likely noiseless outputs from noisy quantum measurements. Our model assumes that circuit depth is sufficient for depolarizing noise, producing corrupted observations that resemble a uniform distribution alongside classical bit-flip errors from readout. Our method consists of two steps: a filtering stage that discards uninformative depolarizing noise and an expectation-maximization (EM) algorithm that computes a maximum likelihood (ML) estimate over the remaining data. We demonstrate the effectiveness of this approach on small-qubit systems using circuit simulations in Qiskit and IBM quantum processing unit (QPU) data, and compare its performance to contemporary statistical QEM techniques. We also show that our method scales to larger qubit counts using synthetically generated data consistent with our noise model. These results suggest that principled statistical methods can offer scalable and interpretable solutions for quantum error mitigation in realistic NISQ settings.

arXiv:2506.00683•IEEE International Conference on Quantum Computing and Engineering (QCE)•Aug 30, 2025•0 citations

Quantum Error Mitigation via Matrix Product Operators

Yuchen Guo, Shuo Yang

In the era of noisy intermediate-scale quantum devices, the number of controllable hardware qubits is insufficient to implement quantum error correction.As an alternative, quantum error mitigation (QEM) can suppress errors in measurement results via repeated experiments and postprocessing of data.Typical techniques for error mitigation, e.g., the quasiprobability decomposition method, ignore correlated errors between different gates.Here, we introduce a QEM method based on the matrix product operator (MPO) representation of a quantum circuit that can characterize the noise channel with polynomial complexity.Our technique is demonstrated on a depth = 20 fully parallel quantum circuit of up to N q = 20 qubits undergoing local and global noise.The circuit error is reduced by a several-times factor with only a small bond dimension D = 1 for the noise channel.The MPO representation increases the accuracy of modeling noise without consuming more experimental resources, which improves the QEM performance and broadens its scope of application.Our method is hopeful of being applied to circuits in higher dimensions with more qubits and deeper depth.

arXiv:2201.00752•PRX Quantum•Oct 31, 2022•45 citations
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.
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.
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.
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.
Calculating the trace of the product of mnm\phantom{\rule{4pt}{0ex}}nmn-qubit density matrices (multivariate trace) is a crucial subroutine in quantum error mitigation and information measure estimation. We propose a unified multivariate trace estimation (UMT) which conceptually unifies the previous qubit-optimal and depth-optimal approaches with tunable quantum circuit depth and number of qubits. The constructed circuits have $\ensuremath{\lceil}(m\ensuremath{-}1)/s\ensuremath{\rceil}$ or $n\ensuremath{\lceil}(m\ensuremath{-}1)/s\ensuremath{\rceil}$ depth corresponding to (s+m)n(s+m)n(s+m)n or s+mns+mns+mn qubits for $s\ensuremath{\in}{1,\ensuremath{\cdots},\ensuremath{\lfloor}m/2\ensuremath{\rfloor}}$, respectively. Such flexible circuit structures enable people to choose suitable circuits for different hardware devices. We apply UMT to virtual distillation to achieve exponential error suppression and design a family of concrete circuits to calculate the trace of the product of eight and nine nnn-qubit density matrices. A numerical example shows that the additional circuits still mitigate the noise expectation value under the global depolarizing channel.
In the noisy intermediate-scale quantum (NISQ) era, quantum error mitigation (QEM) is essential for producing reliable outputs from quantum circuits. We present a statistical signal processing approach to QEM that estimates the most likely noiseless outputs from noisy quantum measurements. Our model assumes that circuit depth is sufficient for depolarizing noise, producing corrupted observations that resemble a uniform distribution alongside classical bit-flip errors from readout. Our method consists of two steps: a filtering stage that discards uninformative depolarizing noise and an expectation-maximization (EM) algorithm that computes a maximum likelihood (ML) estimate over the remaining data. We demonstrate the effectiveness of this approach on small-qubit systems using circuit simulations in Qiskit and IBM quantum processing unit (QPU) data, and compare its performance to contemporary statistical QEM techniques. We also show that our method scales to larger qubit counts using synthetically generated data consistent with our noise model. These results suggest that principled statistical methods can offer scalable and interpretable solutions for quantum error mitigation in realistic NISQ settings.
In the era of noisy intermediate-scale quantum devices, the number of controllable hardware qubits is insufficient to implement quantum error correction.As an alternative, quantum error mitigation (QEM) can suppress errors in measurement results via repeated experiments and postprocessing of data.Typical techniques for error mitigation, e.g., the quasiprobability decomposition method, ignore correlated errors between different gates.Here, we introduce a QEM method based on the matrix product operator (MPO) representation of a quantum circuit that can characterize the noise channel with polynomial complexity.Our technique is demonstrated on a depth = 20 fully parallel quantum circuit of up to N q = 20 qubits undergoing local and global noise.The circuit error is reduced by a several-times factor with only a small bond dimension D = 1 for the noise channel.The MPO representation increases the accuracy of modeling noise without consuming more experimental resources, which improves the QEM performance and broadens its scope of application.Our method is hopeful of being applied to circuits in higher dimensions with more qubits and deeper depth.