# Universal Fault-Tolerant Quantum Computing with Stabiliser Codes

Paul Webster  Centre for Engineered Quantum Systems, School of Physics, The
University of Sydney, Sydney, NSW 2006, Australia  Michael Vasmer  Perimeter
Institute for Theoretical Physics, Waterloo, ON N2L 2Y5, Canada  Institute for
Quantum Computing, University of Waterloo, Waterloo, ON N2L 3G1, Canada
Thomas R. Scruby  Department of Physics and Astronomy, University College
London, London WC1E 6BT, UK  Stephen D. Bartlett  Centre for Engineered
Quantum Systems, School of Physics, The University of Sydney, Sydney, NSW
2006, Australia

###### Abstract

The quantum logic gates used in the design of a quantum computer should be
both _universal_ , meaning arbitrary quantum computations can be performed,
and _fault-tolerant_ , meaning the gates keep errors from cascading out of
control. A number of no-go theorems constrain the ways in which a set of
fault-tolerant logic gates can be universal. These theorems are very
restrictive, and conventional wisdom holds that a universal fault-tolerant
logic gate set cannot be implemented natively, requiring us to use costly
distillation procedures for quantum computation. Here, we present a general
framework for universal fault-tolerant logic with stabiliser codes, together
with a no-go theorem that reveals the very broad conditions constraining such
gate sets. Our theorem applies to a wide range of stabiliser code families,
including concatenated codes and conventional topological stabiliser codes
such as the surface code. The broad applicability of our no-go theorem
provides a new perspective on how the constraints on universal fault-tolerant
gate sets can be overcome. In particular, we show how non-unitary
implementations of logic gates provide a general approach to circumvent the
no-go theorem, and we present a rich landscape of constructions for logic gate
sets that are both universal and fault-tolerant. That is, rather than
restricting what is possible, our no-go theorem provides a signpost to guide
us to new, efficient architectures for fault-tolerant quantum computing.

##  I Introduction

Quantum computing offers the promise of efficiently solving problems that are
intractable for conventional computers. Delivering on this promise is a
challenge, because quantum systems are especially vulnerable to noise, and a
quantum advantage can easily be destroyed by decoherence. One approach to this
challenge is to use quantum error-correcting codes to construct near-noiseless
logical qubits using redundancy in many physical qubits [1, 2]. Furthermore,
to process the encoded quantum information, we require quantum logic gates
that are _fault-tolerant_ , meaning that they do not compromise the protection
of the code by significantly increasing the probability of logical errors.
Realising fault-tolerant implementations of a quantum-computationally
universal set of logical operators on a quantum error-correcting code family
is essential for scalable quantum computing.

Constructing a quantum computing architecture with a universal, fault-tolerant
gate set has been a longstanding challenge for the field, because the
existence of such a gate set for a given quantum code is highly constrained by
several no-go theorems. The most significant of these is the Eastin-Knill
theorem [3], which proves that the simplest approach to fault-tolerance –
transversal gates – cannot yield a universal gate set for any quantum code.
For particular code families, more general no-go theorems have subsequently
been proven. For example, for topological stabiliser codes, implementing gates
by locality-preserving logical operators [4] and braiding defects [5] is
insufficient for universality. The conventional wisdom is that a quantum error
correcting code cannot natively possess a universal, fault-tolerant set of
logic gates.

Notwithstanding these no-go results, a large and apparently diverse range of
approaches have been proposed to implement universal, fault-tolerant quantum
logic [18, 7, 12, 6, 11, 5, 19, 14, 13, 9, 10, 8, 22, 23, 21, 20, 15, 16, 17,
24]. The most well-known amongst these approaches is magic state distillation
[18], which lowers the logical error rate of a particular non-fault-tolerant
gate by brute force, and as such is expensive in terms of resource cost. With
distillation and more broadly, these approaches all make use of some extra
technique that lies outside the scope of the no-go theorems. The theory of
quantum computing architectures is left in an undesirable situation, where
systematic approaches to designing fault-tolerant quantum logic are highly
constrained by no-go theorems, and the ‘tricks’ used to circumvent these
constraints are _ad hoc_ and lack unifying principles. The result is a
spectrum of potential quantum computing architectures with a mix of efficient
and costly elements that are difficult to compare with each other.

In this paper, we resolve this situation for a broad class of stabiliser code
families, by identifying the structures in the sets of logical operators that
lead to such no-go theorems as well as the avenues for circumventing the
constraints of these theorems. We present two main results. First, we prove a
highly general no-go result precluding a universal set of fault-tolerant
logical operators implemented using only unitary gates. This theorem applies
to a wide range of stabiliser codes that includes concatenated stabiliser
codes and topological stabiliser codes with conventional topological order as
important subclasses. To derive this result, we generalise earlier approaches
to fault tolerance – including transversal gates [3], locality-preserving
logical operators [4], constant-depth quantum circuits [25] and braiding
logical operators [5] – to the class of _bounded-spread logical operators_.
This class of operators spreads errors by at most a factor constant in the
code size. We prove that all unitary, fault-tolerant implementations of
logical operators have bounded spread, demonstrating the necessity of the oft-
postulated relationship between fault tolerance and spread of errors. We then
prove a substantial generalisation of the Eastin-Knill theorem [3] on our
class of stabiliser code families by showing that the set of bounded-spread
logical operators cannot be universal. It then follows as a corollary that a
set of fault-tolerant logical operators implemented unitarily cannot be
universal.

With this general no-go theorem, we see that many standard approaches to fault
tolerance are indeed constrained, but because non-unitary operations can have
unbounded spread they have the potential to circumvent this constraint. This
observation leads to our second main result. We show that there are two
natural classes of approaches to circumventing the no-go result, both of which
use non-unitary operations to differentially treat correctable errors and
logical operators, and which together encompass a wide range of fault-tolerant
schemes. We describe these classes respectively as _gradational_ , which
includes code deformation and pieceable fault tolerance, and _intrinsically
fault-tolerant_ which includes state injection and code switching. The
apparent diversity of approaches to implementing a universal set of logical
operators fault-tolerantly thus emerges naturally from our analysis.

The paper is structured as follows. In Sec. II, we define fault tolerance and
related concepts. In Sec. III, we introduce the notion of bounded-spread
logical operator implementations and prove our no-go results. In Sec. IV, we
show how these results can be circumvented.

##  II Fault Tolerance

In this section we define fault tolerance of quantum logic gates on quantum
error-correcting code families. We largely follow Aharanov and Ben-Or [1],
modifying their approach to explicitly account for error-correction performed
by a decoder acting on errors, instead of simply partitioning errors into good
and bad faults. This modification allows for a more flexible construction
appropriate to a range of code families, instead of specifically to the
concatenated codes considered in Ref. [1].

Operations on quantum error-correcting codes can be described by quantum
channels acting on the physical qubits. A quantum channel is a completely-
positive trace-preserving (CPTP) map on the state of the qubits. Such a
channel admits a dual map, $\mathcal{A}$, that acts on operators on the
physical qubits and corresponds to the Heisenberg picture [26]. We use this
dual map throughout, referring to it as the quantum channel for brevity. Its
action can be expressed in terms of the action of its Kraus operators,
$A_{i}$, as

$\mathcal{A}(U)=\sum_{i}A_{i}UA_{i}^{\dagger}$ (1)

where $\sum_{i}A_{i}^{\dagger}A_{i}=I$. We refer to a quantum channel as
_unitary_ if it has only one Kraus operator, $A_{i}=A$, but we emphasise that
general quantum channels are not unitary.

We model the noise afflicting the code by a quantum channel,
$\mathcal{E}_{\eta}$, that is applied before each timestep of computation.
This noise is parameterised by a noise rate $\eta$, independent of the code.
To mitigate the effects of this noise, error correction is performed using a
decoder, $\mathcal{D}$ – a quantum channel that returns the system to the
logical subspace, correcting errors without extracting logical information.

Scalable protection against noise can be achieved with a code family – a
sequence of error-correcting codes indexed by a positive integer $l$. We
require that this code family has a threshold, i.e., that there exists a non-
zero noise rate below which the effect of noise on the logical qubits after
error correction can be arbitrarily suppressed by choosing sufficiently large
$l$. We quantify the effect of noise on the logical qubits using the
_distance_ between the noise channel followed by decoding,
$\mathcal{D}\circ\mathcal{E}_{\eta}$, and the identity channel, $\mathcal{I}$.
We use a measure of distance restricted to the logical space, since we only
require that error correction succeeds if the original state is a logical
state. A code family then has a threshold if there exists a decoder
$\mathcal{D}$ and threshold noise rate $\eta_{t}>0$ such that

$\lim_{l\to\infty}\left\|\mathcal{D}\circ\mathcal{E}_{\eta}-\mathcal{I}\right\|_{\diamond,\mathcal{L}}=0\,,\quad\text{for}\
\eta<\eta_{t}\,.$ (2)

Here, we have used the diamond norm $\|\cdot\|_{\diamond,\mathcal{L}}$
(following Ref. [1]) restricted to the logical space as our distance measure.
We refer to a decoder $\mathcal{D}$ that satisfies Eq. (2) for some
$\eta_{t}>0$ as a _thresholded decoder_.

We now consider quantum logic gates, expressed as quantum channels. In the
presence of noise, attempting to apply a quantum channel $\mathcal{A}$ will
instead result in a noisy implementation
$\mathcal{A}_{\mathcal{E}{{}_{\eta}}}$. If the time over which $\mathcal{A}$
is applied is constant in the code size then we can assume that
$\mathcal{A}_{\mathcal{E}_{\eta}}=\mathcal{A}\circ\mathcal{E}_{\eta}$; more
generally, $\mathcal{A}_{\mathcal{E}_{\eta}}$ corresponds to $\mathcal{A}$
along with the application of $\mathcal{E}_{\eta}$ before each timestep.

We define $\mathcal{A}$ to be _fault-tolerant_ if
$\mathcal{A}_{\mathcal{E}_{\eta}}$ followed by decoding approximates
$\mathcal{A}$ on the logical space to arbitrarily high precision. Precisely,
$\mathcal{A}$ is fault-tolerant for decoder $\mathcal{D}$ if there exists a
threshold noise rate $\eta_{t,\mathcal{A}}>0$ such that

$\lim_{l\to\infty}\left\|\mathcal{D}\circ\mathcal{A}_{\mathcal{E}_{\eta}}-\mathcal{A}\right\|_{\diamond,\mathcal{L}}=0\,,\quad\text{for}\
\eta<\eta_{t,\mathcal{A}}\,.$ (3)

This notion of fault tolerance is decoder-dependent. However, conventionally
the problem of constructing fault-tolerant quantum channels is considered
independently of decoding, allowing flexibility to choose any thresholded
decoder which may be optimised for other criteria such as efficiency. For this
reason, we define the decoder-independent notion of _unconditional fault
tolerance_ : a quantum channel $\mathcal{A}$ is defined to be unconditionally
fault-tolerant if it is fault-tolerant for all thresholded decoders. Since
unconditionally fault-tolerant quantum channels form the class of channels
that can be considered fault-tolerant for a code family without specification
of the decoder that is to be used, we hereafter focus on them, but further
discussion of conditionally (i.e., decoder-dependently) fault-tolerant
channels is presented in Appendix F.

Universal fault-tolerant quantum computing requires fault-tolerant
implementations of a universal set of logical operators on a code family. A
_logical operator implementation_ is a quantum channel that acts as a logical
operator on the logical space of a code. Specifically, an implementation of
logical operator $\bar{A}$ is a quantum channel such that, for any logical
operator $\bar{U}$, if $U$ is a representative of $\bar{U}$, then
$\mathcal{A}(U)$ is a representative of logical operator
$\bar{A}\bar{U}\bar{A}^{\dagger}$. A logical operator implementation can have
any action on non-logical operators. If a logical operator implementation is a
unitary quantum channel, we refer to it as a unitary implementation of a
logical operator, but we do not assume in general that logical operator
implementations are unitary. We describe a set of implementations of logical
operators as universal if they implement a universal set of logical operators.

##  III Restrictions on Sets of Fault-Tolerant Logical Gates

In this section, we present the first of our two main results, which is a
general no-go theorem restricting sets of fault-tolerant logic gates in
stabiliser code families. Building on the abstract and highly general
framework for fault tolerance outlined above, we now focus more specifically
on the case of local stochastic noise [27]. In this case, the probability of
an error decreases exponentially with its weight, so decoders typically
prioritise correcting low-weight (high probability) errors while allowing
certain high-weight (low probability) errors to be uncorrectable. For this
reason, the fault tolerance of a quantum channel with respect to this noise
model is related to the extent to which it spreads errors (i.e., increases the
weight of errors).

By considering local stochastic noise, we are lead to the notion of _bounded-
spread logical operator implementations_ – logical gates as quantum channels
that increase the weight of errors only by a factor constant in the code size.
In Sec. III.1, we introduce bounded-spread logical operator implementations
and show that, for local stochastic noise, unconditionally fault-tolerant
unitary quantum channels necessarily have bounded spread. In Sec. III.2 we
show that bounded-spread logical operator implementations are fundamentally
limited. Specifically, we show for a large class of stabiliser codes families,
including concatenated codes and conventional topological stabiliser codes
(such as surface and colour codes) that a universal set of logical operator
implementations cannot be achieved using only bounded-spread quantum channels.
For the code families to which it applies, this result significantly
generalises previous no-go results on transversal gates [28, 3], locality-
preserving logical operators [4], constant-depth quantum circuits [25] and
braiding defects [5]. Moreover, in the context of Sec. III.1, it shows that
any approach to fault-tolerant universal quantum computing must go beyond the
most natural techniques in some way – a topic we pursue further in Sec. IV. A
diagrammatic summary of the main results of this section is presented in Fig.
1.

Figure 1: Summary of the results of Sec. III. Black boxes represent conditions
on quantum channels, the red box represents an assumption on the noise model
and the blue box represents a condition on the code family. Theorem 1 states
that if the three conditions in the first column are met then the quantum
channel must have bounded spread. Theorem 2 states that if the two conditions
in the second column are met then a universal set of logical operator
implementations cannot be realised. Corollary 1 combines these theorems,
stating that if the conditions in the first column and in the blue box are all
satisfied then a universal set of logical operator implementations cannot be
realised.

###  III.1 Bounded Spread and Fault Tolerance

We here consider local stochastic noise models [27] in more detail. A noise
model is _stochastic_ if we can specify it with a set of errors $\\{E\\}$ that
occur randomly according to a probability distribution $\\{p(E)\\}$. It is
_local_ if the probability of an error decays exponentially with its weight.
(We here define the weight of a general operator to be the number of physical
qubits on which it acts non-trivially, generalising the usual notion for Pauli
operators.) General local stochastic noise models do not assume geometric
locality of errors and can include phenomena such as bias, short-range
correlations or adversarial noise, and our results apply in these cases.
However, for simplicity, we present our results explicitly for the special
case of independent and identically distributed (iid) single-qubit Pauli
errors. In this case, errors, $E$, are assumed to be in the Pauli group,
$\mathbf{P}_{n}$, and occur with probability

