Simple Algorithm
Quantum Computing · Rydberg State · 32 min

Magic State Distillation

Buying non-Clifford gates with distilled resource states.

Clifford gates are cheap in most codes but classically simulable; the TT gate is what makes quantum computers powerful, and no transversal trick provides it in the surface code. The fix is to manufacture noisy TT states and distill them with Clifford operations alone, trading many bad copies for one good one.

What you’ll learn

  • Derive TT-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 [[15,1,3]][[15,1,3]] Reed–Muller code: ε→35ε3\varepsilon\to35\varepsilon^3, acceptance probability and threshold.
  • Derive the cost exponent γ=log⁡315≈2.46\gamma=\log_315\approx2.46, and compare with modern protocols and magic state cultivation.

Gate teleportation and the Clifford hierarchy

Let ∣T⟩=T∣+⟩=12(∣0⟩+eiπ/4∣1⟩)\ket{T}=T\ket{+}=\tfrac{1}{\sqrt2}(\ket0+e^{i\pi/4}\ket1). (Some papers call it ∣A⟩\ket{A}; Bravyi and Kitaev use the Clifford-equivalent Hadamard eigenstate.) A CNOT from the data onto ∣T⟩\ket{T}, a ZZ measurement and a conditional SS apply TT 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 ρ=(1−ε)∣T⟩ ⁣⟨T∣+ε ∣T⊥⟩ ⁣⟨T⊥∣\rho=(1-\varepsilon)\dyad{T}+\varepsilon\,\dyad{T^\perp} after twirling: ∣T⟩\ket{T} and ∣T⊥⟩=Z∣T⟩\ket{T^\perp}=Z\ket{T} are eigenvectors of the Clifford SXSX, with eigenvalues eiπ/4e^{i\pi/4} and −eiπ/4-e^{i\pi/4}, so applying SXSX at random removes the off-diagonal terms. Consuming ∣T⊥⟩\ket{T^\perp} instead of ∣T⟩\ket{T} applies ZTZT in either measurement branch: a magic-state error becomes a ZZ error on the data.

Which states can be distilled?

The six single-qubit stabilizer states sit at ±x^,±y^,±z^\pm\hat x,\pm\hat y,\pm\hat z on the Bloch sphere. Their convex hull is the stabilizer octahedron ∣rx∣+∣ry∣+∣rz∣≤1\abs{r_x}+\abs{r_y}+\abs{r_z}\le1.

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 T∣+⟩T\ket{+}, (1,1,0)/2(1,1,0)/\sqrt2, Clifford-equivalent to the Hadamard eigenstate; and face directions such as (1,1,1)/3(1,1,1)/\sqrt3, the eigenstates of the order-3 Clifford SHSH (up to phase). Their 5-to-1 protocol distills face states whose polarization exceeds 3/7≈0.65\sqrt{3/7}\approx0.65; the 15-to-1 protocol distills edge states.

Check your understanding

A noisy magic state has Bloch vector 0.6⋅(1,1,0)/20.6\cdot(1,1,0)/\sqrt2, i.e. polarization 0.60.6 along the T∣+⟩T\ket{+} direction. Can any protocol built from Cliffords distill it?

  1. No: ∣rx∣+∣ry∣≈0.85≤1\abs{r_x}+\abs{r_y}\approx0.85\le1, so it lies inside the octahedron and every such protocol is classically simulable
  2. Yes: any state that is not maximally mixed can be distilled
  3. Yes, by 15-to-1, because its polarization exceeds 1/21/2
  4. No, because it is not a pure state
Show the answer

A. No: ∣rx∣+∣ry∣≈0.85≤1\abs{r_x}+\abs{r_y}\approx0.85\le1, so it lies inside the octahedron and every such protocol is classically simulable

0.6/2≈0.4240.6/\sqrt2\approx0.424 in each of rxr_x and ryr_y, summing to 0.850.85. Inside the octahedron the state is a mixture of stabilizer states. Along this axis the boundary is at polarization 1/2≈0.711/\sqrt2\approx0.71, i.e. error ε≈0.146\varepsilon\approx0.146; this state has ε=0.2\varepsilon=0.2.

