The Cost of Magic and Magic Resource Theory

Magic resource theory stopped being abstract the moment people used it to draw the line quantum advantage must cross. Stabilizer-rank simulators (Bravyi–Gosset) and quasiprobability Monte-Carlo simulators (Pashayan and collaborators) run in time set by $\chi$ or $\mathcal{R}^2$, and they now simulate near-Clifford circuits with roughly 50 non-Clifford gates — precisely locating where classical methods must give out, and providing the honest baseline that any claim of quantum advantage has to beat. On the compilation side, because each $T$ consumes a distilled magic state, and magic-state factories dominate the space-time volume of surface-code algorithms, quantifying a target unitary's intrinsic magic yields lower bounds on achievable $T$-count that certify a compilation is optimal. In topological hardware the theory makes a sharp physical prediction: Ising-anyon and Majorana platforms braid to the full Clifford group but produce zero magic, so they need injected magic to become universal, while Fibonacci anyons braid to dense, magical gates and are natively universal — the cost of universality is exactly the cost of supplying the magic braiding cannot make. Most recently, the stabilizer Rényi entropy has crossed into many-body physics and experiment: randomized-measurement protocols on trapped-ion and Rydberg arrays now estimate the magic of prepared states directly, turning non-stabilizerness into a measurable probe of quantum complexity that distinguishes classically spoofable outputs from authentically quantum ones.

Picture the set of all $n$-qubit density matrices as a convex body. Inside it sits the stabilizer polytope $\mathrm{STAB}_n$, the convex hull of the finitely many pure stabilizer states. Free operations — Cliffords, Pauli measurements, stabilizer ancillas — map this polytope into itself and can never carry a point out of it. Magic is simply how far outside the polytope a state lies, or, for a mixed state, how deep it must be buried before the polytope can contain it. A state grazing a facet is barely magical; a state that forces you to inflate the polytope by a large factor before it fits (large robustness) is highly magical. Every magic monotone is one honest way of turning "distance from the free set" into a number, and different monotones answer different operational questions about that distance.

There is a second picture that makes magic literally a negativity. In odd prime dimension, the discrete Wigner function assigns a quasiprobability $W_\rho(u)$ to each phase-space point, and the discrete Hudson theorem says a pure state has an everywhere-nonnegative Wigner function if and only if it is a stabilizer state. Magic then is the negativity: a state can fuel non-classical computation only if its Wigner function dips below zero somewhere, and the total negativity (the mana) measures the failure of a positive-quasiprobability classical simulation. The two pictures — geometric distance from the polytope, and negativity of a quasiprobability — are two faces of the one resource. The reason all of this is not bookkeeping for its own sake is that the same magic gauge reads the cost of computation from both directions at once. The second figure is the picture a fault-tolerance architect actually reasons about: a magic-poor circuit is one a classical computer can fake quickly, while a magic-rich circuit is where classical simulation blows up — and the crossover is set by a magic monotone, the stabilizer rank.

The whole framework rests on one convex set: the free states. These are the mixed stabilizer states, the convex hull of the pure ones, and everything about magic is measured relative to this polytope.

where: $\mathrm{STAB}_n$ — the set of $n$-qubit (mixed) stabilizer states; $|\phi\rangle$ — a pure stabilizer state, the simultaneous $+1$ eigenstate of $n$ commuting independent Paulis; $\mathrm{conv}$ — convex hull. Reading: there are $2^n\prod_{k=1}^{n}(2^k+1)$ pure stabilizer states, a finite set whose hull is a polytope; a state is free precisely when it lies inside it. The first and most operational monotone is the robustness of magic: the minimum total $\ell_1$ weight of any signed mixture of stabilizer states that reproduces $\rho$. Negative coefficients are what let the mixture reach outside the polytope, and the price is paid in $\ell_1$ weight above one.

