Magic State Distillation
Buying non-Clifford gates with distilled resource states.
Clifford gates are cheap in most codes but classically simulable; the gate is what makes quantum computers powerful, and no transversal trick provides it in the surface code. The fix is to manufacture noisy states and distill them with Clifford operations alone, trading many bad copies for one good one.
What you’ll learn
- Derive -gate teleportation from a magic state, and explain via the Clifford hierarchy why the correction is Clifford.
- Prove that states inside the stabilizer octahedron can never be distilled, and identify the magic directions.
- Analyze 15-to-1 distillation with the Reed–Muller code: , acceptance probability and threshold.
- Derive the cost exponent , and compare with modern protocols and magic state cultivation.
Gate teleportation and the Clifford hierarchy
Let . (Some papers call it ; Bravyi and Kitaev use the Clifford-equivalent Hadamard eigenstate.) A CNOT from the data onto , a measurement and a conditional apply to the data, as derived in the Excited State lesson. Why is the correction a Clifford gate?
So the only non-Clifford resource is the state itself. Noisy preparations give after twirling: and are eigenvectors of the Clifford , with eigenvalues and , so applying at random removes the off-diagonal terms. Consuming instead of applies in either measurement branch: a magic-state error becomes a error on the data.
Which states can be distilled?
The six single-qubit stabilizer states sit at on the Bloch sphere. Their convex hull is the stabilizer octahedron .
Outside the octahedron, states can be useful. Bravyi and Kitaev (2005) proved that Clifford operations plus copies of a noisy state whose Bloch vector points far enough along a magic direction are universal. There are two kinds: edge directions such as that of , , Clifford-equivalent to the Hadamard eigenstate; and face directions such as , the eigenstates of the order-3 Clifford (up to phase). Their 5-to-1 protocol distills face states whose polarization exceeds ; the 15-to-1 protocol distills edge states.
A noisy magic state has Bloch vector , i.e. polarization along the direction. Can any protocol built from Cliffords distill it?
- No: , so it lies inside the octahedron and every such protocol is classically simulable
- Yes: any state that is not maximally mixed can be distilled
- Yes, by 15-to-1, because its polarization exceeds
- No, because it is not a pure state
Show the answer
A. No: , so it lies inside the octahedron and every such protocol is classically simulable
in each of and , summing to . Inside the octahedron the state is a mixture of stabilizer states. Along this axis the boundary is at polarization , i.e. error ; this state has .
The 15-to-1 protocol
The protocol is built on the quantum Reed–Muller code. Label its 15 qubits by the non-zero vectors of .
A pattern of errors passes the -checks undetected exactly when , i.e. when the columns at the error positions sum to zero. How many weight-3 patterns pass undetected?
Show the answer
35
Three distinct non-zero vectors sum to zero exactly when they have the form . Choose an unordered pair in ways; each triple arises from 3 of its pairs: . These are the 35 lines of the projective space , and they fix the leading coefficient of .
Prepare with Clifford operations, then apply to each of the 15 qubits, consuming one noisy magic state per qubit. Each injection succeeds or, with probability , adds a error: the noise is an i.i.d. -error pattern .
Measure the 4 -type checks (for instance by unencoding with Cliffords and measuring 14 qubits) and keep the output only if the syndrome is trivial.
Even-weight Hamming codewords are -stabilizers (harmless); odd-weight ones are logical errors.
The lightest undetected logical errors are the 35 weight-3 triples. The acceptance probability is .
Exactly, by MacWilliams duality with the simplex code (weights 0 and 8): . Solving gives the threshold , slightly below the octahedron boundary for this axis: a thin window of non-stabilizer states that this protocol cannot distill.
The cost of distillation, and beyond
Rescale to turn the recursion into a pure power.
The error falls like , provided .
Reaching takes , and each round multiplies the number of input states by 15 (ignoring rejections).
For a code with parameters that distills states at once and suppresses errors as , the same argument gives . Triorthogonal codes (Bravyi & Haah, 2012) reach ; Hastings and Haah (2018) achieved ; and constructions from 2024 using codes over larger alphabets reach constant overhead, , asymptotically.
Asymptotics are not the whole story. In a surface-code machine the Clifford operations inside a factory are themselves logical operations with errors. Litinski (2019) showed that by giving the early, error-tolerant parts of a 15-to-1 factory smaller code distances, its space-time cost becomes far smaller than earlier estimates suggested.
Key takeaways
- is teleported from with Clifford corrections because ; after twirling, magic-state errors act as errors on the data.
- States inside the stabilizer octahedron are useless with Cliffords (Gottesman–Knill plus convexity); states far enough along a magic direction outside it can be distilled.
- 15-to-1 with the Reed–Muller code (transversal ) gives , acceptance about and threshold .
- Repeated 15-to-1 costs states; triorthogonal and newer codes lower , and cultivation may replace most distillation.
Check yourself
In the interactive lesson these are scored with your confidence, and what you miss comes back for review.
Why can a single-qubit state inside the stabilizer octahedron never be distilled into a magic state with Clifford operations?
- Because its purity is too low
- Because Clifford circuits cannot create entanglement
- Because it is a mixture of stabilizer states, and stabilizer operations map stabilizer mixtures to stabilizer mixtures
- Because distillation would require measurements in the basis
Show the answer
C. Because it is a mixture of stabilizer states, and stabilizer operations map stabilizer mixtures to stabilizer mixtures
Convexity plus Gottesman–Knill: the protocol on a stabilizer mixture is a mixture of stabilizer circuits, so its outputs stay in the stabilizer polytope.
To leading order, the 15-to-1 protocol maps input error to…
Show the answer
A.
The code's -distance is 3, so failure needs at least three errors forming an undetected odd-weight Hamming codeword, and there are 35 such triples.
Starting from , what output error do two rounds of 15-to-1 give, to leading order?
Show the answer
D.
Round 1: . Round 2: . The cost is about noisy states per output, a little more once rejections are counted.
Repeated 15-to-1 distillation needs noisy states per output. What is ?
Show the answer
B.
Each round costs a factor 15 and cubes the error, so after rounds the cost is while grows like : .
Further reading
- S. Bravyi & A. Kitaev, "Universal quantum computation with ideal Clifford gates and noisy ancillas", Phys. Rev. A 71, 022316 (2005).
- D. Gottesman & I. L. Chuang, "Demonstrating the viability of universal quantum computation using teleportation and single-qubit operations", Nature 402, 390 (1999).
- S. Bravyi & J. Haah, "Magic-state distillation with low overhead", Phys. Rev. A 86, 052329 (2012).
- D. Litinski, "Magic state distillation: not as costly as you think", Quantum 3, 205 (2019).
- C. Gidney, N. Shutty & C. Jones, "Magic state cultivation: growing T states as cheap as CNOT gates" (2024), arXiv preprint.