Magic State Distillation

Every fault-tolerant quantum computer runs into the same wall. To keep errors from spreading, you apply logical gates transversally — one physical gate per qubit, so a single fault stays contained in one block. Transversal gates are the safest thing an encoded machine can do. But the Eastin–Knill theorem proves that the transversal logical gates of any code form a finite group, and a finite group can never be dense in the unitary group. No code is universal on transversal gates alone; something continuous, hence dangerous, is always missing. Magic state distillation is the elegant way around the wall. Instead of performing the missing non-Clifford operation directly on encoded data, you factor it out of the live computation. Clifford gates — generated by Hadamard, phase, and CNOT — are fault-tolerant on good codes, but by the Gottesman–Knill theorem they are also classically simulable, so they are not enough. Universality is bought back by injecting a non-stabilizer "magic state" such as $|T\rangle$ , which drives one logical $T$ gate through gate teleportation using only Cliffords and a measured correction — pushing the entire non-Clifford difficulty offline into preparing these ancillas. The catch: magic states cannot be prepared fault-tolerantly — that is exactly the operation the theorem forbids — so raw copies arrive noisy, with error rate $p$ set by the hardware. Distillation is the purification stage: a Clifford circuit consumes many noisy copies, measures the stabilizers of a chosen code, and on the clean-syndrome outcome emits fewer copies whose error is crushed from $p$ to $\sim c\,p^m$ . Iterate a few times and the error falls below any target. Because every round discards most of its input, this offline factory dominates the qubit-hours of real algorithms — which is why magic, not Cliffords, sets the price of quantum computation.

Key takeaways

The Eastin–Knill theorem forbids any code from having a universal transversal gate set; distillation dodges it by supplying the missing non-Clifford piece as an offline resource state.
A magic state such as $|T\rangle=(|0\rangle+e^{i\pi/4}|1\rangle)/\sqrt2$ drives one logical $T$ gate through gate teleportation, using only Cliffords plus a measurement-controlled correction.
Distillation feeds $n$ noisy copies of error $p$ into a Clifford syndrome measurement and, on acceptance, outputs cleaner copies with error $p'\approx c\,p^{m}$ , with $m$ the smallest undetectable logical-error weight.
The Bravyi–Kitaev 15-to-1 protocol uses the Reed–Muller code's transversal $T$ to distill $|T\rangle$ at $p'\approx 35\,p^3$ ; the 5-qubit protocol distills $|H\rangle$ -type states at $p'\approx 5\,p^3$ .
The map $p\mapsto 35p^3$ has a sharp threshold $p_*=1/\sqrt{35}\approx0.169$ : below it error is driven super-exponentially to zero, above it distillation fails and wastes qubits.
Only states outside the stabilizer polytope can be distilled at all, tying the protocol to magic monotones like the robustness of magic and the stabilizer Rényi entropy.
Key idea: push all non-Clifford difficulty into offline, distillable ancillas — noisy non-stabilizer states are purified by Clifford-only syndrome measurement on a code whose transversal non-Clifford gate maps the magic state to itself, suppressing error from $p$ to $\sim c\,p^{m}$ , then consumed one-by-one to apply logical $T$ gates via gate teleportation.

Where this lives today

Distillation is the pacing item of real fault-tolerant hardware. The surface code — the leading architecture for superconducting and trapped-ion machines — admits fault-tolerant Cliffords through lattice surgery but has no transversal $T$ , so practical designs wall off large chip regions as dedicated magic-state factories running 15-to-1 and its descendants, then pipe clean $|T\rangle$ states into the data. In the widely cited estimates for factoring RSA-2048 with Shor's algorithm, these factories and the $T$ -count dominate the qubit-hours, driving work on $T$ -count reduction, block codes that distill many states at once, and "cultivation" schemes that skip full distillation. The same subroutine completes topological quantum computers: Ising-anyon and Majorana platforms braid perfect Cliffords but are provably non-universal, and distilled magic states supply their missing $\pi/8$ gate, while universal Fibonacci anyons need none. And a successful round operationally certifies non-stabilizerness — only states outside the stabilizer polytope survive — tying the enterprise back to the resource theory of magic.

