qubits are in a maximally entangled Bell state. This
protocol takes 1 to complete. The second example (c)
is the movement of a square patch into a diﬀerent tile.
For this, the square patch is enlarged by patch defor-
mation, which takes 1, and then made smaller again
at no time cost. The third example (d) is the measure-
ment of a square patch in the Y basis. For this, the
patch is deformed such that the X and Z edge are on
the same side of the patch. An ancillary patch is ini-
tialized in the |0i state and the operator Z ⊗Y between
the ancilla and the qubit is measured. The ancilla is
discarded by measuring it in the Z basis.
Translation to surface codes. As described in
Appendix A, protocols designed within this framework
can be straightforwardly translated into surface-code
operations. Essentially, patches correspond to surface-
code patches with dashed and solid edges as rough and
smooth boundaries. Thus, for surface codes with a code
distance d, each tile corresponds to d
qubits. Each time step roughly corresponds to d code
cycles, i.e., measuring all surface-code check operators
d times. We associate a time step with all surface-code
operations which have a time cost that scales with d, but
no time step with operations whose time cost is inde-
pendent of the code distance, but may still be nonzero.
For this reason, the correspondence between 1 and d
code cycles is not exact.
Two-patch and multi-patch measurements corre-
spond to (twist-based) lattice surgery [9, 11] and multi-
qubit lattice surgery , respectively, which both re-
quire d code cycles to account for measurement errors.
Qubit initialization has no time cost, since, in the case
of X and Z eigenstates, it can be done simultaneously
with the subsequent lattice surgery [9, 13]. For arbi-
trary states, initialization corresponds to state injec-
tion [13, 14]. Its time cost does not scale with d. Simi-
larly, single-qubit measurements in the X or Z basis cor-
respond to the simultaneous measurement of all phys-
ical data qubits in the corresponding basis and some
classical error correction, which does not scale with d
either. Patch deformation is code deformation, which
requires d code cycles, unless the patch becomes smaller
in the process, in which case it corresponds to single-
qubit measurements. Note that not all surface-code op-
erations are covered by this framework. An extended
set of rules is discussed in Appendix B.
In essence, the framework can be used to estimate the
space-time cost of a computation. The leading-order
term of the space-time cost – the term that scales with
– of a protocol that uses s tiles for t time steps is
st · d
in terms of (physical data qubits)·(code cycles).
The space cost is s ·d
physical data qubits. Determin-
ing the exact time cost requires special care. In some
protocols, the subleading contributions due to state in-
jection and classical processing may need to be taken
into account. For these protocols, we will show how
they can be adapted to prevent such contributions from
increasing the time cost beyond t · d code cycles.
Having established the rules of the game and the corre-
spondence of our framework to surface-code operations,
our goal is to implement arbitrary quantum computa-
tions. In this work, we discuss strategies to tackle the
following problem: Given a quantum circuit, how does
one execute it as fast as possible on a surface-code-based
quantum computer of a certain size? This is an opti-
mization problem that was shown to be NP-hard , so
the focus is on heuristics rather than a general solution.
The content of this paper is outlined in Fig. 3.
The input to our problem is an arbitrary gate cir-
cuit corresponding to the computation. We refer to the
qubits that this circuit acts on as data qubits. As we
review in Sec. 1, the natural universal gate set for sur-
face codes is Cliﬀord+T , where Cliﬀord gates are cheap
and T gates are expensive. In fact, Cliﬀord gates can
be treated entirely classically, and T gates require the
consumption of a magic state |0i+e
|1i. Only faulty
(undistilled ) magic states can be prepared in our frame-
work. To generate higher-ﬁdelity magic states for large-
scale quantum computation, a lengthy protocol called
magic state distillation  is used.
It is therefore natural to partition a quantum com-
puter into a block of tiles that is used to distill magic
states (a distillation block) and a block of tiles that
hosts the data qubits (a data block) and consumes
magic states. The speed of a quantum computer is gov-
erned by how fast magic states can be distilled, and how
fast they can be consumed by the data block.
In Sec. 2, we discuss how to design data blocks. In
particular, we show three designs: compact, intermedi-
ate and fast blocks. The compact block uses 1.5n + 3
tiles to store n qubits, but takes up to 9 to consume
a magic state. Intermediate blocks use 2n + 4 tiles and
require up to 5 per magic state. Finally, the fast block
uses 2n +
8n + 1 tiles, but requires only 1 to con-
sume a magic state. The compact block is an option for
early quantum computers with few qubits, where the
generation of a single magic state takes longer than 9.
The fast block has a better space-time overhead, which
makes it more favorable on larger scales.
Data blocks need to be combined with distillation
blocks for universal quantum computing. In Sec. 3,
we discuss designs of distillation blocks. Since magic
state distillation is the main operation of a surface-
code-based quantum computer, it is important to min-
imize its space-time cost. We discuss distillation proto-
Accepted in Quantum 2019-02-01, click title to verify 3