magic-state distillation

In plain terms

A fault-tolerant quantum computer performs most of its gates transversally, qubit by qubit, and there's always one gate left that no code handles that way. The standard solution is to keep a supply of a particular state, called a magic state, which can be spent to perform the missing gate using only the gates the machine does well. That moves the whole problem into the quality of the supply, as a noisy magic state gives a noisy gate.

Distillation cleans the supply. Take fifteen noisy copies, encode them into a code chosen so that the errors you expect either trigger a check or leave the answer correct, measure the checks, and throw the batch away if any check complains. What survives is one state whose error rate is roughly thirty-five times the cube of the rate you started with. Cubing is dramatic: one error in a hundred becomes about one in thirty thousand, and another round takes it to about one in a million million.

The counting is what makes the scheme work. Only errors that hide from every check can survive, and the lightest error pattern that hides needs three faults at once, so the cube comes from counting fault patterns rather than from any quantum subtlety. The price is the fifteen states consumed per output, and in practice the distillation factories dominate the size of a fault-tolerant machine.

In CSD

The corpus proves the fifteen-to-one protocol end to end, in four rows, so its error bound is a theorem about counted fault patterns rather than a quoted figure. The counting row establishes that exactly thirty-five weight-three patterns escape the checks and that the whole hidden family has a bounded size. The code row exhibits the encoded states and proves that applying the missing gate to each of the fifteen qubits implements the inverse of that gate on the encoded qubit, which is the identity the protocol runs on. The error row shows that the checks answer deterministically on the ideal state, that a hidden pattern acts as an encoded phase flip whose sign is the pattern's parity, and that the accepted output is the magic state up to a known correction.

The bound then follows: the probability of accepting is at least the chance that nothing went wrong, the probability of accepting a wrong answer is at most the counted patterns weighted by their probabilities, and the conditional error is their ratio. The recursion iterates that bound and the iterated rate tends to zero below one twentieth. The honest boundary is the modelling assumption that a round's output errors are again independent, and that the threshold used is a convenient sufficient value rather than the protocol's exact fixed point.

Mathematically

patternMeasure is the product of fifteen Bernoulli measures with weight p, and patternMeasure_singleton gives p^|e| (1 - p)^(15 - |e|). measure_acceptSet_ge bounds acceptance below by (1 - p)^15, and measure_wrongSet_le bounds accepted-and-wrong above by 35 p^3 + 2^11 p^5, since an accepted wrong pattern has odd weight at least three, with exactly 35 of weight three and at most 2^11 of weight five or more (the counts of ReedMuller15.lean, transported by wt_eq_weight). distillation_error_le is the ratio, and distillation_error_le_ninety weakens it to 90 p^3 for p at most 1/20.

distillIter p k iterates p to 90 p^3, distillIter_le bounds it by p (90 p^2)^k, and tendsto_distillIter concludes convergence to zero for p at most 1/20. Upstream, tTrans_logical0 and tTrans_logical1 are the transversal identity on the punctured Reed-Muller code, and the injection identity injectSlice_magicState with the channel form injectionChannel_apply are the gate-teleportation half.

The name

Sergey Bravyi and Alexei Kitaev introduced magic-state distillation in 2005, with the fifteen-to-one protocol built on the punctured Reed-Muller code, and the scheme still anchors cost estimates for fault-tolerant machines. Reed and Muller's codes date from 1954 and were designed for classical communication, so the protocol is an example of a classical construction turning out to have exactly the symmetry a quantum problem needed.

Craig Gidney and Austin Fowler later cut the overhead substantially with catalysed schemes, and the accounting of how much of a machine is distillation factory remains an active engineering question.

Related entries

• magic stateA magic state is the fuel of quantum advantage, a single special state that, consumed by otherwise classically trackable Clifford circuits, unlocks the one gate the Gottesman-Knill theorem can't simulate.
• Gottesman-Knill theoremThe Gottesman-Knill theorem marks the boundary of quantum advantage, as circuits built from the Clifford gates can be simulated classically, because in the right picture they're nothing more than linear algebra on bits.
• Clifford plus TClifford plus T is the standard universal gate set, as the Clifford gates alone are classically simulable and adding the single eighth-turn phase gate makes every unitary reachable to any accuracy you ask for.
• threshold theoremThe threshold theorem says imperfect components suffice, as long as each one fails below a fixed rate you can make a quantum computation as reliable as you like by encoding it inside itself repeatedly, and the price is only a power of a logarithm.
• transversal gateA transversal gate computes on encoded information by acting on each physical qubit separately, so a fault in one qubit stays in one qubit and the code keeps its protection while the computation runs.