The physical picture

Picture a magic state as a bottle of concentrated "non-Clifford juice." Clifford gates can pour, stir, and measure but never synthesize the juice; gate teleportation lets you spend one bottle to brew one $T$ gate. Hardware only hands you watery, contaminated bottles — every raw $|T\rangle$ carries error $p$ . Distillation is a filtration press: pour fifteen dirty bottles into a Clifford machine, check that no error syndrome lit up, and out comes a single far-purer bottle — because to slip through undetected an error must match one of the rare patterns the code cannot tell from "no error at all," costing a factor $p^m$ instead of $p$ . The reason a specific code works is a small miracle of group theory. The 15-qubit punctured Reed–Muller code has a transversal logical $T$ : applying physical $T^\dagger$ to all fifteen qubits realizes the logical $T^\dagger$ . Feed in fifteen raw $|T\rangle$ copies, apply transversal $T^\dagger$ , and the ideal component lands exactly on the code's logical $|T\rangle$ . Measuring the fourteen stabilizers with Clifford circuits then heralds errors — the all-trivial syndrome means none was detected, and decoding returns one clean physical $|T\rangle$ , as the first figure shows.

Figure

The 15-to-1 factory: fifteen noisy T-states at error p ≈ 10⁻² enter a Clifford circuit that encodes the Reed–Muller code and measures 14 stabilizers; accepting only the trivial syndrome yields one clean T-state at p′ ≈ 35p³ ≈ 3.5×10⁻⁵, any detected error rejected

Geometrically the story is cleaner still. After a Clifford twirl, any noisy magic state sits on the segment from the pure $|T\rangle$ to the maximally mixed center of the stabilizer polytope, its position fixed by the single number $p$ . Distillation is then a map on that one number, $p\mapsto p'$ , with two fixed points — purity at $p=0$ and garbage at the polytope — split by an unstable threshold $p_*$ . Below $p_*$ iteration flows to purity super-exponentially fast; above it flows to junk. The second figure plots this map against the diagonal, and the crossing is the threshold.

Figure

The 15-to-1 distillation map p′ = 35p³ (blue) against the identity p′ = p (amber). They cross at the threshold p = 1/√35 ≈ 0.169: an input below p is pulled toward 0 (distills), one above p* is pushed up (fails). The curve lies far below the diagonal for small p, giving cubic suppression

The core equations

The magic states are the natural non-Clifford targets — resources for the gates that lift the Cliffords to universality. The canonical single-qubit choices are $|T\rangle$ and its Clifford cousin $|H\rangle$ .

|T\rangle=\frac{1}{\sqrt2}\left(|0\rangle+e^{i\pi/4}|1\rangle\right)=T|+\rangle,\qquad |H\rangle=\cos\tfrac{\pi}{8}\,|0\rangle+\sin\tfrac{\pi}{8}\,|1\rangle \qquad (1)

where: $T=\mathrm{diag}(1,e^{i\pi/4})$ — the $\pi/8$ phase gate; $|+\rangle=(|0\rangle+|1\rangle)/\sqrt2$ — a stabilizer state carrying no magic; $|H\rangle$ — the $+1$ eigenstate of the Hadamard, equivalent to $|T\rangle$ up to a Clifford. Why they matter: adjoining $T$ to the Clifford group generates a dense subgroup of $\mathrm{SU}(2^n)$ , so these states plus Cliffords are universal — while Cliffords alone are classically simulable. One clean copy of $|T\rangle$ is spent per logical $T$ by gate teleportation: a CNOT couples data to ancilla, a $Z$ measurement teleports the gate through, and the only leftover is an outcome-conditioned Clifford correction.

