Efficient Classical Simulation of Random Shallow 2D Quantum Circuits
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...
| Main Authors: | , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
American Physical Society
2022-04-01
|
| Series: | Physical Review X |
| Online Access: | http://doi.org/10.1103/PhysRevX.12.021021 |
| _version_ | 1811306932413136896 |
|---|---|
| author | John C. Napp Rolando L. La Placa Alexander M. Dalzell Fernando G. S. L. Brandão Aram W. Harrow |
| author_facet | John C. Napp Rolando L. La Placa Alexander M. Dalzell Fernando G. S. L. Brandão Aram W. Harrow |
| author_sort | John C. Napp |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-04-13T08:54:33Z |
| format | Article |
| id | doaj.art-782dde1aec4546499deacbef03ff8d44 |
| institution | Directory Open Access Journal |
| issn | 2160-3308 |
| language | English |
| last_indexed | 2024-04-13T08:54:33Z |
| publishDate | 2022-04-01 |
| publisher | American Physical Society |
| record_format | Article |
| series | Physical Review X |
| spelling | doaj.art-782dde1aec4546499deacbef03ff8d442022-12-22T02:53:20ZengAmerican Physical SocietyPhysical Review X2160-33082022-04-0112202102110.1103/PhysRevX.12.021021Efficient Classical Simulation of Random Shallow 2D Quantum CircuitsJohn C. NappRolando L. La PlacaAlexander M. DalzellFernando G. S. L. BrandãoAram W. HarrowA 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.http://doi.org/10.1103/PhysRevX.12.021021 |
| spellingShingle | John C. Napp Rolando L. La Placa Alexander M. Dalzell Fernando G. S. L. Brandão Aram W. Harrow Efficient Classical Simulation of Random Shallow 2D Quantum Circuits Physical Review X |
| title | Efficient Classical Simulation of Random Shallow 2D Quantum Circuits |
| title_full | Efficient Classical Simulation of Random Shallow 2D Quantum Circuits |
| title_fullStr | Efficient Classical Simulation of Random Shallow 2D Quantum Circuits |
| title_full_unstemmed | Efficient Classical Simulation of Random Shallow 2D Quantum Circuits |
| title_short | Efficient Classical Simulation of Random Shallow 2D Quantum Circuits |
| title_sort | efficient classical simulation of random shallow 2d quantum circuits |
| url | http://doi.org/10.1103/PhysRevX.12.021021 |
| work_keys_str_mv | AT johncnapp efficientclassicalsimulationofrandomshallow2dquantumcircuits AT rolandollaplaca efficientclassicalsimulationofrandomshallow2dquantumcircuits AT alexandermdalzell efficientclassicalsimulationofrandomshallow2dquantumcircuits AT fernandogslbrandao efficientclassicalsimulationofrandomshallow2dquantumcircuits AT aramwharrow efficientclassicalsimulationofrandomshallow2dquantumcircuits |