Abstract
As Moore’s law reaches its limits, quantum computers are emerging that hold promise to dramatically outperform classical computers. It is now possible to build quantum processors with over 100 qubits, which are expected to be beyond the reach of classical simulation. These developments have been accompanied by the anticipation that, at some stage, a quantum computer should be able to perform a task that is practically impossible for any classical computer. The lead candidate for reaching this threshold is random circuit sampling, which involves sampling the output of a quantum computer after implementing a sequence of random quantum operations. However, it is difficult to provide theoretical guarantees on the hardness of simulating random quantum circuits by classical computers. Here we prove that estimating the output probabilities of random quantum circuits is #P-hard for any classical computer. We also extend our results to a restricted model of quantum computation known as instantaneous quantum polynomial-time (IQP) circuits. We achieve this by a worst-case to average-case reduction for quantum-circuit simulation. The robustness of our result to the estimation error serves as a new hardness criterion for the performance of classical algorithms. Our results suggest that there is an exponential hardness barrier for the approximate classical simulation of most quantum circuits.