Fault-tolerant gates via homological product codes
Tomas Jochym-O’Connor
Walter Burke Institute for Theoretical Physics, Institute for Quantum Information & Matter, California Institute of Technology,
Pasadena, CA 91125, USA
January 30, 2019
A method for the implementation of a univer-
sal set of fault-tolerant logical gates is presented
using homological product codes. In particular,
it is shown that one can fault-tolerantly map
between different encoded representations of a
given logical state, enabling the application of
different classes of transversal gates belonging
to the underlying quantum codes. This allows
for the circumvention of no-go results pertaining
to universal sets of transversal gates and pro-
vides a general scheme for fault-tolerant compu-
tation while keeping the stabilizer generators of
the code sparse.
1 Introduction
Quantum error correction extends qubit coherence
times through error mitigation and will be a require-
ment for any large-scale quantum computation. In this
vein, tremendous research efforts have been placed on
finding quantum error correcting codes that may be re-
alizable in both the near and distant future. Among
the leading candidates for experimental implementa-
tion are 2D topological stabilizer codes, such as the
toric code [1, 2], which allow for the correction of errors
by measuring small-weight local checks while protecting
logical information in highly non-local degrees of free-
dom [37]. These codes are experimentally appealing
due to their stabilizers being low-weight, thus minimiz-
ing the effect of noise during measurement. They can be
generalized to higher spatial dimensions, again with the
stabilizer generators being relatively low-weight, and
provide theoretically simple implementations of differ-
ent classes of fault-tolerant logic [813]. The motivation
for quantum error correcting codes to have geometri-
cally local stabilizers (in a given dimension) is to sim-
plify experimental architectures, yet this may not nec-
essarily be a hard requirement. However, the need for
low-weight stabilizer checks is much stronger, as larger
weight checks lead to more noise propagation, and gen-
erally lower threshold error rates. The theory of quan-
Tomas Jochym-O’Connor: tjoc@caltech.edu
tum low-density parity check (LDPC) codes has been
developed to address such concerns and finding good
codes with low-weight checks remains a very active area
of research [1419]. Moreover, LDPC constructions can
be used to construct codes with very little overhead for
fault-tolerant computation, relying on the preparation
of logical ancillary states [2023]. This work will not
focus on the development of such codes, but rather will
center on how to generally use such codes for the pur-
poses of fault-tolerant computation.
Obtaining a universal set of fault-tolerant gates is
complicated by the existence of no-go results for such
constructions using only transversal gates [24, 25].
However, many alternative schemes have been devel-
oped to circumvent this restriction. They rely on the
preparation of special ancillary states and gate tele-
portation [2628], or tailored fault-tolerant construc-
tions for certain classes of codes [8, 2936]. This work
extends the set of fault-tolerant alternatives, present-
ing a scheme for fault-tolerant logic on any CSS code
while keeping the underlying stabilizer measurements
low-weight.
We present a method for implementing fault-tolerant
logical gates in a homological product code [16].
Namely, given the homological product of two quantum
codes, we show how to map in a fault-tolerant man-
ner between the encoded homological product logical
state to a logical state specified by one of the two codes.
Then, if the underlying codes have a set of transversal
gates, such logical gates can be applied and the state
can be re-encoded back into the full codespace fault-
tolerantly. There are no restrictions on the underlying
codes, other than having to be defined by a boundary
operator δ : C C such that δ
2
= 0 in the linear
space C. In particular, by using versions of the 2D and
3D color codes [9, 37] as the underlying codes in the con-
struction, a universal set of fault-tolerant operations can
be implemented. The mapping between different rep-
resentations of the code follows a similar construction
to Ref. [30], where one of the two codes is unencoded
while the other provides the protection. The key dif-
ference between the methods is that the stabilizers of
the homological product can remain low-weight, unlike
Accepted in Quantum 2019-01-18, click title to verify 1
arXiv:1807.09783v2 [quant-ph] 29 Jan 2019
those in a concatenated model. Moreover, we present
a decoding method to address errors that may occur
during the unencoding of one of the two codes. Given
certain properties of the underlying codes, this will re-
sult in a finite probability error threshold along the lines
of Ref. [38] as well as potential protection against mea-
surement errors.
The article is organized as follows: In Sec. 2 we review
the theory of CSS codes defined by chain complexes and
the construction of the homological product codes, care-
fully considering their underlying structure. In Sec. 3 we
present the main result, a fault-tolerant method to im-
plement a logical gate using homological product codes
as well as discuss a simple decoding procedure. In Sec. 4
we present examples of codes that exhibit a set of uni-
versal fault-tolerant gates, expanding on the notions of
code padding and doubling. Finally, we conclude with
some remarks and open questions in Sec. 5.
2 Homological Product Codes
2.1 Single sector theory
We begin by reviewing the connection between CSS
codes and homology. Namely, as in Ref. [16], we focus
on single sector theory
1
in Z
2
, that is a chain complex
defined by a linear space C and a linear boundary oper-
ator δ : C C, such that δ
2
= 0. We can then use such
a boundary operator to define a CSS code [39, 40], that
is a stabilizer code whose generators can be expressed
as either X-type or Z-type.
Let C be a n-dimensional binary space Z
n
2
, then δ
will be a n × n binary matrix. The (perhaps over-
complete) generating set of X stabilizers will be given
by the rows of δ, that is for a given row, a generator S
X
i
will have X support on the qubits with a 1 in the given
row. Similarly, the Z stabilizers will be defined by the
columns of the matrix. Given δ
2
= 0, we are thus as-
sured commutativity of the stabilizers. The number of
independent generators of both type will be rank(δ),
and as such the number of logical qubits of the code
will be k = n 2rank(δ).
For the remainder of this section we shall focus on the
reverse implication. That is, given a CSS code whose X
and Z stabilizer spaces are of the same dimension, one
can construct a boundary operator δ of a single-sector
theory. The results presented are a fairly straightfor-
ward corollary of Lemma 3 from Ref. [16], yet we in-
clude them here for completeness and to review some
1
In general, CSS codes can be constructed from chain com-
plexes where δ
i
: C
i
C
i1
are linear operator satisfying:
δ
i1
δ
i
= 0.
important concepts, namely the canonical boundary op-
erator.
Lemma 1. Given a CSS code on n qubits, whose X and
Z stabilizer spaces are each of cardinality 2
l
, therefore
encoding k = n 2l qubits. Then, there exists a in-
vertible matrix W , and canonical boundary operator δ
0
defined as:
δ
0
=
0
k
0 0
0 0
l
1
l
0 0
l
0
l
, (1)
such that δ = W δ
0
W
1
, where the rows (columns) of δ
contain a set of generators of the X (Z) stabilizer group.
Proof. Given the existence of a CSS code, by the
Gottesman-Knill theorem [41] there exists a unitary
operator U composed solely of CNOT gates that
maps |ψi |0i
l
|+i
l
to the encoded stabilizer code,
where l = (n k)/2 and |ψi is a k-qubit state. This
statement can be expressed in terms of matrix manip-
ulation on Z
2
, where δ
0
will represent the initial state
of the stabilizers before the application of the encoding
circuit, that is the rows of δ
0
represent the initial |+i
states, and the columns the initial |0i states. A CNOT
gate with qubit i as control, and qubit j as target can
then be expressed according to the invertible matrix:
W
i,j
= 1 + w
i
w
T
j
, (2)
where w
k
is the standard basis column vector one non-
zero entry at position k. The action of W
i,j
by conjuga-
tion maps column c
j
to the sum of columns c
i
c
j
, and
row r
i
to the sum of rows r
i
r
j
. This is the exact ac-
tion required from a CNOT, as it maps X
i
to X
i
X
j
and
Z
j
to Z
i
Z
j
. Note, as required for a valid representation
of a CNOT gate, W
2
i,j
= 1 W
i,j
= W
1
i,j
, where again
we are working modulo 2. Then, the encoding opera-
tion W can be broken into its CNOT components and
can be expressed as W = W
i
N
,j
N
· · · W
i
2
,j
2
W
i
1
,j
1
. As
such,
δ = (W
i
N
,j
N
· · · W
i
1
,j
1
)δ
0
(W
i
N
,j
N
· · · W
i
1
,j
1
)
1
(3)
= (W
i
N
,j
N
· · · W
i
1
,j
1
)δ
0
(W
i
1
,j
1
· · · W
i
N
,j
N
), (4)
will be a valid representation of the stabilizers of the
code. Since W is a valid representation of the encoding
circuit of the code, the rows (columns) of δ will remain a
valid representation of the X (Z) stabilizers since they
were so for δ
0
.
Perhaps as importantly for the purposes of this arti-
cle, if the given CSS code has a generating set of stabi-
lizers that are sparse, then the resulting constructed δ
will be sparse. We define the sparsity of a code to be the
Accepted in Quantum 2019-01-18, click title to verify 2
smallest integer w such that there exists a set of genera-
tors of the code whose weights are at most w while any
given qubit participates in at most w stabilizer checks.
Corollary 2. Given a CSS code on n qubits with an
equal number of X and Z stabilizers and sparsity t, then
a boundary operator δ can be constructed such that no
row or column will have more than t
2
non-zero entries.
Proof. Given some sparse representative set of stabiliz-
ers {S
X
i
, S
Z
i
}, as in the proof of Lemma 1, a unitary
circuit W can be chosen that maps Z
k+i
S
Z
i
and
X
k+l+i
S
X
i
. Consider the right action of W
1
in
terms of its action on the canonical boundary operator:
δ
0
W
1
=
0
k×n
s
X
1
.
.
.
s
X
l
0
l×n
, (5)
where on the right side of the equality we have a matrix
whose rows are either all-zero or a binary representa-
tion s
X
i
of the stabilizer S
X
i
. This follows from the
fact that the right application of W
1
results in the
propagation of the initial X stabilizers to their final
generator form. Then, by the sparsity of the stabilizer
generators, each row will be of weight at most t and
each column will have weight at most t. Now consider
the left application of W applied to δ
0
W
1
, thus com-
pleting the conjugation, the resulting matrix W δ
0
W
1
will have rows that will be sums of the different rows
of δ
0
W
1
. Moreover, each row of W δ
0
W
1
will be a
sum of at most t rows s
X
i
, and will as such be of weight
at most t
2
. Finally, since a given row can map to at
most t other rows, each non-zero entry within a column
of δ
0
W
1
can map to at most t entries within that col-
umn. Therefore, since there were at most w non-zeros
entries in a column of δ
0
W
1
, there can be at most t
2
non-zeros in each column of W δ
0
W
1
2.2 Homological Product Construction
Given two complexes (C
1
, δ
1
), (C
2
, δ
2
) with their asso-
ciated spaces and single sector boundary operators, we
define a new operator as in Ref. [16],
= δ
1
1 + 1 δ
2
, (6)
acting on C
1
C
2
. It follows from δ
2
i
= 0 that
2
= 0,
again since we are working in Z
2
. Therefore, (C
1
C
2
, ) is a valid single sector complex, defining its own
quantum CSS code.
We now restate some important properties of the ho-
mological product.
Lemma 3 ([16]). Let (C
1
, δ
1
), (C
2
, δ
2
) be complexes
defining codes with k
1
, and k
2
logical operators, respec-
tively. Let = δ
1
1 + 1 δ
2
, then the resulting com-
plex (C
1
C
2
, ) will encode k = k
1
k
2
logical qubits and
ker = ker δ
1
ker δ
2
+ im . (7)
Suppose that w
a
is the sparsity of δ
a
. Moreover, let
d
X
a
, d
Z
a
be the X and Z distances for the correspond-
ing codes. Then, the weight and distances of the new
code can be bounded according to the parameters of the
original code.
Lemma 4 ([16]). The sparsity of is upper bounded
by w
1
+ w
2
. The X and Z distance of the new code
satisfy the following bounds:
max {d
α
1
, d
α
2
} d
α
d
α
1
d
α
2
, α = X, Z. (8)
2.3 Encoding the homological product code
In this subsection, we review some facts about the
encoding circuit for [16]. As eluded to in Sec-
tion 2.1, there are invertible matrices W
a
such that δ
a
=
W
a
δ
a,0
W
1
a
, where δ
a,0
are the canonical boundary op-
erators for δ
a
. The matrices W
a
are binary represen-
tatives of the encoding circuit for the given code, and
as such, by taking their tensor product we obtain the
encoding operation for . That is:
= (W
1
W
2
)(δ
1,0
1 + 1 δ
2,0
)(W
1
1
W
1
2
) (9)
:= (W
1
W
2
)
0
(W
1
W
2
)
1
, (10)
where we have defined
0
to be the canonical boundary
operator for . We can express
0
in matrix form as
follows:
0
= (δ
1,0
1 + 1 δ
2,0
) (11)
=
1
k
1
δ
2,0
0 0
0 1
l
1
δ
2,0
1
l
1
1
n
2
0 0 1
l
1
δ
2,0
, (12)
where k
i
are the number of logical qubits and l
i
= (n
i
k
i
)/2 is the number of X/Z stabilizers of the given code
code.
It is worth further exploring the form of
0
, as this
will be informative of how the logical information is
encoded in the code. Each row and column of
0
will be
of weight at most 2. Moreover, if a given row has 2 non-
zeros entries, say at positions q
i
and q
j
, then any column
with a non-zero entry at q
i
will also have a non-zero
entry at position q
j
in order to satisfy commutativity.
As such, these rows and columns represent an initial
entangled Bell pair between qubits q
i
and q
j
since they
will be stabilized by the operators X
q
i
X
q
j
and Z
q
i
Z
q
j
.
Accepted in Quantum 2019-01-18, click title to verify 3
...
...
...
...
...
...
...
...
...
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
l
1
l
1
l
2
l
2
k
2
k
1
n
1
n
2
Figure 1: Initial state of the homological product code prior to
encoding [16]. Each circle represents a qubit, with the black
qubits representing those holding the logical information to be
encoded. Blue qubits are prepared in the |0i state, while red
qubits are prepared in |+i. The yellow qubits joined by an
oscillating edge are prepared in a Bell pair (|00i + |11i)/
2.
The initial state can be pictorially represented by
Fig. 1, where along a fixed row and column, the states
in C
1
and C
2
are fixed, respectively. Then, the ten-
sor product binary operators W
1
1 and 1 W
2
will
have geometric meaning in this picture. Note for the
remainder of this work, we will denote U
i
as the physi-
cal encoding unitaries composed of CNOT gates acting
on the quantum states whose binary representation is
given by W
i
. Thus U
1
will couple qubits within verti-
cal bands, while U
2
will couple qubits within horizontal
bands, as represented in Fig. 2.
3 Fault-tolerant logical gates
3.1 Partial decoding of the homological product
code
The key idea for expanding the set of available fault-
tolerant logical gates will be for the two underlying
codes composing the homological product to have dif-
ferent complimentary sets of transversal gates. Then,
we can achieve the application of these logical gates by
only decoding one of the two underlying codes, while re-
maining protected by the other. This is reminiscent of
the scheme for implementing fault-tolerant gates using
two concatenated codes [30], with the added advantage
that the stabilizers remain low-weight in the case of the
homological product.
The main result is that, while we decode one of the
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
(a) C
1
encoder
...
...
...
...
...
...
...
...
...
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
(b) C
2
encoder
Figure 2: Schematic representation of the support of the en-
coding circuits for each of the codes underlying the homo-
logical product code, defined by the boundary operator =
δ
1
1 + 1 δ
2
. The overall encoding circuit has a binary
representation of the operator W
1
W
2
, which acts on the ini-
tial state represented in Fig. 1. That is, the physical encoding
unitary U
1
for the code C
1
will act on every column on qubits
from Fig. 1, and conversely the physical encoding unitary U
2
will act on every row.
codes, we still remain fully protected by the other code.
While errors may potentially propagate during the ap-
plication of the decoding process, they can still be cor-
rected as long as the number of faults is less than half
the distance of the underlying code protecting the in-
formation (that is the code that remains encoded at all
times). The main Theorem is a variant of Lemma 4
stated above (originally Lemma 2 from Ref. [16]), yet is
proved using the concept of error bands.
Recall the homological product is defined by the com-
plex (C
1
C
2
, ), where C
i
are binary spaces. The com-
plex defines a code with n
1
n
2
physical qubits, which
we label (i, j) where 1 i n
1
and 1 j n
2
.
Then, a Pauli operator P is supported only on (i, j)
if Tr
(i
0
,j
0
)6=(i,j)
(P ) = P
i,j
6= 0, we will therefore denote
such Pauli operators P
i,j
. We will call the error band E
1
a
to be all possible Pauli operators of the form
Q
j
P
a,j
,
that is a product of any Pauli operators P
i,j
with i = a.
Conversely, the error band E
2
a
will be all possible Pauli
operators of the form
Q
j
P
j,a
. Moreover, we will say
that a Pauli error E is supported on the set {e
1
, · · · e
l
} of
error bands E
1
a
if the operator is supported by the qubits
composing those error bands, that is E E
1
e
1
· · ·E
1
e
l
.
A Pauli operator supported on a set of error bands E
2
a
is
defined similarly and whether the operator is supported
on error bands E
1
a
or E
2
a
should be clear from context.
Note that the unitary U
1
will only couple qubits within
a fixed error bands E
1
a
, while conversely U
2
will only
couple qubits within fixed error bands E
2
a
.
Theorem 5. Let (C
1
, δ
1
), (C
2
, δ
2
) be complexes and let
(C
1
C
2
, ) be the homological product code constructed
Accepted in Quantum 2019-01-18, click title to verify 4
from these codes with = δ
1
1 + 1 δ
2
. Then any er-
ror E supported on fewer than d
2
error bands E
1
a
cannot
support a logical operator. Similarly, any error E sup-
ported on fewer than d
1
error bands E
2
a
cannot support
a logical operator.
Proof. Consider an error E supported on fewer than d
2
error bands E
1
a
, let the affected bands be denoted by the
set {e
1
, · · · , e
l
}, that is E E
1
e
1
· · ·E
1
e
l
, where l < d
2
.
Since any error can be expressed in the Pauli basis, if
we show any Pauli error supported on the above set
cannot support a logical operator, E cannot support
a logical operator. As such, without loss of general-
ity, suppose E is a Pauli error. Consider the modified
error E
0
= U
1
EU
1
, where U
1
is the encoding unitary
for the code C
1
. Then, if we can show that E
0
cannot
support a logical operator on the new codespace after
applying U
1
, then by unitary equivalence it cannot on
the homological product codespace.
Any logical operator must commute with all of the
stabilizers of the code. The modified codespace is given
by the boundary operator
1,0
= (W
1
1
1)(W
1
1) =
δ
1,0
1 + 1 δ
2
, that is it will correspond to k
1
logical
codeblocks encoded in the code (C
2
, δ
2
) along with ac-
companying encoded ancilla state
2
. This can be viewed
visually by considering the initial unencoded state in
Fig. 1 followed by the encoding operation of Fig. 2b.
Therefore, in order for E
0
to support a logical error, it
will have to support a logical operator on one of the
first k
1
error bands E
2
a
. Without loss of generality, con-
sider the first error band E
2
1
, that is the first row of
qubits in Figs. 1-2, and the support of E
0
on that band,
E
0
1
= E
0
E
2
1
(E
1
e
1
· · · E
1
e
l
) E
2
1
. Therefore, the
weight of the Pauli operator given by E
0
1
is limited by
the number of initial error bands E
1
a
on which the error
was supported, that is: wt(E
0
1
) l < d
2
, and as such
since any logical operator supported on the band E
2
1
must be of weight at least d
2
, the error E
0
1
cannot sup-
port a logical error. Since this will be true for all en-
coded logical bands supported on E
2
a
, with a k
1
, the
error E
0
cannot support a non-trivial logical error.
To conclude, since E
0
cannot support a logical error
on the code specified by the boundary operator
1,0
,
then E = U
1
E
0
U
1
cannot support a logical operator on
the code specified by = (W
1
1)
1,0
(W
1
1
1).
Equipped with Theorem 5, we propose the following
scheme to implement a fault-tolerant logical gate. Sup-
pose the logical gate G
1
can be implemented transver-
sally on the single-qubit partition of the code induced
by the complex (C
1
, δ
1
), that is it can be implemented
by applying gates that are each individually supported
2
An encoded ancillary state is a fixed state that contains no
non-trivial logical information, yet still may be partially encoded.
on single qubits of the code. Then, in order to apply
the logical gate G
1
on the logical state of the homo-
logical code (C
1
C
2
, ), we begin by unencoding the
code (C
2
, δ
2
), that is we apply the unitary 1U
2
. At this
point, the first k
2
blocks of n
1
qubits remain encoded
in the code (C
1
, δ
1
), while the the remaining blocks are
in an encoded ancillary state. Therefore, we can apply
the transversal implementation of the logical gate G
1
on any of the k
2
logical states we desire. We complete
the logical gate application by then reencoding into the
code (C
1
C
2
, ) by applying 1 U
2
.
The proposed scheme is fault-tolerant in that, it will
be able to correct against up to b(d
1
1)/2c faults
throughout the process. Any error P
a,b
that occurs dur-
ing the application of either 1 U
1
2
, 1 U
2
, or the
transversal gate can spread to a high-weight error, yet
such an error will remain within a single error band E
2
a
.
This follows as the application of 1 U
2
only ever cou-
ples qubits within the same error band E
2
a
. Similarly, a
transversal gate with respect to the code (C
1
, δ
1
) will not
couple different error bands E
2
a
, by definition. There-
fore, any single fault P
a,b
can result in an error that
is contained within the error band E
2
a
. Since any log-
ical error must be supported on at least d
1
such error
bands, any error affecting less than half of such error
bands must remain correctible by the Knill-Laflamme
condition [42].
By symmetry, given a transversal gate G
2
on the
single-qubit partition of the code (C
2
, δ
2
), a fault-
tolerant implementation of G
2
can be achieve by ap-
plying U
1
1, followed by the transversal gate, and a
reencoding U
1
1. Such a fault-tolerant gate will be
able to correct against up to b(d
2
1)/2c faults.
3.2 Correcting errors
In the last section, we showed how even when de-
coding one of the two codes, we can always protect
against at least b(d
i
1)/2c faults. However, the en-
coding/decoding operations may generally have O(n
c
i
)
time steps
3
, and as such, errors will accumulate within
a given error band (assuming an independent non-
Markovian error processes), resulting in an error with
probability: p
e
O(n
c
i
), where p
e
is the physical error
rate. This is undesirable from the perspective of fault
tolerance, as we hope that for a given family of codes,
by growing the distance, the probability of incurring a
logical error decreases exponentially below some thresh-
old value. Yet, if the underlying error rate is growing
3
Decoding of stabilizer codes amounts to Gaussian elimina-
tion on the binary-symplectic matrices representing the stabiliz-
ers. This can be done using a polynomial number (in the input
size) of elementary matrix row manipulations which correspond
to Clifford gates.
Accepted in Quantum 2019-01-18, click title to verify 5
polynomially with the distance, this yields a pseudo-
threshold for each code, rather than a global threshold
for a code family.
In this section, we present a simple decoding algo-
rithm for the homological product code, based on the
decoding algorithm of the individual codes composing
the homological product. While the presented scheme
will likely be far from ideal in many settings, it will
serve as a proof of principle decoder as well as provide
a means to correct against errors during the implemen-
tation of the fault-tolerant logical gates. This will help
alleviate the concern errors accumulating within an er-
ror band due to the encoding/decoding having a macro-
scopic number of individual time steps. As will be dis-
cussed at the end of this subsection, in some cases this
will guarantee a fault-tolerance threshold against inde-
pendent noise. However, the existence and value of such
a threshold would have to be studied on a case-by-case
basis.
Consider the homological product code as specified in
the previous subsection, with a boundary operator =
δ
1
1 + 1 δ
2
. Moreover, suppose we have recovery
operators R
i
for each code that returns the code to the
codespace and corrects with certainty when the weight
of the error is below half the distance of the respective
code. We present the following Corollary to Theorem 5,
which follows directly from the proof of that result.
Corollary 6 (of Theorem 5). Let (C
1
, δ
1
), (C
2
, δ
2
) be
complexes and let (C
1
C
2
, ) be the homological product
code constructed from these codes with = δ
1
1 +
1 δ
2
. Then, for any error E supported on fewer than
b(d
j
1)/2c error bands E
i
a
, the error E
0
= U
i
EU
i
is
correctible using the recovery operator R
j
, where i, j
{1, 2} such that i 6= j.
The above Corollary states that given a correctible
error, as stated by Theorem 5, conjugating that error by
either decoding operator U
i
will result in a correctible
error on the remaining encoded states in the code C
j
.
We propose the following decoding algorithm. Given
an encoded state in the traditional homological prod-
uct code, we measure the syndromes of the code as
specified by the row (X type) and columns (Z type)
of the boundary operator . Now, given these mea-
surement outcomes, we can map them onto syndrome
outcomes for either of the two code, using the follow-
ing procedure. Without loss of generality, suppose we
would like to map them onto the syndromes of the
code C
2
. We know the modified boundary operator
1,0
= (W
1
1
1)(W
1
1) = δ
1,0
1+1δ
2
corresponds
to k
1
logical states that are encoded in the code C
2
.
Specifically, the first k
1
n
2
rows and columns of
1,0
will
correspond to the stabilizers of the code C
2
, see Eq. 12
for an example, replacing δ
2,0
with δ
2
. Suppose we mea-
sured a given stabilizer S
l
of the original stabilizer code
such that ES
l
= (1)
b
l
S
l
E, that is b
l
{0, 1} records
the stabilizer measurement outcome. Then since the
encoding circuit is Clifford, and S is Pauli, we can effi-
ciently classically compute the form of the transformed
syndrome S
0
l
= U
1
S
l
U
1
. Moreover, S
0
l
will keep the
same commutation relation with the transformed er-
ror E
0
, that is E
0
S
0
l
= (1)
b
l
U
1
S
l
EU
1
= (1)
b
l
S
0
l
E
0
.
Therefore, we can use the transformed stabilizers S
0
l
to determine the syndrome of E
0
in the code C
2
. To
find the appropriate recovery Pauli operator Q
0
we use
the known decoder of C
2
, and transform Q
0
back into
a recovery operator for the original code by classically
computing Q = U
1
Q
0
U
1
, which is again efficient since
U
1
is a Clifford circuit.
We can then generalize the above method to address a
build up of errors throughout the fault-tolerant process
presented in Sec. 3.1. Suppose, without loss of general-
ity, we want to implement the logical gate G
2
which is
transversal for the code C
2
. Then, we would start with
unencoding C
1
by applying U
1
= V
1
· · · V
t
, where V
i
are the CNOT gates used in constructing the encoding
unitary U
1
. After the application of each V
i
, the code
will be partially unencoded and the resulting boundary
operator will be of the form
1,i
= δ
1,i
1 + 1 δ
2
,
where δ
1,i
= (V
i
· · · V
1
)δ
1,0
(V
1
· · · V
i
)
4
. If we assume
that throughout the application of each V
i
operator the
generators of the code remain sparse, then we can mea-
sure these generators after each application V
i
in order
to address the errors that occurred during the appli-
cation of that gate. The errors are then corrected by
classically mapping the stabilizer generators
1,i
onto
those of
1,0
, and using, as outlined above, the decoder
of C
2
to correct for the resulting errors.
A final remark on the stabilizer generators of
1,i
. As
stated above, if we were to measure them after every
application of V
i
, V
i
, we would like them to remain
sparse. In general, while the initial and final bound-
ary operators
1,0
and are certainly sparse, there will
be no guarantee that the intermediary matrices remain
sparse as well. However, for many common codes, such
as topological codes, this can be achieved by choosing
an appropriate encoding unitary. Roughly speaking, the
idea is to build up the non-local logical operators of a
topological code by growing the code at its boundary
in a systematic manner [43]. Moreover, if the stabi-
lizers remain sparse at every time step, and the dis-
tance of each of the respective codes scale as n
α
i
i
for
some positive power of α
i
, then we can invoke the re-
sult Ref. [38] to prove the existence of a fault tolerance
4
We have used an abuse of notation to denote V
i
as both the
unitary CNOT gate and the binary representative for the CNOT.
We feel it is clear from the context which operator we are referring
to.
Accepted in Quantum 2019-01-18, click title to verify 6
threshold. Moreover, as outlined in Ref. [38], if the syn-
drome measurements are repeated then we may over-
come measurement errors as well and still have a finite
error threshold. Finally, repeated measurements may
even be avoided if the underlying codes have single-shot
correction properties [44, 45]. An explicit construction
of a decoder applied to this setting remains an interest-
ing open problem.
4 Universal constructions
In this section, we explore an explicit example of a fam-
ily of codes for implementing a universal set of fault-
tolerant operations using the construction from Sec-
tion 3.1. We will focus on the Clifford + T universal
gate set [46]. Let the code C
1
be the 2D color code with
distance d
1
encoding a single logical qubit. The code
has parameters [[c
1
d
2
1
, 1, d
1
]], for a constant c
1
, and can
implement any Clifford gate transversally [9, 37]. The
code C
2
will be composed of the gauge-fixed 3D color
code. That is, a particular choice of the 3D color code
where volume cell terms are of both X and Z type,
while the face terms are only of Z type. The result-
ing code has a transversal implementation of a T =
diag(e
/8
, e
/8
), a non-Clifford gate and code pa-
rameters [[c
2
d
3
2
, 1, d
2
]], for a constant c
2
[8, 9]. How-
ever, due to the asymmetry in the number of X and
Z stabilizer generators, arising from having to fix the
face terms to be Z-type, the resulting code cannot be
directly used in the single-sector homological product
code construction. We present two alternative code con-
structions of C
2
, one based on code padding, and one
using two complementary copies and re-encoding them
in the [[4, 2, 2]] repetition code.
4.1 Code padding
Suppose we have a CSS code C that we want to use in
a universal fault-tolerant implementation of a homolog-
ical product code, and moreover assume without loss
of generality there are more Z generators than X gen-
erators. In order to use the code C in a homological
product code construction, as presented, we must have
the same number of independent X and Z stabilizers. A
rather simple alternative code that we can use is to pad
the original code with extra ancillary qubits in the |+i
state, thus adding an extra set of single-qubit X gener-
ators. The resulting code will have the same distance
as the original code, where all non-trivial logical Pauli
operators can be supported on the original qubits of the
code. For example, in the case of the smallest gauge-
fixed 3D color code, the 15-qubit Reed-Muller code, we
can pad the code with an extra 6 |+i qubits, resulting
in a [[21, 1, 3]] code. While this extra padding of qubits
|ψ
1
i
|ψ
2
i
|0i
|+i
Figure 3: Encoding circuit for the 4-qubit repetition code. The
stabilizers generators of the code are: X
4
, Z
4
.
does not change the base code other than trivially al-
ternating the number of underlying stabilizer genera-
tors, these generators will play a role in the homologi-
cal product, via the initial entanglement present in the
unencoded state, represented by
0
.
Therefore, the universal scheme for implementing a
set of fault-tolerant logical operations that can cor-
rect an arbitrary single qubit error will use the Steane
and padded Reed-Muller codes, which are the small-
est distance 3 versions of the 2D and padded 3D color
codes, respectively. The overall scheme will have cod-
ing parameters [[147, 1, 3
]], where 3
corresponds to the
minimum fault-tolerant distance of the overall scheme,
not necessarily the distance of the homological code
itself. The stabilizer measurements will be of weight
at most 15, see Appendix A. This is a large improve-
ment over requiring measuring stabilizers of weight 28
in the concatenated scheme [30], which leads to punitive
threshold values and qubit overheads [4749].
4.2 Code doubling
The process of code doubling was first presented in
Refs. [50, 51] for converting between Majorana fermion
codes and stabilizer codes. We will outline the general
logical procedure for any CSS code here, yet it can be
generalized for arbitrary stabilizer code rather similarly.
Consider a CSS code A
(1)
of n physical qubits with
stabilizer generators S
(1)
X
i
=
Q
j∈X
i
X
(1)
j
, where X
i
is
a list of qubits in the support of S
(1)
X
i
and the use of
the superscript (1) will become clear shortly. Similarly,
the Z stabilizers are given by S
(1)
Z
i
=
Q
j∈Z
i
Z
(1)
j
. Con-
sider now a rotated version of A
(1)
where each of the
X stabilizers are replaced by Z stabilizers and vice-
versa, call this code A
(2)
. More explicitly, the X and
Z stabilizers of A
(2)
are given by: S
(2)
X
i
=
Q
j∈Z
i
X
(2)
j
,
S
(2)
Z
i
=
Q
j∈X
i
Z
(2)
j
. Therefore, the different superscripts
represent different blocks of n qubits.
These two codes are then re-encoded into the
[[4, 2, 2]] repetition code, whose encoding circuit is given
in Fig. 3. The third block of qubits will be initially pre-
pared as |0i
n
, while the fourth block will be prepared
as |+i
n
. Consider how the stabilizers are transformed
Accepted in Quantum 2019-01-18, click title to verify 7
under the action of the circuit in Fig. 3:
S
(1)
X
i
=
Y
j∈X
i
X
(1)
j
Y
j∈X
i
X
(1)
j
X
(3)
j
(13)
S
(2)
X
i
=
Y
j∈Z
i
X
(2)
j
Y
j∈Z
i
X
(2)
j
X
(3)
j
(14)
X
(4)
j
X
(1)
j
X
(2)
j
X
(3)
j
X
(4)
j
(15)
S
(1)
Z
i
=
Y
j∈Z
i
Z
(1)
j
Y
j∈Z
i
Z
(1)
j
Z
(4)
j
(16)
S
(2)
Z
i
=
Y
j∈X
i
Z
(2)
j
Y
j∈X
i
Z
(2)
j
Z
(4)
j
(17)
Z
(3)
j
Z
(1)
j
Z
(2)
j
Z
(3)
j
Z
(4)
j
. (18)
Note that we can combine the mapped stabilizers with
those of the repetition code in order to recognize a
complete symmetry between the X and Z stabiliz-
ers of the code. While it may immediately follow
from the presented construction, one can show that the
above construction is equivalent to concatenating the
[[4, 2, 2]] code with the code A
(1)
and its rotated com-
pliment A
(2)
. Moreover, the distance of the new code
will be twice that of the original code. Therefore, this
concatenated code provides a code that can be used in
the homological product code construction.
Choosing the code A
(1)
to be the gauge-fixed 3D color
code along with its rotated compliment A
(2)
, we can
use these codes in conjunction with the 2D color code
for the purposes of universal fault-tolerant computation
via homological product codes. To perform any logical
Clifford gate, it will be sufficient to decode the [[4, 2, 2]]
repetition code, followed by the decoding of A
(i)
, for
either or both i {1, 2}, depending on which code-
block one would like to apply the desired Clifford gate
transversally.
In order to implement the T gate fault-tolerantly,
one would first decode the 2D color code, as spec-
ified in Sec. 3.1. At this point, one could not di-
rectly apply the non-Clifford gate transversally, as the
two encoded codeblocks will still be further encoded
in the [[4, 2, 2]] code. However, one can then decode
the [[4, 2, 2]] code by applying the circuit of Fig. 3 in re-
verse. This will preserve the protection guaranteed by
Theorem 5 as each block of 4-qubits will belong to the
same error band, allowing the application of a transver-
sal T gate bookended by fault-tolerant operations.
A final note regarding code doubling: since the stabi-
lizers are symmetrized, the code will gain a transversal
Hadamard gate. The logical result of the transversal
Hadamard will be to implement logical Hadamard fol-
lowed by logical SWAP between the two logical qubits.
As such, for this particular operation, code doubling
allows for a rapid implementation of this logical gate
without having to decode one of the codes in the homo-
logical product.
5 Conclusion
This work introduces a method for implementing a set
of logical gates using homological product codes, appli-
cable to any set of CSS codes. Namely, we show that if
the underlying codes composing the homological prod-
uct have complementary classes of transversal gates,
then this scheme can be used to implement a fault-
tolerant universal gate set. Moreover, if the underlying
codes have stabilizer generators that are sparse, the con-
struction will remain sparse, allowing for the implemen-
tation of a fault-tolerant gate set that does not require
measurement of high-weight operators. This method
is particularly interesting for the theory of quantum
LDPC codes, where the hope would be to construct
codes with good parameters and sets of transversal
gates. If one were able to find such codes, this may
lead to an alternative method for implementing univer-
sal fault-tolerant computation with constant overhead,
in a similar manner to recent results that used special
ancillary states to obtain a universal set of gates [20
23]. A recent result exploring the connection between
homological product codes and single-shot error correc-
tion highlights a potential avenue for constructing codes
with interesting transversal gates [45], yet new construc-
tions remain elusive.
The presented scheme relies on decoding one of the
two codes composing the homological product, apply-
ing the transversal gate, and re-encoding. The encod-
ing/decoding process may indeed spread errors in a dra-
matic way, yet due to the protection of the other code,
the global operation remains fault-tolerant. If the en-
coder/decoder of each code preserves the sparsity of the
code after each gate, then modified stabilizers may be
measured during the encoding/decoding process, allow-
ing for increased protection. Moreover, this should im-
ply the existence of a finite error probability threshold
due to the stabilizer generators always being low weight
as long as the distance grows as a positive power of the
number of qubits [38].
Acknowledgments
We thank Benjamin J. Brown, and Sam Roberts for
insightful discussions on intermediary correction of er-
rors during the fault-tolerant operations. We also thank
Christopher Chamberland and John Preskill for com-
ments during the development of this work and Sergey
Bravyi for feedback on the initial manuscript. We ac-
knowledge the support from the Walter Burke Insti-
Accepted in Quantum 2019-01-18, click title to verify 8
tute for Theoretical Physics in the form of the Sherman
Fairchild Fellowship as well as support from the In-
stitute for Quantum Information and Matter (IQIM),
an NSF Physics Frontiers Center (NFS Grant PHY-
1733907).
References
[1] Alexei Y. Kitaev. Fault-tolerant quantum compu-
tation by anyons. Annals of Physics, 303(1):2–30,
2003. DOI: 10.1016/S0003-4916(02)00018-0.
[2] Austin G. Fowler, Matteo Mariantoni, John M.
Martinis, and Andrew N. Cleland. Surface codes:
Towards practical large-scale quantum computa-
tion. Phys. Rev. A, 86:032324, 2012. DOI:
10.1103/PhysRevA.86.032324.
[3] R. Barends, J. Kelly, A. Megrant, A. Veitia,
D. Sank, E. Jeffrey, T. C. White, J. Mutus, A. G.
Fowler, B. Campbell, et al. Superconducting quan-
tum circuits at the surface code threshold for fault
tolerance. Nature, 508(7497):500–503, 2014. DOI:
10.1038/nature13171.
[4] Jerry M. Chow, Jay M. Gambetta, Easwar Mage-
san, David W. Abraham, Andrew W. Cross, B. R.
Johnson, Nicholas A. Masluk, Colm A. Ryan,
John A. Smolin, Srikanth J. Srinivasan, et al. Im-
plementing a strand of a scalable fault-tolerant
quantum computing fabric. Nature communica-
tions, 5, 2014. DOI: 10.1038/ncomms5015.
[5] Daniel Nigg, Markus Mueller, Esteban A Martinez,
Philipp Schindler, Markus Hennrich, Thomas
Monz, Miguel A Martin-Delgado, and Rainer
Blatt. Quantum computations on a topologically
encoded qubit. Science, page 1253742, 2014. DOI:
10.1126/science.1253742.
[6] J. Kelly, R. Barends, A. G. Fowler, A. Megrant,
E. Jeffrey, T. C. White, D. Sank, J. Y. Mutus,
B. Campbell, Yu Chen, et al. State preservation
by repetitive error detection in a superconducting
quantum circuit. Nature, 519(7541):66–69, 2015.
DOI: 10.1038/nature14270.
[7] Maika Takita, Antonio D orcoles, Easwar Mage-
san, Baleegh Abdo, Markus Brink, Andrew
Cross, Jerry M Chow, and Jay M Gambetta.
Demonstration of weight-four parity measurements
in the surface code architecture. Phy. Rev.
Lett., 117(21):210505, 2016. DOI: 10.1103/Phys-
RevLett.117.210505.
[8] ector Bomb´ın. Gauge color codes: optimal
transversal gates and gauge fixing in topological
stabilizer codes. New J. Phys., 17(8):083002, 2015.
DOI: 10.1088/1367-2630/17/8/083002.
[9] Aleksander Kubica and Michael E. Beverland. Uni-
versal transversal gates with color codes: A simpli-
fied approach. Phys. Rev. A, 91:032330, 2015. DOI:
10.1103/PhysRevA.91.032330.
[10] Sergey Bravyi and Robert onig. Classification
of topologically protected gates for local stabilizer
codes. Phys. Rev. Lett., 110(17):170503, 2013.
DOI: 10.1103/PhysRevLett.110.170503.
[11] Fernando Pastawski and Beni Yoshida. Fault-
tolerant logical gates in quantum error-correcting
codes. Phys. Rev. A, 91:012305, 2015. DOI:
10.1103/PhysRevA.91.012305.
[12] Aleksander Kubica, Beni Yoshida, and Fernando
Pastawski. Unfolding the color code. New
Journal of Physics, 17(8):083026, 2015. DOI:
10.1088/1367-2630/17/8/083026.
[13] Tomas Jochym-O’Connor, Aleksander Kubica, and
Theodore J Yoder. Disjointness of stabilizer
codes and limitations on fault-tolerant logical
gates. Phys. Rev. X, 8(2):021047, 2018. DOI:
10.1103/PhysRevX.8.021047.
[14] DJC MacKay, G Mitchison, and PL McFadden.
Sparse-graph codes for quantum error correction.
IEEE Transactions on Information Theory, 50(10):
2315–2330, 2004. DOI: 10.1109/TIT.2004.834737.
[15] Alexey A Kovalev and Leonid P Pryadko. Im-
proved quantum hypergraph-product ldpc codes.
In 2012 IEEE International Symposium on Infor-
mation Theory Proceedings, pages 348–352. IEEE,
2012. DOI: 10.1109/ISIT.2012.6284206.
[16] Sergey Bravyi and Matthew B Hastings. Ho-
mological product codes. In Proceedings of the
forty-sixth annual ACM symposium on Theory of
computing, pages 273–282. ACM, 2014. DOI:
10.1145/2591796.2591870.
[17] Michael H Freedman and Matthew B Hastings.
Quantum systems on non-k-hyperfinite complexes:
a generalization of classical statistical mechanics
on expander graphs. Quant. Inf. Comput., 14(1-
2):144–180, 2014. DOI: 10.26421/QIC14.1-2.
[18] Jean-Pierre Tillich and Gilles emor. Quan-
tum ldpc codes with positive rate and mini-
mum distance proportional to the square root
of the blocklength. IEEE Transactions on In-
formation Theory, 60(2):1193–1202, 2014. DOI:
10.1109/TIT.2013.2292061.
[19] Mathew B. Hastings. Weight reduction for
quantum codes. Quantum Information & Com-
putation, 17(15-16):1307–1334, 2017. DOI:
10.26421/QIC17.15-16.
[20] Daniel Gottesman. Fault-tolerant quantum com-
putation with constant overhead. Quantum In-
formation & Computation, 14(15-16):1338–1372,
2014. DOI: 10.26421/QIC14.15-16.
[21] Anthony Leverrier, Jean-Pierre Tillich, and Gilles
Z´emor. Quantum expander codes. In Foundations
Accepted in Quantum 2019-01-18, click title to verify 9
of Computer Science (FOCS), 2015 IEEE 56th An-
nual Symposium on, pages 810–824. IEEE, 2015.
DOI: 10.1109/FOCS.2015.55.
[22] Omar Fawzi, Antoine Grospellier, and Anthony
Leverrier. Efficient decoding of random errors for
quantum expander codes. In Proceedings of the
50th Annual ACM SIGACT Symposium on Theory
of Computing, pages 521–534. ACM, 2018. DOI:
10.1145/3188745.3188886.
[23] Omar Fawzi, Antoine Grospellier, and An-
thony Leverrier. Constant overhead quantum
fault-tolerance with quantum expander codes.
arXiv:1808.03821, 2018. URL https://arxiv.
org/abs/1808.03821.
[24] Bryan Eastin and Emanuel Knill. Restrictions
on transversal encoded quantum gate sets. Phys.
Rev. Lett., 102:110502, 2009. DOI: 10.1103/Phys-
RevLett.102.110502.
[25] Bei Zeng, Andrew W. Cross, and Isaac L. Chuang.
Transversality Versus Universality for Additive
Quantum Codes. IEEE Transactions on In-
formation Theory, 57:6272–6284, 2011. DOI:
10.1109/TIT.2011.2161917.
[26] Peter W. Shor. Fault-tolerant quantum compu-
tation. Proceedings of the 37th Annual Symposium
on Foundations of Computer Science, pages 56–65,
1996. DOI: 10.1109/SFCS.1996.548464.
[27] Emanuel Knill, Raymond Laflamme, and Woj-
ciech H. Zurek. Threshold accuracy for quan-
tum computation. arXiv: quant-ph/9610011,
1996. URL https://arxiv.org/abs/quant-ph/
9610011.
[28] Sergey Bravyi and Alexei Kitaev. Universal quan-
tum computation with ideal Clifford gates and
noisy ancillas. Phys. Rev. A, 71:022316, 2005. DOI:
10.1103/PhysRevA.71.022316.
[29] Adam Paetznick and Ben W. Reichardt. Uni-
versal fault-tolerant quantum computation with
only transversal gates and error correction. Phys.
Rev. Lett., 111:090505, 2013. DOI: 10.1103/Phys-
RevLett.111.090505.
[30] Tomas Jochym-O’Connor and Raymond
Laflamme. Using concatenated quantum codes
for universal fault-tolerant quantum gates. Phys.
Rev. Lett., 112:010505, 2014. DOI: 10.1103/Phys-
RevLett.112.010505.
[31] Jonas T. Anderson, Guillaume Duclos-Cianci, and
David Poulin. Fault-tolerant conversion between
the steane and reed-muller quantum codes. Phys.
Rev. Lett., 113:080501, 2014. DOI: 10.1103/Phys-
RevLett.113.080501.
[32] ector Bomb´ın. Dimensional jump in quantum er-
ror correction. New J. Phys., 18(4):043038, 2015.
DOI: 10.1088/1367-2630/18/4/043038.
[33] Sergey Bravyi and Andrew Cross. Doubled color
codes. arXiv:1509.03239, 2015. URL https://
arxiv.org/abs/1509.03239.
[34] Tomas Jochym-O’Connor and Stephen D. Bartlett.
Stacked codes: Universal fault-tolerant quantum
computation in a two-dimensional layout. Phys.
Rev. A, 93:022323, 2016. DOI: 10.1103/Phys-
RevA.93.022323.
[35] Cody Jones, Peter Brooks, and Jim Harrington.
Gauge color codes in two dimensions. Phys.
Rev. A, 93(5):052332, 2016. DOI: 10.1103/Phys-
RevA.93.052332.
[36] Theodore J. Yoder, Ryuji Takagi, and Isaac L.
Chuang. Universal fault-tolerant gates on concate-
nated stabilizer codes. Phys. Rev. X, 6:031039, Sep
2016. DOI: 10.1103/PhysRevX.6.031039.
[37] ector Bomb´ın and Miguel A. Martin-Delgado.
Topological quantum distillation. Phys. Rev.
Lett., 97:180501, 2006. DOI: 10.1103/Phys-
RevLett.97.180501.
[38] Alexey A. Kovalev and Leonid P. Pryadko. Fault
tolerance of quantum low-density parity check
codes with sublinear distance scaling. Phys. Rev.
A, 87:020304, Feb 2013. DOI: 10.1103/Phys-
RevA.87.020304.
[39] A. Robert Calderbank and Peter W. Shor. Good
quantum error-correcting codes exist. Phys. Rev.
A, 54:1098–1105, 1996. DOI: 10.1103/Phys-
RevA.54.1098.
[40] Andrew W. Steane. Multiple-Particle Interfer-
ence and Quantum Error Correction. Proc.
Roy. Soc. Lond., 452:2551–2577, 1996. DOI:
10.1098/rspa.1996.0136.
[41] Daniel Gottesman. Stabilizer Codes and Quantum
Error Correction. PhD thesis, California Institute
of Technology, 1997.
[42] Emanuel Knill and Raymond Laflamme. Theory of
quantum error-correcting codes. Phys. Rev. A, 55:
900–911, 1997. DOI: 10.1103/PhysRevA.55.900.
[43] Benjamin J Brown, Wonmin Son, Christina V
Kraus, Rosario Fazio, and Vlatko Vedral. Gen-
erating topological order from a two-dimensional
cluster state using a duality mapping. New J.
Phys., 13(6):065010, 2011. DOI: 10.1088/1367-
2630/13/6/065010.
[44] ector Bomb´ın. Single-shot fault-tolerant quan-
tum error correction. Phys. Rev. X, 5:031043, 2015.
DOI: 10.1103/PhysRevX.5.031043.
[45] Earl Campbell. A theory of single-shot error cor-
rection for adversarial noise. Quantum Sci. Tech-
nol., 2019. DOI: 10.1088/2058-9565/aafc8f.
[46] Adriano Barenco, Charles H. Bennett, Richard
Cleve, David P. DiVincenzo, Norman Margolus,
Peter Shor, Tycho Sleator, John A. Smolin, and
Accepted in Quantum 2019-01-18, click title to verify 10
Harald Weinfurter. Elementary gates for quantum
computation. Phys. Rev. A, 52(5):3457, 1995. DOI:
10.1103/PhysRevA.52.3457.
[47] Christopher Chamberland, Tomas Jochym-
O’Connor, and Raymond Laflamme. Thresholds
for universal concatenated quantum codes. Phys.
Rev. Lett., 117:010501, 2016. DOI: 10.1103/Phys-
RevLett.117.010501.
[48] Christopher Chamberland, Tomas Jochym-
O’Connor, and Raymond Laflamme. Overhead
analysis of universal concatenated quantum
codes. Phys. Rev. A, 95:022313, Feb 2017. DOI:
10.1103/PhysRevA.95.022313.
[49] Christopher Chamberland and Tomas Jochym-
O’Connor. Error suppression via complementary
gauge choices in reed-muller codes. Quantum Sci.
Technol., 2(3):035008, 2017. DOI: 10.1088/2058-
9565/aa7c4a.
[50] Alexei Kitaev. Anyons in an exactly solved model
and beyond. Annals of Physics, 321(1):2–111,
2006. DOI: 10.1016/j.aop.2005.10.005.
[51] Sergey Bravyi, Barbara M Terhal, and Bernhard
Leemhuis. Majorana fermion codes. New J.
Phys., 12(8):083039, 2010. DOI: 10.1088/1367-
2630/12/8/083039.
A Examples of boundary operators
Boundary operator for the 7-qubit Steane code, each
row and column have weight 4:
δ
7
=
1 1 1 1 0 0 0
1 1 0 0 1 1 0
1 0 1 0 1 0 1
1 0 0 1 0 1 1
0 1 1 0 0 1 1
0 1 0 1 1 0 1
0 0 1 1 1 1 0
. (19)
Note that for the Steane code, every non-trivial element
of the stabilizer group is represented in the rows and
columns, this will not hold in general for other codes.
A boundary operator for the padded 15-qubit Reed-
Muller code, composed of 21 qubits:
δ
15p
=
011010011001011 111000
110000110011110 110010
101001010101101 101100
000011111111000 100100
100110010110011 011001
001100111100110 010010
010101011010101 001001
111111110000000 000000
100101101001011 000000
001111000011110 000010
010110100101101 000100
111100001111000 000100
011001100110011 000001
110011001100110 000010
101010101010101 000001
000000000000000 000000
000000000000000 000000
000000000000000 000000
000000000000000 000000
000000000000000 000000
000000000000000 000000
. (20)
We have visually split the matrix into two sets, the first
15 qubits and 6 ancillary qubits. The first 15 qubits
are where the logical information is stored, while the
extra 6 qubits represent the padded ancilla qubits that
are prepared in the |+i state. Note that none of the
Z stabilizers, represented by the columns, have sup-
port on the last 6 qubits. It is fairly straightforward
to check that rank(δ
15p
) = 10. One can recover in-
dependent generators for the rows that correspond to
the 15-qubit Reed-Muller code X stabilizers on the first
15 qubits, and individual single-qubit X generators on
the last 6 qubits. One can also recover the independent
15-qubit Reed-Muller code Z generators by considering
the columns as well as a representative of the indepen-
dent 6 gauge face generators in the last 6 columns, these
correspond to fixing the gauge in the Z basis.
The homological product boundary operator =
δ
7
+ 1 + 1 δ
15p
will have sparsity 15, that is every
row and column in will be of weight at most 15. This
corresponds to the maximum weight operator one would
have to measure for implementing the universal scheme
on the homological product of these two codes, an im-
provement over the universal concatenated model [30]
which would require measuring operators of weight 28.
More importantly, in using higher distance versions of
each of the codes, the concatenated model would re-
quire measuring operators whose weight will grow lin-
early with system size, as opposed to that of the homo-
logical construction which will remain constant-sized.
Accepted in Quantum 2019-01-18, click title to verify 11