Title: From estimation of quantum probabilities to simulation of quantum circuits
Abstract: We show that there are two distinct aspects of a general quantum circuit that can make it hard to efficiently simulate with a classical computer. The first aspect, which has been well-studied, is that it can be hard to efficiently estimate the probability associated with a particular measurement outcome. However, we show that this aspect alone does not determine whether a quantum circuit can be efficiently simulated. The second aspect is that, in general, there can be an exponential number of ‘relevant’ outcomes that are needed for an accurate simulation, and so efficient simulation may not be possible even in situations where the probabilities of individual outcomes can be efficiently estimated. We show that these two aspects are distinct and independently necessary for simulability.
Specifically, we prove that a family of quantum circuits is efficiently simulatable if it satisfies two properties: one related to the efficiency of Born rule probability estimation, and the other related to the sparsity of the outcome distribution. We then prove a pair of hardness results (using standard complexity assumptions and a variant of a commonly-used average case hardness conjecture), where we identify families of quantum circuits that satisfy one property but not the other, and for which we can prove that efficient simulation is not possible. To prove our results, we consider a notion of simulation of quantum circuits, that we call EPSILON-simulation. This notion is less stringent than exact sampling and is now in common use in quantum hardness proofs.