$p(E)=p^{\text{wt}(E)}(1-p)^{n-\text{wt}(E)}$ (4)

The _spread_ of a quantum channel is a measure of the extent to which it can
increase the weight of errors. More precisely, we define the spread of a Pauli
operator, $E\in\mathbf{P}_{n}$ under the action of a quantum channel
$\mathcal{A}$ to be

$s_{\mathcal{A}}\left(E\right)=\frac{\text{wt}\left(\mathcal{A}(E)\right)}{\text{wt}\left(E\right)}$
(5)

We define the spread of $\mathcal{A}$ to be the maximum spread of any Pauli
operator under $\mathcal{A}$:

$s_{\mathcal{A}}=\max_{E\in\mathbf{P}_{n}}s_{\mathcal{A}}(E)$ (6)

We say $\mathcal{A}$ has bounded spread if there exists a constant $C$
(independent of $l$) such that $s_{\mathcal{A}}\leq C$ for all
$l\in\mathbb{N}$.

Bounded-spread quantum channels do not significantly increase the weight of
errors. Many of the standard approaches to fault tolerance make use of
bounded-spread quantum channels (see Appendix D for examples). Indeed,
transversal gates have spread that is bounded by the number of code blocks
they act on, and so have bounded spread (assuming they act on a fixed number
of code blocks). More generally, the spread of a quantum circuit consisting of
local unitary gates scales with its depth, and so constant-depth quantum
circuits also have bounded spread. Locality-preserving logical operators in
topological codes can only grow the support of errors within a constant-size
neighbourhood around the original support [4, 29], and so also have bounded
spread. Finally, braiding defects in topological stabiliser codes is also
bounded-spread, because such braiding operations can only increase the weight
of logical operators (or uncorrectable errors) by a constant factor (as shown
in Appendix D.3) and correctable errors are corrected before they can spread
beyond a local region.

####  III.1.1 Unitary quantum channels and bounded spread

For unitary quantum channels, fault tolerance is closely related to spread. A
unitary quantum channel defined by $\mathcal{U}(E)=UEU^{\dagger}$ has noisy
counterpart
$\mathcal{U}_{\mathcal{E}{{}_{p}}}=\mathcal{U}\circ\mathcal{E}_{p}$ and so
gives rise to an error on the logical space iff $\mathcal{E}_{p}$ results in
an error $E$ such that $UEU^{\dagger}$ is uncorrectable for $\mathcal{D}$.
Intuitively, unbounded-spread unitary channels should fail to be
unconditionally fault-tolerant since they can map low weight errors, $E$,
(which occur with higher probability) to high weight errors, $UEU^{\dagger}$
(which may be uncorrectable).

We now prove that indeed unitary channels can be unconditionally fault-
tolerant only if they have bounded spread. This proof depends on the following
technical lemma which is proven in Appendix A.

######  Lemma 1.

Let $\mathcal{U}$ be an unconditionally fault-tolerant, unitary quantum
channel. Then for any single qubit error, $E_{i}$, there exists a constant $C$
(independent of $l$) such that $\text{wt}\left(\mathcal{U}(E_{i})\right)\leq
C$ for all $l\in\mathbb{N}$.

######  Theorem 1.

Let $\mathcal{U}$ be an unconditionally fault-tolerant, unitary quantum
channel. Then, $\mathcal{U}$ necessarily has bounded spread.

###### Proof.

By definition of spread, there exists an error, $E\in\mathbf{P}_{n}$ such that
$s_{\mathcal{U}}=\frac{\text{wt}\left(UEU^{\dagger}\right)}{\text{wt}\left(E\right)}$.
$E$ can be decomposed into a product of single-qubit Pauli errors,
$E=\prod_{i=1}^{\text{wt}(E)}E_{i}$. Using this decomposition,

$\displaystyle s_{\mathcal{U}}$
$\displaystyle=\frac{\text{wt}\left(UEU^{\dagger}\right)}{\text{wt}(E)}$ (7)
$\displaystyle=\frac{\text{wt}\left(U\left(\prod_{i=1}^{\text{wt}(E)}E_{i}\right)U^{\dagger}\right)}{\text{wt}(E)}$
(8)
$\displaystyle=\frac{\text{wt}\left(\prod_{i=1}^{\text{wt}(E)}UE_{i}U^{\dagger}\right)}{\text{wt}(E)}$
(9)
$\displaystyle\leq\frac{\sum_{i=1}^{\text{wt}(E)}\text{wt}\left(UE_{i}U^{\dagger}\right)}{\text{wt}(E)}$
(10) $\displaystyle\leq\frac{\text{wt}(E)\max_{1\leq
i\leq\text{wt}(E)}\text{wt}\left(UE_{i}U^{\dagger}\right)}{\text{wt}(E)}$ (11)
$\displaystyle=\max_{1\leq
i\leq\text{wt}(E)}\text{wt}\left(UE_{i}U^{\dagger}\right)$ (12)

Thus, for all errors $E$ there exists a single-qubit error $E_{i}$ such that
$s_{\mathcal{U}}\leq\text{wt}(UE_{i}U^{\dagger})$. By Lemma 1, there exists
$C$ indepedent of $l$ such that $\text{wt}(UE_{i}U^{\dagger})\leq C$. Hence,
for all $E\in\mathbf{P}_{n}$, $s_{\mathcal{U}}\leq C$ for all $l\in\mathbb{N}$
and so $\mathcal{U}$ has bounded spread. ∎

The proof of Theorem 1 illuminates the role of unitarity. Specifically, the
essential property of unitary channels, which is used in Eq. 9, is that they
act as

$\mathcal{U}\Bigl{(}\prod_{i}E_{i}\Bigr{)}=\prod_{i}\mathcal{U}\left(E_{i}\right)$
(13)

for all errors $E_{i}\in\mathbf{P}_{n}$. Thus, for unitary channels the spread
of a logical Pauli operator is lower-bounded by the maximum spread of a
single-qubit Pauli error.

We note that the converse of Theorem 1 – that bounded-spread, unitary quantum
channels are necessarily unconditionally fault-tolerant – does not follow.
Indeed, we emphasise that while correctable errors are often associated with
low-weight errors, due to entropic effects the bulk of the probability
distribution is on high weight errors (specifically, those of weight close to
$np$). For this reason, bounding the spread of errors is insufficient to
guarantee fault tolerance, since one must also consider whether a channel
shifts the support of benign high-weight errors to transform them into
uncorrectable errors. Nevertheless, the necessity of an unconditionally fault-
tolerant, unitary quantum channel having bounded spread places significant
constraints on how a universal fault-tolerant gate set can be realised, as we
now show.

###  III.2 No-Go Theorem

We here present a no-go theorem that rules out the existence of a universal
set of logical operators that admit bounded-spread implementations for a broad
class of stabiliser code families. This class of stabiliser codes includes
important code families such as conventional topological stabiliser codes and
concatenated stabiliser codes. Our result is not specific to the noise models
considered in Sec. III.1, but it takes on particular significance in this
context, because it then rules out a universal set of unconditionally fault-
tolerant logical operators being implemented by unitary quantum channels.

The no-go theorem stems from the observation that bounded-spread logical
operator implementations cannot significantly increase the weight of logical
Pauli operators of stabiliser codes, and this constrains the set of such logic
gates. Specifically, let $d_{\bar{L}}$ denote the distance of logical operator
$\bar{L}$, i.e., the minimum weight of a representative of $\bar{L}$. If
$\mathcal{A}$ is an implementation of logical operator $\bar{A}$ then it must
map representatives of logical operator $\bar{L}$ to representatives of
$\bar{A}\bar{L}\bar{A}^{\dagger}$. Because representatives of logical Pauli
operators of stabiliser codes are physical Pauli operators [30], implies that

$s_{\mathcal{A}}\geq\frac{d_{\bar{A}\bar{P}\bar{A}^{\dagger}}}{d_{\bar{P}}}$
(14)

for all logical Pauli operators, $\bar{P}$, where $s_{\mathcal{A}}$ is the
spread of $\mathcal{A}$. Thus, $\bar{A}$ can only admit a bounded-spread
implementation if

$\frac{d_{\bar{A}\bar{P}\bar{A}^{\dagger}}}{d_{\bar{P}}}\leq C$ (15)

for some constant $C$ independent of $l$ for all logical Pauli operators,
$\bar{P}$. Thus, if there is no universal set of logical operators, $\bar{A}$,
that satisfy Eq. (15) on a given code family, then the code family cannot
admit a universal set of bounded-spread logical operator implementations.

To formalise this argument, we define the subset of logical operators,
$\mathbf{L}_{\downarrow}\subseteq\mathbf{L}$, of distance at most a constant
factor larger than the code distance $d$, i.e.,

$\mathbf{L}_{\downarrow}=\left\\{\bar{L}\in\mathbf{L}\middle|\exists
C\in\mathbb{R}:\frac{d_{\bar{L}}}{d}\leq C\text{ for all
}l\in\mathbb{N}\right\\}\,.$ (16)

We also define
$\mathbf{P}_{\downarrow}=\mathbf{L}_{\downarrow}\cap\mathbf{P}_{n}$ to be the
subset of logical Pauli operators in $\mathbf{L}_{\downarrow}$. The following
lemma shows that a logical operator that admits a bounded-spread
implementation necessarily map elements of $\mathbf{P}_{\downarrow}$ to
elements of $\mathbf{L}_{\downarrow}$.

######  Lemma 2.

Let $\mathcal{A}$ be a bounded-spread implementation of logical operator
$\bar{A}$. Then

$\bar{P}\in\mathbf{P}_{\downarrow}\implies\bar{A}\bar{P}\bar{A}^{\dagger}\in\mathbf{L}_{\downarrow}\,.$
(17)

###### Proof.

If $\bar{P}\in\mathbf{P}_{\downarrow}$ then there exists a constant $C$ such
that $d_{\bar{P}}/d\leq C$. Thus,

$s_{\mathcal{A}}\geq\frac{d_{\bar{A}\bar{P}\bar{A}^{\dagger}}}{d_{\bar{P}}}=\frac{d_{\bar{A}\bar{P}\bar{A}^{\dagger}}/d}{d_{\bar{P}}/d}\geq
C^{-1}\frac{d_{\bar{A}\bar{P}\bar{A}^{\dagger}}}{d}\,.$ (18)

Thus, $\mathcal{A}$ can have bounded spread only if
$d_{\bar{A}\bar{P}\bar{A}^{\dagger}}/d$ is bounded, which implies that
$\bar{A}\in\mathbf{L}_{\downarrow}$. ∎

We define a code family to be $\mathbf{B}$-_constrained_ if the group

$\mathbf{B}=\left\langle\left\\{\bar{B}\in\mathbf{L}\middle|\bar{B}\bar{P}\bar{B}^{\dagger}\in\mathbf{L}_{\downarrow}\,\,\forall\bar{P}\in\mathbf{P}_{\downarrow}\right\\}\right\rangle$
(19)

is not universal. The following no-go theorem then follows.

######  Theorem 2.

A $\mathbf{B}$-constrained code family cannot admit a universal set of
bounded-spread logical operator implementations.

###### Proof.

By Lemma 2, the set of logical operators that admit bounded-spread
implementations is contained in the set
$\left\\{\bar{B}\in\mathbf{L}\middle|\bar{B}\bar{P}\bar{B}^{\dagger}\in\mathbf{L}_{\downarrow}\,\,\forall\bar{P}\in\mathbf{P}_{\downarrow}\right\\}$.
Thus, if the group generated by this set is not universal then the set of
bounded-spread logical operator implementations cannot be universal. ∎

This theorem implies that any approach to fault tolerance based on bounded-
spread quantum channels cannot be universal in $\mathbf{B}$-constrained code
families. Indeed, Theorem 2 implies the Eastin-Knill theorem [3] for
$\mathbf{B}$-constrained code families and the Bravyi-König theorem for
conventional topological stabiliser codes [4] (which we show below are
$\mathbf{B}$-constrained). This is also true for non-unitary, bounded-spread
implementations, such as those by braiding defects. In particular, Theorem 1
of Ref. [5] is also implied (for the case of defects with Pauli stabilisers).

From Theorem 1 and Theorem 2 we hence have the following corollary.

######  Corollary 1.

A set of unitary implementations of logical operators that are unconditionally
fault-tolerant with local stochastic noise for a $\mathbf{B}$-constrained
stabiliser code family cannot be universal.

Corollary 1 is our main no-go result. It is significant because large and
important classes of stabiliser code families are $\mathbf{B}$-constrained, as
we now show.

####  III.2.1 $\mathbf{B}$-constrained stabiliser code families

Stabiliser codes are widely used in quantum computing architectures, and many
of the most commonly-considered stabiliser code families are
$\mathbf{B}$-constrained. Here, we show that codes that are asymmetric or have
infinite disjointness are necessarily $\mathbf{B}$-constrained, which implies
that important classes of code families such as conventional topological
stabiliser codes and concatenated stabiliser codes are
$\mathbf{B}$-constrained.

Asymmetric code families are those with significantly different distances of
logical Pauli operators. Precisely, a code family is symmetric if it admits a
set of generators, $\mathbf{P}_{g}$ of the logical Pauli group such that
$d_{\bar{P}}\propto d$ for all $\bar{P}\in\mathbf{P}_{g}$. Otherwise, it is
asymmetric. Asymmetric code families are expected to be
$\mathbf{B}$-constrained, as their logical Pauli operators can be partitioned
into sets of lower-distance operators and higher-distance operators which
cannot be interchanged by bounded-spread quantum channels. This intuition can
be made precise: as shown in Appendix B, $\mathbf{L}_{\downarrow}$ for
asymmetric code families is contained in the subspace of the logical operators
spanned by $\mathbf{P}_{\downarrow}$, so $\mathbf{B}$ leaves invariant the
subspace stabilised by these logical Pauli operators, precluding universality.
Thus, asymmetric stabiliser code families are constrained by Theorem 2 and
Corollary 1.

An illustrative example of an asymmetric code family is the three-dimensional
surface code [6]. This has logical $\bar{X}$ and $\bar{Z}$ operators supported
on regions of two and one dimensions respectively, and so their ratio scales
with the linear dimensions of the code making the code family asymmeteric. For
this code family, $\mathbf{L}_{\downarrow}=\\{\bar{I},\bar{Z}\\}$ (since
$\bar{Z}$ is the only one-dimensional logical operator), so $|\bar{0}\rangle$
is stabilised by all bounded-spread logical operator implementations. This
precludes a universal set of bounded-spread logical operator implementations
and hence a universal set of unconditionally fault-tolerant logical operator
implementations by unitary quantum channels.

