Measurement-induced entanglement and complexity in random constant-depth 2D quantum circuits

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.

22 + 12 pages, 11 figures

References in corpus (11)

• Classical simulation of infinite-size quantum lattice systems in two spatial dimensions
• Entanglement versus Correlations in Spin Systems
• Entropy scaling and simulability by Matrix Product States
• Evenly distributed unitaries: on the structure of unitary designs
• A Sharp Fannes-type Inequality for the von Neumann Entropy
• Localizable Entanglement
• Postselection-free entanglement dynamics via spacetime duality
• Entanglement of assistance and multipartite state distillation
• One-shot entanglement generation over long distances in noisy quantum networks
• Quantum pseudo-randomness from cluster-state quantum computation
• Entanglement of Collaboration

Cited by in corpus (4)

• Exactly solvable many-body dynamics from space-time duality
• Scalable projected entangled-pair state representation of random quantum circuit states
• Measurement-Induced Entanglement in Conformal Field Theory
• Measurement-induced entanglement in noisy 2D random circuits