|\psi\rangle_L\otimes|T\rangle_a\;\xrightarrow{\ \mathrm{CNOT}(L\to a),\ M_Z(a)\ }\;\begin{cases}T|\psi\rangle_L & \text{outcome }0\\[2pt] S\,T|\psi\rangle_L & \text{outcome }1\end{cases} \qquad (2)

where: $|\psi\rangle_L$ — the logical data qubit receiving a $T$ ; $a$ — an ancilla prepared in $|T\rangle$ ; $M_Z$ — a Pauli- $Z$ measurement; $S=T^2=\mathrm{diag}(1,i)$ — the Clifford phase gate. Reading: the outcome-1 byproduct is a fault-tolerant Clifford, so the sole non-Clifford resource consumed is the magic state itself. To make "the error rate $p$ " meaningful, first symmetrize the noise by a Clifford twirl — averaging over the single-qubit Cliffords that fix the $|T\rangle$ axis, collapsing any noise channel to a depolarizing mixture set by one number.

\Lambda(\rho)=\frac{1}{|\mathcal{C}_1'|}\sum_{C\in\mathcal{C}_1'} C\,\rho\,C^\dagger \;\Longrightarrow\; \rho_p=(1-p)\,|T\rangle\!\langle T|+p\,|T^\perp\rangle\!\langle T^\perp| \qquad (3)

where: $\mathcal{C}_1'$ — the single-qubit Cliffords fixing the $|T\rangle$ axis (a $\mathbb{Z}_3$ rotation about the magic direction); $|T^\perp\rangle$ — the orthogonal magic state; $p$ — the depolarizing error rate. Reading: after the twirl the state is one scalar $p$ , so distillation reduces to the scalar recursion $p\mapsto p'$ of the second figure. The 15-to-1 protocol implements that map. Because the code detects every single error, the leading undetectable logical fault has weight three, with exactly 35 patterns.

p'=\frac{35\,p^3+O(p^4)}{1-O(p)}\;\approx\;35\,p^3 \qquad (4)

where: $35$ — the number of weight-3 error configurations that act as a logical error; $p$ — the twirled input error per copy; the denominator is the acceptance probability, $\to1$ as $p\to0$ . Reading: cubic suppression with coefficient 35 — each round roughly triples the reliable digits in $1/p$ at a factor-15 qubit cost. Iterating reaches any accuracy, and the total raw states grow only polylogarithmically in the target error, set by one figure of merit.

p_{k+1}=c\,p_k^{m},\qquad N(p_0\to\varepsilon)\sim\big[\log(1/\varepsilon)\big]^{\gamma},\qquad \gamma=\frac{\log n}{\log m} \qquad (5)

where: $n$ — input copies per output (15 here); $m$ — the suppression exponent (3 here); $c$ — the leading coefficient (35 here); $\gamma$ — the overhead exponent, $\log_3 15\approx2.46$ . Reading: reaching $\varepsilon$ needs only $k\sim\log_m\log(1/\varepsilon)$ rounds, so cost is gentle in accuracy but the prefactor is large — lowering $\gamma$ toward 1 is the central goal. Whether a state can be distilled is bounded by a magic monotone: the robustness of magic measures how far outside the stabilizer polytope a state lies, and never increases under Clifford operations.

\mathcal{R}(\rho)=\min\Big\{\textstyle\sum_i|x_i|\ :\ \rho=\sum_i x_i\,\sigma_i,\ \sigma_i\in\mathrm{STAB}\Big\}\;\ge\;1 \qquad (6)

where: $\sigma_i$ — pure stabilizer states; $x_i$ — real, possibly negative, quasiprobability weights; $\mathrm{STAB}$ — the stabilizer states. Reading: $\mathcal{R}(\rho)=1$ exactly for stabilizer states, which carry no magic, and $\mathcal{R}$ upper-bounds the magic any Clifford protocol can output — resource is concentrated, never manufactured.