An alternative way for a code family to be $\mathbf{B}$-constrained is for the
group generated by $\mathbf{L}_{\downarrow}$ to be the logical Pauli group.
This is sufficient because then $\mathbf{B}$ is contained in the Clifford
group, which is not universal. A sufficient condition for this is that the
code family is symmetric and has infinite disjointness. The disjointness of a
stabiliser code is a measure of how many almost disjoint representatives there
are of each logical Pauli operator (see Appendix C or Ref. [25] for a more
precise definition) and infinite-disjointness code families are those with a
disjointness, $\Delta$, satisfying $\lim_{l\to\infty}\Delta(l)=\infty$. As
shown in Appendix B, for infinite-disjointness code families all logical non-
Pauli operators, $\bar{U}$, satisfy
$\lim_{l\to\infty}\frac{d_{\bar{U}}}{d_{\bar{P}}}=\infty$ for some logical
Pauli operator $\bar{P}$. For a code family that is also symmetric, this
implies that a generating set of logical Pauli operators is contained in
$\mathbf{P}_{\downarrow}$ while no logical non-Pauli operators are in
$\mathbf{L}_{\downarrow}$, so $\mathbf{B}$ is contained in the Clifford group.
Thus, symmetric, infinite-disjointness stabiliser code families are
constrained by Theorem 2 and Corollary 1.

An illustrative example of a symmetric, infinite-disjointness code family is
the two-dimensional surface code. This has only string-like logical Pauli
operators which all have the same distance, $l$, so it is symmetric. By
contrast, all non-Pauli logical operators, such as the Hadamard gate, have
support on the full code and so have distance $\Theta(l^{2})$. Thus, we indeed
have that $\mathbf{L}_{\downarrow}$ is the logical Pauli group and it is clear
that logical Pauli operators cannot be mapped to logical non-Pauli operators
by bounded-spread quantum channels, so the bounded-spread logical operator
implementations are indeed in the Clifford group and so not universal.

Importantly, the two cases – asymmetric and symmetric with infinite
disjointness – taken together imply that all stabiliser code families with
infinite disjointness are $\mathbf{B}$-constrained. Thus, the no-go results
apply to all infinite-disjointness code families which, as we show in Appendix
C includes a number of important classes of stabiliser code families. Indeed,
all concatenated stabiliser code families have infinite disjointness (see
Appendix C.1). Conventional topological stabiliser codes – i.e., those with
conventional topological order [32] – also all have infinite disjointness (see
Appendix C.2). These are topological stabiliser codes that can be associated
with topological quantum field theories (TQFTs) with excitations that
correspond to error syndromes and which can propagate freely throughout the
code by multiplication by stabilisers [32]. This includes all two-dimensional
topological stabiliser codes [33] and all scale and translationally symmetric
(STS) codes [34], including the surface and colour codes in all spatial
dimensions. It remains an open question whether more general classes of low-
density parity check (LDPC) codes also necessarily have infinite disjointness
and are therefore also constrained by our no-go results.

####  III.2.2 Extensions

We conclude this section by noting two extenstions of the above results.
First, for local noise it is natural to strengthen the threshold criterion in
Eq. (2) and fault tolerance criterion in Eq. (3) to require that the logical
error rate decreases exponentially in the distance of the code, i.e.,
$\left\|\mathcal{D}\circ\mathcal{E}_{p}-\mathcal{I}\right\|_{\diamond,\mathcal{L}}\sim\exp\left(-\alpha(p)\cdot
d\right)$ and
$\left\|\mathcal{D}\circ\mathcal{A}_{\mathcal{E}_{p}}-\mathcal{A}\right\|_{\diamond,\mathcal{L}}\sim\exp\left(-\alpha^{\prime}(p)\cdot
d\right)$ (for some decay rates $\alpha(p)$ and $\alpha^{\prime}(p)$ which are
positive for sufficiently low $p$) [35]. It can be shown that Corollary 1
still applies in this case. Indeed, a unitary implementation of a logical
operator, $\mathcal{U}$, that circumvents Theorem 2 necessarily spreads some
logical Pauli operator, which has weight at least $d$, by some factor $f(d)$
that is unbounded in $d$. In analogy to the proof of Theorem 1, this implies
that there is some error of weight at most $\lceil d/f(d)\rceil$ that is
spread under $\mathcal{U}$ to an error of weight at least $d$. Analogously to
the proof of Lemma 1, this implies that $\mathcal{U}$ is not unconditionally
fault-tolerant with these modified definitions, since it means there is an
error of weight at least $d$ (which can be uncorrectable) that arises as a
result of $\mathcal{U}$ with probability at least $p^{\lceil
d/f(d)\rceil}\not\sim\exp\left(-\alpha^{\prime}(p)d\right)$. Thus, our main
no-go result also applies to this modified setting.

We also note that our results for stabiliser codes straightforwardly
generalise to subsystem codes. Specifically, for subsystem codes we can define
distances and disjointness to be calculated only on the bare logical
operators. Considering only the bare logical operators is sufficient because
logical operator implementations necessarily map bare logical operators to
bare logical operators [36]. Hence, the proofs of all the results can
naturally generalise to the case of subsystem codes by considering bare
logical operators and so Theorems 1 and 2 and Corollary 1 also apply to
subsystem codes.

##  IV Universal Fault-Tolerant Logical Operator Implementations

The results of Sec. III place constraints on sets of fault-tolerant logical
operators. Importantly, however, these no-go theorems also point to the ways
in which these constraints can be circumvented. In particular, these
constraints can be overcome by using non-unitary quantum channels, which are
not constrained by Theorem 1. A logical operator implementation can have
unbounded spread but nonetheless be fault-tolerant if it differentially treats
correctable errors and logical operators. This differential treatment is the
hallmark of error-correction, which by definition corrects correctable errors
while leaving logical operators unchanged. Circumventing Corollary 1 can
therefore be achieved if error-correction can be integrated into a logical
operator implementation, to allow for transformations of logical operators to
be performed without correspondingly transforming correctable errors. As we
show in this section, a diverse range of techniques for realising a universal
set of fault-tolerant logical operator implementations can be understood as
manifestations of this idea.

The challenge in realising a logical operator implementation that integrates
error-correction into its action in this way is that the two processes cannot
be separated. Indeed, it is not sufficient to simply first perform error-
correction and then the logical operator implementation, since new errors can
arise between these processes that will not be corrected before the logical
operator implementation acts on them. There are two ways, however, that the
necessary integration can be achieved.

One way is to decompose an unbounded-spread logical operator implementation
into an unbounded-length sequence of bounded-spread logical operator
implementations. This decomposition can then be interspersed with conventional
error-correction which removes correctable errors before they are allowed to
grow too much under the action of the logical operator implementation. We
refer to such channels as _gradational_ and consider them in Sec. IV.1.

The second way is to use an unconventional approach to error-correction that
can be integrated more directly into a logical operator implementation.
Specifically, we note that error correction by teleportation (as described in
Ref. [37]) allows for simultaneous implementation of a logical operator in a
way that yields the teleportation gadget of Ref. [38]. Arguably, this idea is
what underpins standard universal, fault-tolerant schemes, of which approaches
such as state injection and code switching are variants. We refer to such
channels as _intrinsically fault-tolerant_ and consider them in Sec. IV.2.

Gradational and intrinsically fault-tolerant quantum channels represent two
broad classes of fault-tolerant logical operator implementations that can
circumvent our no-go results. Table 1 summarises their manifestations in a
range of approaches to fault-tolerantly implementing a universal set of
logical operators.

| Code Switching | Direct Implementation
---|---|---
Gradational | Code Conversion [16, 17] | Pieceable Fault Tolerance [9, 10]
| Dimensional Conversion | with Delayed Error Correction [11]
Intrinsically Fault-Tolerant | Gauge fixing [12, 14, 13] | Magic State Injection [24]
| Dimensional Jumping [15] | Coherent State Injection [5, 6, 7, 8]
Table 1: Summary of approaches to fault-tolerant, universal gate sets. The
approaches are classified as gradational or intrinsically fault-tolerant,
corresponding to the two classes presented in Sec. IV.1 and Sec. IV.2
respectively. They are also classified based on whether they are a form of
code switching (fault-tolerant mapping between two codes) or direct
implementation (of an unbounded-spread logical operator within a single code).

###  IV.1 Gradational Logical Operator Implementations

A gradational logical operator implementation is one of the form

$\mathcal{A}=\prod_{i=1}^{t}\mathcal{K}_{i}\mathcal{U}_{i}$ (20)

where each $\mathcal{U}_{i}$ is a unitary, fault-tolerant (and hence bounded-
spread) quantum channel and each $\mathcal{K}_{i}$ is a quantum channel that
allows for error-correction, but acts trivially on logical operators. The
action of such an implementation consists of channels $\mathcal{U}_{i}$ that
transform the logical space interspersed with channels $\mathcal{K}_{i}$ that
are used to remove errors to ensure that the state of the code remains in the
appropriate logical space at all times. Gradational logical operator
implementations are thus fault-tolerant by construction. However, they are not
unitary (since the channels $\mathcal{K}_{i}$ are not unitary) and so are not
constrained by Theorem 1.

Gradational logical operator implementations can be understood as the minimal
approach to circumventing Corollary 1. Indeed, gradational logical operator
implementations can be decomposed into unitary quantum channels used to
transform the logical information interspersed with error correction, which is
in the spirit of standard fault-tolerant quantum computing. However, unlike
unitary implementations of logical operators, intermediate error-correction is
integrated into the implementation of gradational logical operator
implementations themselves, and cannot be avoided by increasing the code size.
Indeed, since the spread of each timestep is bounded (as each
$\mathcal{U}_{i}$ must have bounded spread), the time taken for an unbounded-
spread, gradational logical operator implementation necessarily grows with the
size of the code size, $l$. Thus, gradational logical operator implementations
allow for universal fault-tolerant quantum computing in a natural way, but
only at the cost of introducing a significant time overhead associated with
unbounded-spread logical operator implementations.

We now consider two common approaches to fault-tolerant logic gates that are
specific examples of gradational logical operator implementations: code
deformation, and pieceable fault tolerance.

####  IV.1.1 Code Deformation

An important class of gradational logical operator implementation is _code
deformation_. A gradational implementation of logical operator $\bar{A}$ can
be constructed by decomposing a unitary implementation of $\bar{A}$ into
single and two-qubit gates. By staggering the implementation of these gates
such that only a constant number are implemented in each timestep, we can
ensure that the spread at each such timestep remains bounded. The product of
gates performed at the $i$th timestep then corresponds to a bounded-spread
unitary quantum channel $\mathcal{U}_{i}$. As a consequence of this
staggering, each $\mathcal{U}_{i}$ is not individually a logical operator
implementation, and in general will not preserve the logical space. Rather,
each $\mathcal{U}_{i}$ will map the logical code space to the logical code
space of a different code. This process can be understood as a form of code
deformation,
$\mathcal{C}\to\mathcal{C}_{1}\to\cdots\to\mathcal{C}_{m-1}\to\mathcal{C}$.
This code deformation can be interspersed with error correction performed at
the $i$th timestep by a decoder, $\mathcal{D}_{i}$ on code $\mathcal{C}_{i},$
to construct a gradational implementation of logical operator $\bar{A}$ of the
form:

$\mathcal{A}=\prod_{i=1}^{t}\mathcal{D}_{i}\mathcal{U}_{i}\,.$ (21)

Fault tolerance of such a code deformation process depends on a number of
conditions. First, each quantum channel $\mathcal{U}_{i}$ must be fault-
tolerant, which is consistent with Theorem 1 because it has bounded spread.
Second, each intermediate code family, $\mathcal{C}_{i}$, must have a
threshold so that the logical information remains protected throughout the
process. Finally, each decoder, $\mathcal{D}_{i}$ on each code
$\mathcal{C}_{i}$ must be thresholded and feasible to implement. Implementing
such a decoder can be challenging, since these intermediate codes do not
necessarily maintain important structures of the original code, such as Pauli
stabilisers, and sparsity or geometric locality of stabiliser generators.

An important first example of code deformation is braiding defects in
topological (and hypergraph product [39]) codes. While such braiding logical
operator implementations are not unitary, they nonetheless have bounded spread
(as shown in Appendix D.3) meaning that they are also constrained by Corollary
1.

An alternative type of code deformation that can allow Corollary 1 to be
circumvented is _code conversion_ [40]. Examples can be found by re-expressing
conventional code switching [14, 13, 12] as a gradational process. It involves
deforming between an initial and final code that together admit a universal
set of bounded-spread logical operator implementations, by passing through a
sequence of codes such that each mapping between successive codes has bounded
spread. One such example is concatenated Steane and Reed-Muller codes [41,
42], which are connected by codes that are mixed concatenations of each type
of code and so can be mapped between by code conversion (as detailed in
Appendix E.2) [16, 17]. This allows for the (transversal) Clifford group on
the concatenated Steane code to be supplemented by a gradational
implementation of the non-Clifford $\bar{T}$ gate to realise a universal gate
set.

A second example is _dimensional conversion_ , which is inspired by
dimensional jumping [15]. It is code conversion between topological codes of
different spatial dimensions (discussed in Appendix E.2). One such example is
between the 3D and 2D surface codes, which are connected by a sequence of 3D
surface codes on rectangular prisms. Dimensional conversion can be used to
deform between these codes to allow for the non-Clifford
$\overline{\text{CCZ}}$, which completes a universal gate set for the 2D
surface code.

Dimensional conversion on higher dimensional codes illuminates the role of
non-unitarity in circumventing Corollary 1. Specifically, (as discussed in
Appendix E.2) we can achieve a universal set of fault-tolerant logical
operator implementations by using a gradational jump between 4D and 6D surface
codes such that the codes at all timesteps are self-correcting [43, 44]. Such
self-correcting memories allow for passive error-correction, i.e. dissipation
of energy into the environment, to be used instead of active error-correction.
This shows that non-unitary dissipative channels can be used to circumvent
Corollary 1, disproving the notion that measurements and classical processing
are essential to fault-tolerantly implementing a universal gate set.

####  IV.1.2 Pieceable Fault Tolerance

Even without a convenient set of intermediate codes, a gradational logical
operator implementation can still be possible. An important example is
_pieceable fault tolerance_ [9, 10]. This approach can be used in the case of
logical operators on CSS codes where all the unitary operators, $U_{i}$, used
in the implementation of $\bar{U}$ are diagonal in the computational basis. In
this case, $Z$-type stabilisers are left unchanged throughout and so $X$
errors can be corrected in the standard way by measuring $Z$ stabilisers at
appropriate intervals and using the initial decoder for such errors. At the
same time, $Z$ errors are not spread by such an implementation and so, for
concatenated codes, their correction can be deferred until the end of the
process when the state has been returned to the original logical space [9,
10].

