  Random quantum circuits are commonly viewed as hard to simulate classically.
In some regimes this has been formally conjectured, and there had been no
evidence against the more general possibility that for circuits with uniformly
random gates, approximate simulation of typical instances is almost as hard as
exact simulation. We prove that this is not the case by exhibiting a shallow
circuit family with uniformly random gates that cannot be efficiently
classically simulated near-exactly under standard hardness assumptions, but can
be simulated approximately for all but a superpolynomially small fraction of
circuit instances in time linear in the number of qubits and gates. We
furthermore conjecture that sufficiently shallow random circuits are
efficiently simulable more generally. To this end, we propose and analyze two
simulation algorithms. Implementing one of our algorithms numerically, we give
strong evidence that it is efficient both asymptotically and, in some cases, in
practice. To argue analytically for efficiency, we reduce the simulation of 2D
shallow random circuits to the simulation of a form of 1D dynamics consisting
of alternating rounds of random local unitaries and weak measurements -- a type
of process that has generally been observed to undergo a phase transition from
an efficient-to-simulate regime to an inefficient-to-simulate regime as
measurement strength is varied. Using a mapping from quantum circuits to
statistical mechanical models, we give evidence that a similar computational
phase transition occurs for our algorithms as parameters of the circuit
architecture like the local Hilbert space dimension and circuit depth are
varied.
