A Caltech Library Service

Efficient Classical Simulation of Random Shallow 2D Quantum Circuits

Napp, John C. and La Placa, Rolando L. and Dalzell, Alexander M. and Brandão, Fernando G. S. L. and Harrow, Aram W. (2022) Efficient Classical Simulation of Random Shallow 2D Quantum Circuits. Physical Review X, 12 (2). Art. No. 021021. ISSN 2160-3308. doi:10.1103/PhysRevX.12.021021.

[img] PDF - Published Version
Creative Commons Attribution.

[img] PDF - Submitted Version
See Usage Policy.

[img] PDF - Supplemental Material
Creative Commons Attribution.


Use this Persistent URL to link to this item:


A central question of quantum computing is determining the source of the advantage of quantum computation over classical computation. Even though simulating quantum dynamics on a classical computer is thought to require exponential overhead in the worst case, efficient simulations are known to exist in several special cases. It was widely assumed that these easy-to-simulate cases as well as any yet-undiscovered ones could be avoided by choosing a quantum circuit at random. We prove that this intuition is false by showing that certain families of constant-depth, 2D random circuits can be approximately simulated on a classical computer in time only linear in the number of qubits and gates, even though the same families are capable of universal quantum computation and are hard to exactly simulate in the worst case (under standard hardness assumptions). While our proof applies to specific random circuit families, we demonstrate numerically that typical instances of more general families of sufficiently shallow constant-depth 2D random circuits are also efficiently simulable. We propose two classical simulation algorithms. One is based on first simulating spatially local regions which are then “stitched” together via recovery maps. The other reduces the 2D simulation problem to a problem of simulating 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 observed that the dynamics generally undergo a phase transition from a low-entanglement (and efficient-to-simulate) regime to a high-entanglement (and 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 both of our algorithms as parameters of the circuit architecture like the local Hilbert space dimension and circuit depth are varied and, additionally, that the effective 1D dynamics corresponding to sufficiently shallow random quantum circuits falls within the efficient-to-simulate regime. Implementing the latter algorithm for the depth-3 “brickwork” architecture, for which exact simulation is hard, we find that a laptop could simulate typical instances on a 409×409 grid with a total variation distance error less than 0.01 in approximately one minute per sample, a task intractable for previously known circuit simulation algorithms. Numerical results support our analytic evidence that the algorithm is asymptotically efficient.

Item Type:Article
Related URLs:
URLURL TypeDescription Material Paper
Napp, John C.0000-0003-0990-2695
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:© 2022 Published by the American Physical Society under the terms of the Creative Commons Attribution 4.0 International license. Further distribution of this work must maintain attribution to the author(s) and the published article’s title, journal citation, and DOI. Received 4 March 2021; revised 15 January 2022; accepted 14 February 2022; published 27 April 2022. We thank Richard Kueng, Saeed Mehraban, Anand Natarajan, Mehdi Soleimanifar, Nicole Yunger Halpern, and Tianci Zhou for helpful discussions and feedback. Numerical simulations were performed using the ITensor Library. This work was funded by NSF Grants No. CCF-1452616, No. CCF-1729369, No. PHY-1818914, and No. DGE-1745301, the NSF QLCI program through Grant No. OMA-2016245, as well as ARO Contract No. 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). This work was done prior to A. D. joining the AWS Center for Quantum Computing.
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
Issue or Number:2
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:03 Jun 2022 18:48

Repository Staff Only: item control page