For topological codes, simply omitting correction of $Z$ errors at
intermediate times would undermine fault tolerance [10]. This is because the
code distance is only polynomial in the time taken by the implementation, so
unacceptably many $Z$ errors can accumulate through intermediate timesteps.
However, this can be addressed by extracting syndrome information on these
accumulated errors by making appropriate $X$ measurements on intermediate
states of the code, and later performing the corrections of $Z$ errors based
on this information at the end of the implementation of the logical operator.
This addition of _delayed error correction_ to pieceable fault tolerance can
allow for a fault-tolerant gradational implementation on topological codes
without fully implementing thresholded decoders on each intermediate code.
Indeed, as discussed in Appendix E.3, this technique can be understood as the
basis for the fault-tolerant implementation of the non-Clifford
$\overline{\text{CCZ}}$ logical operator on the two-dimensional surface code
in Ref. [11].

###  IV.2 Intrinsically Fault-Tolerant Logical Operator Implementations

Intrinsically fault-tolerant logical operator implementations are an
alternative approach to circumventing Corollary 1. Unlike gradational
implementations, intrinsically fault-tolerant implementations can be performed
in constant time (independent of code size). They require that error-
correction and the logical operator implementation are performed as a single
process, to ensure that all correctable errors present at the time the logical
operator is implemented are corrected. In particular, since errors can arise
at the beginning of a timestep at which a logical operator is implemented, we
cannot simply apply standard error-correction before or after the
implementation of the logic gate.

However, there exists an alternative approach to error correction that can
meet this requirement: error-correction can be implemented via teleportation
[37] (as in Fig. 2 with $\bar{U}=\bar{I}$). Furthermore, this technique allows
for a logical operator $\bar{U}$ to be implemented simultaneously with the
error-correction gadget [38] via gate teleportation, as shown in Fig. 2. This
provides a perspective on why this teleportation-based approach is so
effective for implementing fault-tolerant logical operators – it allows for
fault-tolerant implementation of logical operators of unbounded spread by
correcting correctable errors while transforming logical operators. The
elements of the teleportation gadget that are non-unitary are the adaptive
quantum channels – implementations of logical operators conditional on logical
measurement outcomes. These channels propagate logical operators but not
correctable errors, as needed to circumvent Corollary 1, since the former
affect the logical measurement outcome but the latter do not.

Figure 2: Teleportation gadget for intrinsically fault-tolerant implemention
of single-qubit logical operator $\bar{U}$. In the case where
$\bar{U}=\bar{I}$ it implements error-correction by teleportation. For general
$\bar{U}$, this error-correction ensures that $\bar{U}$ is implemented fault-
tolerantly.

For CSS codes, in the case of logical operator implementations that spread
errors only of one type (i.e., only $X$ or only $Z$ errors), a simplification
of this approach is possible. Specifically, in this case teleportation error-
correction is only necessary for the type of error that is spread by the
implementation of $\bar{U}$ as the other type of error can be corrected in the
standard way at a later time. This gives simplified teleportation gadgets, as
shown in Fig. 3.

(a) (b)

Figure 3: Simplified teleportation gadgets implementing $\bar{U}$ on CSS codes
that are intrinsically fault-tolerant with respect to (a)$X$ errors and (b)
$Z$ errors. (The first gate in (a) represents $\overline{\text{CNOT}}_{2,1}$
conjugated by $\bar{U}$ on the control qubit.)

Since the teleportation gadget emerges naturally from the requirements of an
intrinsically fault-tolerant logical operator implementation, it manifests in
a range of apparently distinct approaches to implementing a universal set of
fault-tolerant logical operators. In particular, we now briefly review its use
in the two most standard approaches: state injection and code switching.

####  IV.2.1 State Injection

State injection is a straightforward application of teleportation, named to
put greater emphasis on the preparation of the state in the case that the
other circuit components admit simple fault-tolerant implementations.

##### Symmetric Codes – Magic State Injection:

Infinite-disjointness codes that are symmetric (i.e., those with approximately
equal distances of logical Pauli operators) can admit only Clifford bounded-
spread logical operators (as shown by the proof of Lemma 4). Completing a
universal gate set thus requires a non-Clifford logical operator, typically
$\bar{T}$ (a logical $\bar{Z}$ rotation by $\pi/4$). Using teleportation to
implement such an operator is referred to as _magic state injection_. Using
the circuit in Fig. 3(a) with $\bar{U}=\bar{T}$, we obtain the circuit for
magic state injection shown in Fig. 4. The offline preparation of the magic
state, $\bar{T}|\bar{+}\rangle$, is generally the most challenging part of the
procedure, but this can be achieved (albeit with significant resource cost) by
magic state distillation [18]. Examples of codes for which magic state
injection can be effective include two-dimensional topological codes [45] and
concatenated Steane codes [46].

Figure 4: Magic state injection circuit obtained by letting $\bar{U}=\bar{T}$
in Fig. 3(a)

##### Asymmetric Codes – Coherent State Injection:

Asymmetric codes (i.e. those with significantly different distances of logical
Pauli operators) cannot admit bounded-spread logical operator implementations
that interchange arbitary Pauli operators (see proof of Lemma 3). For example,
such codes with a single logical qubit do not admit a bounded-spread logical
Hadamard operator, which is often sufficient to complete a universal gate set.
Letting $\bar{U}=\bar{H}$ in the circuit in Fig. 3(b) we obtain the circuit
shown in Fig. 5. We refer to this technique as _coherent state injection_
since the injected state $|\bar{+}\rangle$ is coherent – meaning that it is a
superposition of computational basis states [47]– and it is this resource that
cannot be created by bounded-spread logical operators in asymmetric codes,
analogously to magic in symmetric codes. Unlike magic states, coherent states
can be stabiliser states and thus can be prepared even in asymmetric codes in
a straightforward way and can be prepared in constant-time in codes that admit
single-shot error-correction of $X$ errors. Examples of codes for which
coherent state injection can complete a universal logical gate set include
three-dimensional surface codes [6, 5], three-dimensional colour codes [7] and
concatenated Reed-Muller codes. We note that coherent state injection can also
effectively be used for subsystem codes, such as the Bacon-Shor code [8].

Figure 5: Coherent state injection circuit obtained by letting
$\bar{U}=\bar{H}$ in Fig. 3(b)

####  IV.2.2 Code Switching

Code switching is an approach by which logical information is teleported
between two codes to complete a universal gate set. Specifically, we take two
codes, $\mathcal{C}_{1}$ and $\mathcal{C}_{2}$ and construct fault-tolerant
implementations of the logical identity between the codes; $\bar{I}_{1\to
2}:\mathcal{C}_{1}\to\mathcal{C}_{2}$ and its inverse, $\bar{I}_{2\to
1}:\mathcal{C}_{2}\to\mathcal{C}_{1}$. These operators allow any fault-
tolerant logical operator, $\bar{U}_{2}$, of $\mathcal{C}_{2}$ to be
implemented fault-tolerantly on $\mathcal{C}_{1}$ by
$\bar{U}_{1}=\bar{I}_{2\to 1}\bar{U}_{2}\bar{I}_{1\to 2}$. They are thus
sufficient to lift a set of bounded-spread logical operator implementations to
universality in the case that the union of bounded-spread logical operator
implementations of $\mathcal{C}_{1}$ and $\mathcal{C}_{2}$ is universal. In
this case, Theorem 2 implies that if $\mathcal{C}_{1}$ and $\mathcal{C}_{2}$
then $\bar{I}_{1\to 2}$ or its inverse must have unbounded spread.

The essential question for realising a universal gate set by code switching is
thus how $\bar{I}_{1\to 2}$ and $\bar{I}_{2\to 1}$ can be implemented. This
can be done by applying teleportation with the special case that
$\bar{U}=\bar{I}$. Unlike state injection, the primary challenge in
implementing this circuit is generally not state preparation, but instead the
implementation of the entangling gate between the two codes.

Code switching has been effectively used to circumvent Corollary 1 in
topological and concatenated code families. Specifically, dimensional jumping
[15] can be understood as a form of code switching between two-dimensional and
three-dimensional colour codes. Similarly, code switching can also be used to
switch between concatenated Steane and Reed-Muller codes [13, 14]. While these
code switching schemes are typically described in the language of gauge
fixing, they can be translated into essentially equivalent circuits based on
teleportation between different codes, as discussed in Appendix E.1.

##  V Conclusion

In this paper, we have provided an alternative lens through which to view
architecture design for universal, fault-tolerant quantum computing. This lens
takes the form of a general no-go result (Corollary 1), which excludes the
possibility of realising a universal set of unconditionally fault-tolerant,
unitary implementations of logical operators on a large class of stabiliser
(and subsystem) code families, including important examples like concatenated
codes and conventional topological stabiliser codes, with local stochastic
noise. With the new perspective provided by this lens, we see how natural
approaches to universal, fault-tolerant logical operator implementations can
be constructed, and how a range of apparently disparate schemes that achieve
universal fault-tolerant logic can be understood as instances of our approach.

A natural question that remains open is: in what other ways can our no-go
result can be circumvented? One approach could be to consider non-local noise
models, for which high-probability errors cannot be equated with low-weight
errors. However, while local stochastic noise is only an approximation to the
noise likely to afflict a real quantum computer, a complete physical noise
model that accounts for additional phenomena such as long-range correlated
errors is unlikely to be more conducive to fault-tolerant channels. Thus, even
if particular noise models may allow for circumvention of Corollary 1 this is
unlikely to be practical significance.

A more fruitful approach may be to allow for _conditionally fault-tolerant_
logical operator implementations – those that are fault-tolerant only with
respect to specific decoders. Indeed, one could imagine tailoring a decoder
such that a particular unbounded-spread logical operator implementation is
fault-tolerant with respect to it. This could be done if particular high-
weight errors that arise with significant probability under the action of the
channel can be made correctable for this decoder. One could then use this
channel as the basis for a universal set of logical operator implementations
that are fault-tolerant provided this particular decoder is used. Conversely,
given a particular type of decoder, which may allow for particular classes of
high-weight errors to be corrected, one could seek out unbounded-spread
logical operator implementations that are fault-tolerant with respect to this
type of decoder. An example of this approach can be seen in Ref. [19], where
unbounded-spread logical operator implementations are constructed in such a
way that low-weight errors are mapped to errors that are correctable for any
decoder that explicitly respects the concatenated structure of the code family
(see Appendix F), and a similar scheme based on homological product codes
[48]. It remains an open question how conditionally fault-tolerant logical
operator implementations can be used in general to circumvent Corollary 1.

Another approach could be to use a code family that is not
$\mathbf{B}$-constrained. Such a code family would be unconstrained by Theorem
2 and so could conceivably admit a universal set of unconditionally fault-
tolerant, unitary implementations of logical operators. As we have shown,
standard code families such as conventional topological stabiliser codes and
concatenated stabiliser codes are $\mathbf{B}$-constrained as they necessarily
have infinite disjointness. However, it is unknown whether other classes of
code families, such as topological stabiliser codes with fracton order, or
more general LDPC codes, necessarily have infinite disjointness. In
particular, since the disjointness of a code is upper-bounded by the ratio of
the number of physical qubits ($n$) to the code distance ($d$) [25], if
symmetric LDPC codes with $d$ linear in $n$ could be found then they could be
unconstrained by Corollary 1. Such a symmetric, finite-disjointness code
family could potentially allow for universal, fault-tolerant quantum computing
using only unitary quantum channels and thus may avoid the challenges and high
overheads associated with universality in standard code families.

Conversely, if more general LDPC codes are shown to have infinite disjointness
and hence are constrained by our no-go results, then the results of Sec. IV
could be applied to them to overcome this obstacle. Indeed, the analysis of
that section could serve as a template for constructing a universal set of
fault-tolerant logical operations for important code families, such as LDPC
codes with asymptotically non-zero rate. This could open up promising new
avenues for more efficient and practical fault-tolerant quantum computing.

###### Acknowledgements.

This work is supported by the Australian Research Council via the Centre of
Excellence in Engineered Quantum Systems (EQUS) project number CE170100009.
Research at Perimeter Institute is supported in part by the Government of
Canada through the Department of Innovation, Science and Economic Development
Canada and by the Province of Ontario through the Ministry of Colleges and
Universities. T.R.S. acknowledges support from University College London and
the Engineering and Physical Sciences Research Council [grant number
EP/L015242/1]. The authors would like to thank Dan Browne, Simon Burton,
Robert Harris, Aleksander Kubica and Armanda Quintavalle for helpful
discussions.

##  Appendix A Proof of Lemma 1

######  Lemma 1.

Let $\mathcal{U}$ be an unconditionally fault-tolerant, unitary quantum
channel. Then for any single qubit error, $E_{i}$, there exists a constant $C$
(independent of $l$) such that $\text{wt}\left(\mathcal{U}(E_{i})\right)\leq
C$ for all $l\in\mathbb{N}$.

###### Proof.

For single qubit error, $E_{i}$, assume that
$\text{wt}\left(\mathcal{U}(E_{i})\right)$ is unbounded (i.e. there does not
exist a constant $C$ such that $\text{wt}\left(\mathcal{U}(E_{i})\right)\leq
C$ for all $l\in\mathbb{N}$). Define a set of errors,

$\mathbf{E_{i}}=\\{E_{i}^{\alpha}\otimes R\\}$ (22)

where $R$ can be any ($n-1$)-qubit unitary and the exponent
$\alpha\in\mathbb{Z}_{2}$ satisfies

$\alpha=0\iff|\text{supp}(\mathcal{U}(E_{i}))\cap\text{supp}(\mathcal{U}(R))|\geq\frac{\text{wt}(\mathcal{U}(E_{i}))}{2}$
(23)

$\mathbf{E_{i}}$ can be understood to be a set of errors that can have any
action, $R$, on the $n-1$ qubits excluding qubit $i$, but have a specified
action of $I$ or $E$ on qubit $i$ dependent on $R$. The probability of an
error in this set occuring is thus bounded by

$p(\mathbf{E_{i}})\geq p$ (24)

By construction, all elements in the set $\mathcal{U}(\mathbf{E_{i}})$ have
support on at least half of the qubits in $\text{supp}(\mathcal{U}(E_{i}))$.
Indeed, this is clear from Eqn. 23 for elements where $\alpha=0$. For elements
where $\alpha=1$, $\mathcal{U}(E_{i}\otimes
R)=\left(UE_{i}U^{\dagger}\right)\left(URU^{\dagger}\right)=\mathcal{U}(E_{i})\mathcal{U}(R)$,
the support of which contains
$\text{supp}(\mathcal{U}(E_{i}))\setminus\text{supp}(\mathcal{U}(R))$ which
includes at least $\frac{\text{wt}(\mathcal{U}(E_{i}))}{2}$ qubits by Eq. 23.

Thus, the probability of an error in $\mathcal{U}(\mathbf{E_{i}})$ is bounded
by

$p(\mathcal{U}(\mathbf{E_{i}}))\leq\binom{\text{wt}(\mathcal{U}(E_{i}))}{\frac{1}{2}\text{wt}(\mathcal{U}(E_{i}))}p^{\frac{1}{2}\text{wt}(\mathcal{U}(E_{i}))}$
(25)

