Noise and the frontier of quantum supremacy

Abstract

Noise is the defining feature of the NISQ era, but it remains unclear if noisy quantum devices are capable of quantum speedups. Quantum supremacy experiments have been a major step forward, but gaps remain between the theory behind these experiments and their actual implementations. In this work we initiate the study of the complexity of quantum random circuit sampling experiments with realistic amounts of noise. Actual quantum supremacy experiments have high levels of uncorrected noise and exponentially decaying fidelities. It is natural to ask if there is any signal of exponential complexity in these highly noisy devices. Surprisingly, we show that it remains hard to compute the output probabilities of noisy random quantum circuits without error correction. More formally, so long as the noise rate of the device is below the error detection threshold, we show it is #P-hard to compute the output probabilities of random circuits with a constant rate of noise per gate. This hardness persists even though these probabilities are exponentially close to uniform. Interestingly these hardness results also have implications for the complexity of experiments in a low-noise setting. The issue here is that prior hardness results for computing output probabilities of random circuits are not robust enough to imprecision to connect with the Stockmeyer argument for hardness of sampling from circuits with constant fidelity. We exponentially improve the robustness of prior results to imprecision, both in the cases of Random Circuit Sampling and BosonSampling. In the latter case we bring the proven hardness within a constant factor in the exponent of the robustness required for hardness of sampling for the first time. We then show that our results are in tension with one another -- the high-noise result implies the low-noise result is essentially optimal, even with generalizations of our techniques.

43 pages, 2 figures, presented at QIP 2021

References in corpus (9)

• Supplementary information for "Quantum supremacy using a programmable superconducting processor"
• Quantum computational advantage using photons
• Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy
• Random quantum circuits anti-concentrate in log depth
• Classical simulation of lossy boson sampling using matrix product operators
• Fermion Sampling: a robust quantum computational advantage scheme using fermionic linear optics and magic input states
• Error-detection-based quantum fault tolerance against discrete Pauli noise
• Noise Threshold of Quantum Supremacy
• Accuracy threshold for postselected quantum computation

Cited by in corpus (8)

• Computational advantage of quantum random sampling
• Quantum Computational Advantage via High-Dimensional Gaussian Boson Sampling
• A polynomial-time classical algorithm for noisy random circuit sampling
• Tight bounds on the convergence of noisy random circuits to the uniform distribution
• Fermion Sampling: a robust quantum computational advantage scheme using fermionic linear optics and magic input states
• Classical algorithms and quantum limitations for maximum cut on high-girth graphs
• Classical simulation of bosonic linear-optical random circuits beyond linear light cone
• Efficient approximation of experimental Gaussian boson sampling