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.
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.
Error mitigation has elevated quantum computing to the scale of hundreds of qubits and tens of layers; however, yet larger scales (deeper circuits) are needed to fully exploit the potential of quantum computing to solve practical problems otherwise intractable. Here we demonstrate three key results that pave the way for the leap from quantum utility to quantum advantage: (1) we present a thorough derivation of random and systematic errors associated to the most advanced error mitigation strategies, including probabilistic error cancellation (PEC), zero noise extrapolation (ZNE) with probabilistic error amplification, and tensor-network error mitigation (TEM); (2) we prove that TEM (i) has the lowest sampling overhead among all three techniques under realistic noise, (ii) is optimal, in the sense that it saturates the universal lower cost bound for error mitigation, and (iii) is therefore the most promising approach to quantum advantage; (3) we propose a concrete notion of practical quantum advantage in terms of the universality of algorithms, stemming from the commercial need for a problem-independent quantum simulation device. We also establish a connection between error mitigation, relying on additional measurements, and error correction, relying on additional qubits, by demonstrating that TEM with a sufficient bond dimension works similarly to an error correcting code of distance 3. We foresee that the interplay and trade-off between the two resources will be the key to a smooth transition between error mitigation and error correction, and hence between near-term and fault-tolerant quantum computers. Meanwhile, we argue that quantum computing with optimal error mitigation, relying on modest classical computer power for tensor network contraction, has the potential to reach larger scales in accurate simulation than classical methods alone.
Quantum simulation of dynamics is an important goal in the noisy intermediate-scale quantum era, within which quantum error mitigation may be a viable path towards modifying or eliminating the effects of noise. Most studies on quantum error mitigation have focused on the resource cost due to its exponential scaling in the circuit depth. Methods such as probabilistic error cancellation rely on discretizing the evolution into finite time steps and applying the mitigation layer after each time step, modifying only the noise part without any Hamiltonian dependence. This may lead to Trotter-like errors in the simulation results even if the error mitigation is implemented ideally, which means that the number of samples is taken as infinite. Here we analyze the aforementioned errors which have been largely neglected before. We show that they are determined by the commutating relations between the superoperators of the unitary part, the device noise part, and the noise part of the open dynamics to be simulated. We include both digital quantum simulation and analog quantum simulation setups and consider defining the ideal error mitigation map both by exactly inverting the noise channel and by approximating it to first order in the time step. We use single-qubit toy models to numerically demonstrate our findings. Our results illustrate fundamental limitations of applying probabilistic error cancellation in a stepwise manner to continuous dynamics, thus motivating the investigations of truly time-continuous error cancellation methods. Published by the American Physical Society 2024
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.
Quantum error mitigation (QEM) infers noiseless expectation values from noisy variants of a target quantum circuit. Unlike quantum error correction, QEM requires no additional hardware resources and is therefore routinely employed in experiments on contemporary quantum processors. QEM strategies based on agnostic noise amplification (ANA) are intrinsically resilient to temporal noise drift during the execution of the experiment, but their sampling cost (runtime overhead) remains a major practical bottleneck. In this work, we introduce the virtual noise scaling framework and combine it with layered mitigation to further enhance performance. While virtual noise scaling consistently reduces sampling overhead, we identify a specific noise threshold for the layered mitigation approach. When the noise level is above this threshold, layered mitigation decreases the sampling overhead; conversely, when below it, the overhead increases. Notably, this threshold is circuit-independent and depends solely on the number of layers. For strong noise, the combination of virtual noise scaling and layered mitigation yields several orders of magnitude reduction in sampling overhead compared with conventional zero-noise extrapolation post-processing. As a result, mitigation tasks that once seemed unrealistic are now challenging but achievable. The proposed approach is compatible with dynamic circuits and can be seamlessly integrated with error detection and quantum error correction schemes. In addition, it is also applicable to ANA-based mitigation of mid-circuit measurements and preparation errors. Our findings extend to any constant-step amplification factors and therefore also apply to probabilistic error amplification (PEA) QEM. We validate our post-processing approach by applying it to previously reported experimental data, where we observe a substantial improvement in mitigation efficiency and accuracy.
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.