By Stirling’s approximation [49], this implies that

$\lim_{l\to\infty}p(\mathcal{U}(\mathbf{E_{i}}))\leq(4p)^{\frac{1}{2}\text{wt}(\mathcal{U}(E_{i}))}$
(26)

Since $\text{wt}\left(\mathcal{U}(E_{i})\right)$ is unbounded, there exists a
subfamily indexed by $\\{l^{\prime}\\}\subseteq\mathbb{N}$ of the code family
such that
$\lim_{l^{\prime}\to\infty}\text{wt}\left(\mathcal{U}(E_{i})\right)=\infty$.
Thus, by Eq. 26, for $p<\frac{1}{4}$,

$\lim_{l^{\prime}\to\infty}p(\mathcal{U}(\mathbf{E_{i}}))=0$ (27)

Hence, we can define a thresholded decoder, $\mathcal{D}$, such that
$\mathcal{U}(\mathbf{E_{i}})=U\mathbf{E_{i}}U^{\dagger}$ is contained in the
set of uncorrectable errors, $\mathbf{F}_{\mathcal{D}}$, on codes in the
subfamily indexed by $\\{l^{\prime}\\}$. Then, on this subfamily, the
probability of an uncorrectable error for $\mathcal{D}$ is lower-bounded by

$p\left(U^{\dagger}\mathbf{F}_{\mathcal{D}}U\right)\geq
p(U^{\dagger}\mathcal{U}\left(\mathbf{E_{i}}\right)U^{\dagger})=p(\mathbf{E_{i}})\geq
p\not\to 0$ (28)

Thus $\mathcal{U}$ is not fault-tolerant for $\mathcal{D}$, and so
$\mathcal{U}$ is not unconditionally fault-tolerant. ∎

##  Appendix B Sufficient Conditions for a Code Family to be
$\mathbf{B}$-constrained

In this appendix we show that stabiliser code families that are either
asymmetric or both symmetric and infinite-disjointness are necessarily
$\mathbf{B}$-constrained, as described in Sec. III.2. For these proofs, recall
that

$\displaystyle\mathbf{L}_{\downarrow}$
$\displaystyle=\left\\{\bar{L}\in\mathbf{L}\middle|\exists
C\in\mathbb{R}:\frac{d_{\bar{L}}}{d}\leq C\text{ for all
}l\in\mathbb{N}\right\\}$ (29) $\displaystyle\mathbf{P}_{\downarrow}$
$\displaystyle=\mathbf{L}_{\downarrow}\cap\mathbf{P}_{n}$ (30)
$\displaystyle\mathbf{B}$
$\displaystyle=\left\langle\left\\{\bar{B}\in\mathbf{L}\middle|\bar{B}\bar{P}\bar{B}^{\dagger}\in\mathbf{L}_{\downarrow}\,\,\forall\bar{P}\in\mathbf{P}_{\downarrow}\right\\}\right\rangle$
(31)

and we define stabiliser code family to be $\mathbf{B}$-constrained if
$\mathbf{B}$ is not universal.

######  Lemma 3.

An asymmetric stabiliser code family is necessarily $\mathbf{B}$-constrained.

###### Proof.

Any logical operator, $\bar{V}$, that is not expressible as a linear
combination of elements of $\mathbf{P}_{\downarrow}$ must instead have
expression in the logical Pauli basis that contains a term, $\bar{Q}$, outside
$\mathbf{P}_{\downarrow}$. This implies that for any representative, $V$, of
$\bar{V}$, there exists a representative, $Q$, of $\bar{Q}$ such that
$\text{supp}(Q)\subseteq\text{supp}({V})$. Hence $d_{\bar{V}}\geq d_{\bar{Q}}$
and so $\bar{V}\not\in\mathbf{L}_{\downarrow}$. Thus, all elements of
$\mathbf{L}_{\downarrow}$ are expressible as a linear combination of elements
of $\mathbf{P}_{\downarrow}$. Thus, $\mathbf{B}$ is a subgroup of the
normaliser of the subspace of logical operators spanned by
$\mathbf{P}_{\downarrow}$. Hence the subspace stabilised by
$\mathbf{P}_{\downarrow}$ is invariant under the action of operators in
$\mathbf{B}$. Since $\langle\mathbf{P}_{\downarrow}\rangle$ is a non-empty,
proper subgroup of $\mathbf{P}_{n}$, this subspace is a non-trivial, proper
subspace. Thus, $\mathbf{B}$ is not universal and so the code family is
$\mathbf{B}$-constrained. ∎

######  Lemma 4.

An infinite-disjointness, symmetric stabiliser code family is necessarily
$\mathbf{B}$-constrained.

###### Proof.

Let $\bar{U}$ be a non-Pauli logical operator. Then, there exists logical
Pauli $\bar{P}$ such that $[\bar{U},\bar{P}]$ is not a scalar multiple of
$\bar{I}$, which implies that for the minimum-weight representative $P$ of
$\bar{P}$ and minimum-weight representative $U$ of $\bar{U}$

$|\text{supp}(P)\cap\text{supp}(U)|\geq\text{wt}\left([U,P]\right)\geq
d_{\bar{V}}$ (32)

for some logical operator $\bar{V}$.

By the scrubbing lemma [25],

$\Delta|\text{supp}(P)\cap\text{supp}(U)|\leq\text{wt}(U)$ (33)

Rearranging and using that $d_{\bar{U}}=\text{wt}(U)$ and Eq. 32, this implies

$\frac{d_{\bar{U}}}{d_{\bar{V}}}\geq\Delta$ (34)

Since the code family is assumed to be infinite-disjointness, then taking the
limit of Eq. 34 implies

$\lim_{l\to\infty}\frac{d_{\bar{U}}}{d_{\bar{V}}}=\infty$ (35)

Thus, $\bar{U}\not\in\mathbf{L}_{\downarrow}$.

Hence, $\mathbf{L}_{\downarrow}$ is a subset of the logical Pauli group and so
also there is some non-trivial logical Pauli $\bar{P}$ in
$\mathbf{L}_{\downarrow}$. Since the code family is assumed to be symmetric,
there is some generating set $\mathbf{P}_{g}$ of the logical Pauli group such
that $\lim_{l\to\infty}\frac{d_{\bar{Q}}}{d_{\bar{P}}}\neq\infty$ for any
$\bar{Q}\in\mathbf{P}_{g}$. Thus,
$\mathbf{P}_{g}\subseteq\mathbf{L}_{\downarrow}$ and so all elements of
$\left\\{\bar{B}\in\mathbf{L}\middle|\bar{B}\bar{P}\bar{B}^{\dagger}\in\mathbf{L}_{\downarrow}\,\,\forall\bar{P}\in\mathbf{P}_{\downarrow}\right\\}$
are logical Clifford operators. Thus, $\mathbf{B}$ is contained in the logical
Clifford group, which is not universal. ∎

##  Appendix C Disjointness of Code Families

The disjointness is a measure of how many mostly disjoint representatives of
logical Pauli operators a stabiliser code has [25]. Specifically, the
$1$-disjointness is the largest integer $\Delta_{1}$ such that each logical
Pauli operator admits at least $\Delta_{1}$ representatives with mutually
disjoint support (i.e. such that no qubit is in the support of more than one
of the representatives for each logical operator). The disjointness of a code
is lower-bounded by its $1$-disjointness. In particular, for a code to be
infinite-disjointness it is sufficient that
$\lim_{l\to\infty}\Delta_{1}(l)=\infty$.

The disjointness is a generalisation of the $1$-disjointness that also
accounts for almost disjoint representatives. Specifically, the unnormalised
$c$-disjointness (for $c\geq 1$) is the largest integer,
$\Delta_{c}^{\prime}$, such that each logical Pauli operator admits at least
$\Delta_{c}^{\prime}$ representatives that are $c$-disjoint, i.e. such that no
qubit is in the support of more than $c$ of the representatives for each
logical operator. The (normalised) $c$-disjointness is the unnormalised
$c$-disjointness divided by $c$: $\Delta_{c}=c^{-1}\Delta_{c}^{\prime}$. The
disjointness of the code is the maximum value taken by the $c$-disjointness
for any $c$:

$\Delta=\max_{c\in\mathbb{Z}_{+}}\Delta_{c}$ (36)

In this appendix, we show that concatenated stabiliser code families and
conventional topological stabiliser codes families necessarily have infinite
disjointness. In each case, we also comment on possible extensions.

###  C.1 Concatenated Codes

Concatenation of quantum-error correcting codes is a natural and effective
technique for constructing code families. Specifically, for any $[[n,1,d]]$
quantum error-correcting code, $\mathcal{C}$, there exists a code family such
that $\mathcal{C}_{l}$ is an $[[n^{l},1,d^{l}]]$ code constructed by the
$l$-fold concatenation of $\mathcal{C}$. More generally, we may concatenate
different codes – by concatenating a sequence of $[[n_{i},1,d_{i}]]$ codes, we
can construct a code family such that $\mathcal{C}_{l}$ is a
$[[\prod_{i=1}^{l}n_{i},1,\prod_{i=1}^{l}d_{i}]]$ code constructed by the
concatenation of the first $l$ codes in the sequence. (We assume here that
$n_{i}$ is bounded in $i$, since the idea is that the codes used in the
concatenation should be small codes that are used as building blocks for the
large concatenated code.) The quantum threshold theorem implies that
concatenated code families indeed admit thresholded decoders [1, 2].

In order to prove that concatenated stabiliser codes (i.e. concatenated code
families where all codes in the concatenation are stabiliser codes) have
infinite-disjointness, we first prove the following lemma showing that the
disjointness of a code constructed by concatenating a pair of codes is at
least the product of the disjointnesses of the two codes.

######  Lemma 5.

Let $\Delta$ be the disjointness of a concatenated code constructed by
encoding the physical qubits of code 1, with disjointness $\delta_{1}$ into
code 2, with disjointness $\delta_{2}$. Then,
$\Delta\geq\delta_{1}\delta_{2}$.

###### Proof.

Logical operator representatives of the concatenated code are constructed by
specifying a representative of the logical operator on code $1$, and then, for
each non-trivial Pauli operator in this representative, specifying a
representative of the corresponding logical operator on code $2$. For each of
the codes, $i=1,2$, there exists $c_{i}$ such that there is a set of
$c_{i}\delta_{i}$ $c_{i}$-disjoint representatives of each logical Pauli
operator of code $i$. Using combinations of logical operator representatives
from these sets, we can construct a set of $c_{1}c_{2}\delta_{1}\delta_{2}$
representatives of any logical operator on the concatenated code. Each
physical qubit is in the support of one of these representatives only if the
chosen code $1$ logical operator representative is one of the at most $c_{1}$
with support on the block that contains this qubit and the chosen code $2$
logical operator representative is one of the at most $c_{2}$ with support on
the corresponding qubit within the block. Thus, each qubit is in the support
of at most $c_{1}c_{2}$ of the $c_{1}c_{2}\delta_{1}\delta_{2}$ logical
operator representatives. Hence,

$\Delta\geq\frac{c_{1}c_{2}\delta_{1}\delta_{2}}{c_{1}c_{2}}=\delta_{1}\delta_{2}$
(37)

∎

We now prove that concatenated codes are necessarily infinite-disjointness.

######  Theorem 3.

Concatenated stabiliser codes are infinite-disjointness

###### Proof.

The disjointness is a ratio of cardinalities of sets of representatives of
logical Pauli operators, which are necesarily upper-bounded by the number of
representatives of each logical Pauli operator (which is equal to the size of
the stabiliser group, $2^{n-k}$). Thus, since the disjointness of any non-
trivial code satisfies $\Delta>1$ [25], it follows that the disjointness is
bounded by $\Delta\geq\frac{2^{n-k}}{2^{n-k}-1}$. Since each code used in the
concatenation has a number of physical qubits, $n$, bounded by some constant
$N$, this implies that there exists a constant $C=\frac{2^{N-k}}{2^{N-k}-1}>1$
such that the disjointness of each code used in the concatenation is at least
$C$.

By induction, the disjointness, $\delta_{l}$, of the code after $l$ levels of
concatenation thus satisfies $\delta_{l}\geq C^{l}$. Indeed, this is trivial
for $l=1$ and, assuming that it is true for $l=m-1$, it follows by Lemma 5
that

$\delta_{l}\geq\delta_{l-1}\delta\geq C^{l-1}C\geq C^{l}$ (38)

where $\delta$ is the disjointness of the $l$th code in the concatenation.

Thus, the disjointness of the concatenated code, $\Delta(l)=\delta_{l}$
satisfies

$\lim_{l\to\infty}\Delta(l)\geq\lim_{l\to\infty}C^{l}=\infty$ (39)

∎

By Theorem 2 and Corollary 1 respectively, we thus have the following no-go
results for concatenated codes.

######  Corollary 2.

No concatenated stabiliser code family can admit a universal set of bounded-
spread logical operator implementations.

######  Corollary 3.

A set of unitary implementations of logical operators that are unconditionally
fault-tolerant with local stochastic noise for a concatenated stabiliser code
family cannot be universal.

These results can also be generalised to concatenated subsystem codes by
applying the same arguments to disjointness of bare logical operators (as
discussed in Sec. III.2).

We also note that concatenated codes are a special case of tensor network
codes [50] which have a tree structure. This tree structure straightforwardly
gives rise to the property of having infinite disjointness – increasing $l$
corresponds to growing the tree which increases the number of indepenent
blocks on which logical operator representatives can act, implying that the
number of (almost) disjoint such representatives grows exponentially in $l$.
An interesting question for future work concerns the disjointness of other
classes of tensor network codes, especially holographic codes [51, 52, 53].
Holographic codes have a similar structure to concatenated codes, but
correspond to more complex tensor networks in which a physical qubit can be
dependent on multiple tensors closer to the centre of the network. This
dependence makes it less clear whether sufficiently many almost disjoint
logical operator representatives can necessarily be constructed in holographic
codes for them to have infinite disjointness. We note that if they, or other
classes of tensor network codes, do not necessarily have infinite disjointness
then they could be promising candidates to circumvent our results and could
possibly realise a universal set of unitary implementations of logical
operators.

###  C.2 Conventional Topological Stabiliser Codes

Topological codes naturally correspond to code families. Specifically, a
topological stabiliser code is defined by a stabiliser group generated by
operators that are geometrically local on a lattice in $D\geq 2$ dimensions.
This group must be chosen such that all logical operators have support on a
non-local region, meaning a region of at least the size of the shortest path
across the lattice which we define as $l$. This defines a code family as
logical error rates can be arbitrarily suppressed by increasing $l$.

