Measurement-induced entanglement and complexity in random constant-depth 2D quantum circuits
arXiv:2410.23248 · doi:10.1103/PhysRevX.15.021059
Abstract
We analyse the entanglement structure of states generated by random constant-depth two-dimensional quantum circuits, followed by projective measurements of a subset of sites. By deriving a rigorous lower bound on the average entanglement entropy of such post-measurement states, we prove that macroscopic long-ranged entanglement is generated above some constant critical depth in several natural classes of circuit architectures, which include brickwork circuits and random holographic tensor networks. This behaviour had been conjectured based on previous works, which utilize non-rigorous methods such as replica theory calculations, or work in regimes where the local Hilbert space dimension grows with system size. To establish our lower bound, we develop new replica-free theoretical techniques that leverage tools from multi-user quantum information theory, which are of independent interest, allowing us to map the problem onto a statistical mechanics model of self-avoiding walks without requiring large local Hilbert space dimension. Our findings have consequences for the complexity of classically simulating sampling from random shallow circuits, and of contracting tensor networks: First, we show that standard algorithms based on matrix product states which are used for both these tasks will fail above some constant depth and bond dimension, respectively. In addition, we also prove that these random constant-depth quantum circuits cannot be simulated by any classical circuit of sublogarithmic depth.
arXiv comment22 + 12 pages, 11 figures
References in corpus (83)
- Holographic Derivation of Entanglement Entropy from AdS/CFT
- Measurement-based quantum computation
- A Multiparticle Generalization of Entanglement Swapping
- Classical simulation of infinite-size quantum lattice systems in two spatial dimensions
- Measurement-Induced Phase Transitions in the Dynamics of Entanglement
- Entanglement monotones
- Quantum Zeno Effect and the Many-body Entanglement Transition
- Quantum Entanglement Growth Under Random Unitary Dynamics
- Integration with respect to the Haar measure on unitary, orthogonal and symplectic group
- Operator hydrodynamics, OTOCs, and entanglement growth in systems without conservation laws
- Theory of the phase transition in random unitary circuits with measurements
- Holographic duality from random tensor networks
- Unitary-projective entanglement dynamics
- Entanglement versus Correlations in Spin Systems
- Quantum Error Correction in Scrambling Dynamics and Measurement-Induced Phase Transition
- Entropy scaling and simulability by Matrix Product States
- Quantum advantage with shallow circuits
- Dynamical purification phase transitions induced by quantum measurements
- Evenly distributed unitaries: on the structure of unitary designs
- Exact Spectral Form Factor in a Minimal Model of Many-Body Quantum Chaos
- The computational complexity of PEPS
- A Sharp Fannes-type Inequality for the von Neumann Entropy
- Exact Correlation Functions for Dual-Unitary Lattice Models in 1+1 Dimensions
- Quantum state merging and negative information
- Entanglement Percolation in Quantum Networks
- Localizable Entanglement
- Entanglement Transitions from Holographic Random Tensor Networks
- Exact dynamics in dual-unitary quantum circuits
- Statistical mechanics of quantum error correcting codes
- Postselection-free entanglement dynamics via spacetime duality
- Long-range quantum entanglement in noisy cluster states
- Self-Organized Error Correction in Random Unitary Circuits with Measurement
- Renormalization group transformations on quantum states
- Quantum Sampling Problems, BosonSampling and Quantum Supremacy
- Measurement-induced entanglement and teleportation on a noisy quantum processor
- Non-Abelian Topological Order and Anyons on a Trapped-Ion Processor
- A decoupling approach to the quantum capacity
- Entanglement of assistance and multipartite state distillation
- Efficient classical simulation of random shallow 2D quantum circuits
- Quantum advantage with noisy shallow circuits in 3D
- Isometric Tensor Network States in Two Dimensions
- The entanglement membrane in chaotic many-body systems
- Ergodic and non-ergodic dual-unitary quantum circuits with arbitrary local Hilbert space dimension
- One-shot decoupling
- Measurement as a shortcut to long-range entangled quantum matter
- Fractal, logarithmic and volume-law entangled non-thermal steady states via spacetime duality
- Quantum Circuits assisted by LOCC: Transformations and Phases of Matter
- Spacetime duality between localization transitions and measurement-induced transitions
- Exact emergent quantum state designs from quantum chaotic dynamics
- Long-range entanglement from measuring symmetry-protected topological phases
- Nishimori's cat: stable long-range entanglement from finite-depth unitaries and weak measurements
- Diagnostics of mixed-state topological order and breakdown of quantum memory
- Architectures for quantum simulation showing a quantum speedup
- How Dynamical Quantum Memories Forget
- Nonlinear sigma models for monitored dynamics of free fermions
- Entanglement Domain Walls in Monitored Quantum Circuits and the Directed Polymer in a Random Environment
- Decoupling with unitary approximate two-designs
- GHZ extraction yield for multipartite stabilizer states
- Classical algorithms for quantum mean values
- Isometric Tensor Network representation of string-net liquids
- Contracting projected entangled pair states is average-case hard
- Probing post-measurement entanglement without post-selection
- A Maximum Entropy Principle in Deep Thermalization and in Hilbert-Space Ergodicity
- Probing sign structure using measurement-induced entanglement
- Entanglement of Assistance is not a bipartite measure nor a tripartite monotone
- Multipartite entanglement percolation
- Finite-time teleportation phase transition in random quantum circuits
- One-shot entanglement generation over long distances in noisy quantum networks
- Distinguishing multi-partite states by local measurements
- Measurement induced entanglement transition in two dimensional shallow circuit
- Random tensor networks with nontrivial links
- Efficient quantum pseudorandomness with simple graph states
- Quantum pseudo-randomness from cluster-state quantum computation
- Postselection-free learning of measurement-induced quantum dynamics
- Entanglement of Collaboration
- Random-matrix models of monitored quantum circuits
- Universal structure of measurement-induced information in many-body ground states
- Deep thermalization in Gaussian continuous-variable quantum systems
- Random insights into the complexity of two-dimensional tensor network calculations
- Decoupling by local random unitaries without simultaneous smoothing, and applications to multi-user quantum information tasks
- Sign problem in tensor network contraction
- Verifiable measurement-based quantum random sampling with trapped ions
- Quantum Entanglement Phase Transitions and Computational Complexity: Insights from Ising Models