Magic-induced computational separation in entanglement theory

Abstract

Entanglement serves as a foundational pillar in quantum information theory, delineating the boundary between what is classical and what is quantum. The common assumption is that higher entanglement corresponds to a greater degree of `quantumness'. However, this folk belief is challenged by the fact that classically simulable operations, such as Clifford circuits, can create highly entangled states. The simulability of these states raises a question: what are the differences between `low-magic' entanglement, and `high-magic' entanglement? We answer this question in this work with a rigorous investigation into the role of magic in entanglement theory. We take an operational approach to understanding this relationship by studying tasks such as entanglement estimation, distillation and dilution. This approach reveals that magic has notable implications for entanglement. Specifically, we find an operational separation that divides Hilbert space into two distinct regimes: the entanglement-dominated (ED) phase and magic-dominated (MD) phase. Roughly speaking, ED states have entanglement that significantly surpasses their magic, while MD states have magic that dominates their entanglement. The competition between the two resources in these two phases induces a computational phase separation between them: there are {sample- and time-efficient} quantum algorithms for almost any entanglement task on ED states, while these tasks are {provably computationally intractable} in the MD phase. Our results find applications in diverse areas such as quantum error correction, many-body physics, and the study of quantum chaos, providing a unifying framework for understanding the behavior of quantum systems. We also offer theoretical explanations for previous numerical observations, highlighting the broad implications of the ED-MD distinction across various subfields of physics.

References in corpus (65)

• Quantum entanglement
• Topological entanglement entropy
• Entanglement detection
• Improved Simulation of Stabilizer Circuits
• Quantum Resource Theories
• Measurement-Induced Phase Transitions in the Dynamics of Entanglement
• Quantum Zeno Effect and the Many-body Entanglement Transition
• Chaos in quantum channels
• Efficient quantum state tomography
• 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
• The Resource Theory of Stabilizer Computation
• Chaos and complexity by design
• Everything You Always Wanted to Know About LOCC (But Were Afraid to Ask)
• Quantum advantage with shallow circuits
• Dynamical purification phase transitions induced by quantum measurements
• Critical properties of the measurement-induced transition in random quantum circuits
• Quantum Low-Density Parity-Check Codes
• Improved classical simulation of quantum circuits dominated by Clifford gates
• Bipartite entanglement and entropic boundary law in lattice spin systems
• Trading classical and quantum computational resources
• Stabilizer Rényi entropy
• Simulation of quantum circuits by low-rank stabilizer decompositions
• Quantum simulation of time-dependent Hamiltonians and the convenient illusion of Hilbert space
• Ground state entanglement and geometric entropy in the Kitaev's model
• The Entanglement of Formation for Isotropic States
• Quantum Trajectories and Quantum Measurement Theory
• Tradeoffs for reliable quantum information storage in 2D systems
• Driving non-Gaussian to Gaussian states with linear optics
• The maximally entangled set of multipartite quantum states
• Topological Entanglement Entropy of Fracton Stabilizer Codes
• Distillation of continuous-variable entanglement with optical means
• Quantum Chaos is Quantum
• Emergent irreversibility and entanglement spectrum statistics
• Stabilizer entropies are monotones for magic-state resource theory
• Catalysis and activation of magic states in fault tolerant architectures
• Spurious topological entanglement entropy from subsystem symmetries
• Multipartite Entangled Spatial Modes of Ultracold Atoms Generated and Controlled by Quantum Measurement
• Transformations among Pure Multipartite Entangled States via Local Operations Are Almost Never Possible
• Entanglement Complexity in Quantum Many-Body Dynamics, Thermalization and Localization
• Nonstabilizerness determining the hardness of direct fidelity estimation
• GHZ extraction yield for multipartite stabilizer states
• Dynamical Magic Transitions in Monitored Clifford+T Circuits
• Resource theory of quantum scrambling
• Topological Order Following a Quantum Quench
• No second law of entanglement manipulation after all
• Efficient unitary designs with a system-size independent number of non-Clifford gates
• Entanglement-magic separation in hybrid quantum circuits
• Learning t-doped stabilizer states
• Transitions in entanglement complexity in random quantum circuits by measurements
• Quantum Entropy and Central Limit Theorem
• Lower bound for the T count via unitary stabilizer nullity
• Pseudomagic Quantum States
• Transitions in Entanglement Complexity in Random Circuits
• Learning efficient decoders for quasi-chaotic quantum scramblers
• Irreversibility and Entanglement Spectrum Statistics in Quantum Circuits
• Measurement-Induced Phase Transition in a Quantum Spin System
• Unscrambling Quantum Information with Clifford decoders
• Bell sampling from quantum circuits
• Phase transition in Stabilizer Entropy and efficient purity estimation
• Gaussification and entanglement distillation of continuous variable systems: a unifying picture
• Quantifying dynamical magic with completely stabilizer preserving operations as free
• Efficient learning of $t$-doped stabilizer states with single-copy measurements
• On the experimental feasibility of continuous-variable optical entanglement distillation

Cited by in corpus (23)

• Probing quantum complexity via universal saturation of stabilizer entropies
• Efficient mutual magic and magic capacity with matrix product states
• Quantum Non-Local Nonstabilizerness
• Entanglement and Stabilizer entropies of random bipartite pure quantum states
• Independent stabilizer Rényi entropy and entanglement fluctuations in random unitary circuits
• Quantum Complexity Fluctuations from Nuclear and Hypernuclear Forces
• Bridging Entanglement and Magic Resources within Operator Space
• Entanglement-induced provable and robust quantum learning advantages
• Magic transition in measurement-only circuits
• Interplay of entanglement structures and stabilizer entropy in spin models
• Entanglement theory with limited computational resources
• An Exact Link between Nonlocal Nonstabilizerness and Operator Entanglement
• Non-Clifford Cost of Random Unitaries
• Nonstabilizerness generation in a multiparticle quantum walk
• Rise and fall of nonstabilizerness via random measurements
• Robustness of Magic in the quantum Ising chain via Quantum Monte Carlo tomography
• Analyzing the free states of one quantum resource theory as resource states of another
• Experimental characterization of the hierarchy of quantum correlations in top quark pairs
• Optimal quantum reservoir learning in proximity to universality
• Stabilizer Rényi Entropy for Translation-Invariant Matrix Product States
• Gottesman-Knill Limit on One-way Communication Complexity: Tracing the Quantum Advantage down to Magic Resources
• An Algorithm for Estimating $\alpha$-Stabilizer Rényi Entropies via Purity
• Pseudoentanglement Ain't Cheap