On the geometry and typicality of quantum magic

This paper provides a comprehensive geometric characterization of the stabilizer polytope, the set of all mixed quantum states that can be represented as convex combinations of pure stabilizer states. Despite the central role of magic in quantum computation, the geometry of this polytope has remained elusive due to the rapid growth of the number of stabilizer states with the system size. The authors analyze the polytope from three perspectives: local geometry (inradius), global geometry (volume radius), and combinatorial complexity (number of facets).

The authors establish a universal lower bound on the Hilbert–Schmidt inradius of the stabilizer polytope, proving that any state with a purity below a specific threshold (approximately 1/(d - 0.458)) is necessarily a stabilizer state. This result resolves a long-standing conjecture regarding the difficulty of detecting magic in single-copy quantum states. By combining this local geometric information with the reverse Santaló inequality, the authors determine the volume radius of the stabilizer polytope up to logarithmic factors, revealing that the stabilizer polytope is remarkably well-spread in the operator space.

Using these geometric insights, the authors characterize the typicality of magic in random induced states—states obtained by tracing out a subsystem from a larger Haar-random pure state. They prove a sharp phase transition in the probability of magic, showing that magic is robust against environmental mixing; a subsystem remains typically magic even when coupled to an environment nearly twice its size. Finally, the authors provide a significantly improved lower bound on the number of facets of the stabilizer polytope, showing that it scales as exp[Ω(d^2/log^2 d)]. This implies that any exact description of the magic-free region requires a doubly exponential number of linear inequalities, highlighting the fundamental complexity of characterizing quantum magic.