Derivation AFifteen-to-one distillation from the quantum Reed–Muller code

The goal is to see how fifteen noisy $|T\rangle$ copies at error $p$ become one copy at error $\approx 35p^3$ , and to pin down the algebraic fact that makes it work — a code whose logical $T$ is realized by physical $T$ on every qubit. We recall that transversal symmetry, use it to encode the ideal input onto the logical $|T\rangle$ , herald errors with Clifford-only measurements, count the undetectable faults, and read off the output error and threshold — every number checkable against Bravyi–Kitaev (2005).

Step 1. Fix the code. The punctured 15-qubit Reed–Muller code is a self-dual CSS code with $n=15$ , $k=1$ , $d=3$ and — crucially — a transversal logical $T$ : applying $T^\dagger$ to all fifteen qubits realizes the logical $T^\dagger$ (up to a Clifford). Why: this single algebraic coincidence is the whole engine — the code is chosen because its non-Clifford transversal gate matches the magic state we purify.

Step 2. Encode. Apply transversal $T^\dagger$ to the fifteen copies. On the ideal component $(T|+\rangle)^{\otimes15}$ this produces the encoded $|+\rangle_L$ acted on by logical $T$ — the code's logical magic state $|T\rangle_L$ . Why: this turns fifteen physical magic states into one encoded magic state, so the code's error detection acts on the accompanying noise.

Step 3. Herald with Clifford measurements. Measure the fourteen stabilizers; the all-trivial syndrome is acceptance, and any single physical error flips a stabilizer and is rejected. Why: with $d=3$ the code detects every weight-1 and weight-2 error, so acceptance guarantees no low-weight fault slipped through — pure postselection, no non-Clifford cost.

Step 4. Count the survivors. The lowest-weight errors that escape detection and act as a nontrivial logical operator have weight 3, with exactly 35 such configurations, each of probability $\sim p^3$ . Why: 35 is a fixed count of weight-3 elements in the relevant logical coset, not a fitted constant.

Step 5. Read off output and threshold. On acceptance, decode $|T\rangle_L$ back to one physical $|T\rangle$ ; its residual error is the undetected-logical-error probability $p_{\text{out}}\approx 35p^3$ , and setting $35p_*^3=p_*$ gives $p_*=1/\sqrt{35}\approx0.169$ . Why: the fixed point is where "distillation helps" turns into "distillation hurts," and the large $0.169$ is why raw error of a few percent is already well inside the distillable regime. *Verified: the coefficient 35 and threshold $1/\sqrt{35}\approx0.169$ are the standard Bravyi–Kitaev (2005) values; recount the weight-3 logical patterns and solve $35p_*^3=p_*$ .*

Go deeper · Derivation B · 1 minThreshold and round count of the iterated distillation map

Derivation BThreshold and round count of the iterated distillation map

The goal is to treat one round of distillation as a one-dimensional dynamical system on the error rate, $p\mapsto c\,p^{m}$ , and extract two things a resource estimator needs: the threshold separating "purifies" from "diverges," and the round count to reach a target error. We find the fixed points, test stability, identify the basin, solve the recursion in closed form, and plug in the 15-to-1 numbers to show only a handful of rounds is needed.

Step 1. Find the fixed points. Solving $p=c\,p^{m}$ gives $p=0$ or $p_*=c^{-1/(m-1)}$ ; for 15-to-1, $c=35$ , $m=3$ , so $p_*=35^{-1/2}\approx0.169$ . Why: these are the pure state and the crossover — nothing else is invariant, so they organize everything.

Step 2. Test stability. Near $p=0$ the map $p'\approx c\,p^{m}$ with $m\ge2$ has vanishing derivative — the origin is super-attracting, so $p_*$ is the unstable separatrix. Why: super-attraction means convergence faster than geometric once close — the origin of "a few rounds suffice."

Step 3. Identify the basin. Any $p_0<p_*$ flows to zero; any $p_0>p_*$ is pushed toward the useless fixed point. Why: a sharp go/no-go with no gentle degradation.

