Clifford circuits — quantum circuits built from Hadamard, CNOT, and phase gates — can be simulated efficiently on a classical computer. The Gottesman-Knill theorem guarantees this: any state reachable by Clifford operations from a computational basis state can be tracked using a polynomial-size stabilizer tableau. Clifford computation is quantum in form but classical in substance.
Universality requires magic — non-Clifford resources that take states outside the stabilizer polytope. The T gate is the canonical example. Add enough T gates to a Clifford circuit and you get universal quantum computation, which (assuming standard complexity conjectures) is not efficiently simulable classically. Magic is the ingredient that makes quantum computation hard for classical computers.
Leone, Eisert, and Oliviero (arXiv 2602.22330, February 2026) prove that deciding whether a quantum state has magic is itself super-exponentially hard. The membership problem for the stabilizer polytope — given a quantum state, determine whether it lies inside the convex hull of stabilizer states — requires time that scales as exp(n²), where n is the number of qubits. Not polynomial. Not merely exponential. Super-exponential.
The proof reduces the stabilizer polytope membership problem to 3-SAT, a known NP-complete problem, but the encoding requires a number of variables that scales quadratically in the number of qubits, giving the exp(n²) lower bound rather than the usual exp(n) of NP-complete problems.
The consequences ripple outward. Computing any magic monotone — a measure of how far a state is from the stabilizer polytope — requires solving the membership problem as a subroutine, or something at least as hard. Magic monotones are the resource measures of magic: they quantify how much non-Clifford resource a state contains. If measuring the resource is intractable, then the resource theory of magic cannot be operationalized for general states.
Worse: even the question of classical simulability — can a particular quantum computation be efficiently simulated classically? — becomes intractable in regimes involving logarithmically many non-Clifford gates. A circuit with O(log n) T gates is provably classically simulable, but verifying that the circuit's output state is simulable is computationally hard. You can simulate it, but you can't efficiently prove that you can simulate it.
The quantum resource that makes computation powerful is a resource whose quantity cannot be efficiently assessed.