where: $\mathcal{R}(\rho)$ — robustness of magic, $\ge1$ with equality iff $\rho\in\mathrm{STAB}_n$; $x_i$ — real, possibly negative, coefficients of a pseudo-mixture; $\sigma_i$ — pure stabilizer states. Reading: $\mathcal{R}$ is a norm-like distance, it is multiplicative-submultiplicative under tensor products, and $\mathcal{R}^2$ controls the sample cost of quasiprobability Monte-Carlo simulation. For pure states a second monotone, the stabilizer extent, is sharper for the fastest simulators. It relaxes the "must be a probability" constraint to a complex-amplitude decomposition and minimizes the squared $\ell_1$ weight; its reciprocal is the stabilizer fidelity, the largest overlap with any stabilizer state.

where: $\xi(|\psi\rangle)$ — stabilizer extent, $\ge1$, multiplicative for states of at most three qubits; $c_i$ — complex amplitudes over (non-orthogonal) stabilizer states; $F_S$ — stabilizer fidelity. Reading: extent equals $1$ on the free set and grows with magic; for a single qubit $\xi=1/F_S$, tying the two together. The most direct simulation-cost monotone is the stabilizer rank: the fewest stabilizer states needed to write $|\psi\rangle$ exactly. It is $1$ exactly for stabilizer states and counts the "quantum branches" a classical simulator must track.

where: $\chi(|\psi\rangle)$ — stabilizer rank, $=1$ iff stabilizer; $r$ — number of terms. Reading: a circuit with $t$ injected magic states simulates in time $\sim\chi(|A\rangle^{\otimes t})\cdot\mathrm{poly}(n)$, and because $\chi(|A\rangle^{\otimes6})\le7$ one has $\chi(|A\rangle^{\otimes t})\le2^{\alpha t}$ with $\alpha\le\tfrac{\log_2 7}{6}\approx0.468<1$. The phase-space route defines magic through a quasiprobability. In odd prime dimension the discrete Wigner function is the finite-field analogue of the continuous one, real and normalized but not always positive.

where: $W_\rho(u)$ — Wigner quasiprobability at phase-space point $u\in\mathbb{Z}_d\times\mathbb{Z}_d$; $A_u$ — phase-space point operator (Hermitian, $\mathrm{Tr}\,A_u=1$); $d$ — qudit dimension, odd prime for the cleanest theory. Reading: $W_\rho$ is a genuine probability distribution exactly when $\rho$ is a stabilizer state; any negative cell is a fingerprint of magic. The mana packages that negativity into an additive monotone — the logarithm of the total $\ell_1$ mass of the Wigner function.

where: $\mathcal{M}(\rho)$ — mana, additive, $\ge0$, $=0$ iff $W_\rho\ge0$; $\mathrm{sn}(\rho)=\sum_{u:\,W<0}|W_\rho(u)|$ — the sum-negativity. Reading: since $\sum_u W=1$, the total mass is $\sum_u|W|=1+2\,\mathrm{sn}$, so mana grows monotonically with the negative quasiprobability that any classical Monte-Carlo simulation must fight. For qubits, where the clean Wigner picture fails, a measurable substitute is the stabilizer Rényi entropy, defined from the fourth moments of the Pauli spectrum.

where: $M_2$ — the second stabilizer Rényi entropy, $=0$ iff stabilizer; $\mathcal{P}_n$ — the $4^n$ Pauli strings (phase-free); $\langle\psi|P|\psi\rangle$ — Pauli expectation, the Pauli spectrum. Reading: the numbers $\Xi_P=\langle P\rangle^2/d$ form a probability distribution ($\sum_P\Xi_P=1$ for pure states), and $M_2$ is its collision (2-Rényi) entropy shifted so that stabilizer states — whose spectrum is flat on a subgroup — read zero; it is estimable from randomized measurements. Finally, the operational meaning of one unit of magic: gate teleportation consumes a single magic state to enact a $T$ using only Clifford operations, converting circuit nonlinearity into resource consumption.