Within the class of topological stabiliser codes, we can identify a subclass
we refer to as _conventional topological stabiliser codes_. This subclass
includes all two-dimensional topological stabiliser codes, all scale and
translationally symmetric (STS) codes [34] including the surface and colour
codes in all spatial dimensions, and all topological stabiliser codes with
defects that use the standard encoding as defined in Ref. [5]. Conventional
topological stabiliser codes are topological stabiliser codes that have
conventional topological order [32], meaning that they can be associated with
topological quantum field theories with topological excitations that
correspond to error syndromes and which can propagate freely throughout the
code by multiplication by stabilisers. Logical Pauli operators on conventional
topological stabiliser codes have representatives that correspond to
topologically equivalent paths of an excitation through the code, such as
paths around a handle of a torus, around a topological defect, or between two
code boundaries.

Conventional topological stabiliser codes necessarily have infinite
disjointness, as we show below. This implies that, by Theorem 2 and Corollary
1 respectively, we have the following no-go results for conventional
topological stabiliser codes.

######  Corollary 4.

No conventional topological stabiliser code family can admit a universal set
of bounded-spread logical operator implementations.

######  Corollary 5.

A set of unitary implementations of logical operators that are unconditionally
fault-tolerant with local stochastic noise for a conventional topological
stabiliser code family cannot be universal.

While the proof of infinite disjointness for general conventional topological
stabiliser codes that follows is quite technical, we note that is is
straightforward to see for a number of the most common instances. Indeed, in
Fig. 6 we show visually how some of these instances can easily be seen to have
infinite disjointness.

We also note that it is unclear whether more general topological stabiliser
codes necessarily have infinite disjointness. The property for conventional
topological stabiliser codes emerges from their TQFT structure; increasing $l$
can be understood to be like fine-graining the model to allow for a greater
number of topologically equivalent paths of excitations. This generalises to
encodings on any topological stabiliser code that depend only on _topological
excitations_ , as in the defect encodings considered in Ref. [5]. However,
more general topological stabiliser codes (in $D\geq 3$ dimensions) can have
more exotic excitation structures integral to their encoding [32], which makes
it unclear whether they necessarily must also have infinite disjointness. In
particular, it is known that the locality-preserving logical operators
admitted by such codes cannot be universal [4], but if finite-disjointness
topological stabiliser codes are possible it could nonetheless be the case
that more general fault-tolerant, unitary implementations of logical operators
could be sufficient for universality. This is an interesting question for
future work.

(a)

Figure 6: Illustrations of infinite disjointness of examples of conventional
topological stabiliser codes.
(a) Toric code: Logical operator representatives correspond to topologically
non-trivial loops around the torus. Specifically, $\bar{X}_{1}$ and
$\bar{Z}_{2}$ are vertically oriented loops, $\bar{X}_{2}$ and $\bar{Z}_{1}$
are horizontally oriented loops and products such as $\bar{Y}_{1}$ and
$\bar{Y}_{2}$ are diagonally oriented loops (which go around both holes).
Disjoint representatives of each logical operator correspond to parallel loops
around the torus (e.g. translating the red loop gives a disjoint,
topologically equivalent grey loop). The disjointness of the code is thus
lower-bounded by the circumference around the torus, which is grows with $l$.
(b) Colour code: Logical operator representatives correspond to topological
excitations that traverse to all three boundaries. Labelling the height of the
triangle, $l$, we can construct $l$ representatives (of the kind shown in red
and grey) such that each qubit is in the support of at most two of the
representatives). The disjointness is thus bounded by $\frac{l}{2}$ which goes
to infinity
(c) 3D surface code: $\bar{Y}$ logical operator representatives correspond to
the paths of point-like charge between top and bottom faces and a line-like
flux stretching from front to back passing from left face to right. We can
construct $l$ representatives (of the kind shown) so that each qubit is only
in the support of at most two of the representatives. Since the $\bar{X}$ and
$\bar{Z}$ operators are simply planes and columns and so have $l$ disjoint
representatives, this implies that the disjointness of the code is at least
$\frac{l}{2}$.

####  C.2.1 Proof of Infinite Disjointness

A code on a given lattice has a set of paths through the lattice. We allow
such paths to have discontinuities, provided they are locally continuous. We
define two paths to be topologically equivalent if one can be deformed into
the other. We thereby define equivalence classes of paths, $\alpha_{i}$, such
that two paths are in the same class iff they are topologically equivalent.
Such classes of paths can be defined by, for example, the boundaries they pass
between or the defects (such as holes or twists) that they enclose. We define
a notion of product of classes whereby $\alpha_{ij}=\alpha_{i}\alpha_{j}$
denotes the equivalence class of paths that are a representative path of
$\alpha_{i}$ followed by a representative path of $\alpha_{j}$. We can specify
an independent generating set of classes of paths, $A=\\{\alpha_{j}\\}$ with
respect to this product.

A logical Pauli operator, $\bar{P}$ on a conventional topological stabiliser
code can be defined by associating a list of excitations of the TQFT,
$E_{\bar{P}}=\\{p_{j}\\}$ with each class of paths, $\alpha_{j}\in A$. By
this, we mean that that representatives of $\bar{P}$ are compositions of
$p_{j}$ traversing a representative path of $\alpha_{j}$, for all $j$. We
refer to a generating path class $\alpha_{j}\in A$ as _encoding_ if there is
some $\bar{P}$ for which $p_{j}$ is not trivial (i.e. such that an excitation
that is not the vacuum must traverse a path in $\alpha_{j}$ to implement
$\bar{P}$). The following lemma shows that encoding generating path classes
necessarily have as many disjoint representatives as the code distance (which
is necessarily extensive in $l$).

######  Lemma 6.

Let $\alpha_{j}\in A$ be an encoding generating path class on a code with
distance $d$. Then, there exist at least $d$ disjoint representatives of
$\alpha_{j}$.

###### Proof.

Assume that there are not $d$ disjoint representatives. Then, there exists
some region of the code that is a _bottleneck_ for $\alpha_{j}$, by which we
mean that there is a set of less than $d$ qubits on which all representatives
must have support. However, by the cleaning lemma [54], we can necessarily
clean all logical operators off this bottleneck so that it acts trivially
there. Thus, no logical operator can have a non-trivial excitation on
$\alpha_{j}$, and so $\alpha_{j}$ is not an encoding path. ∎

We now prove that conventional topological stabiliser codes necessarily have
infinite disjointness. To do so, we make the assumption that the number of
independent generating path classes is constant in $l$, which is true if the
genus of the (hyper)-surface and the number of boundaries and defects are all
constant. This assumption is justified by the fact that code families are
intended to provide improved protection on a given topology by increasing code
size, rather than altering this topology.

######  Theorem 4.

Conventional topological stabiliser codes are infinite-disjointness.

###### Proof.

Let $\bar{P}$ be a logical Pauli operator. Representatives of $\bar{P}$
correspond to a choice of representative paths from each encoding generating
path class, $\alpha_{j}$. By Lemma 6, we can choose $d$ representatives of
$\bar{P}$ such that the representatives from each $\alpha_{j}$ are disjoint.
Thus, the number of these representatives of which any qubit is in the support
is at most the number of encoding generating path classes which by assumption
is a constant, $C$, in $l$. Thus, the disjointness is bounded by
$\Delta=\frac{d}{C}$ and so $\lim_{l\to\infty}\Delta=\infty$. ∎

##  Appendix D Examples of Bounded-Spread Logical Operator Implementations

In this appendix, we review important classes of bounded-spread logical
operator implementations. Specifically, we identify such classes, consider
their fault tolerance and show that they indeed have bounded spread. This is
important for two reasons. First, it verifies the consistency of Theorem 1
with past work that has explored logical operator implementations in these
classes as fault-tolerant. Second, it shows the breadth of direct
applicability of Theorem 2 to a range of types of logical operator
implementations, independent of assumptions on the noise model or unitarity.

###  D.1 Transversal Gates

A transversal gate is a logical operator implementation that can be decomposed
into a tensor product of physical unitary operators such that no more than one
physical qubit from each code block is in the support of each of these
operators [3]. Transversal gates are generally assumed to be fault-tolerant on
any code family. Indeed, with an unbiased noise model (i.e. where the
probability of errors depends only on the support of the error) transversal
gates acting on a single block are unconditionally fault-tolerant as they
preserve the probability of errors, and so leave the probability of an
uncorrectable error unchanged. More generally, if all code blocks are assumed
to be identical and decoded in the same way, then transversal gates across any
constant number of code blocks are also unconditionally fault-tolerant. To see
this, group corresponding qubits on different blocks into sites and note that
an uncorrectable error can arise under the action of a transversal gate only
if errors occur at every site corresponding to the support of an uncorrectable
error. Since the probability of an error at a site is constant in the size of
the code, $l$, there exists a threshold for such a logical operator
implementation if there is a threshold for the code family.

The fault tolerance of transversal gates means that Theorem 1 implies that
they must have bounded spread. Indeed, transversal gates clearly have a spread
upper-bounded by the number of code blocks on which they act, which means that
they indeed have bounded spread (when acting on a cosntant number of code
blocks). This corroborates that transversal gates indeed cannot be universal
on $\mathbf{B}$-constrained code families, by Theorem 2. Indeed, the fact that
transversal gates do not spread errors at all within a code block means that
the requirement of infinite disjointness can be dropped and so Theorem 2 can
be generalised for transversal gates on any stabiliser code family [25]. In
fact, it is known by other means that transversal gates cannot be universal on
any code family [3].

###  D.2 Locality-Preserving Logical Operators

A locality-preserving logical operator is a type of logical operator
implementation on topological codes that preserves the locality of errors.
Locality-preserving logical operator implementations are typically unitary,
but we do not assume that they necssarily are. We do assume, however, that
they take constant time (since they only require interactions across regions
of constant size) and so such an implementation $\mathcal{A}$ has noisy
counterpart
$\mathcal{A}_{\mathcal{E}_{\eta}}=\mathcal{A}\circ\mathcal{E}_{\eta}$.

Locality-preserving logical operators are fault-tolerant with respect to
thresholded decoders for which correctability of errors is associated with
their locality. This is because in this case $\mathcal{A}(E)$ has support
contained in a local region around the support of $E$ so, if $E$ is
correctable then $\mathcal{A}(E)$ must also be correctable (for sufficiently
large $l$), meaning that $\left(\mathcal{D}\circ\mathcal{A}\right)(E)$ must be
equivalent to the identity.

Locality-preserving logical operators also have bounded spread. Indeed, a
locality-preserving logical operator, $\mathcal{A}$, maps an operator, $E$, to
$\mathcal{A}(E)$ with support contained in an $\epsilon$-neigbourhood around
$\text{supp}(E)$, for some constant $\epsilon$. In a $D$-dimensional code,
such an $\epsilon$-neighbourhood is contained in the union of $D$-cubes with
side length $2\epsilon+1$ centred on each qubit in the support of $E$. Thus,
the spread of any error, $E$, under the action of a locality-preserving
logical operator is bounded by

$s_{\mathcal{A}}(E)\leq\frac{\text{wt}(E)(2\epsilon+1)^{D}}{\text{wt}(E)}=(2\epsilon+1)^{D}$
(40)

and so they indeed have bounded spread. Since they have bounded spread,
locality-preserving logical operators are not sufficient for universal quantum
computing on infinite-disjointness or asymmetric codes, by Theorem 2. In
particular, this applies to conventional topological stabiliser codes (since
they are infinite-disjointness). This is consistent with existing no-go
results constraining the gate sets implementable by locality-preserving
logical operators [4, 36, 29].

###  D.3 Braiding Defects

Another common approach to fault tolerance in topological codes is the
introduction of defects which can be braided to implement logical operators
[5, 59, 55, 57, 56, 58, 60]. More recently, it has been shown that this
approach can also be taken in non-topological LDPC codes, such as hypergraph
product codes [39] Braiding defects is a form of code deformation and so can
be fault-tolerant provided that thresholded decoders can be applied at
intermediate times to meet the requirements discussed in Sec. IV.1.1. This is
relatively easy to achieve in this case, since the fact that each of the
intermediate codes differ only by the configuration of defects means the same
approach to decoding can be taken in all cases.

General code deformations are not constrained by Corollary 1, since they are
non-unitary. However, it is known that braiding defects in topological
stabiliser codes cannot be universal [5]. This is because logical operators
implemented by braiding defects are bounded-spread and so are constrained by
Theorem 2.

Indeed, assume that the standard encoding into defects is used [5]. Assume
also that all topologically non-trivial paths in a topological stabiliser code
with defects all have lengths that are $\Theta(l)$, meaning that they differ
by at most a constant factor in the size of the code. This is reasonable for
the purpose of understanding the logical operators implementable by braiding,
since it can be satisfied by choosing appropriate sizes and separations of
defects and the action of a braiding logical operator on the logical space is
independent of these factors. Under this assumption, all non-trivial braiding
processes are topologically equivalent to a product of processes in which each
point on a defect is moved through a distance $\Theta(l)$. Since the image of
a logical Pauli operator under the action of a braiding logical operator can
be represented by the topological excitation used to implement the original
logical operator following a (possibly different) braiding process [5], and
all braiding processes differ by a factor, $c$, bounded in $l$, the spread of
any logical Pauli operator, $\bar{P}$, by braiding logical operator
implementation $\mathcal{B}$ is bounded by

$S_{\mathcal{B}}(\bar{P})\leq c$ (41)

An example of the bounded spread of logical operators under braiding is shown
in Fig. 7.

Meanwhile, decoding during braiding corrects all local errors (which hence are
removed before they are spread beyond a constant-size region), and maps only
errors of weight proportional to the code distance to logical Pauli operators,
which increases their weight only by a constant. Thus, the spread of errors
under braiding is also bounded. Hence, braiding defects necessarily has
bounded spread.

Thus, a universal set of logical operator implementations cannot be realised
by braiding defects in topological stabiliser codes, in spite of the fact that
such implementations are non-unitary. This is an example of where Theorem 2
can be significant in its own terms, even when Theorem 1 and hence Corollary 1
are not applicable.

Figure 7: Example of a logical operator implemented by braiding defects. The
defect configuration is four holes, such that the closest holes are separated
by a distance $l$. Braiding one hole around another grows the support of a
string-like logical operator of length $l$ (blue) but it remains string-like
and of length $\Theta(l)$, so its spread under the braid is constant.

##  Appendix E Examples of Fault-Tolerant, Unbounded-Spread Logical Operator
Implementations

In this appendix, we provide further details on approaches to universal fault-
tolerant quantum computing. Specifically, we first consider code switching,
both as an intrinsically fault-tolerant process and as a gradational process.
We then consider pieceable fault tolerance with delayed error correction.

###  E.1 Code Switching

Code switching is a useful technique between two codes that have sets of
logical operators admitting bounded-spread implementations such that the union
is a universal gate set. We have examples of such codes for both concatenated
and topological code families. In particular, the Steane code admits
transversal implementations of the full Clifford group, while the Reed-Muller
code admits a transversal implementation of a non-Clifford ($\bar{T}$) logical
operator. (See Table 2 for the definitions of these codes.) These codes can be
concatenated to construct code families – the concatenated Steane code and
concatenated Reed-Muller code respectively. Alternatively, the codes can be
generalised to (conventional) topological stabiliser code families – the
Steane and Reed-Muller codes are the smallest instances of the two-dimensional
triangular and three-dimensional tetrahedral colour codes respectively. In
both cases, the code families inherit the transversal gates of the original
codes. Code switching between the Steane and Reed-Muller codes can thus be
used as a basis for realising a universal gate set with these code families.

