Magic-induced computational separation in entanglement theory

• DOI: 10.48550/arxiv.2403.19610
• Publication Date: 2024-03-28
• Authors: Andi Gu; Salvatore F. E. O...; Lorenzo Leone
• Keywords: Separation (statistics)

Entanglement serves as a foundational pillar in quantum information theory, delineating the boundary between what is classical and quantum. The common assumption that higher entanglement corresponds to greater degree of 'quantumness'. However, this folk belief challenged by fact classically simulable operations, such Clifford circuits, can create highly entangled states. simulability these states raises question: are differences 'low-magic' entanglement, 'high-magic' entanglement? We answer question work with rigorous investigation into role magic theory. take an operational approach understanding relationship studying tasks estimation, distillation dilution. This reveals has surprisingly strong implications for entanglement. Specifically, we find sharp separation splits Hilbert space two distinct phases: entanglement-dominated (ED) phase magic-dominated (MD) phase. Roughly speaking, ED have significantly surpasses their magic, while MD dominates competition resources phases induces computational them: there sample- time-efficient algorithms almost any task on states, provably computationally intractable To demonstrate power our results beyond highlight relevance findings many-body physics topological error correction. Additionally, offer simple theoretical explanations phenomenological observations made previous numerical studies using ED-MD phases.