Universal Sampling Lower Bounds for Quantum Error Mitigation

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.

5+15 pages, 4 figures, published version; See also a related work by Tsubouchi et al., which appeared in the same arXiv posting as arXiv:2208.09385

References in corpus (31)

• Noise-Induced Barren Plateaus in Variational Quantum Algorithms
• Hybrid quantum-classical algorithms and quantum error mitigation
• Mitigating measurement errors in multi-qubit experiments
• Scalable mitigation of measurement errors on quantum computers
• Learning-based quantum error mitigation
• Virtual Distillation for Quantum Error Mitigation
• Fundamental limits of quantum error mitigation
• Exponential Error Suppression for Near-Term Quantum Devices
• Mitigating realistic noise in practical noisy intermediate-scale quantum devices
• The Quantum Wasserstein Distance of Order 1
• Unified approach to data-driven quantum error mitigation
• Generalized quantum subspace expansion
• Multi-exponential Error Extrapolation and Combining Error Mitigation Techniques for NISQ Applications
• Error mitigation via verified phase estimation
• Extending quantum probabilistic error cancellation by noise scaling
• Quasiprobability decompositions with reduced sampling overhead
• Optimal resource cost for error mitigation
• Quantum Error Mitigation using Symmetry Expansion
• Fundamental limitations on distillation of quantum channel resources
• Dual-state purification for practical quantum error mitigation
• Universal cost bound of quantum error mitigation based on quantum estimation theory
• Hypercontractivity of quasi-free quantum semigroups
• Physical Implementability of Linear Maps and Its Application in Error Mitigation
• No-go theorems for quantum resource purification II: new approach and channel theory
• Unifying and benchmarking state-of-the-art quantum error mitigation techniques
• Operational applications of the diamond norm and related measures in quantifying the non-physicality of quantum maps
• On contraction coefficients, partial orders and approximation of capacities for quantum channels
• Simulating single photons with realistic photon sources
• Quantum Error Mitigation Relying on Permutation Filtering
• Mitigating errors by quantum verification and post-selection
• Mitigating Quantum Errors via Truncated Neumann Series

Cited by in corpus (35)

• Quantum Error Mitigation
• Barren Plateaus in Variational Quantum Computing
• Machine Learning for Practical Quantum Error Mitigation
• Universal cost bound of quantum error mitigation based on quantum estimation theory
• Quantum-Selected Configuration Interaction: classical diagonalization of Hamiltonians in subspaces selected by quantum computers
• Group-theoretic error mitigation enabled by classical shadows and symmetries
• Volumetric Benchmarking of Error Mitigation with Qermit
• Limits of noisy quantum metrology with restricted quantum controls
• Quantum error cancellation in photonic systems -- undoing photon losses
• Symmetric Clifford twirling for cost-optimal quantum error mitigation in early FTQC regime
• Demonstrating quantum error mitigation on logical qubits
• Quantum Dynamic Programming
• Synergy between noisy quantum computers and scalable classical deep learning
• Multireference error mitigation for quantum computation of chemistry
• Error mitigation and circuit division for early fault-tolerant quantum phase estimation
• Quantum error mitigation for rotation symmetric bosonic codes with symmetry expansion
• Resource-efficient Generalized Quantum Subspace Expansion
• Readout Error Mitigation for Mid-Circuit Measurements and Feedforward
• Limitations of Noisy Quantum Devices in Computational and Entangling Power
• Adaptive measurement strategy for quantum subspace methods
• Error Mitigation Thresholds in Noisy Random Quantum Circuits
• Density matrix representation of hybrid tensor networks for noisy quantum devices
• Error Crafting in Mixed Quantum Gate Synthesis
• Mitigating Errors in Analog Quantum Simulation by Hamiltonian Reshaping or Hamiltonian Rescaling
• Shot-noise reduction for lattice Hamiltonians
• Estimates of loss function concentration in noisy parametrized quantum circuits
• Error Mitigation of BQP Computations using Measurement-Based Verification
• Direct Analysis of Zero-Noise Extrapolation: Polynomial Methods, Error Bounds, and Simultaneous Physical-Algorithmic Error Mitigation
• Symmetric channel verification for purifying noisy quantum channels
• Mitigating photon loss in linear optical quantum circuits
• Protocol for Purifying Noisy Preparation and Measurements of Qubits
• BBGKY hierarchy for quantum error mitigation
• Robust Error Accumulation Suppression for Quantum Circuits
• Optimal randomized measurements for a family of non-linear quantum properties
• Critical Scaling of the Quantum Wasserstein Distance