Efficient classical simulation of random shallow 2D quantum circuits

Random quantum circuits are commonly viewed as hard to simulate classically. In some regimes this has been formally conjectured — in the context of deep 2D circuits, this is the basis for Google’s recent announcement of “quantum computational supremacy” — 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 random circuit family that cannot be efficiently classically simulated 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; this example limits the robustness of recent worst-case-to-average-case reductions for random circuit simulation. While our proof is based on a contrived random circuit family, we furthermore conjecture that sufficiently shallow constant-depth random circuits are efficiently simulable more generally. To this end, we propose and analyze two simulation algorithms. Implementing one of our algorithms for the depth-3 “brickwork” architecture, for which exact simulation is hard, we found that a laptop could simulate typical instances on a 409 × 409 grid with variational distance error less than 0.01 in approximately one minute per sample, a task intractable for previously known circuit simulation algorithms. Numerical evidence indicates that the algorithm remains efficient asymptotically.

Key to both our rigorous complexity separation and our conjecture is an observation that 2D shallow random circuit simulation can be reduced to a simulation of a form of 1D dynamics consisting of alternating rounds of random local unitaries and weak measurements. Similar processes have recently been the subject of an intensive research focus, which has found numerically that the dynamics generally undergo a phase transition from an efficient-to-simulate regime to an inefficient-to-simulate regime as measurement strength is varied. Via a mapping from random quantum circuits to classical statistical mechanical models, we give analytical 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, and additionally that the 1D dynamics corresponding to sufficiently shallow random quantum circuits falls within the efficient-to-simulate regime.