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 a higher degree of 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 the question: What are the differences between “low-magic” entanglement and “high-magic” entanglement? To understand this interplay between entanglement and magic, we take an operational approach by studying tasks such as entanglement estimation, distillation, and dilution. We uncover a separation of Hilbert space into two distinct regimes: the entanglement-dominated (ED) phase, where entanglement surpasses magic, and the magic-dominated (MD) phase, where magic dominates entanglement. This separation induces a computational phase transition: entanglement-related tasks are efficiently solvable in the ED phase, but become 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.