Step 4. Solve the recursion. Writing $q_k=c^{1/(m-1)}p_k$ linearizes the map to $q_{k+1}=q_k^{m}$ , so $p_k=c^{-1/(m-1)}\big(c^{1/(m-1)}p_0\big)^{m^k}$ . Requiring $p_k\le\varepsilon$ gives $k\ge\log_{m}\!\big[\ln(c^{1/(m-1)}/\varepsilon)\,/\,\ln(1/(c^{1/(m-1)}p_0))\big]$ ; for $p_0=10^{-2}$ , $\varepsilon=10^{-15}$ this gives $k\approx3$ . Why: the double logarithm makes accuracy cheap — dropping $\varepsilon$ many orders adds one round — and each round drives the polylog overhead $\gamma=\log n/\log m$ . *Verified: $p_*=c^{-1/(m-1)}$ reproduces $0.169$ for $(c,m)=(35,3)$ ; iterating from $p_0=10^{-2}$ gives $3.5\times10^{-5}$ , $1.5\times10^{-12}$ , $1.2\times10^{-34}$ .*

Go deeper · Derivation C · 1 minGate teleportation injects one logical T gate

Derivation CGate teleportation injects one logical T gate

The goal is to prove by explicit algebra that consuming one ideal $|T\rangle$ applies a logical $T$ to arbitrary data with only a Clifford byproduct — the fact that turns a distilled ancilla directly into a gate. We write the data–ancilla state, apply the CNOT, project onto each outcome, and identify the correction on the unwanted branch, keeping every factor of $e^{i\pi/4}$ since carrying the phases is the whole point.

Step 1. Set up. Take data $|\psi\rangle=\alpha|0\rangle+\beta|1\rangle$ and ancilla $|T\rangle=\tfrac{1}{\sqrt2}(|0\rangle+e^{i\pi/4}|1\rangle)$ , data as CNOT control and ancilla as target: $\tfrac{1}{\sqrt2}\big[\alpha|0\rangle(|0\rangle+e^{i\pi/4}|1\rangle)+\beta|1\rangle(|0\rangle+e^{i\pi/4}|1\rangle)\big]$ . Why: making the magic state the target lets the data's $|1\rangle$ branch pick up the phase that becomes $T$ .

Step 2. Apply CNOT. The control's $|1\rangle$ component flips the target labels: $\tfrac{1}{\sqrt2}\big[\alpha|0\rangle(|0\rangle+e^{i\pi/4}|1\rangle)+\beta|1\rangle(|1\rangle+e^{i\pi/4}|0\rangle)\big]$ . Why: this entangles the ancilla phase with the data amplitude, staging it to transfer at measurement.

Step 3. Measure the ancilla in $Z$ , outcome 0. The target- $|0\rangle$ terms leave the data in $\alpha|0\rangle+\beta e^{i\pi/4}|1\rangle=T|\psi\rangle$ — the desired gate, no correction. Why: the phase lands cleanly on the $|1\rangle$ amplitude, realizing $T$ for free.

Step 4. Outcome 1. The target- $|1\rangle$ terms leave $\alpha e^{i\pi/4}|0\rangle+\beta|1\rangle$ , and applying the Clifford $S=\mathrm{diag}(1,i)$ returns $e^{i\pi/4}\,T|\psi\rangle$ . Why: the byproduct is the Clifford $S=T^2$ , applied fault-tolerantly at negligible cost, so the only non-Clifford resource ever spent is the ancilla — which makes distilled magic states directly convertible into $T$ gates. *Verified: expanding the CNOT and projecting onto each outcome reproduces the Nielsen–Chuang gate-teleportation identity; outcome 1 equals $ST|\psi\rangle$ up to the phase $e^{i\pi/4}$ .*

Limiting cases

Behavior of the 15-to-1 map $p'\approx 35p^3$ across regimes:

Case	Result	Meaning
Deep low-noise	$p\ll p_*\ \Rightarrow\ p'\approx 35\,p^3$	Cubic suppression; three rounds take $p=10^{-2}$ below $10^{-34}$ , at a factor-15 qubit cost per round.
Threshold (fixed point)	$35\,p_^3=p_\ \Rightarrow\ p_*=1/\sqrt{35}\approx0.169$	The leading-order crossover; higher-order terms lower it slightly but it stays $O(0.1)$ — distillation tolerates surprisingly large input noise.
Yield / overhead	$N\sim[\log(1/\varepsilon)]^{\gamma},\ \gamma=\log_3 15\approx2.46$	Raw states per output grow only polylogarithmically in accuracy; $\gamma=\log n/\log m$ is the figure of merit, pushed toward 1 by Bravyi–Haah codes.
Vanishing acceptance	$P_{\text{acc}}=1-O(p)\to1$	For small $p$ almost every batch is accepted, so yield approaches $1/15$ ; near threshold acceptance falls and overhead balloons.
Non-distillable region	$\rho\in\mathrm{STAB}\ \Rightarrow\ \mathcal{R}(\rho)=1$	Inside the stabilizer polytope the magic is zero and Cliffords preserve zero — no protocol produces a magic state.

Common trap“Distillation just cleans up any noisy state, and it does it for free.”

Neither half is true. First, distillation cannot create magic — only concentrate what is already present. If the twirled input lies inside the stabilizer polytope (robustness $\mathcal{R}=1$ ), every Clifford keeps it there, so the output has zero magic however many copies you feed in. Second, even a magical input distills only if its error is below threshold: above $p_*\approx0.169$ the map $35p^3$ sits above the diagonal and each round makes things worse. Third, "for free" is wrong — the protocol postselects on a clean syndrome and discards a constant fraction of every batch, so a successful round still consumes 15 inputs per output and rounds are stacked. This is why magic-state factories, not Clifford gates, dominate the qubit-hours of fault-tolerant algorithms.

Worked examples

1 · Two rounds of 15-to-1 from a one-percent source

A raw $|T\rangle$ source has twirled error $p_0=10^{-2}$ . Find the output error after one, two, and three rounds of 15-to-1, and the raw states per final copy.

Step 1. Apply the map once: $p_1=35\times(10^{-2})^3=35\times10^{-6}=\mathbf{3.5\times10^{-5}}$ . The error drops nearly three orders of magnitude, since the cube of $10^{-2}$ is $10^{-6}$ and the coefficient 35 only partly offsets it.

Step 2. Iterate: $p_2=35\times(3.5\times10^{-5})^3=\mathbf{1.5\times10^{-12}}$ , then $p_3\approx\mathbf{1.2\times10^{-34}}$ . The exponent roughly triples each round — the super-exponential convergence of a super-attracting fixed point.

Step 3. Count raw states (ignoring rejections): each output consumes 15 inputs, so two rounds need $15^2=225$ copies and three need $15^3=\mathbf{3375}$ . Two rounds already reach $\sim10^{-12}$ , below the $\sim10^{-15}$ target of most algorithms. Two rounds: $p_2\approx1.5\times10^{-12}$ from 225 raw states.

2 · Is a given source above or below threshold?

Hardware A delivers twirled states at $p=0.05$ ; hardware B at $p=0.20$ . Which can be distilled by 15-to-1, and what happens to each under iteration?

Step 1. Compare to $p_*=1/\sqrt{35}\approx0.169$ . Hardware A has $p=0.05<p_*$ (distillable basin); hardware B has $p=0.20>p_*$ (above threshold).

Step 2. Iterate A: $p'=35\times(0.05)^3=4.4\times10^{-3}$ — an order of magnitude below input — and a second round gives $\approx3.0\times10^{-6}$ . Error collapses toward zero.