The 15-to-1 protocol

The protocol is built on the [[15,1,3]][[15,1,3]] quantum Reed–Muller code. Label its 15 qubits by the non-zero vectors of F24\mathbb{F}_2^4.

Predict before you look

A pattern e\mathbf{e} of ZZ errors passes the XX-checks undetected exactly when HXe=0H_X\mathbf{e}=0, 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 {a,b,a+b}\{a,b,a+b\}. Choose an unordered pair {a,b}\{a,b\} in (152)=105\binom{15}{2}=105 ways; each triple arises from 3 of its pairs: 105/3=35105/3=35. These are the 35 lines of the projective space PG(3,2)PG(3,2), and they fix the leading coefficient of 35ε335\varepsilon^3.

DerivationDistillation by error detection
  1. Prepare ∣+ˉ⟩\ket{\bar+} with Clifford operations, then apply T†=S†TT^\dagger=S^\dagger T to each of the 15 qubits, consuming one noisy magic state per qubit. Each injection succeeds or, with probability ε\varepsilon, adds a ZZ error: the noise is an i.i.d. ZZ-error pattern e∈F215\mathbf{e}\in\mathbb{F}_2^{15}.

  2. accept  ⟺  HXe=0  ⟺  e∈the [15,11,3] Hamming code\text{accept}\iff H_X\mathbf{e}=0\iff\mathbf{e}\in\text{the }[15,11,3]\text{ Hamming code}

    Measure the 4 XX-type checks (for instance by unencoding with Cliffords and measuring 14 qubits) and keep the output only if the syndrome is trivial.

  3. logical error  ⟺  e is a Hamming codeword of odd weight\text{logical error}\iff\mathbf{e}\ \text{is a Hamming codeword of odd weight}

    Even-weight Hamming codewords are ZZ-stabilizers (harmless); odd-weight ones are logical Zˉ\bar Z errors.

  4. εout=35 ε3+O(ε4)1−15ε+O(ε2)=35 ε3+O(ε4)\varepsilon_{\mathrm{out}} = \frac{35\,\varepsilon^3+\order{\varepsilon^4}}{1-15\varepsilon+\order{\varepsilon^2}} = 35\,\varepsilon^3+\order{\varepsilon^4}

    The lightest undetected logical errors are the 35 weight-3 triples. The acceptance probability is 1−15ε+O(ε2)1-15\varepsilon+\order{\varepsilon^2}.

  5. εout=1+15u8−15u7−u152 (1+15u8),u=1−2ε\varepsilon_{\mathrm{out}} = \frac{1+15u^8-15u^7-u^{15}}{2\,(1+15u^8)},\qquad u=1-2\varepsilon

    Exactly, by MacWilliams duality with the simplex code (weights 0 and 8): Pr⁡[accept]=116(1+15u8)\Pr[\text{accept}]=\tfrac{1}{16}(1+15u^8). Solving εout=ε\varepsilon_{\mathrm{out}}=\varepsilon gives the threshold ε≈0.141\varepsilon\approx0.141, slightly below the octahedron boundary ε≈0.146\varepsilon\approx0.146 for this axis: a thin window of non-stabilizer states that this protocol cannot distill.

The cost of distillation, and beyond

DerivationCost exponent
  1. εj+1=35 εj3 ⟹ 35 εj+1=(35 εj)3\varepsilon_{j+1}=35\,\varepsilon_j^3\ \Longrightarrow\ \sqrt{35}\,\varepsilon_{j+1} = \big(\sqrt{35}\,\varepsilon_j\big)^3

    Rescale to turn the recursion into a pure power.

  2. εk=135(35 ε0)3k\varepsilon_k = \frac{1}{\sqrt{35}}\big(\sqrt{35}\,\varepsilon_0\big)^{3^k}

    The error falls like exp⁡(−c 3k)\exp(-c\,3^k), provided 35 ε0<1\sqrt{35}\,\varepsilon_0<1.

  3. N=15k=(3k)log⁡315=O(log⁡γ(1/εout)),γ=log⁡315≈2.46N = 15^k = \big(3^k\big)^{\log_3 15} = \order{\log^{\gamma}(1/\varepsilon_{\mathrm{out}})},\qquad \gamma=\log_315\approx2.46

    Reaching εout\varepsilon_{\mathrm{out}} takes 3k∝log⁡(1/εout)3^k\propto\log(1/\varepsilon_{\mathrm{out}}), and each round multiplies the number of input states by 15 (ignoring rejections).

