A Caltech Library Service

Efficient classical simulation of random shallow 2D quantum circuits

Napp, John and La Placa, Rolando L. and Dalzell, Alexander M. and Brandão, Fernando G. S. L. and Harrow, Aram W. (2019) Efficient classical simulation of random shallow 2D quantum circuits. . (Unpublished)

[img] PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


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.

Item Type:Report or Paper (Discussion Paper)
Related URLs:
URLURL TypeDescription Paper
La Placa, Rolando L.0000-0001-7867-226X
Dalzell, Alexander M.0000-0002-3756-8500
Brandão, Fernando G. S. L.0000-0003-3866-9378
Harrow, Aram W.0000-0003-3220-7682
Additional Information:We thank Nicole Yunger Halpern, Richard Kueng, Saeed Mehraban, Ramis Movassagh, Anand Natarajan, and Mehdi Soleimanifar for helpful discussions. Numerical simulations were performed using the ITensor Library. This work was funded by NSF grants CCF-1452616, CCF-1729369, PHY-1818914, and DGE-1745301, as well as ARO contract W911NF-17-1-0433, the MIT-IBM Watson AI Lab under the project Machine Learning in Hilbert space and the Dominic Orr Fellowship at Caltech. The Institute for Quantum Information and Matter (IQIM) is an NSF Physics Frontiers Center (PHY-1733907).
Group:Institute for Quantum Information and Matter, AWS Center for Quantum Computing
Funding AgencyGrant Number
NSF Graduate Research FellowshipDGE-1745301
Army Research Office (ARO)W911NF-17-1-0433
Dominic Orr Graduate FellowshipUNSPECIFIED
Record Number:CaltechAUTHORS:20210512-104029585
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:109094
Deposited By: George Porter
Deposited On:12 May 2021 19:48
Last Modified:12 May 2021 19:48

Repository Staff Only: item control page