Sampling (noisy) quantum circuits through randomized rounding

Abstract

The present era of quantum processors with hundreds to thousands of noisy qubits has sparked interest in understanding the computational power of these devices and how to leverage it to solve practically relevant problems. For applications that require estimating expectation values of observables the community developed a good understanding of how to simulate them classically and denoise them. Certain applications, like combinatorial optimization, however demand more than expectation values: the bit-strings themselves encode the candidate solutions. While recent impossibility and threshold results indicate that noisy samples alone rarely beat classical heuristics, we still lack classical methods to replicate those noisy samples beyond the setting of random quantum circuits. Focusing on problems whose objective depends only on two-body correlations such as Max-Cut, we show that Gaussian randomized rounding in the spirit of Goemans-Williamson applied to the circuit's two-qubit marginals-produces a distribution whose expected cost is provably close to that of the noisy quantum device. For instance, for Max-Cut problems we show that for any depth-D circuit affected by local depolarizing noise p, our sampler achieves an approximation ratio $1-O[(1-p{)}^D]$, giving ways to efficiently sample from a distribution that behaves similarly to the noisy circuit for the problem at hand. Beyond theory we run large-scale simulations and experiments on IBMQ hardware, confirming that the rounded samples faithfully reproduce the full energy distribution, and we show similar behaviour under other various noise models. Our results supply a simple classical surrogate for sampling noisy optimization circuits, clarify the realistic power of near-term hardware for combinatorial tasks, and provide a quantitative benchmark for future error-mitigated or fault-tolerant demonstrations of quantum advantage.

35 pages, 6 figures

References in corpus (33)

• Supplementary information for "Quantum supremacy using a programmable superconducting processor"
• A variational eigenvalue solver on a quantum processor
• Ising formulations of many NP problems
• A Quantum Approximate Optimization Algorithm
• Error mitigation for short-depth quantum circuits
• Quantum Error Correction for Quantum Memories
• Quantum Error Mitigation
• Self-Verifying Variational Quantum Simulation of the Lattice Schwinger Model
• Variational ansatz-based quantum simulation of imaginary time evolution
• Quantum Approximate Optimization of Non-Planar Graph Problems on a Planar Superconducting Processor
• Algorithms for entanglement renormalization
• Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy
• Fundamental limits of quantum error mitigation
• The Quantum Wasserstein Distance of Order 1
• A polynomial-time classical algorithm for noisy random circuit sampling
• Quasiprobability decompositions with reduced sampling overhead
• Classical algorithms for quantum mean values
• Tight bounds on the convergence of noisy random circuits to the uniform distribution
• Classical simulation of short-time quantum dynamics
• Simulating large-size quantum spin chains on cloud-based superconducting quantum computers
• Classically estimating observables of noiseless quantum circuits
• Diagonalization of large many-body Hamiltonians on a quantum processor
• Benchmarking Quantum Processor Performance at Scale
• Provable bounds for noise-free expectation values computed from noisy samples
• Validating quantum-supremacy experiments with exact and fast tensor network contraction
• Classical surrogate simulation of quantum systems with LOWESA
• Efficient simulation of parametrized quantum circuits under non-unital noise through Pauli backpropagation
• Simulating quantum circuits with arbitrary local noise using Pauli Propagation
• Scalable Circuits for Preparing Ground States on Digital Quantum Computers: The Schwinger Model Vacuum on 100 Qubits
• Characterizing Physical Error Contributions of Quantum Gates
• On the Role of Entanglement and Statistics in Learning
• Polynomial-Time Classical Simulation of Noisy Quantum Circuits with Naturally Fault-Tolerant Gates
• Quantum Error Mitigation for Sampling Algorithms