Adam Bouland

BosonSampling and Random Circuit Sampling are important both as a theoretical tool for separating quantum and classical computation, and as an experimental means of demonstrating quantum speedups. Prior works have shown that average-case hardness of sampling follows from certain unproven conjectures about the hardness of computing output probabilities, such as the Permanent-of-Gaussians Conjecture (PGC), which states that $e^{-n\log{n}-n-O(\log n)}$ additive-error estimates to the output probability of most random BosonSampling experiments are $\#P$-hard. Prior works have only shown weaker average-case hardness results that do not imply sampling hardness. Proving these conjectures has become a central question in quantum complexity. In this work, we show that $e^{-n\log n-n-O(n^\delta)}$ additive-error estimates to output probabilities of most random BosonSampling experiments are $\#P$-hard for any $\delta>0$, exponentially improving on prior work. In the process, we circumvent all known barrier results for proving PGC. The remaining hurdle to prove PGC is now “merely” to show that the $O(n^\delta)$ in the exponent can be improved to $O(\log n).$ We also obtain an analogous result for Random Circuit Sampling. We then show, for the first time, a hardness of average-case classical sampling result for BosonSampling, under an anticoncentration conjecture. Specifically, we prove the impossibility of multiplicative-error sampling from random BosonSampling experiments with probability $1-2^{-\tilde{\mathstrut O}(N^{1/3})}$ for input size $N$, unless the Polynomial Hierarchy collapses. This exponentially improves upon the state-of-the-art. To do this, we introduce new proof techniques which tolerate exponential loss in the worst-to-average-case reduction. This opens the possibility to show the hardness of average-case sampling without ever proving PGC.

Abstract Understanding the power of random quantum circuit sampling experiments has emerged as one of the most pressing topics in the near-term quantum era. In this work we make progress toward bridging the major remaining gaps between theory and experiment, incorporating the effects of experimental imperfections into the theoretical hardness arguments. We do this first by proving that computing the output probability of an $m$-gate random quantum circuit to within additive imprecision $2^{-O(m^{1+\epsilon})}$ is #P-hard for any $\epsilon>0$, an exponential improvement over the prior hardness results of Bouland et al. and Movassagh which were resistant to imprecision $2^{-O(m^3)}$. This improvement very nearly reaches the threshold ($2^{-O(m)}/\text{poly}(m)$) sufficient to establish the hardness of sampling for constant-depth random quantum circuits. To prove this result we introduce new error reduction techniques for polynomial interpolation, as well as a new robust Berlekamp-Welch argument over the Reals which may be of independent interest. Second we show that these results are still true in the presence of a constant rate of noise, so long as the noise rate is below the error detection threshold. That is, even though random circuits with a constant noise rate converge rapidly to the maximally mixed state, the (exponentially) small deviations in their output probabilities away from uniformity remain difficult to compute. Interestingly, we then show that our two main results are in tension with one another, and the latter result implies the former result is essentially optimal with respect to additive imprecision error, even with substantial generalizations of our techniques.