where: $|A\rangle=T|+\rangle=(|0\rangle+e^{i\pi/4}|1\rangle)/\sqrt2$ — the magic state consumed per $T$; $M_Z$ — a computational-basis measurement with outcome $m\in\{0,1\}$; $S^m$ — a Clifford fix-up conditioned on $m$. Reading: whichever outcome occurs, the net action is the non-Clifford $T$ up to a deterministically corrected Clifford, so the only non-Clifford ingredient in the entire machine is the offline magic state itself.

1 · A full magic audit of the T state (fully worked)

Compute the four standard magic numbers of $|A\rangle=T|+\rangle=(|0\rangle+e^{i\pi/4}|1\rangle)/\sqrt2$: its robustness, extent, stabilizer fidelity, and second stabilizer Rényi entropy, and say what each one buys operationally.

Step 1. Bloch vector. $|A\rangle$ has $\langle X\rangle=\tfrac1{\sqrt2}$, $\langle Y\rangle=\tfrac1{\sqrt2}$, $\langle Z\rangle=0$, so $\vec r_A=\tfrac1{\sqrt2}(\hat x+\hat y)$ with $\ell_1$ norm $\sqrt2$. Robustness for a single qubit equals the Bloch $\ell_1$ norm above one, so $\mathcal{R}(|A\rangle)=\mathbf{\sqrt2\approx1.414}$, and the Monte-Carlo cost per $T$ is $\mathcal{R}^2=\mathbf{2}$.

Step 2. Stabilizer fidelity. The nearest stabilizer state is $|+\rangle$: $F_S=|\langle+|A\rangle|^2=\tfrac14|1+e^{i\pi/4}|^2=\tfrac14(2+\sqrt2)=\mathbf{(2+\sqrt2)/4\approx0.854}$. The magic state overlaps the free set by $85\%$ — close, yet provably outside it.

Step 3. Extent. Decomposing $|A\rangle=a|+\rangle+b|+i\rangle$ gives $|a|=|b|=\sqrt{1-\tfrac1{\sqrt2}}$, so $\xi=\big(|a|+|b|\big)^2=4\big(1-\tfrac1{\sqrt2}\big)=\mathbf{4-2\sqrt2\approx1.172}$, and consistently $\xi=1/F_S$ (since $1/0.854=1.172$). The extent, not the robustness, sets the sharper stabilizer-rank simulation bound.

Step 4. Stabilizer Rényi entropy. The Pauli spectrum is $\langle I\rangle=1,\ \langle X\rangle=\langle Y\rangle=\tfrac1{\sqrt2},\ \langle Z\rangle=0$, so $\sum_P\langle P\rangle^4=1+\tfrac14+\tfrac14+0=\tfrac32$ and $M_2=-\log_2\!\big(\tfrac1d\sum_P\langle P\rangle^4\big)=-\log_2\!\big(\tfrac{3/2}{2}\big)=-\log_2\tfrac34=\mathbf{\log_2\tfrac43\approx0.415}$ bits. All four agree that $|A\rangle$ is genuinely, and modestly, magical: $\mathcal{R}=\sqrt2$, $\xi=1.172$, $F_S=0.854$, $M_2=0.415$.

2 · Where the classical-simulability frontier falls

A near-Clifford circuit contains $t$ $T$-gates. Estimate the classical simulation cost by the robustness (Monte-Carlo) route and by the stabilizer-rank route, and locate the frontier beyond which each becomes infeasible at a $2^{50}$-operation budget.

Step 1. Robustness route. The sample count scales as $\mathcal{R}(|A\rangle)^{2t}=2^{t}$. Setting $2^{t}=2^{50}$ gives a frontier at $t\approx\mathbf{50}$ $T$-gates for the Monte-Carlo method — and with a realistic accuracy prefactor, closer to $t\approx40$.

Step 2. Stabilizer-rank route. The cost scales as $\chi(|A\rangle^{\otimes t})\lesssim2^{\alpha t}$ with $\alpha\approx0.47$ from $\chi(|A\rangle^{\otimes6})\le7$. Setting $2^{0.47 t}=2^{50}$ gives $t\approx50/0.47\approx\mathbf{106}$ in principle; memory for the $\sim2^{0.47t}$ stabilizer terms is the true limiter, which in practice caps demonstrations near $t\approx50$–$60$.

