
Magic State Distillation: Not as Costly as You Think
Daniel Litinski @ Dahlem Center for Complex Quantum Systems, Freie Universit
¨
at Berlin, Arnimallee 14, 14195 Berlin, Germany
Despite significant overhead reductions since
its first proposal, magic state distillation is often
considered to be a very costly procedure that
dominates the resource cost of fault-tolerant
quantum computers. The goal of this work is
to demonstrate that this is not true. By writ-
ing distillation circuits in a form that separates
qubits that are capable of error detection from
those that are not, most logical qubits used for
distillation can be encoded at a very low code
distance. This significantly reduces the space-
time cost of distillation, as well as the number
of qubits. In extreme cases, it can cost less to
distill a magic state than to perform a logical
Clifford gate on full-distance logical qubits.
Quantum error correction is expected to be an es-
sential part of a large-scale quantum computer [1–3].
The most promising quantum error-correcting codes
are two-dimensional topological codes such as surface
codes [4, 5]. With these codes, the preparation of log-
ical Pauli eigenstates and the measurement of logical
Pauli product operators (e.g., via lattice surgery [6–
8]) are fault-tolerant operations, which is sufficient for
fault-tolerant logical Clifford gates. However, logical
non-Clifford gates, such as T gates, cannot be executed
directly. Instead, they can be performed by preparing
a resource state that is consumed to execute a non-
Clifford gate [9]. For T gates, this resource state is a
magic state |mi = (|0i + e
iπ/4
|1i)/
√
2. Such a state
can be used to perform a π/8 rotation P
π/8
= e
−iP π/8
,
where P is an n-qubit Pauli product operator from the
set {X, Y, Z, }
⊗n
. Here, X, Y and Z are Pauli op-
erators, such that Z
π/8
corresponds to a T gate. If a
magic state is available, a logical n-qubit P
π/8
gate is
performed by measuring the logical Pauli product P ⊗Z
acting on the n qubits and the magic state, see Fig. 1.
The problem with magic states is that, with surface
codes, only faulty magic states can be prepared. They
are faulty in the sense that they are initialized with
an error probability proportional to the physical error
rate p
phys
, regardless of the code distance. If these
states are used to perform logical P
π/8
rotations, one
out of every ∼1/p
phys
logical gates is expected to be
faulty. Since faulty gates spoil the outcome of a com-
putation, but classically intractable quantum compu-
tations with a useful computational result typically in-
volve more than 10
8
T gates [10], low-error magic states
are required to execute gates with a low error probabil-
ity. One possibility to generate low-error magic states is
via a magic state distillation protocol. These protocols
are short error-detecting quantum computations that
use multiple high-error magic states to generate fewer
low-error states. Many such protocols [8, 11–21] have
been developed since magic state distillation was first
proposed [9], gradually decreasing the cost of distilla-
tion. Even though state-of-the-art protocols are orders
of magnitude more efficient than the earliest propos-
als, magic state distillation is still often described as
a costly procedure and the leading contributing factor
to the overhead of fault-tolerant quantum computing,
which is the primary motivation for research into alter-
natives to magic state distillation [22–27].
In this work, we reduce the cost of distillation by an-
other order of magnitude. On the level of circuits, none
of the distillation protocols discussed in this work are
new. Rather, the circuits are written in a way that the
number of qubits is low and the circuit depth is high.
The overhead reduction is achieved by finding surface-
code implementations of these protocols in which the
code distance of each surface-code patch is never higher
than required to achieve a specific output error prob-
ability, as was previously proposed in Ref. [21]. This
yields protocols that not only have a low space-time
cost, but also a small qubit footprint.
The cost of distillation. How does one quantify
the cost of a distillation protocol? The space-time cost
is often quantified in units of d
3
, where d is the code
distance. However, this can be confusing, if different
code distances are used in different parts of the quantum
computer. Consider an n
q
-qubit quantum computation
with n
T
T gates and a quantum computer consisting of
a block of qubits used to distill magic states and a block
of qubits used to store the n
q
data qubits and consume
Figure 1: A P
π/8
rotation on n qubits can be performed by
measuring the Pauli product operator P ⊗ Z acting on the n
qubits and a magic state |mi = (|0i + e
iπ/4
|1i)/
√
2. The
magic state is discarded via an X measurement. Measurement
outcomes of −1 of the P ⊗ Z or X measurement prompt a
P
π/4
or P
π/2
correction, respectively.
Accepted in Quantum 2019-10-30, click title to verify 1
arXiv:1905.06903v3 [quant-ph] 6 Nov 2019