For a code with parameters [[n,k,d]][[n,k,d]] that distills kk states at once and suppresses errors as ε→O(εd)\varepsilon\to\order{\varepsilon^d}, the same argument gives γ=log⁡(n/k)/log⁡d\gamma=\log(n/k)/\log d. Triorthogonal codes (Bravyi & Haah, 2012) reach γ→log⁡23≈1.58\gamma\to\log_23\approx1.58; Hastings and Haah (2018) achieved γ<1\gamma<1; and constructions from 2024 using codes over larger alphabets reach constant overhead, γ=0\gamma=0, 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

  • TT is teleported from ∣T⟩=T∣+⟩\ket{T}=T\ket{+} with Clifford corrections because T∈C(3)T\in\mathcal{C}^{(3)}; after twirling, magic-state errors act as ZZ 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 [[15,1,3]][[15,1,3]] Reed–Muller code (transversal TT) gives ε→35ε3\varepsilon\to35\varepsilon^3, acceptance about 1−15ε1-15\varepsilon and threshold ε≈0.141\varepsilon\approx0.141.
  • Repeated 15-to-1 costs O(log⁡2.46(1/ε))\order{\log^{2.46}(1/\varepsilon)} states; triorthogonal and newer codes lower γ\gamma, 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.

Question 1

Why can a single-qubit state inside the stabilizer octahedron never be distilled into a magic state with Clifford operations?

  1. Because its purity is too low
  2. Because Clifford circuits cannot create entanglement
  3. Because it is a mixture of stabilizer states, and stabilizer operations map stabilizer mixtures to stabilizer mixtures
  4. Because distillation would require measurements in the TT 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.

Question 2

To leading order, the 15-to-1 protocol maps input error ε\varepsilon to…

  1. 35 ε335\,\varepsilon^3
  2. 15 ε315\,\varepsilon^3
  3. 35 ε235\,\varepsilon^2
  4. ε/15\varepsilon/15
Show the answer

A. 35 ε335\,\varepsilon^3

The code's ZZ-distance is 3, so failure needs at least three ZZ errors forming an undetected odd-weight Hamming codeword, and there are 35 such triples.

Question 3

Starting from ε=10−2\varepsilon=10^{-2}, what output error do two rounds of 15-to-1 give, to leading order?

  1. 3.5×10−53.5\times10^{-5}
  2. 1.2×10−91.2\times10^{-9}
  3. 10−810^{-8}
  4. 1.5×10−121.5\times10^{-12}
Show the answer

D. 1.5×10−121.5\times10^{-12}

Round 1: 35×10−6=3.5×10−535\times10^{-6}=3.5\times10^{-5}. Round 2: 35×(3.5×10−5)3≈1.5×10−1235\times(3.5\times10^{-5})^3\approx1.5\times10^{-12}. The cost is about 152=22515^2=225 noisy states per output, a little more once rejections are counted.

Question 4

Repeated 15-to-1 distillation needs O(log⁡γ(1/εout))\order{\log^{\gamma}(1/\varepsilon_{\mathrm{out}})} noisy states per output. What is γ\gamma?

  1. log⁡215≈3.91\log_215\approx3.91
  2. log⁡315≈2.46\log_315\approx2.46
  3. 11
  4. 35/1535/15
Show the answer

B. log⁡315≈2.46\log_315\approx2.46

Each round costs a factor 15 and cubes the error, so after kk rounds the cost is 15k15^k while log⁡(1/ε)\log(1/\varepsilon) grows like 3k3^k: γ=log⁡15/log⁡3\gamma=\log15/\log3.

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.