Efficient classical simulation of random shallow 2D quantum circuits
arXiv:2001.00021 · doi:10.1103/PhysRevX.12.021021
Abstract
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.
arXiv comment83 pages, 17 figures. v2: minor fixes and clarifications, added a reference
References in corpus (92)
- Supplementary information for "Quantum supremacy using a programmable superconducting processor"
- Efficient classical simulation of slightly entangled quantum computations
- Quantum computational advantage using photons
- A Practical Introduction to Tensor Networks: Matrix Product States and Projected Entangled Pair States
- Efficient simulation of one-dimensional quantum many-body systems
- Average Entropy of a Subsystem
- Characterizing Quantum Supremacy in Near-Term Devices
- Strong quantum computational advantage using a superconducting quantum processor
- Quantum Computational Supremacy
- Matrix product states represent ground states faithfully
- Operator Spreading in Random Unitary Circuits
- Measurement-Induced Phase Transitions in the Dynamics of Entanglement
- Quantum Zeno Effect and the Many-body Entanglement Transition
- Validating quantum computers using randomized model circuits
- Integration with respect to the Haar measure on unitary, orthogonal and symplectic group
- Measurement-driven entanglement transition in hybrid quantum circuits
- Operator hydrodynamics, OTOCs, and entanglement growth in systems without conservation laws
- Theory of the phase transition in random unitary circuits with measurements
- Measurement-induced criticality in random quantum circuits
- Instantaneous non-local computation of low T-depth quantum circuits
- The Heisenberg Representation of Quantum Computers
- Holographic duality from random tensor networks
- Unitary-projective entanglement dynamics
- Simulating quantum computation by contracting tensor networks
- A blueprint for demonstrating quantum supremacy with superconducting qubits
- Quantum Error Correction in Scrambling Dynamics and Measurement-Induced Phase Transition
- Entropy scaling and simulability by Matrix Product States
- Hand-waving and Interpretive Dance: An Introductory Course on Tensor Networks
- Dynamical purification phase transitions induced by quantum measurements
- Critical properties of the measurement-induced transition in random quantum circuits
- Entanglement Tsunami: Universal Scaling in Holographic Thermalization
- Aspects of generic entanglement
- Scalable probes of measurement-induced criticality
- Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy
- Average-case complexity versus approximate simulation of commuting quantum computations
- Quantum Supremacy and the Complexity of Random Circuit Sampling
- Entanglement transition from variable-strength weak measurements
- Emergent statistical mechanics of entanglement in random unitary circuits
- Quantum state merging and negative information
- Entanglement phase transitions in measurement-only dynamics
- Measurement-induced topological entanglement transitions in symmetric random quantum circuits
- Entanglement Transitions from Holographic Random Tensor Networks
- Statistical mechanics of quantum error correcting codes
- Measurement Protected Quantum Phases
- Measurement and entanglement phase transitions in all-to-all quantum circuits, on quantum trees, and in Landau-Ginsburg theory
- Postselection-free entanglement dynamics via spacetime duality
- Measurement-induced quantum criticality under continuous monitoring
- Long-range quantum entanglement in noisy cluster states
- Self-Organized Error Correction in Random Unitary Circuits with Measurement
- Entanglement spreading in a minimal model of maximal many-body quantum chaos
- Measurement-induced criticality in (2+1)-d hybrid quantum circuits
- Achieving quantum supremacy with sparse and noisy commuting quantum computations
- Measurement-induced phase transition: A case study in the non-integrable model by density-matrix renormalization group calculations
- Instantaneous Quantum Computation
- The Dynamics of 1D Quantum Spin Systems Can Be Approximated Efficiently
- How robust is a quantum gate in the presence of noise?
- Conformal invariance and quantum non-locality in critical hybrid circuits
- Entanglement and dynamics of diffusion-annihilation processes with Majorana defects
- Universality of entanglement transitions from stroboscopic to continuous measurements
- Approximate unitary -designs by short random quantum circuits using nearest-neighbor and long-range gates
- Establishing the Quantum Supremacy Frontier with a 281 Pflop/s Simulation
- Fault-tolerant quantum computation
- Measurement-induced entanglement transitions in many-body localized systems
- Architectures for quantum simulation showing a quantum speedup
- Quantum Supremacy for Simulating A Translation-Invariant Ising Spin Model
- Moments and Cumulants of Polynomial random variables on unitary groups, the Itzykson-Zuber integral and free probability
- How Dynamical Quantum Memories Forget
- Classical simulation of photonic linear optics with lost particles
- Emergence of typical entanglement in two-party random processes
- Contracting Arbitrary Tensor Networks: General Approximate Algorithm and Applications in Graphical Models and Quantum Circuit Simulations
- Unitary designs from statistical mechanics in random quantum circuits
- Classical algorithms for quantum mean values
- Classical simulatability, entanglement breaking, and quantum computation thresholds
- Dynamical phase transitions in sampling complexity
- Phase transition of computational power in the resource states for one-way quantum computation
- How Quantum Are Non-Negative Wavefunctions?
- Gaussian Noise Sensitivity and BosonSampling
- Quantum supremacy in constant-time measurement-based computation: A unified architecture for sampling and verification
- Efficient classical simulation of noisy quantum computation
- Quantum computational supremacy in the sampling of bosonic random walkers on a one-dimensional lattice
- Transitions in the computational power of thermal states for measurement-based quantum computation
- A toy model for decoherence in the black hole information problem
- Dynamics of Rényi entanglement entropy in diffusive qudit systems
- Dynamics of Renyi entanglement entropy in local quantum circuits with charge conservation
- Polynomial Simulations of Decohered Quantum Computers
- Holographic quantum simulation
- Efficient unitary paths and quantum computational supremacy: A proof of average-case hardness of Random Circuit Sampling
- Optimal Quantum Circuits for Nearest-Neighbor Architectures
- Noise-resilient preparation of quantum many-body ground states
- The Asymptotics of Quantum Max-Flow Min-Cut
- Can Chaotic Quantum Circuits Maintain Quantum Supremacy under Noise?
- Adaptive Quantum Computation, Constant Depth Quantum Circuits and Arthur-Merlin Games
Cited by in corpus (80)
- Observation of measurement-induced quantum phases in a trapped-ion quantum computer
- Statistical mechanics of quantum error correcting codes
- Postselection-free entanglement dynamics via spacetime duality
- Conformal invariance and quantum non-locality in critical hybrid circuits
- Computational advantage of quantum random sampling
- Quantum advantage with noisy shallow circuits in 3D
- Universality of entanglement transitions from stroboscopic to continuous measurements
- Fractal, logarithmic and volume-law entangled non-thermal steady states via spacetime duality
- Measurement-induced entanglement transitions in many-body localized systems
- Nishimori's cat: stable long-range entanglement from finite-depth unitaries and weak measurements
- Efficient classical simulation of noisy random quantum circuits in one dimension
- Topological transitions with continuously monitored free fermions
- Random quantum circuits anti-concentrate in log depth
- Dynamical purification and the emergence of quantum state designs from the projected ensemble
- A polynomial-time classical algorithm for noisy random circuit sampling
- Computational power of one- and two-dimensional dual-unitary quantum circuits
- Contracting Arbitrary Tensor Networks: General Approximate Algorithm and Applications in Graphical Models and Quantum Circuit Simulations
- Correlations in Perturbed Dual-Unitary Circuits: Efficient Path-Integral Formula
- Disordered monitored free fermions
- Dynamical Magic Transitions in Monitored Clifford+T Circuits
- Probing post-measurement entanglement without post-selection
- Boundaries of quantum supremacy via random circuit sampling
- Tight bounds on the convergence of noisy random circuits to the uniform distribution
- Fermion Sampling: a robust quantum computational advantage scheme using fermionic linear optics and magic input states
- Diagnosing entanglement dynamics in noisy and disordered spin chains via the measurement-induced steady-state entanglement transition
- Noise and the frontier of quantum supremacy
- Finite-time teleportation phase transition in random quantum circuits
- Measurement induced entanglement transition in two dimensional shallow circuit
- Decodable hybrid dynamics of open quantum systems with Z_2 symmetry
- Monitored fermions with conserved charge
- Simulating Noisy Variational Quantum Algorithms: A Polynomial Approach
- Diagrammatic method for many-body non-Markovian dynamics: memory effects and entanglement transitions
- Quantum supremacy and random circuits
- Surface codes, quantum circuits, and entanglement phases
- Postselection-free learning of measurement-induced quantum dynamics
- Measurement induced transitions in non-Markovian free fermion ladders
- Classically estimating observables of noiseless quantum circuits
- Entanglement Phases in large-N hybrid Brownian circuits with long-range couplings
- Quantum Convolutional Neural Networks are Effectively Classically Simulable
- Complexity phase diagram for interacting and long-range bosonic Hamiltonians
- Opening the Black Box Inside Grover's Algorithm
- Efficient sampling of noisy shallow circuits via monitored unraveling
- Experimental demonstration of scalable cross-entropy benchmarking to detect measurement-induced phase transitions on a superconducting quantum processor
- Renormalization group for measurement and entanglement phase transitions
- Atomic Quantum Technologies for Quantum Matter and Fundamental Physics Applications
- The minimal canonical form of a tensor network
- Simulating quantum circuits using efficient tensor network contraction algorithms with subexponential upper bound
- Universal structure of measurement-induced information in many-body ground states
- Continuous-time dynamics and error scaling of noisy highly-entangling quantum circuits
- Simulating 2D topological quantum phase transitions on a digital quantum computer
- Emulating Quantum Interference with Generalized Ising Machines
- Robust sparse IQP sampling in constant depth
- Random insights into the complexity of two-dimensional tensor network calculations
- Entanglement entropy scaling of noisy random quantum circuits in two dimensions
- Forbidden subspaces for level-1 QAOA and IQP circuits
- Exploring Shallow-Depth Boson Sampling: Towards Scalable Quantum Supremacy
- Sign problem in tensor network contraction
- Phase transition in von Neumann entanglement entropy from replica symmetry breaking
- Quantum complexity phase transitions in monitored random circuits
- Measurement-induced entanglement and complexity in random constant-depth 2D quantum circuits
- Roadmap for quantum simulation of the fractional quantum Hall effect
- Designs from magic-augmented Clifford circuits
- Benchmarking a boson sampler with Hamming nets
- The resource theory of tensor networks
- Flow to Nishimori universality in weakly monitored quantum circuits with qubit loss
- Integrability of Goldilocks quantum cellular automata
- Phase transitions in sampling and error correction in local Brownian circuits
- Emergent unitary designs for encoded qubits from coherent errors and syndrome measurements
- Classical simulability of Clifford+T circuits with Clifford-augmented matrix product states
- Classical simulation of bosonic linear-optical random circuits beyond linear light cone
- Extending Classically Simulatable Bounds of Clifford Circuits with Nonstabilizer States via Framed Wigner Functions
- Efficient approximation of experimental Gaussian boson sampling
- Random Quantum Circuits with Time-Reversal Symmetry
- Quantum Entanglement Phase Transitions and Computational Complexity: Insights from Ising Models
- Revisiting Nishimori multicriticality through the lens of information measures
- Sampling and the complexity of nature
- Post-measurement Quantum Monte Carlo
- Field theory of charge sharpening in symmetric monitored quantum circuits
- Measurement-induced entanglement in noisy 2D random circuits
- Evolutionary reduction of the laser noise impact on quantum gates