Resource Cost of Distillation

Distillation works, but it is expensive, and for many proposed algorithms the magic-state factory dominates the qubit count and runtime of the whole machine. This lesson estimates that cost.

Counting raw states: the distillation tree

A multi-round factory is a tree. Each $15$ -to- $1$ block consumes $15$ inputs and produces $1$ output. To feed an $r$ -round factory, each of the $15$ inputs to the top block is itself the output of a $(r{-}1)$ -round sub-factory, and so on. Ignoring post-selection rejection, the number of raw magic states consumed per final distilled output is

N_{\text{raw}} = 15^{\,r}.

The number of rounds $r$ is set by how far the error must fall. Starting from raw error $\varepsilon_0$ and iterating $\varepsilon \mapsto 35\,\varepsilon^3$ :

\varepsilon_0 = 10^{-3} \;\xrightarrow{\ \times\ }\; \varepsilon_1 = 35(10^{-3})^3 = 3.5\times10^{-8} \;\xrightarrow{\ \times\ }\; \varepsilon_2 = 35(3.5\times10^{-8})^3 \approx 1.5\times10^{-21}.

To reach a target of $10^{-12}$ , two rounds suffice ( $\varepsilon_2 \ll 10^{-12}$ while $\varepsilon_1 = 3.5\times10^{-8}$ is not yet good enough). So $N_{\text{raw}} = 15^2 = 225$ raw magic states per distilled output — before accounting for batches thrown away on a nontrivial syndrome.

Space and time on a surface code

In a surface-code architecture each of those $15$ (or $225$ ) magic-state inputs is an encoded logical qubit occupying a patch of physical qubits, and the Clifford circuit of the protocol is realized by lattice surgery over many code cycles. A useful rule of thumb from the Fowler–Devitt–Jones analyses is that a single-level $15$ -to- $1$ factory occupies on the order of $\sim\!10^2$ – $10^3$ logical-qubit-tiles and takes on the order of $\sim\!10\,d$ code cycles (with $d$ the code distance), so a two-level factory costs roughly the square of that.[^fowler-surface] Historically, factories were projected to consume the majority of the physical qubits in a fault-tolerant machine running, say, Shor's algorithm.

Why the cost matters — and recent progress

Because $T$ count drives factory throughput, two research directions attack the cost:

Better protocols / lower overhead. Triorthogonal codes and block codes amortize many outputs per block; catalyzed $|CCZ\rangle \to 2|T\rangle$ conversions cut the per- $T$ cost substantially.[^gidney-fowler]
Reducing $T$ count in the algorithm. Fewer non-Clifford gates means fewer magic states; this is the point of $T$ -count optimization.

Litinski's re-analysis argued that, with careful surface-code layout, distillation is "not as costly as you think" — a single well-designed factory can keep up with a realistic algorithm's $T$ demand.[^litinski] Still, the basic accounting stands: every logical $T$ costs one distilled magic state, and each of those costs a tree of $\sim\!15^r$ raw inputs plus the spacetime to error-correct them all.

Try it

For raw input error $\varepsilon_0 = 10^{-3}$ and target output error $10^{-12}$ , find the smallest number of rounds $r$ of $15$ -to- $1$ distillation and return the raw-state cost $15^{r}$ per distilled output. Drive the recurrence $\varepsilon \mapsto 35\,\varepsilon^3$ yourself.

[^fowler-surface]: Fowler, Mariantoni, Martinis, Cleland, Surface codes, arXiv:1208.0928. [^gidney-fowler]: Gidney, Fowler, Efficient magic state factories…, arXiv:1812.01238. [^litinski]: Litinski, Magic State Distillation: Not as Costly as You Think, arXiv:1905.06903.

Run your code to see the quantum state.