Exponentially tighter bounds on limitations of quantum error mitigation

Abstract

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 comment15+23 pages, 4 figures, replaced with final version

References in corpus (29)

• Variational Quantum Algorithms
• The theory of variational hybrid quantum-classical algorithms
• A Quantum Approximate Optimization Algorithm
• Noisy intermediate-scale quantum (NISQ) algorithms
• Error mitigation for short-depth quantum circuits
• Stabilizer Codes and Quantum Error Correction
• Exact and Approximate Unitary 2-Designs: Constructions and Applications
• Quantum Error Mitigation
• Roads towards fault-tolerant universal quantum computation
• Obstacles to State Preparation and Variational Optimization from Symmetry Protection
• Probabilistic error cancellation with sparse Pauli-Lindblad models on noisy quantum processors
• Efficient Distributed Quantum Computing
• Fundamental limits of quantum error mitigation
• An Introduction to Quantum Error Correction and Fault-Tolerant Quantum Computation
• On the quantum Renyi relative entropies and related capacity formulas
• Multi-exponential Error Extrapolation and Combining Error Mitigation Techniques for NISQ Applications
• Quasiprobability decompositions with reduced sampling overhead
• Simulation of Qubit Quantum Circuits via Pauli Propagation
• The Quantum Approximate Optimization Algorithm Needs to See the Whole Graph: Worst Case Examples
• Universal cost bound of quantum error mitigation based on quantum estimation theory
• NLTS Hamiltonians from good quantum codes
• Tight bounds on the convergence of noisy random circuits to the uniform distribution
• Error propagation in NISQ devices for solving classical optimization problems
• A single $T$-gate makes distribution learning hard
• On contraction coefficients, partial orders and approximation of capacities for quantum channels
• Quantum statistical query learning
• Efficient classical simulation and benchmarking of quantum processes in the Weyl basis
• Exponential concentration in quantum kernel methods
• Statistical Queries and Statistical Algorithms: Foundations and Applications

Cited by in corpus (5)

• Conserved charges in the quantum simulation of integrable spin chains
• Emergence of noise-induced barren plateaus in arbitrary layered noise models
• Virtual quantum error detection
• Wavefunction branching: when you can't tell pure states from mixed states
• Shor-Laflamme distributions of graph states and noise robustness of entanglement