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.

arXiv comment5+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 (59)

• Quantum Computing in the NISQ era and beyond
• Dynamical Decoupling of Open Quantum Systems
• Quantum computational chemistry
• Dynamical suppression of decoherence in two-state quantum systems
• General Benchmarks for Quantum Repeaters
• Fundamental Limits of Repeaterless Quantum Communications
• Error mitigation for short-depth quantum circuits
• Quantum Computers and Dissipation
• Noise-Induced Barren Plateaus in Variational Quantum Algorithms
• On quantum Renyi entropies: a new generalization and some properties
• The second laws of quantum thermodynamics
• Distance measures to compare real and ideal quantum processes
• Efficient variational quantum simulator incorporating active error minimisation
• Entanglement-Assisted Classical Capacity of Noisy Quantum Channels
• Maintaining coherence in Quantum Computers
• Practical Quantum Error Mitigation for Near-Future Applications
• Hybrid quantum-classical algorithms and quantum error mitigation
• Hybrid Quantum-Classical Hierarchy for Mitigation of Decoherence and Determination of Excited States
• Mitigating measurement errors in multi-qubit experiments
• Scalable mitigation of measurement errors on quantum computers
• Low-cost error mitigation by symmetry verification
• 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
• Quantum logarithmic Sobolev inequalities and rapid mixing
• Decoding quantum errors with subspace expansions
• The ${\chi }^2$-divergence and Mixing times of quantum Markov processes
• 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
• Continuity bounds on the quantum relative entropy
• 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
• Hilbert's projective metric in quantum information theory
• 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
• Uncertainty relations in implementation of unitary operations
• Relative Entropy Convergence for Depolarizing Channels
• 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
• Entropy Production of Doubly Stochastic Quantum Channels
• Simulating single photons with realistic photon sources
• Quantum conditional relative entropy and quasi-factorization of the relative entropy
• On the modified logarithmic Sobolev inequality for the heat-bath dynamics for 1D systems
• Quantum Error Mitigation Relying on Permutation Filtering
• Mitigating errors by quantum verification and post-selection
• Mitigating Quantum Errors via Truncated Neumann Series
• A Fundamental Upper Bound for Signal to Noise Ratio of Quantum Detectors

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