Distillation Protocols

Magic-state distillation takes many noisy copies of a magic state and, using only stabilizer operations (Clifford gates, Pauli measurements, and stabilizer-state ancillas), outputs fewer copies of much higher fidelity. The flagship example is the $15$ -to- $1$ protocol of Bravyi and Kitaev.[^bravyi-kitaev]

The idea: encode, then decode

Distillation is built from a quantum error-correcting code whose transversal $T$ (or $T^\dagger$ ) gate is supported by its structure. The recipe is:

Take $15$ noisy copies of the magic state, each carrying error $\varepsilon$ .
Treat them as if they were the inputs to a transversal logical $T$ on a particular $[[15,1,3]]$ code.
Measure the code's stabilizers. The measurement detects any single faulty input, because the code has distance $3$ .
Post-select on the trivial syndrome (all stabilizers $+1$ ). If any check fires, throw the batch away and start over. If all checks pass, decode to recover one output magic state.

Because the code detects every weight-one error, a single bad input among the $15$ is caught and rejected. The output is corrupted only when three or more inputs were simultaneously bad in a correlated way — an event of order $\varepsilon^3$ .

The code: quantum Reed–Muller $[[15,1,3]]$

The $15$ -to- $1$ protocol uses the punctured quantum Reed–Muller code $\mathrm{RM}^*$ , a self-dual CSS code on $15$ qubits encoding $1$ logical qubit with distance $3$ . Its defining feature is that the transversal application of $T^\dagger$ (one $T^\dagger$ on each of the $15$ physical qubits) implements a logical $T$ . Feeding in $15$ copies of $|T\rangle$ and measuring the $X$ -type stabilizers projects onto the codespace; the surviving logical qubit is a distilled $|T\rangle$ .

The output-error scaling

The headline result, derived by counting which input-error patterns survive post-selection, is that to leading order the output error is

\varepsilon_{\text{out}} \;=\; 35\,\varepsilon_{\text{in}}^{\,3} \;+\; O(\varepsilon_{\text{in}}^{4}).

The coefficient $35$ counts the weight- $3$ error patterns that the distance- $3$ code cannot distinguish from a logical error (the minimal-weight representatives of the logical operator); it is the exact leading coefficient computed by Bravyi and Kitaev. The crucial qualitative feature is the cubic suppression: each round of distillation roughly cubes the error. If $\varepsilon_{\text{in}} = 10^{-2}$ , one round gives $\varepsilon_{\text{out}} \approx 35\times10^{-6} = 3.5\times10^{-5}$ — a $\sim\!300\times$ improvement from a single round.

Iterating to arbitrary fidelity

Because each round cubes the error (times $35$ ), concatenating $r$ rounds drives the error down doubly-exponentially fast in $r$ . After $r$ rounds,

\varepsilon_r \approx \frac{1}{\sqrt{35}}\bigl(\sqrt{35}\,\varepsilon_0\bigr)^{3^r},

so as long as $\sqrt{35}\,\varepsilon_0 < 1$ — i.e. $\varepsilon_0 < 1/\sqrt{35}$ , the threshold of the next lesson — the error collapses toward zero extremely quickly. This is what makes distillation practical: a handful of rounds takes physically-achievable raw error rates down to the $10^{-10}$ – $10^{-15}$ logical-error regime that large algorithms demand.[^fowler-surface]

Beyond 15-to-1

The $15$ -to- $1$ protocol is conceptually clean but wasteful: $15$ inputs (plus rejected batches) per output. A large literature improves the yield — the ratio of output to input copies. Bravyi and Haah constructed a family of $[[3k+8,\,k,\,2]]$ "triorthogonal" codes with asymptotically vanishing overhead,[^bravyi-haah] and modern surface-code architectures use multi-level distillation factories whose cost we estimate in the next two lessons. But the $15$ -to- $1$ routine remains the canonical pedagogical and practical workhorse, and its $35\,\varepsilon^3$ law is the formula to remember.