| Steane Code | Reed-Muller Code
---|---|---
Stabiliser | $X_{1}X_{2}X_{3}X_{4}$ | $X_{1}X_{2}X_{3}X_{4}X_{8}X_{9}X_{10}X_{11}$
Generators | $X_{2}X_{3}X_{5}X_{6}$ | $X_{2}X_{3}X_{5}X_{6}X_{9}X_{10}X_{12}X_{13}$
| $X_{3}X_{4}X_{5}X_{7}$ | $X_{3}X_{4}X_{5}X_{7}X_{10}X_{11}X_{12}X_{14}$
|  | $X_{8}X_{9}X_{10}X_{11}X_{12}X_{13}X_{14}X_{15}$
| $Z_{1}Z_{2}Z_{3}Z_{4}$ | $Z_{1}Z_{2}Z_{3}Z_{4}$
| $Z_{2}Z_{3}Z_{5}Z_{6}$ | $Z_{2}Z_{3}Z_{5}Z_{6}$
| $Z_{3}Z_{4}Z_{5}Z_{7}$ | $Z_{3}Z_{4}Z_{5}Z_{7}$
|  | $Z_{8}Z_{9}Z_{10}Z_{11}$
|  | $Z_{9}Z_{10}Z_{12}Z_{13}$
|  | $Z_{10}Z_{11}Z_{13}Z_{14}$
|  | $Z_{12}Z_{13}Z_{14}Z_{15}$
|  | $Z_{1}Z_{4}Z_{8}Z_{11}$
|  | $Z_{2}Z_{5}Z_{9}Z_{12}$
|  | $Z_{6}Z_{7}Z_{13}Z_{14}$
Logical | $X_{1}X_{2}X_{3}X_{4}X_{5}X_{6}X_{7}$ | $X_{1}X_{2}X_{3}X_{4}X_{5}X_{6}X_{7}$
Operators | $Z_{1}Z_{2}Z_{3}Z_{4}Z_{5}Z_{6}Z_{7}$ | $Z_{1}Z_{2}Z_{3}Z_{4}Z_{5}Z_{6}Z_{7}$

Table 2: Stabiliser generators and logical operators of the Steane and Reed-
Muller codes.

This code switching can be done fault-tolerantly by using the circuits in Fig.
3. Specifically, there is a transversal implementation of
$\overline{\text{CNOT}}$ with the control on the Reed-Muller (or concatenated
Reed-Muller or 3D colour) code and target on the Steane (or concatenated
Steane or 2D colour) code. Combined with standard techniques for preparing
stabiliser states and performing fault-tolerant logical Pauli measurements in
CSS codes, this allows for a logical state of the Reed-Muller (or concatenated
Reed-Muller or 3D colour) code to be mapped to the same logical state of the
Steane (or concatenated Steane or 2D colour) code by using the circuit in Fig.
3(b) with the first wire being the former code and the second code the latter.
The inverse mapping can similarly be implemented using the circuit in Fig.
3(a).

We emphasise that while codes based on Steane and Reed-Muller codes serve as
useful examples, code switching can be used more generally to achieve a
universal fault-tolerant gate set. Of particular importance for its
relationship to other schemes discussed below, we note that the 2D and 3D
surface codes similarly admit a tranversal implementation of
$\overline{\text{CNOT}}$ between them, and so switching can similarly be
performed between them. The 2D surface code admits a bounded-spread
implementations of the logical Clifford group, while the 3D code admits a
bounded-spread implementation of a non-Clifford ($\overline{\text{CCZ}}$)
logical operator, and so a universal set of fault-tolerant logical operator
implementations can be realised by code switching between these codes.

Our notion of code switching is fundamentally similar to a number of important
schemes for fault tolerant universal sets of logical operator implementations.
In particular, Ref. [13] presents a technique for switching between Steane and
Reed-Muller codes by making appropriate stabiliser measurements of the code
being switched into, and applying appropriate corrections conditionally on the
measurement outcomes. This scheme can be understood to differ from the code
switching technique we have described only in that the physical qubits of the
Steane code are considered to be a subset of those of the Reed-Muller code.
Due to the related structures of the two codes, this allows for operations
that act only on these qubits (specificially, the transversal
$\overline{\text{CNOT}}$ and measurements on these qubits) to be omitted,
producing a potentially more efficient scheme. This technique can be
generalised to concatenated Steane and concatenated Reed-Muller codes by
performing the same operations at all levels of concatenation. While this
scheme is physically different from our code switching technique, we emphasise
that it retains the essential spirit. Specifically, the measurements performed
during switching and corresponding corrections can be understood to introduce
non-unitarity into the logical operator implementation, by allowing for
correctable errors to be detected and corrected during the implementation.
Since these corrections can be necessary even in the absence of noise, and can
only be corrected based on measurements made during the logical operator
implementation, this process differs from standard error correction, and thus
highlights the implementation’s intrinsically fault-tolerant nature. As
described in Ref. [13], the scheme can also be related to using gauge fixing
of a subsystem code to realise the Steane and Reed-Muller codes as required
[14]. This process of gauge fixing similarly is an intrinsically fault-
tolerant process that uses measurement and adaptive corrections to circumvent
Corollary 1.

Dimensional jumping, which switches between topological stabiliser codes of
different dimensions, can similarly be understood as a variation on our code
switching scheme. Indeed, switching between 3D and 2D colour codes in the way
described in Ref. [15] is similar to the scheme of Ref. [13], in that it
corresponds to the case where the physical qubits of the 2D code are a subset
of those of the 3D code, which again allows some operations to be omitted
without fundamentally altering the approach used to circumvent Corollary 1.
Similar to above, this procedure can also be equivalently understood in terms
of fixing the gauge of a subsystem code (the gauge colour code) [12].

###  E.2 Code Conversion

While code switching can be implemented intrinsically fault-tolerantly, it is
also possible to modify it into a gradational process – code conversion. Code
conversion has the advantage that all measurements and adaptively applied
operators correspond to standard error-correction on the intermediate codes.
This means that, in the case where decoders can be used on the intermediate
codes that are analogous to those of the codes being switched between,
standard error-correction and unitary implementations of logical operators can
be sufficient for switching and hence for a universal gate set. Indeed, in the
case where all codes involved are self-correcting, it allows for a universal
gate set without requiring any measurements and adaptive gates.

As a first example, note that it is straightforward to construct a code
conversion scheme for concatentated codes, such as the concatenated Steane and
Reed-Muller codes. To do so, we first construct a unitary circuit to switch
between Steane and Reed-Muller codes. With qubits numbered as in Table 2, such
a circuit for switching from the Steane code to the Reed-Muller code is
$\prod_{i=1,5,7}\text{CNOT}_{i+7,15}\prod_{i=1}^{7}\text{CNOT}_{i,i+7}$, where
controls are on the Steane code and targets on the Reed-Muller code. The
inverse of this circuit,
$\prod_{i=1}^{7}\text{CNOT}_{i,i+7}\prod_{i=1,5,7}\text{CNOT}_{i+7,15}$,
switches from the Reed-Muller code to the Steane code. Switching between the
concatenated codes can then be performed by applying this circuit at one level
of concatenation at a time. Since the CNOT operators are transversal at lower
levels of concatenation, the spread of this circuit applied at a single level
of concatenation does not scale with $l$ and so remains bounded. Indeed, such
a circuit applied at a single level of concatenation is fault-tolerant.

It is straightforward to perform error correction at each intermediate step,
since the intermediate codes remain concatenated codes and so can be decoded
one level at a time. Thus, a code conversion can be performed,
$\mathcal{I}=\prod_{i=1}^{l}\mathcal{D}_{i}\mathcal{U}_{i}$, where $l$ is the
number of levels of concatenation, each $\mathcal{D}_{i}$ is a decoder for the
appropriate concatenated code and $\mathcal{U}_{i}$ is the unitary quantum
channel performing the necessary code switch at the $i$th level of
concatenation. This allows the universal set of logical operator
implementations to be achieved, analogously to for intrinsically fault-
tolerant code switching, using gradational logical operator implementations.
We note that this scheme is related to other proposed code switching schemes
[16, 17], but differs in that we use unitary quantum channels instead of
measurements to perform switching.

####  E.2.1 Dimensional Conversion

It is also possible to perform code switching between different topological
stabiliser codes – dimensional jumping – gradationalally. In particular, we
consider the example of code conversion between (planar) surface codes in
different dimensions, called dimensional conversion.

Specifically, we consider a three-dimensional surface code on an $l\times
l\times l$ cubic lattice and a two-dimensional surface code on an $l\times l$
square lattice. These two codes together have a universal set of bounded-
spread logical operator implementations (Clifford + $\overline{\text{CCZ}}$)
and are connected by a sequence of three-dimensional surface codes on
asymmetric $l\times l\times a$ lattices, for $1\leq a<l$ (as shown in Fig. 8).
Each of these intermediate codes can be error-corrected using any thresholded
three-dimensional surface code decoder. Thus, code conversion between these
codes can be performed if unitary, bounded-spread implementations for
switching between codes on $l\times l\times a$ and $l\times l\times(a+1)$
lattices can be found (for $0\leq a<l$).

Figure 8: Sequence of surface codes through which dimensional conversion
deforms to transform between the standard three-dimensional ($l\times l\times
l$) surface code (far left) and two-dimensional ($l\times l$) surface code
(far right).

We can indeed perform such switches. Specifically, a 2D layer can be added to
produce an $(l\times l\times(a+1))$ surface code by using a locality-
preserving, unitary circuit to appropriately entangle the additional layer to
the boundary of an $(l\times l\times a)$ surface code. Indeed, this can be
done using a product of nearest-neighbour CNOT operators, as described in Sec.
IX of Ref. [61]. A layer can be removed by performing the inverse circuit
between the boundary that is to be removed and the adjanent 2D layer of the
code (see Fig. 9). Since both switches are locality-preserving, they
necessarily have bounded-spread as required. We note that successively adding
layers gives a unitary circuit to encode a 3D surface code from 2D slices,
similar to Ref. [61], but with the addition of intermediate error-correction
to ensure fault tolerance.

The process of dimensional conversion can also be applied between more general
pairs of surface codes by an analogous process. In particular, we note that
dimensional conversion between the symmetric (dim($\bar{X}$)=dim($\bar{Z}$)=2)
4D surface code and an asymmetric (dim($\bar{X}$)=4, dim($\bar{Z}$)=2) 6D
surface code can be achieved and is theoretically interesting. Indeed, it can
be performed by adding/removing 4D surface code layers to switch between a 4D
and 5D code, combined with adding/removing 5D surface code layers to switch
between 5D and 6D.

The significance of this case is that the union of the bounded-spread logical
operator implementations of these codes is universal (Clifford for 4D +
$\overline{\text{CCZ}}$ for 6D) [29] but both codes, and all intermediate
codes, are self-correcting (as they all have logical Pauli operators of
supported on manifolds of at least two dimensions) [43, 44]. A self-correcting
code has a logical space that is the ground space of a local Hamiltonian with
the property that high weight errors correspond to high energy states and so
are naturally suppressed. This means that the active error-correction applied
after adding or removing each layer can be replaced by passive errorr-
correction. This passive error correction can be performed by dissipation of
energy into the environment, without requiring measurements or classical
processing for adaptive corrections. Thus, it shows that none of adaptivity,
classical processing nor even measurements are necessary to circumvent
Corollary 1 – unitary channels supplemented by non-unitary dissipation is
sufficient. This is noteworthy since all other universal schemes we have seen
depend on these ingredients in some way, either explicitly in intrinsically
fault-tolerant implementations, or implicilty by active error-correction.
Hence, this example supports the reasoning in the Sec. IV that it is
differential treatment of logical operators and correctable errors made
possible by non-unitary quantum channels that makes universality possible, not
any of these more specific requirements that are common in universal schemes.

Figure 9: Representation of action on logical operators of removing a layer
during dimensional conversion between 2D and 3D surface codes. A boundary is
viewed as a 2D surface code (split) and then a locality-preserving logical
circuit that is a product of nearest-neighbour CNOT operators is applied
between it and the face of the 3D code adjacent to it to disentangle it from
the 3D code. The final result is that the original logical operators are
mapped to the corresponding logical operators on the new code with the layer
removed. (The removed layer is discarded, so its state is not important.) A
layer can be added by the inverse process.

###  E.3 Pieceable Fault Tolerance with Delayed Error Correction

Code conversion uses code deformation to fault-tolerantly (and non-unitarily)
switch between two codes that together admit a universal set of bounded-spread
logical operator implementations. The gradational technique of pieceable fault
tolerance can also allow direct implementation of an unbounded-spread logical
operator implementation on a single code [9, 10]. Indeed, the scheme of Ref.
[11] for implementing a non-Clifford logical operator on the two-dimensional
surface code can be understood as taking such an approach, supplemented with
the additional technique of delayed error correction to address the problem of
uncorrected errors accumulating over time. We here describe a perspective on
the scheme, focussing on elements salient to this understanding. For a
complete presentation of the scheme, we refer the reader to Ref. [62].

Specifically, Ref. [11] implements an unbounded-spread $\overline{\text{CCZ}}$
logical operator on the two-dimensional surface code. As with all logical
operators there exists a unitary circuit that implements this logical
operator, but this circuit requires entangling each physical qubit non-locally
with a large number of other physical qubits, allowing for errors to spread
over these qubits. This problem is addressed in the way discussed in Sec.
IV.1.1 – the circuit is decomposed into an extensive number of bounded-spread
(in this case transversal) steps and an operation performed between each step
to allow for error-correction in order to give a gradational implementation.

In principle, this gradational implementation could be performed by standard
code deformation. At intermediate times, the encoded state is not a logical
state of the two-dimensional surface code, but will be a logical state of some
more general code on the physical qubits (i.e. that with logical space
stabilised by the image of the surface code stabilisers under the action of
the physical CCZ operators performed up to that point). Error correction at
intermediate times could then be performed by implementing any thresholded
decoders on these intermediate codes. However, while theoretically possible,
this is practically difficult since the intermediate code does not retain
important structural elements that make decoding the surface code feasible.
Specifically, the “stabilisers” of the intermediate code are non-Pauli
operators (since the physical operators applied are non-Clifford), meaning
that these codes are not true stabiliser codes. Moreover, these “stabilisers”
are non-local and high weight (since the physical operators are non-local,
entangling operators), meaning that the intermediate codes are not topological
or even LDPC. Thus, syndrome extraction for standard decoding of the
intermediate codes would require high-weight, non-local, non-Pauli
measurements, which are unlikely to be practical.

