  The class of commuting quantum circuits known as IQP (instantaneous quantum
polynomial-time) has been shown to be hard to simulate classically, assuming
certain complexity-theoretic conjectures. Here we study the power of IQP
circuits in the presence of physically motivated constraints. First, we show
that there is a family of sparse IQP circuits that can be implemented on a
square lattice of n qubits in depth O(sqrt(n) log n), and which is likely hard
to simulate classically. Next, we show that, if an arbitrarily small constant
amount of noise is applied to each qubit at the end of any IQP circuit whose
output probability distribution is sufficiently anticoncentrated, there is a
polynomial-time classical algorithm that simulates sampling from the resulting
distribution, up to constant accuracy in total variation distance. However, we
show that purely classical error-correction techniques can be used to design
IQP circuits which remain hard to simulate classically, even in the presence of
arbitrary amounts of noise of this form. These results demonstrate the
challenges faced by experiments designed to demonstrate quantum supremacy over
classical computation, and how these challenges can be overcome.