Step 3. Iterate B: $p'=35\times(0.20)^3=0.28>0.20$ — the error grew, and further rounds drive it toward the garbage fixed point. A distills (0.05 → 4.4×10⁻³ → 3.0×10⁻⁶ → …); B fails (0.20 → 0.28 → …), starting above $p_*\approx0.169$ .

Physics of the portrait

Magic state distillation is a young idea with a sharp lineage: a stabilizer theory that made Cliffords "easy," a no-go theorem that made universality "hard," and a purification protocol that reconciled the two.

Origins · 1 minmagic state distillation and how this was discovered

magic state distillation

the offline non-Clifford resource that completes fault-tolerant universality · stabilizer codes and quantum resource theory

The concept crystallized from a tension that took a decade to sharpen. Daniel Gottesman's stabilizer formalism and the Gottesman–Knill theorem showed by the late 1990s that Clifford circuits on stabilizer states are efficiently classically simulable — a gift for error correction, since Cliffords are the gates codes implement most naturally, but a warning that Cliffords alone can never be universal. Something non-Clifford was mandatory, yet the safe way to run gates, transversally, could not supply it. In 2004 Emanuel Knill proposed a way through: fault tolerance from noisy ancillas and postselection, hinting the hard resource could be prepared offline. The decisive step came in 2005, when Sergey Bravyi and Alexei Kitaev formalized magic states and gave explicit protocols — the 15-to-1 route on the Reed–Muller code for $|T\rangle$ , a 5-qubit route for $|H\rangle$ — with the thresholds and coefficient 35 still quoted today; Ben Reichardt extended the idea to general CSS codes that year. In 2009 Bryan Eastin and Emanuel Knill closed the loop, proving no code admits a universal transversal gate set, making offline resources unavoidable. Bravyi and Haah's 2012 low-overhead triorthogonal codes, and Howard and Campbell's 2017 bounds via the robustness of magic, turned distillation from a clever trick into the accounting backbone of fault-tolerant architecture.

History

1998

— Gottesman–Knill theorem: Clifford circuits on stabilizer states are efficiently classically simulable

2004

— Knill introduces fault-tolerant computation from noisy ancillas and postselection

2005

— Bravyi and Kitaev define magic states and the 15-to-1 and 5-qubit distillation protocols

2009

— Eastin and Knill prove no code has a universal transversal gate set

2012

— Bravyi and Haah reach low overhead with triorthogonal codes

Going further

Texts and papers. Bravyi & Kitaev, "Universal quantum computation with ideal Clifford gates and noisy ancillas," Phys. Rev. A 71, 022316 (2005) · Nielsen & Chuang, Quantum Computation and Quantum Information, ch. 10 · Preskill, Lecture Notes on Quantum Computation, ch. 7 · Kitaev, Shen & Vyalyi, Classical and Quantum Computation · Eastin & Knill, "Restrictions on transversal encoded quantum gate sets," Phys. Rev. Lett. 102, 110502 (2009) · Bravyi & Haah, "Magic state distillation with low overhead," Phys. Rev. A 86, 052329 (2012) · Reichardt, "Quantum universality from magic states distillation applied to CSS codes," Quant. Inf. Proc. 4, 251 (2005) · Howard & Campbell, "Application of a resource theory for magic states...," Phys. Rev. Lett. 118, 090501 (2017).

Provenance. Magic states, gate teleportation, and the 15-to-1 / 5-to-1 protocols follow Bravyi & Kitaev (2005); the coefficients 35 and 5 and thresholds are their standard values. The Eastin–Knill no-go is Phys. Rev. Lett. 102, 110502 (2009); overhead scaling and triorthogonal codes are Bravyi & Haah (2012); resource-theory monotones Howard & Campbell (2017). A verifier should recompute: the gate-teleportation outcomes and $S$ byproduct; the fixed point of $35p^3=p$ giving $p_*=1/\sqrt{35}\approx0.169$ ; the three-round iteration $p_0=10^{-2}\to\sim10^{-34}$ ; and $\gamma=\log_3 15\approx2.46$ .