The scheme avoids this problem by taking a more nuanced approach based on
pieceable fault tolerance to prevent uncontrolled arising of errors without
standard decoding on intermediate codes. To clarify how this is done, it is
helpful to consider $X$ and $Z$ type errors separately, which can be done
because the surface code is CSS.

To address $X$ errors, we note that the $Z$-type stabilisers (which detect
such errors) commute with all the physical CCZ operators. This means that the
$Z$-type stabilisers of all intermediate codes during the code deformation are
the same as in the two-dimensional surface code. Thus, $X$ errors can in
principle be corrected by use of a standard surface code decoder. It is
important that this correction is performed because uncorrected $X$ errors
would be spread by subsequent CCZ operators, and thus become high-weight,
uncorrectable errors. In practice, it is important to the scheme that this
correction is done in constant time, which requires use of just-in-time
decoding [23] – a technique that allows for the single-shot error-correction
of $X$ errors in the three-dimensional surface code to be leveraged in the
context of this (2+1)D scheme. However, the fundamental approach remains to
correct $X$ errors by measuring $Z$ stabilisers and inferring syndromes, as
with standard decoding.

To address $Z$ errors, the important observation is that $Z$ errors commute
with all the physical CCZ operators and so are not spread by them. This means
that correction of such errors can be delayed without concern of spreading.
Indeed, this is also used in Ref. [10], where such errors are indeed left
unaddressed until after the deformation is complete and a standard decoder can
again be used on the original code. However, this delaying also allows for new
$Z$ errors to arise unhindered throughout the duration of the code
deformation. Since this duration scales polynomially with the code size, $l$,
increasing the code size cannot be assumed to provide improved protection
against such errors. Thus, entirely delaying dealing with $Z$ errors will not
ensure maintenance of a threshold and hence will not be fault-tolerant by our
definition.

In order to address this issue, Ref. [11] extends upon pieceable fault
tolerance by using delayed error correction. Specifically, syndrome
information about $Z$ errors is extracted at each step of the deformation by
qubitwise $X$ measurements. In particular, a teleportation circuit is applied
at the level of physical qubits. (This process involves entangling two layers
of 2D surface codes, and so is interpreted in [11] as creating an $(l\times
l\times 2)$ 3D surface code.) This teleportation circuit can be understood as
similar to teleportation error-correction (as described in Sec. IV.2) but
performed on the level of physical qubits instead of at the logical level
because the logical $X$ operator of the intermediate codes cannot practically
be measured. The $X$ measurements performed in this circuit yield information
that can be used to reconstruct the state of $X$ stabilisers of a three-
dimensional surface code equvialent to the (2+1)D surface code realised during
code deformation. (Repeated measurements are not necessary because the
measurements are qubitwise instead of being of whole stabilisers, and so
measurement errors can be treated equivalently to physical errors [11].) Since
$Z$ errors of a 3D surface code cannot be corrected locally, correction of the
errors implied by this syndrome cannot be completed until the end of the code
deformation process when all measurements have been made. Nevertheless, the
syndrome of $Z$ errors on the final 2D code can be inferred from this 3D code
syndrome and so $Z$ errors can be appropriately corrected. The $Z$ errors of
the 3D code correspond to all $Z$ errors occuring throughout the deformation
and so this correction ensures fault tolerance.

In summary, the scheme of Ref. [11] may thus be understood as a gradational
logical operator implementation of the form
$\mathcal{U}=\prod_{i=1}^{t}\mathcal{K}_{i}\mathcal{U}_{i}$. Here, each
$\mathcal{U}_{i}$ is a transversal implementation of physical CCZ gates such
that $\prod_{i}\mathcal{U}_{i}=\mathcal{U}$. Each $\mathcal{K}_{i}$ for $i<t$
can be expressed as $\mathcal{K}_{i}=\mathcal{D}^{(x)}\mathcal{T}$, where
$\mathcal{D}^{(x)}$ is a (just-in-time) decoder that corrects $X$ errors and
$\mathcal{T}$ is a physical teleportation circuit that extracts syndrome
information about $Z$ errors. The final channel $\mathcal{K}_{t}$ also
includes correction of $Z$ errors based on the collected syndrome information,
as described in the previous paragraph. Thus, the scheme can be understood as
a form of gradational logical operator implementation.

##  Appendix F Conditional Fault Tolerance

Throughout this paper, we have generally required logical operator
implementations to be unconditionally fault-tolerant – fault-tolerant with
respect to all thresholded decoders. This is natural since it allows us to
associate sets of fault-tolerant logical operator implementations with code
families, rather than requiring a different analysis for each possible
decoder. It also follows the lead of most previous approaches to fault
tolerance and so is appropriate for contextualising most of these approaches,
as is evident from Sec. IV and Appendix E.

However, as is clear from Sec. II, fault tolerance is naturally a decoder-
dependent concept. We refer to decoder-dependent fault tolerance as
_conditional fault tolerance_ – fault tolerance of a quantum channel
conditional on a particular decoder or class of decoders being used. A number
of advantages may be realised by more explicitly accounting for this
dependence in future work.

First, it may be more feasible to derive sufficient conditions for conditional
fault tolerance, to supplement the necessary condition we have derived in this
work.

Second, conditional fault tolerance could be more naturally adapted to cases
of code families and decoders with pseudothresholds – i.e. where the effects
of noise on logical qubits after error correction can be suppressed to be less
than the effect of noise on physical qubits, but not arbitrarily suppressed.
Formally, a code family has a pseudothreshold $\eta_{s}$ if there exists a
decoder $\mathcal{D}$ such that

$\left\|\mathcal{D}\circ\mathcal{E}_{\eta}-\mathcal{I}\right\|_{\diamond,\mathcal{L}}<\left\|\mathcal{E}_{k_{\eta}}-\mathcal{I}_{k}\right\|_{\diamond}\,,\quad\text{for}\
\eta<\eta_{s}\,.$ (42)

for sufficiently large $l$. Here, $\mathcal{E}_{k}$ and $\mathcal{I}_{k}$
refer to the noise and identity channels respectively on a $k$ physical
qubits. An appropriate corresponding defintion for fault tolerance on code
families with pseudothresholds is that there exists a pseudothreshold noise
rate $\eta_{s,\mathcal{A}}>0$ such that

$\left\|\mathcal{D}\circ\mathcal{A}_{\mathcal{E}_{\eta}}-\mathcal{A}\right\|_{\diamond,\mathcal{L}}<\left\|A\circ\mathcal{E}_{k_{\eta}}-A\right\|_{\diamond}\,,\quad\text{for}\
\eta<\eta_{s,\mathcal{A}}\,.$ (43)

for sufficiently large $l$. Here, $A$ is the physical unitary operator $A$
corresponding to the logical operator $\bar{A}$ implemented by $\mathcal{A}$.

This definition is much weaker than the definition of fault tolerance with a
threshold in Sec. II and so requiring unconditional fault tolerance for all
decoders with a pseudothreshold would be an unreasonably strong constraint,
and hence one we have not pursued in this work. However, particular decoders
with pseudothresholds can be appropriate in particular contexts, and so
considering conditional fault tolerance (with this adapted definition) for
these particular decoders could be valuable.

Third, and most importantly, Corollary 1 only constrains unconditionally
fault-tolerant logical operator implementations – not conditionally fault-
tolerant implementations. Specifically, an unbounded-spread, unitary
implementation of a logical operator may be fault-tolerant with respect to a
decoder that can correct particular types of high-weight errors that are
likely to arise under the action of the implementation. This leaves open the
possibility of constructing a conditionally fault-tolerant, universal set of
unitary implementations of logical operators by presupposing a particular type
of decoder that allows one to go beyond standard approaches such as
transversality and locality-preserving logical operators without losing fault
tolerance. This possibility appears to have received relatively little
attention to date; while tailored decoders have been used within broader
schemes to address specific problems (such as just-in-time decoding [23, 11]),
they have rarely been used as the single technique to circumvent no-go
theorems on fault-tolerant gate sets. Thus, further exploration could be
fruitful.

However, we note one prominent example of this approach that has been proposed
by Jochym O’Connor and Laflamme [19]. Specifically, this scheme is based on
alternated concatenation of Steane and Reed-Muller codes (for a total of
$\frac{l}{2}$ of each type of code). A logical $\bar{T}$ operator is
transversal on the Reed-Muller code, but the standard unitary circuit has a
spread of three on the Steane code. This means that the unitary implementation
of $\bar{T}$ on the concatenated code by applying the appropriate
implementation at each level of concatenation has a spread of
$3^{\frac{l}{2}}$ since a single-qubit error can be spread by a factor of $3$
for each layer of Steane code. Similarly, $\bar{H}$ is transversal on Steane
codes but not Reed-Muller codes, and so similarly has spread that scales with
the number of layers of Reed-Muller codes, $\frac{l}{2}$. Hence, the
implementations have unbounded-spread and so (by Theorem 1) cannot be
unconditionally fault-tolerant.

Nevertheless, these unbounded-spread, unitary implementations of logical
operators are fault-tolerant (i.e. have a threshold) with respect to standard
concatenated code decoders [63]. This is because such decoders are implemented
one layer at a time. Thus, high weight errors that arise due to spreading on
the layers on which a logical operator implementation is not transversal can
be corrected using the other type of layer, with respect to which errors are
not spread such that uncorrectable errors do not arise as a result of the
implementation. Thus, these high weight errors – which would not need to be
correctable for generic thresholded decoders – are correctable for decoders
that directly use the concatenated structure of the code. Thus, the logical
operator implementations are conditionally fault-tolerant – conditional on the
decoder being implemented one layer at a time. The scheme cannot implement
arbitrary logical operators fault-tolerantly using only unitary quantum
channels, because intermediate error-correction is required between unitary
channels to implement more general logical operators, such as $\overline{TH}$.
However, it allows the generators of a universal set of logical operators to
be implemented unitarily, from which arbitrary operations can be performed
without need for the methods of Sec. IV.

In summary, while the scheme of Ref. [19] is ostensibly similar to
intrinsically fault-tolerant schemes using Steane and Reed-Muller codes [14,
13], it actually uses a fundamentally different technique to leverage the
properties of these codes from code switching or gauge fixing. Specifically,
this technique is directly using the structure of standard concatenated code
decoders to allow for conditionally fault-tolerant logical operator
implementations for such decoders that nonetheless have unbounded spread. This
is a type of conditional fault tolerance because alternative thresholded
decoders could be constructed that do not directly use the concatenation
structure, and the conditionally fault-tolerant logical operator
implementations would not be fault-tolerant with respect to these alternative
decoders. This approach has now also been pursued based on homological product
codes and may prove effective for realising universal sets of fault-tolerant
logical operator implementations on such code families [48]. It may be
fruitful to further pursue such use of conditional fault tolerance further on
more general code families.

## References

  * [1] D. Aharanov and M. Ben-Or, “Fault-Tolerant Quantum Computation with Constant Error Rate”, SIAM Journal on Computing, 38, 2008.
  * [2] P. Aliferis, D. Gottesman and J. Preskill, “Quantum accuracy threshold for concatenated distance-3 codes”, Quant. Inf. Comput., 6, 97–165, 2006.
  * [3] B. Eastin and E. Knill, “Restrictions on Transversal Encoded Gate Sets”, Phys. Rev. Lett., 102, 110502, 2009.
  * [4] S. Bravyi and R. König, “Classification of topologically protected gates for local stabiliser codes”, Phys. Rev. Lett., 110, 170503, 2013.
  * [5] P. Webster and S. D. Bartlett, “Fault-tolerant quantum gates with defects in topological stabiliser codes”, Phys. Rev. A, 102, 022403, 2020.
  * [6] M. Vasmer and D. E. Browne, “Three-dimensional surface codes: Transversal gates and fault-tolerant architectures”, Phys. Rev. A, 100, 012312, 2019.
  * [7] H. Bombin and M. A. Martin-Delgado, “Topological Computation without Braiding”, Phys. Rev. Lett., 98, 160502, 2007.
  * [8] T. J. Yoder, “Universal fault-tolerant quantum computation with Bacon-Shor codes”, arXiv:1705.01686, 2017.
  * [9] E. Knill, R. Laflamme and W. Zurek, “Threshold Accuracy for Quantum Computation”, arXiv:quant-ph/9610011, 1996.
  * [10] T. J. Yoder, R. Takagi and I. L. Chuang, “Universal Fault-Tolerant Gates on Concatenated stabiliser Codes”, Phys. Rev. X, 6, 031039, 2016.
  * [11] B. Brown, “A fault-tolerant non-Clifford gate for the surface code in two dimensions” Sci. Adv., 6, eaay4929, 2020.
  * [12] H. Bombin, “Gauge color codes: optimal transversal gates and gauge fixing in topological stabiliser codes”, New J. Phys., 17, 083002, 2015.
  * [13] J. T. Anderson, G. Duclos-Cianci and D. Poulin, “Fault-tolerant conversion between the Steane and Reed-Muller quantum codes”, Phys. Rev. Lett., 113, 080501, 2014.
  * [14] A. Paetznik and B. Reichardt, “Universal fault-tolerant quantum computation with only transversal gates and error correction”, Phys. Rev. Lett., 111, 090505, 2013.
  * [15] H. Bombin, “Dimensional Jump in Quantum Error Correction”, New J. Phys., 18, 043038, 2016
  * [16] Y. Hwang, B.-S. Choi, Y. Ko and J. Heo, “Fault-tolerant conversion between stabiliser codes by Clifford operations”, arXiv:1511.02596, 2015
  * [17] K. R. Colladay and E. J. Mueller, “Rewiring stabiliser codes”, New. J. Phys., 20, 083030, 2018.
  * [18] S. Bravyi and A. Kitaev, “Universal Quantum Computation with ideal Clifford gates and noisy ancillas”, Phys. Rev. A, 71, 022316, 2005.
  * [19] T. Jochym-O’Connor and R. Laflamme, “Using concatenated quantum codes for universal fault-tolerant quantum gates”, Phys. Rev. Lett., 112, 010505, 2014.
  * [20] S. Bravyi and A. Cross, “Doubled color codes”, arXiv:1509.03239, 2015.
  * [21] T. Jochym O’Connor and S. D. Bartlett, “Stacked codes: universal fault-tolerant quantum computation in a two-dimensional layout”, Phys. Rev. A, 93, 022323, 2016.
  * [22] B. J. Brown, S. Roberts, “Universal fault-tolerant measurement-based quantum computation”, Phys. Rev. Research, 2, 033305, 2020.
  * [23] H. Bombin, “2D quantum computation with 3D topological codes”, arXiv:1810.09571, 2018.
  * [24] E. T. Campbell, B. M. Terhal and C. Vuillot, “Roads towards fault-tolerant universal quantum computation”, Nature, 549, 172–179, 2017.
  * [25] T. Jochym-O’Connor, A. Kubica and T. J. Yoder, “The disjointness of stabiliser codes and limitations on fault-tolerant logical gates”, Phys. Rev. X, 8, 021047, 2018.