Zeph Landau

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.