Step 3. Compare at $t=50$. Robustness needs $\sim2^{50}\approx10^{15}$ samples — borderline infeasible; stabilizer rank needs $\sim2^{0.47\times50}=2^{23.5}\approx1.2\times10^{7}$ terms — easily feasible. The exponent $0.47$ versus $1$ is the whole difference. The magic-controlled exponent, not the raw $T$-count, sets the frontier: sharper monotones (extent, low-rank decompositions) push classical simulation of near-Clifford circuits out to roughly 50 $T$-gates.

Magic resource theory is not one theorem but a convergence: a discrete phase space from quantum foundations, a no-go theorem about classical simulation, and a decade of monotones that turned "non-Cliffordness" into hard numbers.

Texts and papers. Nielsen & Chuang, Quantum Computation and Quantum Information, §10.5–10.6 (stabilizer formalism, Gottesman–Knill) · Preskill, Lecture Notes on Quantum Computation, ch. 7 · Watrous, The Theory of Quantum Information (channels and convex structure) · Gottesman & Chuang, Nature 402, 390 (1999) — gate teleportation · Bravyi & Kitaev, Phys. Rev. A 71, 022316 (2005) — magic states and distillation · Gross, J. Math. Phys. 47, 122107 (2006) — discrete Hudson theorem · Veitch, Mousavian, Gottesman & Emerson, New J. Phys. 16, 013009 (2014) — resource theory of stabilizer computation · Howard & Campbell, Phys. Rev. Lett. 118, 090501 (2017) — robustness of magic · Bravyi, Smith & Smolin, Phys. Rev. X 6, 021043 (2016); Bravyi, Browne, Calpin, Campbell, Gosset & Howard, Quantum 3, 181 (2019) — stabilizer rank and extent · Leone, Oliviero & Hamma, Phys. Rev. Lett. 128, 050402 (2022) — stabilizer Rényi entropy. The anchor numbers for $|A\rangle=T|+\rangle$ can be recovered directly: $\mathcal{R}(|A\rangle)=\sqrt2$ follows from the symmetric $\{|+\rangle,|+i\rangle,|-\rangle,|-i\rangle\}$ pseudo-mixture together with the single-qubit identity $\mathcal{R}=\|\vec r\|_1$; the extent $\xi(|A\rangle)=4-2\sqrt2\approx1.172$ and fidelity $F_S=(2+\sqrt2)/4\approx0.854$ satisfy $\xi=1/F_S$ (note that the occasionally cited value $2(\sqrt2-1)\approx0.83$ cannot be the extent, since $\xi\ge1$ always); $M_2(|A\rangle)=\log_2\tfrac43\approx0.415$ comes from the Pauli spectrum $(1,\tfrac1{\sqrt2},\tfrac1{\sqrt2},0)$; the mana identity $\sum_u|W|=1+2\,\mathrm{sn}$ and the discrete Hudson theorem underpin the phase-space picture; $\chi(|A\rangle^{\otimes6})\le7<2^6$ gives the exponent $\alpha=\log_2 7/6\approx0.468$; and the $\mathcal{R}^2$ Monte-Carlo scaling follows from the robustness monotone. The body-diagonal $|T\rangle$ with $\vec r=(1,1,1)/\sqrt3$ has $\mathcal{R}=\sqrt3$, the single-qubit maximum.

Prerequisites. Stabilizer Formalism and Gottesman–Knill · Clifford Group · Magic State Distillation · Measurement-Based Quantum Computation. Leads to. Magic State Distillation · Topological Quantum Computation · Fibonacci and Ising Anyons · Classical Simulation of Quantum Circuits.

Ask the tutor: Ask me to re-derive $\mathcal{R}(|A\rangle)=\sqrt2$ and $\xi=4-2\sqrt2$ from the Bloch geometry, or to estimate the classical-simulation frontier for a circuit with a $T$-count of your choosing.