Prerequisites. Stabilizer Formalism and Clifford Group · Quantum Error-Correcting Codes · Gate Teleportation · The Cost of Magic and Magic Resource Theory. Leads to. The Cost of Magic and Magic Resource Theory · Topological Quantum Computation · Fibonacci and Ising Anyons · Majorana Zero Modes.

Ask the tutor: Want to walk through why the Reed–Muller code's transversal $T$ is the exact ingredient that makes 15-to-1 distill $|T\rangle$ — or trace a magic state from hardware noise all the way to a logical gate?

Why can't we just apply a T gate transversally like the Cliffords?

Because the Eastin–Knill theorem forbids it. The transversal logical gates of any code form a finite group, and a finite group cannot be dense in the continuous unitary group — so it cannot contain a universal gate set. Intuitively, a continuous family of transversal gates would rotate logical information by arbitrarily small angles without leaving the codespace, defeating the error detection the code exists for. Cliffords fit inside the allowed finite set on good codes, but the $T$ gate does not. Distillation sidesteps the theorem by never performing $T$ on encoded data directly: it prepares the resource offline and teleports it in.

Where does the specific number 35 come from?

It is a combinatorial property of the punctured 15-qubit Reed–Muller code, not a fitted parameter. That code has distance 3, so it detects every weight-1 and weight-2 error and rejects them on the trivial syndrome. The lowest-weight errors that both evade detection and act as a logical operator have weight 3, and enumerating the code's logical cosets gives exactly 35 such configurations, each of probability $\sim p^3$ — so the output error is $\approx 35p^3$ . Change the code and you change both the exponent (via distance) and the coefficient (via this count); the 5-qubit code for $|H\rangle$ gives $5p^3$ .

What does the Clifford twirl actually do, and why is it needed?

Real hardware noise on a magic state can be any channel — biased, coherent, complicated. The twirl averages the state over the single-qubit Cliffords that fix the magic axis, symmetrizing that noise into a simple depolarizing mixture along the $|T\rangle$ direction. Afterward the state is one number, the error rate $p$ , so distillation becomes a clean scalar recursion $p\mapsto p'$ . Twirling costs nothing — it is built from Cliffords — and it is what makes "input error $p$ , output error $35p^3$ " well-defined rather than channel-dependent.

Is distillation the same thing as error correction?

They are cousins, not the same. Error correction protects a logical qubit already carrying data, decoding syndromes and applying corrections to keep the information intact. Distillation is state preparation: it manufactures a specific known ancilla — a magic state — by postselection, throwing away any batch with a nontrivial syndrome rather than repairing it. Error correction cannot discard the data it protects; distillation freely discards, because it is only making disposable fuel. The two run together: distillation feeds clean magic states into an error-corrected computation.

Why does distillation dominate the cost of a fault-tolerant algorithm?

Because Cliffords are nearly free and $T$ gates are not. Clifford operations are transversal or lattice-surgery-based and need no special ancillas, but every non-Clifford $T$ gate consumes one distilled magic state — the output of a factory that burned 15 raw states per round over several rounds, hundreds to thousands of physical qubit-rounds apiece. Algorithms like Shor factoring or quantum chemistry have enormous $T$ -counts, so the factories occupy most of the chip area and runtime — which is why the field works hard to lower both the $T$ -count and the overhead exponent $\gamma$ .

Can any noisy state be distilled if I just run enough rounds?

No — two conditions must hold. First, the state must actually contain magic: inside the stabilizer polytope (robustness of magic equal to 1) it has zero distillable resource, and since Clifford operations cannot increase magic, no number of rounds helps. Second, even a magical state must start below threshold, $p_*\approx0.169$ for 15-to-1; above it the map $35p^3$ lies above the diagonal, so each round makes the state worse. Only inputs both non-stabilizer and below threshold converge to a pure magic state.