Abstract
In this talk we will discuss recent results on the power of random quantum circuits, inspired by the “quantum supremacy” experiments of Google and USTC. We will discuss two new results: first we consider the “low noise” scenario in which the goal is to prove the hardness of approximate sampling from the output distribution of a random quantum circuit. The main obstacle faced in prior work on this subject is that the average-case 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. In this work we exponentially improve this robustness to imprecision. In the case of BosonSampling, we bring the proven hardness to within a constant factor in the exponent of the robustness required for hardness of sampling.
Second, we consider the realistic “high noise” scenario. We show that it remains hard to compute the output probabilities of noisy random quantum circuits without error correction, providing the noise rate of the device is below the error detection threshold. This hardness persists despite the fact that these probabilities are exponentially close to uniform. Consequently, the small deviations away from uniformity are hard to compute, formalizing an important intuition behind Google’s supremacy claim.
Interestingly, we then argue that these two results are connected, in that any further progress on proving hardness in the “low noise scenario” would require techniques which *do not* work to improve the hardness results in the “high noise scenario”.
Based on joint work with Adam Bouland, Zeph Landau and Yunchao Liu, arXiv: 2102.01738 and earlier joint work with Adam Bouland, Chinmay Nirkhe, and Umesh Vazirani, arXiv:1803.04402