Provable bounds for noise-free expectation values computed from noisy samples

Abstract

In this paper, we explore the impact of noise on quantum computing, particularly focusing on the challenges when sampling bit strings from noisy quantum computers as well as the implications for optimization and machine learning applications. We formally quantify the sampling overhead to extract good samples from noisy quantum computers and relate it to the layer fidelity, a metric to determine the performance of noisy quantum processors. Further, we show how this allows us to use the Conditional Value at Risk of noisy samples to determine provable bounds on noise-free expectation values. We discuss how to leverage these bounds for different algorithms and demonstrate our findings through experiments on a real quantum computer involving up to 127 qubits. The results show a strong alignment with theoretical predictions.

arXiv commentPages 17, Figures 6, Tables 3

References in corpus (48)

• A variational eigenvalue solver on a quantum processor
• Ising formulations of many NP problems
• Supervised learning with quantum enhanced feature spaces
• A Quantum Approximate Optimization Algorithm
• Error mitigation for short-depth quantum circuits
• Randomized Benchmarking of Quantum Gates
• From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz
• Robust randomized benchmarking of quantum processes
• Exact and Approximate Unitary 2-Designs: Constructions and Applications
• Variational ansatz-based quantum simulation of imaginary time evolution
• A rigorous and robust quantum speed-up in supervised machine learning
• Procedure for systematically tuning up crosstalk in the cross resonance gate
• Quantum Generative Adversarial Networks for Learning and Loading Random Distributions
• Theory of variational quantum simulation
• Quantum Computing for Finance: State of the Art and Future Prospects
• The Future of Quantum Computing with Superconducting Qubits
• Obstacles to State Preparation and Variational Optimization from Symmetry Protection
• Probabilistic error cancellation with sparse Pauli-Lindblad models on noisy quantum processors
• Warm-starting quantum optimization
• Low-cost error mitigation by symmetry verification
• Improving Variational Quantum Optimization using CVaR
• Quantum Computing for High-Energy Physics: State of the Art and Challenges. Summary of the QC4HEP Working Group
• Quantum computing with Qiskit
• $XY$-mixers: analytical and numerical results for QAOA
• Model-free readout-error mitigation for quantum expectation values
• Quantum annealing initialization of the quantum approximate optimization algorithm
• Grover Mixers for QAOA: Shifting Complexity from Mixer Design to State Preparation
• Scaling of the quantum approximate optimization algorithm on superconducting qubit based hardware
• MAXCUT QAOA performance guarantees for p >1
• Variational Quantum Boltzmann Machines
• Quantum-optimal-control-inspired ansatz for variational quantum algorithms
• Minimizing State Preparations in Variational Quantum Eigensolver by Partitioning into Commuting Families
• Quasiprobability decompositions with reduced sampling overhead
• The complexity of quantum support vector machines
• The Quantum Alternating Operator Ansatz on Maximum k-Vertex Cover
• Quantum Annealing vs. QAOA: 127 Qubit Higher-Order Ising Problems on NISQ Computers
• Short-Depth Circuits for Dicke State Preparation
• Expectation Values from the Single-Layer Quantum Approximate Optimization Algorithm on Ising Problems
• Large-scale quantum approximate optimization on non-planar graphs with machine learning noise mitigation
• Variational Quantum Time Evolution without the Quantum Geometric Tensor
• Error Bounds for Variational Quantum Time Evolution
• Tight and Efficient Gradient Bounds for Parameterized Quantum Circuits
• Numerical Evidence for Exponential Speed-up of QAOA over Unstructured Search for Approximate Constrained Optimization
• Benchmarking Quantum Processor Performance at Scale
• Quantum Kernel Alignment with Stochastic Gradient Descent
• Integrated error-suppressed pipeline for quantum optimization of nontrivial binary combinatorial optimization problems on gate-model hardware at the 156-qubit scale
• Classical benchmarking of zero noise extrapolation beyond the exactly-verifiable regime
• Stochastic Approximation of Variational Quantum Imaginary Time Evolution

Cited by in corpus (10)

• Challenges and Opportunities in Quantum Optimization
• Quantum Approximate Multi-Objective Optimization
• Bias-Field Digitized Counterdiabatic Quantum Algorithm for Higher-Order Binary Optimization
• Multi-Objective Optimization and Network Routing with Near-Term Quantum Computers
• Mitigating exponential concentration in covariant quantum kernels for subspace and real-world data
• Efficient Online Quantum Circuit Learning with No Upfront Training
• Approximate Quadratization of High-Order Hamiltonians for Combinatorial Quantum Optimization
• Digital Zero-Noise Extrapolation with Quantum Circuit Unoptimization
• Evaluating the Limits of QAOA Parameter Transfer at High-Rounds on Sparse Ising Models With Geometrically Local Cubic Terms
• Sampling (noisy) quantum circuits through randomized rounding