# On Quantum Weight Reduction

M. B. Hastings  Station Q, Microsoft Research, Santa Barbara, CA 93106-6105,
USA  Microsoft Quantum and Microsoft Research, Redmond, WA 98052, USA

###### Abstract

We give a general procedure for weight reducing quantum codes. This corrects a
previous workHas (17), and introduces a new technique that we call “coning” to
effectively induce high weight stabilizers in an LDPC code. As one
application, any LDPC code (with arbitrary $O(1)$ stabilizer weights) may be
turned into a code where all stabilizers have weight at most $5$ at the cost
of at most a constant factor increase in number of physical qubits and
constant factor reduction in distance. Also, by applying this technique to a
quantum code whose $X$-stabilizers are derived from a classical log-weight
random code and whose $Z$-stabilizers have linear weight, we construct an LDPC
quantum code with distance $\tilde{\Omega}(N^{2/3})$ and
$\tilde{\Omega}(N^{2/3})$ logical qubits.

An LDPC quantum code is a code (more precisely, a family of codes) in which
every stabilizer acts on $O(1)$ qubits and every qubit participates in $O(1)$
stabilizers. A natural goal is to construct LDPC quantum codes with linear
distance and positive rate; classical codes with such properties are called
“good” and many constructions of them are known. For quantum LDPC codes, there
are several constructions achieving distance
$N^{1/2}\operatorname{polylog}(N)$ based on ideas from topology FML (02) and
higher-dimensional expanders EKZ20a ; KT (20). Finally the $N^{1/2}{\rm
polylog}(N)$ barrier was broken. A construction based on fiber bundlesHHO (20)
achieved distance $\Omega(N^{3/5}/{\rm polylog}(N))$. Then, another
construction gave linear distance up to a logarithm with logarithmically many
logical qubitsPK (20), allowing construction of codes with distance
$N^{1-\alpha/2}$ and $N^{\alpha}$ logical qubits for any $\alpha\in(0,1]$.
Finally, the fiber bundle construction was derandomizedBE (20), and the rate
was improved, giving a different construction of codes with distance
$N^{1-\alpha/2}$ and $N^{\alpha}$ logical qubits, at least for
$\alpha\in[4/5,1]$.

The present paper takes a different approach, based on weight reduction.
Weight reduction, as the name implies, is a procedure to reduce the weight of
stabilizers in a quantum code (and reduce the number of stabilizers acting on
each qubit), perhaps paying the price of some reduction in distance and some
increase in the number of physical qubits. This price is only polynomial in
the “deviation from LDPC” of the original code, suitably defined later.

This has several possible applications; we discuss four. First, many of the
constructions of LDPC quantum codes with distance $\omega(N^{1/2})$ have
fairly high weight stabilizers: while the weights are $O(1)$, the actual
numbers are quite large. By weight reduction, we can construct new codes with
stabilizer weights bounded by some universal quantities which are small $O(1)$
numbers, paying only a constant factor multiplicative cost in rate and number
of physical qubits111However, current constructions based on products and
twisted products of classical codes including HHO (20); PK (20); BE (20) as
well as TZ (14) can be weight reduced more simply using the classical weight
reduction of HHO (20) which has the further advantage of being a chain
homotopy equivalence with bounded Lipschitz constants. In more detail: for
hypergraph product codes which use untwisted products, we can weight reduce
both classical codes in the construction. For codes which are fiber bundles,
we can weight reduce the base code, and the fiber used in current
constructions is a circle which has low weight.. Second, in this paper we give
a construction of a code with distance $N^{1-\alpha/2}$ and $N^{\alpha}$
logical qubits (up to polylogs) for $\alpha\in[2/3,1]$. This is based on
weight reducing a (fairly simple) good quantum code with constant weight
$X$-stabilizers and high weight $Z$-stabilizers. It is perhaps rather
surprising that such a different construction gives similar scaling as those
constructions above, which are instead based on (generalized) products of
complexes. This similarity could perhaps be interpreted as evidence that there
is some fundamental limit to distance and rate of quantum LDPC codes and that
these codes are reaching this limit; alternatively, it could be interpreted
optimistically, that further improvements may be possible. A third conjectural
application is to other constructions of good quantum codes which are almost,
but not quite, LDPC. As an example, consider the homological product codes of
BH (14); these codes have linear distance and rate and square-root weight
stabilizers and are constructed by a homological product of two random codes.
If one could change them into linear distance and rate codes on $N$ qubits in
which every stabilizer has weight $O(N^{\beta})$ (and every qubit participates
in $O(N^{\beta})$ stabilizers) by taking a homological product of a larger
number of codes, then for some sufficiently small $\beta$ this would imply
code with record breaking properties of distance and rate. A fourth
application is to implementing logical Clifford operations on existing high
distance codes. While, for example, the toric code with logical qubits encoded
using punctures has a well-defined methodology to implement logical operations
by measuring products of logical qubits by operators which encircle multiple
punctures, we do not have a general procedure to do logical Clifford
operations on arbitrary codes. We will see that weight reduction allows this.

From one point of view, it is perhaps not surprising that some kind of weight
reducing technique should exist. There is a general procedure to turn quantum
codes into manifolds, first hinted at in BH (14) and then later fully
developed in FH . This procedure uses the stabilizers of the quantum code to
define a chain complex, and then reverse engineers some scheme for attaching
handles using that chain complex. This gives a cell decomposition of some
manifold, and the manifold can be given a metric. If the quantum code is LDPC,
then the resulting cell decomposition has a bounded geometry: every cell
attaches to $O(1)$ other cells. If the quantum code is not LDPC, then every
code attaches to many cells; however, one might expect that one could refine
the cellulation, decomposing each cell into many smaller cells, so that every
cell only attaches to $O(1)$ other cells, and then define an LDPC quantum code
from the resulting refinement of the cellulation. One might hope that if the
initial code is close to LDPC (so that, for example, the power $\beta$ in the
above paragraph is close to $0$), then the qubit overhead entailed by the
refinement would not be too large.

However, to put this abstract idea into practice encounters some obstacles.
For one thing, the procedure to turn a code into a manifold requires a
“lifting”FH  of the code to a chain complex over ${\mathbb{Z}}$, and we do not
know how such a lifting might change the appropriate norm of the rows and
columns of the boundary operator: a code that is “almost LDPC” might lift to
some very non-sparse chain complex. For another thing, this idea is fairly
abstract, and for purposes of weight reducing a code, we would like a concrete
procedure: the refinement needed would depend greatly on the geometry used to
attach the various cells in the procedure of FH . Finally, we would like to do
the weight reduction in as optimal a way as possible.

At the same time, there is one key factor working in our favor, namely, while
we can draw inspiration from geometric ideas like “refining a cellulation”, we
have no obligation to do the weight reduction in a way that makes sense
topologically. Roughly speaking, all we care about is that our various
manipulations do the right thing homologically on certain chain complexes,
without any need that those chain complexes come from cellulations of a
manifold.

A previous paper that I wrote on weight reductionHas (17) claimed to give a
procedure for weight reduction, but Zëmor has pointed out an error in one of
the lemmas. This paper corrects the error in that lemma; other lemmas in that
paper are correct, including distance balancing and the operation described
here as thickening. With the error corrected, the techniques of that paper do
not suffice to do weight reduction, but we introduce a new technique that
makes weight reduction possible. Using this technique and a more careful
analysis, we further find that we can apply weight reduction to a very simple
code, a code whose $X$-stabilizers are low weight, being chosen as the
$X$-stabilizers of a classical (logarithmic) density parity check code, and
whose $Z$-stabilizers are high weight, being chosen uniformly at random from
operators that commute with the given $X$-stabilizers, to obtain an LDPC code
with distance $\tilde{\Omega}(N^{2/3})$ and $\tilde{\Omega}(N^{2/3})$ logical
qubits. By tensoring our code with hypergraph product codesTZ (14) (i.e., by
distance “unbalancing” and then balancing), we can attain (up to polylogs) the
scaling of distance and rate given above for any $\alpha\in[2/3,1]$.

###  .1 Notation and Definitions

Throughout when we say quantum code, we mean a CSS code.

Let us define some parameters of a quantum code. We consider a quantum code
with $N$ qubits, and $N_{X},N_{Z}$ $X$\- and $Z$-type stabilizers; when we
refer to “stabilizers” throughout, we mean generators of the stabilizer group.
Let $K$ be the number of logical qubits.

Assume each qubit participates in at most $q_{X}$ $X$-stabilizers and at most
$q_{Z}$ $Z$-stabilizers. Let $w_{X}$ denote the maximum weight of an
$X$-stabilizer, i.e., the maximum number of Pauli operators in such a
stabilizer. Let $w_{Z}$ denote the maximum weight of a $Z$-stabilizer. Let
$d_{X},d_{Z}$ denote the $X$ and $Z$ distances of the code, i.e., the minimal
weight of the least weight $X$-type and $Z$-type logical operator.

We will assume that all parameters $w_{X},q_{X},w_{Z},q_{Z}$ are $\geq 1$, as
if any of these parameters is $0$ then we have a classical code.

In the language of chain complexes, we have a $2$-complex with three vector
spaces ${\cal A}_{2},{\cal A}_{1},{\cal A}_{0}$ over $\mathbb{F}_{2}$, with
preferred bases, with basis elements (called cells) corresponding to
$Z$-stabilizers, qubits, and $X$-stabilizers, and with boundary operators
$\partial_{1},\partial_{2}$ where $\partial_{j}$ is a linear map from ${\cal
A}_{j}$ to ${\cal A}_{j-1}$. All chain complexes in this paper are over
$F_{2}$; we use the term $2$-complex to indicate that it has $0$-, $1$-,
$2$-cells, but this is a purely algebraic construction, rather than
topological; no assumption is made, for example, that a $1$-cell has two
$0$-cells in it boundary.

We sometimes say that a $1$-chain (we do not distinguish between chains and
cochains) corresponds to a certain $Z$-type or $X$-type operator. This is done
in the obvious way: it is the product of Pauli $Z$ or $X$ on qubits which
whose coefficient in that chain is equal to $1$. We will freely switch between
the terminology of chains and operators, depending on what is most natural.

The column weight of $\partial_{1}$ is bounded by $q_{X}$ and the row weight
is bounded by $w_{X}$. Similarly, the row weight of $\partial_{2}$ is bounded
by $q_{Z}$ and the column weight is bounded by $w_{Z}$. Every nontrivial
representative of $H_{1}$ has weight at least $d_{Z}$ and every nontrivial
representative of $H^{1}$ has weight at least $d_{X}$.

The construction is simplest in the particular case of a code that has the
property of being reasonable. To define this, for every subset $Q$ of qubits
of the code, let $G_{Q}$ be the bipartite graph with left vertices
corresponding to qubits in $Q$ and right vertices corresponding to $X$-type
stabilizers with support on a qubit in $Q$, with edges if a stabilizer acts on
a given qubit.

Let ${\rm supp}(\cdot)$ denote the support of an operator.

Then, a code is reasonable if, for every $Z$-type stabilizer $S$, the graph
$G_{{\rm supp}(S)}$ has the property that, for every connected component of
the graph, the product of Pauli $Z$-operators over qubits corresponding to
left vertices of the component is in the stabilizer group.

Being reasonable is a natural property. Indeed, if it does not hold, then
there is some $Z$-logical operator whose support is contained in the support
of some $Z$-stabilizer. To see this, if the code is not reasonable, then there
is some connected component of $G_{{\rm supp}(S)}$ for some $Z$-type
stabilizer $S$ such that the product of Pauli $Z$-operators over qubits in
that component is not in the stabilizer group; by construction, that product
commutes with the $X$-type stabilizers so it is a $Z$-logical operator.

So, if the $Z$ distance is greater than or equal to the largest stabilizer
weight, then the code is reasonable.

A code has the stronger property of being connected if, for every $Z$-type
stabilizer $S$, $G_{{\rm supp}(S)}$ is connected.

Given a reasonable code, we can choose different stabilizers (i.e., different
generators of the same stabilizer group) to make the code connected: replace
each stabilizer $S$ with one stabilizer for each connected component of
$G_{{\rm supp}(S)}$. Then, remove redundant stabilizers $S$ for which $G_{{\rm
supp}(S)}$ is not connected. Indeed, this can only help reduce $w_{Z}$; this
cannot increase $w_{Z}$ or $q_{Z}$. For example, if a code on two qubits has
stabilizers $Z_{1}$ and $Z_{1}Z_{2}$, with no $X$-type stabilizers, it is
reasonable but not connected; however, we can replace the stabilizers with
$Z_{1}$ and $Z_{2}$ to get a reasonable code with the same stabilizer group.

There is one interesting possible application of “unreasonable” codes. Suppose
one has some code encoding several logical qubits. Then suppose one wishes to
impose some additional constraint on those logical qubits, say
$\tilde{Z}_{1}\tilde{Z}_{2}$, without separately imposing $\tilde{Z}_{1}$ or
$\tilde{Z}_{2}$, and one wishes to do it by adding low weight stabilizers
rather than directly adding some high weight logical operator. This might be
useful for preparing some interesting resource state. We discuss this further
later.

###  .2 Outline

We are going to give a “toolkit” for weight reduction, comprised of several
different ways of transforming a code. The first two we call “copying” and
“gauging”. Despite our use of the term “gauging”, this has nothing to do with
gauge qubits in subsystem codes; it does involve introducing extra physical
qubits to split stabilizers, but all codes are stabilizer, not subsystem. We
handle these two together, as implementing them in the same step can reduce
overhead. The others are called “thickening” and “coning”.

Copying and gauging are, at their heart, operations on a classical code. We
illustrate them by their action on the $X$-stabilizers, but of course they can
be done dually on the $Z$-stabilizers. They can reduce $q_{X},w_{X}$ to
$O(1)$, but they unfortunately increase $w_{Z}$, and may impact the distance.
The gauging operation was in lemma 1 of Has (17); this was the lemma with an
error in it, corrected here.

Thickening was already introduced in Has (17), under the name $Z$-type qubit
splitting. This is an operation that reduces $q_{Z}$ (or, dually, $q_{X}$).
This has the advantage that it reduces $q_{Z}$ without impacting the other
parameters $w_{Z},w_{X},q_{X}$(to be precise, a large $q_{X}$ on the code
input to thickening can lead to a large $w_{Z}$ on the output code, but
otherwise the impact on other parameters is minimal). Indeed, thickening
increases $d_{X}$, though it does this at the cost of increasing $N$.

Coning is a new operation. It can reduce $w_{Z}$, again with minimal impact on
other parameters. This coning operation is an essential part of weight
reduction. It is the main conceptual contribution of the weight reduction of
this paper. This general construction uses two new key ideas, first the
mapping cone from topology as a way to effectively induce stabilizers, and
second, a way of adding additional relations to kill unwanted homology using
recent results on cycle bases in graphs. We explain an example using the toric
code where this coning process reduces to a familiar geometric construction of
“filling in holes”. The mapping cone in a sense gives us a way to “fill in
holes” even when there is no obvious geometry for general codes.

Coning is a general procedure to weight reduce $Z$-stabilizers, but this can
also be thought of as adding additional “nonlocal” operators to a code. That
is, suppose one has some code that is already LDPC, and one wishes to add a
stabilizer that is one of the logical operators of the code (thus, forcing a
logical qubit to take a certain value); coning gives one a procedure to do
this by adding some extra qubits and low weight stabilizers. Thus, this may
have some application in measuring logical operators in arbitrary LDPC quantum
codes; we leave this for future work.

In Section IV, we will show that given these operations, any code can be
weight reduced to an LDPC, with an increase in $N$ and decrease in distance by
a factor polynomial in $w_{X},w_{Z},q_{X},q_{Z}$. However, we give all the
tools here, as it seems difficult to say in advance what may be the most
effective way to weight reduce a given code. One might use the various tools
in different sequences.

In Section V, we apply this weight reduction procedure to construct an LDPC
code with distance $\tilde{\Omega}(N^{2/3})$.

In Section VI, we show how to improve the “coning” construction, so that one
of the important parameters of that construction (called “soundness”) can be
improved, which in turns can improve the distance of the resulting code. This
is not needed for Section V, but is given if it may be useful later. Further,
as we remark in Section VI, the improving soundness procedure allows a partial
derandomization of the construction of Section V.

##  I Copying and Gauging

Copying is a simple technique to reduce $q_{X}$ (or, dually, $q_{Z}$). We
sketch this briefly, since we will give a detailed explanation later when
combining it with gauging. Simply concatenate a code with a repetition code on
$q_{X}$ qubits in the $X$-basis, where the repetition code has stabilizers
$X_{1}X_{2},X_{2}X_{3},\ldots,X_{q_{X}-1}X_{q_{X}}$. This increases the
$Z$-distance of the concatenated code, while leaving the $X$-distance
unchanged, and increases the number of qubits. Unfortunately, it increases the
$Z$-stabilizer weight, because $Z$-operators of the original code get replaced
by logical $Z$-operators of the repetition code, i.e., products of $Z$ over
$q_{X}$ qubits. However, it can reduce $q_{X}$: for each qubit of the original
code, for each $X$-stabilizer acting on that qubit, we can choose a distinct
representative of the logical $X$-operator. In this case, a representative of
logical $X$ in the repetition code is simply $X$ on a single qubit. Thus, this
reduces $q_{X}$ to at most $3$: one stabilizer of the original code, plus at
most two stabilizers of the repetition code.

By combining copying and “gauging” we can get a new code with $w_{X},q_{X}\leq
3$.

We first explain the effect of copying and gauging on the $X$-stabilizers in
Section I.1, and then explain how to change the $Z$-stabilizers in Section
I.2. The operation on the $X$-stabilizers is essentially the same as weight
reducing a classical codeHHO (20). The operation on the $X$-stabilizers will
increase the number of qubits and increase the weight of the $Z$-stabilizers.

Throughout this section, the “original code” is the code before weight
reducing, and the “$X$-reduced code” is the code constructed in this section.
We will then in subsequent sections apply additional operations to the
$X$-reduced code to get a final weight reduced code.

###  I.1 New $X$-Stabilizers

The procedure to reduce $q_{X}$ can be understood intuitively as making
several copies of each qubit in the $X$-basis, adding $X$-stabilizers to
enforce that they are copies, and having different copies participate in
different $X$-stabilizers,, while the procedure to reduce $w_{X}$ can be
understood as the dual.

For each qubit $q$ of the original code, the $X$-reduced code will have
$q_{X}$ qubits, labeled by a pair $(q,j)$ where $j\in\\{1,\ldots,q_{X}\\}$.
Similarly, for each $X$-stabilizer $s$ of the original code, if the stabilizer
acts on $d_{s}\leq w_{X}$ bits, the $X$-reduced code will have $d_{s}$
$X$-stabilizers, labelled by a pair $(s,k)$ where $k\in\\{1,\ldots,d_{s}\\}$.
We add also $q_{X}-1$ additional $X$-stabilizers for each qubit $q$; label
these additional stabilizers by a pair $[q,j]$ for
$j\in\\{1,\ldots,q_{X}-1\\}$. Further, add $d_{s}-1$ additional qubits for
each $X$-stabilizer $s$; label these additional qubits by a pair $[s,k]$.

We will call qubits and $X$-stabilizers labelled by pairs $[s,k]$ and $[q,j]$
the “new” qubits and stabilizers. The other qubits and $X$-stabilizers are
labelled by pairs $(q,j)$ and $(s,k)$, and are called the “copied” qubits and
stabilizers. We say that $(q,j)$ and $[q,j]$ are “associated” with $q$ and
$(s,k)$ and $[s,k]$ are “associated” with $s$.

Thus, if the original code has $N$ qubits and $N_{X}$ $X$-stabilizers, the
$X$-reduced code has $O(N+Nq_{X})=O(Nq_{X})$ qubits and
$O(N+Nq_{X})=O(Nq_{X})$ $X$-stabilizers.

We now specify the $X$-stabilizers. Each stabilizer $[q,j]$ is a product

$X_{(q,j)}X_{(q,j+1)}.$

Each stabilizer $(s,k)$ is as follows. Suppose stabilizer $s$ was a product
$X_{q_{1}}X_{q_{2}}\ldots X_{q_{d_{s}}}$. Then, we have

$\displaystyle(s,1)=$ $\displaystyle X_{[s,1]}X_{(q_{1},j_{s,1})}$ (1)
$\displaystyle 1<k<d_{s}\quad\rightarrow\quad$ $\displaystyle(s,k)=$
$\displaystyle X_{[s,k-1]}X_{[s,k]}X_{(q_{k},j_{s,k})}$
$\displaystyle(s,d_{s})=$ $\displaystyle
X_{[s,d_{s}-1]}X_{(q_{d_{s}},j_{s,d_{s}})}.$

We choose the sequences $j_{s,k}$ so that each qubit is in at most $3$
stabilizers: at most $2$ new stabilizers, plus one other.

We can explain this in the language of boundaries also. The stabilizer $[q,j]$
has qubits $(q,j)$ and $(q,j+1)$ in its coboundary. Similarly, the qubit
$[s,k]$ has boundary $(s,k)+(s,k+1)$ for each $k$. Finally, for each qubit $q$
and each stabilizer $s$, such that $s$ was in the boundary of $q$, we pick
some $j\in\\{1,\ldots,q_{X}\\}$ and some $k\in\\{1,\ldots,d_{s}\\}$ and then
$(s,k)$ will be in the boundary of $(q,j)$, choosing $j,k$ so that each qubit
has at most $3$ stabilizers in its boundary and each stabilizer has at most
$3$ qubits in its coboundary.

###  I.2 New $Z$-Stabilizers

We now explain how to choose the $Z$-stabilizers of the $X$-reduced code. For
each $Z$-stabilizer $S$ of the original code, there will be some
$Z$-stabilizer $\tilde{S}$ of the $X$-reduced code, and these will be the only
$Z$-stabilizers of the $X$-reduced code.

We now specify $\tilde{S}$. Let $S$ be some given $Z$-stabilizer of the
original code, with $S=Z_{q_{1}}Z_{q_{2}}\ldots Z_{q_{w}}$ for some $w$. For
every qubit $q$ of the original code, define

$\tilde{Z}_{q}=\prod_{j=1}^{q_{X}}Z_{(q,j)}.$ (2)

To motivate this, recall that we have, in the previous subsection, “copied”
each qubit in the $X$-basis, and this $\tilde{Z}$ is a logical operator of a
repetition code.

Let

$\tilde{S}=\tilde{Z}_{q_{1}}\tilde{Z}_{q_{2}}\ldots\tilde{Z}_{q_{w}}G,$ (3)

where we next define the operator $G$ so that $\tilde{S}$ commutes with all
stabilizers.

We now define $G$. Each qubit $Q_{a}$ that $S$ acts on may in turn also be in
some $X$-stabilizers. Let $X(S)$ denote the set of $X$ stabilizers which are
in the boundary of some qubit which is in the boundary of $S$. Let

$G=\prod_{s\in X(S)}G_{s},$

where $G_{s}$ is as follows. Since $s$ commutes with $S$ by assumption, there
are an even number of qubits which are in the support of both $S$ and $s$.
Denote these qubits by $q_{s,1},q_{s,2},\ldots$ Each of these qubits is in the
coboundary of some stabilizer of the $X$-reduced code which is associated with
$s$. Let $q_{s,a}$ be in the coboundary of stabilizer $(s,j_{a})$. Order these
qubits so that $j_{1}<j_{2}<\ldots$. For each pair of successive qubits,
$q_{s,2n+1},q_{s,2n+1}$ for $n=0,1,\ldots$, define a “string” which is a
product of operators $Z_{[s,j_{2n}]}Z_{[s,j_{2n}+1]}\ldots
Z_{[s,j_{2n+1}-1]}$. Let $G_{s}$ be the product of these strings.

Then, indeed, the $Z$-stabilizers of the $X$-reduced code commute with all the
$X$-stabilizers.

###  I.3 $X$-Reduced Code Properties

Let parameters with a tilde (such as $\tilde{w}_{X},\tilde{d}_{X},\ldots$)
denote the corresponding parameters of the $X$-reduced code.

The following lemma corrects lemma 1 of Has (17). In particular, item 5
corrects an error in that one.

Also, lemma 1 of Has (17) only did the “gauging” part of this construction,
not the copying. We have combined them here: while copying does increase
$w_{Z}$ (due to the need to replace $Z$ operators of the original code by
higher weight logical $Z$ operators of the concatenated code), this weight
increase is negligible compared to weight increases that are caused by the
gauging operations. So, there is no reason not to do both at once.

######  Lemma 1.

The $X$-reduced code has the following parameters:

  * 1.

$\tilde{N}=O(Nq_{X})$.

  * 2.

$\tilde{K}=K$.

  * 3.

$\tilde{w}_{X},\tilde{q}_{X}=O(1)$.

  * 4.

$\tilde{q}_{Z}\leq{\rm max}(q_{Z},w_{X}q_{Z})$.

  * 5.

$\tilde{w}_{Z}\leq q_{Z}q_{X}(1+w_{X}).$

  * 6.

$\tilde{d}_{Z}\geq d_{Z}q_{X}$.

  * 7.

$\tilde{d}_{X}\geq d_{X}\Omega(1/w_{X})$.

###### Proof.

  * 1.

Shown previously.

  * 2.

We have increased the number of qubits but also increased the rank of the
$X$-stabilizer group by the same amount.

  * 3.

Immediate from construction of the code.

  * 4.

For any copied qubit of the $X$-reduced code, a $Z$-stabilizer acts on that
qubit iff the corresponding $Z$-stabilizer of the original code acts on the
qubit of the original code associated to that copied qubit. Hence, the maximum
number of $Z$-stabilizers acting on those qubits is bounded by $q_{Z}$. For
any new qubit $[s,k]$ of the $X$-reduced code, a $Z$-stabilizer $\tilde{S}$ of
the $X$-reduced code can only act on that qubit if $s$ is in $X(S)$. Hence,
the maximum number of $Z$-stabilizers acting on those qubits is bounded by
$w_{X}q_{Z}$. Hence, $\tilde{q}_{Z}\leq{\rm max}(q_{Z},w_{X}q_{Z})$.

  * 5.

The weight of each $\tilde{Z}$ equals $q_{X}$, so the weight of
$\tilde{Z}_{q_{1}}\tilde{Z}_{q_{2}}\ldots\tilde{Z}_{q_{w}}$ is bounded by
$w_{Z}q_{X}$. The weight of $G$ is equal to the sum over $s\in X(S)$ of the
weight of $G_{s}$, which in turn is bounded by $w_{X}$. The cardinality of
$X(S)$ is bounded by $w_{Z}q_{X}$. So, the weight of $G$ is bounded by
$w_{Z}q_{X}w_{X}$. So, $\tilde{w}_{Z}\leq w_{Z}q_{X}(1+w_{X}).$

  * 6.

It is useful to define two additional stabilizer groups. First, consider the
subgroup of the $X$-stabilizer group (of the $X$-reduced code) consisting of
all stabilizers supported on the copied qubits. Call this group $G_{S}^{X}$,
the subscript standing for “shortened”, in analogy to the idea of a shortened
code in coding theory. Second, consider the group $G_{P}^{Z}$ (the subscript
stands for “punctured”) of products of $Z$-operators acting on the copied
qubits obtained by “forgetting” the action of $Z$-stabilizers on the new
qubits, i.e., an operator is in $G_{P}^{Z}$ iff it can be multiplied some
product of $Z$-operators on the new qubits such that the product is in the
$Z$-stabilizer group. Note that $G_{P}^{Z}$ and $G_{S}^{X}$ commute with each
other; further, they are the stabilizer group of the original code
concatenated with a repetition code in the $X$-basis. Consider any $Z$-logical
operator $L$. This operator is a product of two operators $L_{C}L_{N}$ where
$L_{C}$ acts only on the copied qubits and $L_{N}$ acts only on the new
qubits. If $L_{C}$ is the identity, then $L_{N}$ must be also. Note that
$L_{C}$ must commute with $G_{S}^{X}$. Further, we can multiply $L_{C}$ by any
element of $G_{P}^{Z}$, changing $L_{N}$ in some way, and the result is a
multiplication of $L$ by an element of the stabilizer group. Hence, if $L$ is
nontrivial, then $L_{C}$ must be a nontrivial logical operator of the
concatenated code. Hence, the weight of $\tilde{L}$ must be at least
$d_{Z}q_{X}$.

  * 7.

Consider any nontrivial $Z$-logical operator. This operator is a product of
two operators $L_{C}L_{N}$ where $L_{C}$ acts only on the copied qubits and
$L_{N}$ acts only on the new qubits.

If $L_{N}$ is the identity, it is easy to see that the weight of $L_{C}$ must
be at least $d_{X}$. We can multiply $L$ by an element of $G_{S}^{X}$, which
leaves $L_{N}$ equal to the identity but changes $L_{C}$. The operator $L_{C}$
must commute with $G_{P}^{Z}$. Hence, $L_{C}$ must be a nontrivial logical
operator of the concatenated code and so must have weight at least $d_{X}$.

Suppose instead $L_{N}$ is not equal to the identity. However, by multiplying
$L$ by a product of copied stabilizers, we can turn $L_{N}$ into the identity,
increasing the weight of $L$ by a factor of at most $w_{X}$.

∎

##  II Thickening

We now explain how to reduce $q_{Z}$. This is the same as in Has (17), and we
mostly reproduce the results there, with some added discussion.

###  II.1 Thickening Construction

This step is done in two substeps. In the first step, we take some code $C$
(in this case, $C$ is the code obtained from the previous section after
reducing the $X$-stabilizers). We write that code as a chain complex ${\cal
C}$, associating $X$-stabilizers with $0$-cells, qubits with $1$-cells, and
$Z$-stabilizers with $2$-cells (this shifts the dimension by $1$ from the
convention used in Has (17), where qubits were associated with $2$-cells). We
take the homological product of this complex ${\cal C}$ with a chain complex
${\cal E}$ corresponding to a cellulation of an interval; ${\cal E}$ has only
$0$-cells and $1$-cells in its chain complex. This step may be geometrically
interpreted as “thickening” the complex, by taking its product with an
interval. The resulting product complex is called ${\cal D}$ and the product
code is called $D$.

In the second step, we observe that there is a large redundancy among the
$Z$-type stabilizers of $D$: $Z$-type stabilizers at different values of the
coordinate in the direction of the interval differ only by a product of other
stabilizers. Let us call this coordinate in the interval direction the
“height”. This can be understood as a result of the homological product: the
chain complex ${\cal E}$ has $1$-cells, and as a result the product ${\cal
C}\otimes{\cal E}$ has $3$-cells which encode redundancies among the
$Z$-stabilizers of $D$. This allows us to remove many of the stabilizers in
$D$ and obtain a code $\tilde{C}$ with smaller $q_{Z}$. Geometrically, one may
view this as follows: since the complex has been thickened, we can attach the
cells corresponding to stabilizers at different heights, to avoid attaching
too many to any given cell.

To define ${\cal E}$, fix an integer integer, $\ell>1$. Define chain complex
${\cal E}_{1}\stackrel{{\scriptstyle\partial^{\cal
E}_{1}}}{{\rightarrow}}{\cal E}_{0}$, where ${\rm dim}({\cal E}_{0})=\ell$ and
${\rm dim}({\cal E}_{1})=\ell-1$, with

$\partial^{\cal E}_{1}=\begin{pmatrix}1&\\\ 1&1\\\ &1&1\\\ &&&.&.\\\
&&&&.&.\\\ &&&&&.&.\\\ &&&&&&1&1\\\ &&&&&&&1\end{pmatrix}.$ (4)

This chain complex can be interpreted geometrically as a cellulation of an
interval, with $\ell$ $0$-cells and $(\ell-1)$ $1$-cells. We have
$b_{1}(E)=0,b_{0}(E)=1$.

By the Künneth formula, this code $D$ has the same number of logical qubits as
$C$ does. This code has $Nl+n_{X}(\ell-1)$ qubits and $\ell n_{X}$ $X$-type
stabilizers.

We now define the code $\tilde{C}$. This code $\tilde{C}$ will have the same
number of qubits and $X$-type stabilizers as $D$ does. This code will be
obtained by taking a subset of the $Z$-type stabilizers of the stabilizers of
$D$, while taking all of the $X$-type stabilizers. What we will show is that
although we take only a subset of the $Z$-type stabilizers, the code
$\tilde{C}$ will have the same stabilizer group as $D$.

Recall that the $Z$-type stablizers are in one-to-one correspondence with
basis elements of ${\cal D}_{2}={\cal C}_{2}\otimes{\cal E}_{0}\oplus{\cal
C}_{1}\otimes{\cal E}_{1}$. We keep all $Z$-type stabilizers corresponding to
basis elements of ${\cal C}_{1}\otimes{\cal E}_{1}$. However, for each, basis
elements of ${\cal C}_{2}$, we keep only one $Z$-type stabilizer in ${\cal
C}_{2}\otimes{\cal E}_{0}$. Let $w_{1},\ldots,w_{\ell}$ be basis vectors for
${\cal E}_{0}$ in the standard basis. For each basis element $v\in{\cal
C}_{2}$ in the standard basis, we pick one integer $k$, with $1\leq
k\leq\ell$, and we keep the stabilizer corresponding to $v\otimes w_{k}$.

In the following lemma, $\tilde{K}$ refers to the number of logical qubits of
$\tilde{C}$, while various
$\tilde{w}_{X},\tilde{w}_{Z},\tilde{q}_{X},\tilde{q}_{Z}$ refer to the
appropriate parameters of $\tilde{C}$.

Note item 7, showing that the distance increases by a factor of $\ell$. This
increase in distance is the same as that from distance balancing in Has (17).

Remark: this thickening technique is essentially the same as the distance
balancing in Has (17), using an extra trick of “choosing heights” to reduce
$q_{Z}$. It improves $X$-distance while increasing number of physical qubits
and worsening rate since the number of logical qubits in unchanged. So, the
reader might wonder whether we can do thickening in a way more similar to
EKZ20b , that would reduce $q_{Z}$ while leaving the rate unchanged. We do not
see any way to do this, however: the reduction in $q_{Z}$ depends on a
particular form of redundancy among the $Z$-stabilizers which would not be
present in the distance balancing of EKZ20b . However, we leave this as an
open problem.

######  Lemma 2.

The code $\tilde{C}$ has the following properties:

  * 1.

All stabilizers commute with each other. $\tilde{N}=Nl+n_{X}(\ell-1)$ and
$\tilde{n}_{Z}=n_{Z}+(\ell-1)N$ and $\tilde{n}_{X}=\ell n_{X}$.

  * 2.

Codes $\tilde{C}$ and $D$ have the same stabilizer group. Explicitly, for each
$Z$-type stabilizer of the form $Z_{q_{1}}Z_{q_{2}}\ldots Z_{q_{w}}$ in $C$,
the stabilizer group of $\tilde{C}$ contains $Z_{(q_{1},m)}Z_{(q_{2},m)}\ldots
Z_{(q_{w},m)}$ for all $1\leq m\leq\ell$.

  * 3.

$\tilde{K}=K$.

  * 4.

$\tilde{w}_{X}=w_{X}+2$ if $\ell\geq 3$ and $\tilde{w}_{X}=w_{X}+1$ if
$\ell=2$.

  * 5.

$\tilde{w}_{Z}={\rm max}(w_{Z},2+q_{X})$.

  * 6.

$\tilde{q}_{X}={\rm max}(q_{X},2)$.

  * 7.

$\tilde{d}_{X}=\ell d_{X}$.

  * 8.

$\tilde{d}_{Z}=d_{Z}$.

###### Proof.

This is lemma 2 in Has (17). ∎

###  II.2 Choosing Heights

The value of $\tilde{q}_{Z}$ will depend on which stabilizers
$Z_{(q_{1},k)}Z_{(q_{2},k)}\ldots Z_{(q_{w},k)}$ we choose to include. If we
keep the same $k$ for all $Z$-type stabilizers of $C$, then we have no
improvement in $\tilde{q}_{Z}$. However, if we choose different $k$ for
different stabilizers then we can reduce $\tilde{q}_{Z}$ by making different
stabilizers act on different qubits $(q,k)$. As shown in Has (17), for any
desired $\tilde{q}_{Z}$, we can attain a code with that $\tilde{q}_{Z}$ by
choosing large enough $\ell$. The following lemma gives upper bounds on how
big an $\ell$ is needed.

######  Lemma 3.

Let $w$ be any positive integer. For $\ell$ sufficiently large that

$2e{q_{Z}\choose w+1}(\frac{1}{\ell})^{w+1}{\rm min}(q_{Z}w_{Z},N)\ell\leq 1,$
(5)

there is a choice of $k$ for each $Z$-type stabilizer of $C$ such that

$\tilde{q}_{Z}\leq{\rm max}(w+2,w_{X}).$ (6)

###### Proof.

This is lemma 3 in Has (17). ∎

The relation between $\tilde{q}_{Z}$ and $w$ is as follows: the lemma shows
that there is a choice of $k$ for each $Z$-type stabilizer of $C$ such that
each qubit corresponding to basis element of ${\cal C}_{1}\otimes{\cal E}_{0}$
is in at most $w$ different stabilizers corresponding to basis elements of
${\cal C}_{2}\otimes{\cal E}_{0}$. Additionally, each qubit a corresponding to
basis element of ${\cal C}_{1}\otimes{\cal E}_{0}$ is in at most $2$
stabilizers corresponding to basis elements of ${\cal C}_{1}\otimes cE_{1}$.
There are also qubits corresponding to basis elements of ${\cal
C}_{0}\otimes{\cal E}_{1}$. These are in at most $w_{X}$ stabilizers
corresponding to basis elements of ${\cal C}_{1}\otimes{\cal E}_{1}$.

Let us make some comments on this lemma. First, note that one might have
guessed that it would suffices to take $\ell$ proportional to $q_{Z}$ in order
to attain $\tilde{q}_{Z}=O(1)$. The reasoning behind this would be, roughly:
“if each qubits participates in at most $q_{Z}$ different stabilizers, then if
I thicken by an amount $\ell\sim q_{Z}$, I can put each stabilizer at a
different position.” Unfortunately, the lemma is slightly weaker than this,
and this rough reasoning is not correct.

However, the lemma is not much weaker. Fix any $\tilde{q}_{Z}=O(1)$. Assume
that the code $C$ that is input to this procedure has already been copied and
gauged so that $w_{X}=3$. So, one may take

$\ell=O(q_{Z}^{\frac{w+1}{w}}{\rm min}(q_{Z}w_{Z},N)^{1/w}),$

with $w=\tilde{q}_{Z}-2$. Hence, we have

######  Lemma 4.

For any $\epsilon>0$, we can pick $\tilde{q}_{Z}=O(1)$ with
$\ell=O(q_{Z}^{1+\epsilon}{\rm min}(q_{Z}w_{Z},N)^{O(\epsilon)}).$

Also we have

######  Lemma 5.

We can pick $\tilde{q}_{Z}=O(1)$ with $\ell=q_{Z}w_{Z}+1$.

###### Proof.

This follows from a relationship with graph coloring. Considering a graph with
vertices corresponding to stabilizers, with two vertices neighboring if share
a qubit in their support. This graph has degree $\leq q_{Z}w_{Z}$ and so can
be colored with at most $q_{Z}w_{Z}+1$ colors. ∎

The proof of lemma 3 is probabilistic. It relies on the Lovasz local lemma. If
one is willing to accept a constant factor increase in $\ell$, then there are
efficient algorithms to find the needed choiceMT (10).

Also, if one is will to work with the slightly weaker result that such a
choice of $k$ for each $Z$-type stabilizer exists whenever ${q_{Z}\choose
w+1}(\frac{1}{\ell})^{w+1}N\ell<O(1),$ then the proof of the lemma shows that
choosing the $k$ independently and uniformly at random will work with
probability $\Omega(1)$.

We also remark that lemma 3 can be understood in terms of a variant of a
standard problem in graph theory, called “strong hypergraph coloring”AH (04).
In graph coloring, one has a graph, and one must color each vertex from some
number of colors so that for every edge, both vertices attached to that edge
have different colors. In hypergraph coloring, a hyperedge may have more than
two vertices, and so there are several possible coloring problems. In strong
hypergraph coloring, the requirement is that every vertex in a hyperedge must
have different colors.

To relate these, consider a hypergraph, where hyperedges correspond to qubits
of $C$ and vertices correspond to $Z$-stabilizers of $C$. The vertices in each
hyperedge are the set of $Z$-stabilizers acting on that qubit. Then, a
coloring with at most $\ell$ different colors corresponds to a choice of $k$
for each $Z$-stabilizer of $C$. The case $w=1$ corresponds to a strong
hypergraph coloring. It is possiblestr  that such a strong hypergraph coloring
can require a number of colors of order the vertex degree times the hyperedge
degree, i.e., $\ell=\Theta(w_{Z}q_{Z})$. However, what we see is that from
lemma 4 is that by considering colorings in which, for every hyperedge, no
color in that hyperedge is repeated more than $w$ times, we can use a number
of colors that is closer to $q_{Z}$.

##  III Coning

We mostly consider the case of reasonable codes as that is the simplest and
most important one. In Section III.3, we consider the case of “unreasonable”
codes.

In Section III.2, we give an illustration of the procedure here in a simple
case related to the toric code. This may help clarify it. We also give some
geometric interpretation.

At this point, we need some definitions from homological algebra. Throughout
this section, all chain complexes will be over $\mathbb{F}_{2}$. First we
need:

######  Definition 1.

Given two chain complexes ${\cal A},{\cal B}$, with corresponding boundary
operators $\partial^{\cal A},\partial^{\cal B}$, a linear map $f:{\cal
B}\rightarrow{\cal A}$ is called a chain map if it commutes with the boundary:
$\partial^{\cal A}\circ f=f\circ\partial^{\cal B}$.

We recall the definition of the mapping cone of a chain map. Here the chain
map is assumed to preserve degrees, so that it maps ${\cal B}_{j}$ to ${\cal
A}_{j}$.

######  Definition 2.

Given a chain map $f:{\cal B}\rightarrow{\cal A}$, the cone of $f$, written
$\operatorname{Cone}(f)$, is the following chain complex. The vector space
$\operatorname{Cone}(f)_{j}$ is defined to be ${\cal A}_{j}\oplus{\cal
B}_{j-1}$, and the boundary operator is defined by

$\partial\equiv\begin{pmatrix}\partial^{\cal A}&f\\\
0&\partial_{B}\end{pmatrix}.$ (7)

One useful example of a cone is when ${\cal A}={\cal B}$ and the map $f$ is
the identity map. In this case, all homology groups of
$\operatorname{Cone}(f)$ are trivial. To see this, consider some $j$-chain
$u=x_{j}\oplus y_{j}$ where $x_{j}\in{\cal A}_{j}$ and $y_{j}\in{\cal
B}_{j-1}$. Then if $\partial u=0$, we have $\partial y_{j}=0$ and $\partial
x_{j}=y_{j}$. This implies that $u$ is a boundary: it is the boundary of the
$(j+1)$-chain given by $0\oplus x_{j}$. This is a special case of a more
general result: if the map $f$ induces an isomorphism on all homology groups,
then all homology groups of $\operatorname{Cone}(f)$ are trivialncl .

We now describe the construction to reduce $Z$-stabilizer weight using a cone.
We first construct a code we call the “cone code”; this code will have reduced
$Z$-stabilizer weight but unfortunately doing this may create large
$X$-stabilizer weight and $q_{X}$ While this may seem to merely delay the
problem, the particular way in which the code code is constructed means that
it will be easy to reduce the weight of those $X$-stabilizers by a process
explained later.

Consider some quantum code $C$. Let $C^{\prime}$ be some code that contains
the same qubits as $C$, and contains the same $X$-stabilizers as $C$, but has
only some subset of the $Z$-stabilizers. These will, in most applications, be
stabilizers of $C$ which are already low weight, and do not need to be weight
reduced. We will call these the “direct stabilizers”. The coning construction
will be used to “induce” the remaining stabilizers.

Let ${\cal A}$ be the chain complex corresponding to $C^{\prime}$

We now construct a complex ${\cal B}$. The complex has $-1$-cells, $0$-cells,
and $1$-cells. We may think of ${\cal B}$ as describing a classical code with
the $0$-cells being checks, the $1$-cells being bits, and the $-1$-cells being
“redundancies” among the checks. The complex ${\cal B}$ is given by

${\cal B}=\oplus\overline{{\cal B}}_{i}.$

Before defining the $\overline{{\cal B}}_{i}$, we define some complexes ${\cal
B}_{i}$ from which the $\overline{{\cal B}}_{i}$ are constructed.

The chain complex ${\cal B}_{i}$ has $0$-cells and $1$-cells (no $-1$-cells).
The complex $\overline{{\cal B}}_{i}$ defined later is given by adding
additional $-1$-cells to ${\cal B}$, while constructing some boundary operator
$\partial_{0}$; this is done to kill the zeroth homology of ${\cal B}_{i}$.

Definition of ${\cal B}_{i}$: Let $Q_{1},Q_{2},\ldots,Q_{m}$, for some integer
$m$, be some sequence of sets of qubits of the given code. If we are using the
code constructed after a previous “thickening” step, we will often choose the
$Q_{i}$ to be subsets of qubits corresponding to basis elements of ${\cal
C}_{2}\otimes{\cal E}_{0}$ rather than ${\cal C}_{1}\otimes{\cal E}_{1}$,
simply because there may be no need to weight reduce the other elements.

Choose these sets $Q_{i}$ such that, for every $i$, the product of Pauli $Z$
operators on all qubits in set $Q_{i}$ commutes with all $X$-stabilizers of
the code. The chain complex ${\cal B}_{i}$ will have $1$-cells labeled by
elements of $Q_{i}$.

For each set $Q_{i}$, define a set $S_{i}$ as follows. Each $S_{i}$ will be
the set of $X$-stabilizers of the quantum code which have support on at least
one qubit in $Q_{i}$. Each stabilizer in $S_{i}$ must in fact have support on
an even number of qubits of $Q_{i}$ by assumption. If we have weight reduced
those stabilizers so that they have weight $3$, then indeed each stabilizer in
$S_{i}$ must have support on two qubits of $Q_{i}$. If we have not weight
reduced in this way, then we need to make one more set of choice: for each
stabilizer in $S_{i}$, “pair off” the qubits in $Q_{i}$ on which that
stabilizer has support in some way. That is, if some stabilizer has support on
$k$ qubits in $Q_{i}$, we find $k/2$ pairs of qubits, putting one qubit in
each pair. Then, $0$-cells of ${\cal B}_{i}$ will be in one-to-one
correspondence with a tuple consisting of, first, an element of $S_{i}$, and,
second, one of these pairs; we write such a tuple $(S,j)$ where $S\in S_{i}$
and $j$ labels a pair.

The boundary operator of the chain complex ${\cal B}_{i}$ will be the obvious
one: the boundary of a given $1$-cell consists of all tuples $(S,j)$ such that
the corresponding qubit is in the given pair.

This chain complex then corresponds to a classical code, with bits
corresponding to $1$-cells, and with checks corresponding to $0$-cells, such
that every check acts on two bits.

If ${\cal B}_{i}$ has trivial zeroth homology, then we take $\overline{{\cal
B}}_{i}={\cal B}_{i}$. While the case that ${\cal B}_{i}$ does not have
trivial zeroth homology is the most interesting one, the reader may, on first
reading, want to skip the definition of $\overline{{\cal B}}_{i}$ and simply
assume that ${\cal B}_{i}$ does have zeroth homology, in order to understand
in the simplest case how the coning construction gives the desired result.

Let us sketch what this “desired result” is. For each $i$, the complex ${\cal
B}_{i}$ has some first homology. By assumption, the sum of all $1$-cells is an
element of first homology, but there may be other elements. Each such element
of first homology corresponds to some subset of qubits of the code $C$. The
coning construction will “effectively” induce, for each such subset, $Z$-type
stabilizer given by the product of Pauli $Z$-operators on that subset.

Remark: assuming that the code is reasonable, we then choose, for each
$Z$-stabilizer of the code, one set $Q_{i}$ equal to the support of that
stabilizer. If the code is not reasonable, then potentially this choice will
not produce the original code but rather will increase the stabilizer group by
adding some $Z$-logical operators to the stabilizer group.

We define ${\cal B}_{i}$ to have $1$-cells corresponding to qubits in $Q_{i}$,
$0$-cells corresponding to $X$-stabilizers in $S_{i}$, and the boundary
operator is defined in the obvious way from the quantum code: the matrix
element of the boundary operator of ${\cal B}_{i}$ from the cell corresponding
to a qubit $q\in Q_{i}$ to a cell corresponding to an $X$-stabilizer $x\in
S_{i}$ is equal to the matrix element of the boundary operator of ${\cal A}$
from the cell corresponding to $q$ to the cell corresponding to $x$. We define
${\cal B}_{i}$ to have some set of $-1$-cells and some boundary operator
$\partial_{0}$ mapping $0$-chains to $-1$-chains. The choice of $-1$-cells and
construction of this boundary operator $\partial_{0}$ will be given later. We
however assume that the boundary operator is such that ${\cal B}_{i}$ has
trivial $0$-th homology.

Choice of Chain Map Define, for each $i$, a chain map $f_{i}:{\cal
B}_{i}\rightarrow{\cal A}$ in the obvious way: it maps each $j$-cell in ${\cal
B}_{i}$ for $j\in\\{0,1\\}$ to the corresponding $j$-cell in ${\cal A}_{i}$.
If we have, for some stabilizer in $S_{i}$, more than one pair, we map all
tuples $(S,i)$ for $S\in S_{i}$, to the $0$-cell corresponding to $S$.

Define a chain map $\overline{f}_{i}:\overline{{\cal B}}_{i}\rightarrow{\cal
A}=f_{i}\circ\Pi_{i}$, where $\Pi_{i}:\overline{{\cal B}}_{i}\rightarrow{\cal
B}_{i}$ maps every $0$-cell or $1$-cell in $\overline{\cal B}_{i}$ to the
corresponding cell in ${\cal B}_{i}$ and vanishes on $-1$-cells.

Finally, let ${\cal B}=\oplus_{i}\overline{cB}_{i}$, and define a chain map
$f:{\cal B}\rightarrow{\cal A}$ by

$f=\begin{pmatrix}\overline{f}_{i}\\\ \overline{f}_{2}\\\ \ldots\\\
\overline{f}_{m}\end{pmatrix}.$

######  Definition 3.

The cone code for the given $Q_{1},\ldots,Q_{m}$, and $S_{1},\ldots,S_{m}$,
$\overline{{\cal B}}_{i}$, and $C$ is the code corresponding to
$\operatorname{Cone}(f)$.

We will compare this cone code to another code.

######  Definition 4.

The induced code for the given choices of sets $Q_{i}$, of pairings, and of
$C$, is a code with the same qubits and $X$-stabilizers as $C$, and with the
set of $Z$-stabilizers given by the $Z$-stabilizers of ′ as well as, for every
element of first homology of each ${\cal B}_{i}$, the product of Pauli
$Z$-operators over qubits corresponding to that element of first homology. For
each $i$, we say that the stabilizers induced by ${\cal B}_{i}$ are those
given by elements of first homology of ${\cal B}_{i}$.

We call the $Z$-stabilizers of the induced which correspond to $Z$-stabilizers
of $C^{\prime}$ the direct $Z$-stabilizers and we call the other
$Z$-stabilizers the induced $Z$-stabilizers.

The cone code is not necessarily LDPC, but it may have some improved
properties of $Z$-stabilizer weight, depending on $C$. We ater apply y a
further transformation to the cone code, defining a “reduced cone code”, so
that the result is LDPC assuming certain properties of $C$.

Construction of $\overline{{\cal B}}_{i}$: We now construct the
$\overline{{\cal B}}_{i}$. As mentioned, the reader may wish to skip this on
first reading and proceed to lemma 8, taking every occurrence of
$\overline{{\cal B}}_{i}$ in that lemma to be ${\cal B}_{i}$ and assuming that
${\cal B}_{i}$ has trivial first homology. For notational simplicity, fix some
$i$, and let ${\cal F}={\cal B}_{i}$. We will construct some $\overline{{\cal
F}}$ and let $\overline{{\cal B}}_{i}=\overline{\cal F}$. Write $S=S_{i}$ and
$Q=Q_{i}$.

From ${\cal F}$, construct a graph $G_{i}$ as follows. Each edge corresponds
to a $0$-cell in ${\cal B}_{i}$ each vertex corresponds to a $1$-cell in
${\cal B}_{i}$. An edge attaches two vertices when the corresponding $0$-cell
is in the boundary of the two corresponding $1$-cells.

The induced code can then be expressed very simply in terms of these graphs:
for each connected component of the graph $G_{i}$, the product of Pauli $Z$
operators over all qubits in that component is a $Z$-stabilizer of the induced
code, and those are the only stabilizers induced. We next show in Lemma 6 that
we can make a choice so that there is one induced stabilizer for each
connected component of the graph $G_{Q}$ defined at the start of this paper,
with that stabilizer being the product of Pauli $Z$-operators over qubits
corresponding to left vertices of that component. We will always make such a
choice.

For notational simplicity, we will refer to $G_{i}$ simply as $G$ in this part
of the construction, and refer to $Q_{i}$ as $Q$.

The following lemma guarantees the existence of pairings with certain
properties. We always make such a choice.

######  Lemma 6.

It is possible to choose the pairing so that the graph $G$ has the same number
of connected components as the graph $G_{Q}$. Putting the connected components
into one-to-one correspondence, we can choose the vertices of a given
connected component of $G$ to correspond to the same qubits as the vertices of
the corresponding connected component of $G_{Q}$

###### Proof.

For brevity, we identify vertices of $G$ with vertices of $G_{Q}$ that
correspond to the same qubits, i.e., we say that $G,G_{Q}$ have the same
vertex sets but different edge sets. Pick any pairing. All the vertices in a
given connected component of $G$ must be in the same connected component of
$G_{Q}$. Pick any connected component $C$ of $G_{Q}$. Suppose that corresponds
to more than one connected component of $G$, called $D_{1},D_{2},\ldots$ Then,
there must be two different connected components of $G$, called
$D,D^{\prime}$, with vertices $v\in D$ and $v^{\prime}\in D^{\prime}$ such
that some stabilizer has support on both $v$ and $v^{\prime}$. Modify the
pairing, by pairing $v,v^{\prime}$ with each other on that stabilizer (and
pairing the vertex that was paired with $v$ with the one that was paired with
$v^{\prime}$). This reduces the number of connected components of $G$. Repeat
until the conclusions of the lemma hold. ∎

Elements of zeroth cohomology of ${\cal F}$ correspond to closed $1$-chains on
this graph $G$.

By the decongestion lemmaFH , we can find a basis of simple cycles for the
zeroth cohomology of ${\cal F}$ of weight $O(n\log(n))$ where $n=|Q_{i}|$.
Further, each edge appears in the basis at most $O(\log(n)^{2})$ times.

We construct $\overline{\cal B}_{i}$ by adding a $-1$-cell to ${\cal B}_{i}$
for each cycle in such a basis. The coboundary of the given $-1$-cell is the
sum of edges in the basis.

Geometric Interpretation of Added $-1$-cells: We can give a geometric
interpretation of the added $-1$-cells. Given graph $G_{i}$, we can extend
that graph to a $2$-complex we call ${\cal S}_{i}$ with trivial first homology
by attaching a $2$-disc to each cycle in the basis. Then, vertices, edges, and
faces of that $2$-complex become $1$-, $0$-, and $-1$-cels of $\overline{\cal
B}_{i}$ respectively. When constructing the cone code, these get shifted in
dimension by $1$ to become $2$-, $1$, and $0$-cells. Thus, in a sense the
dimensions appear “upside down”: the $j$-cells of ${\cal S}_{i}$ become
$(2-j)$-cells in the cone code. A crucial property for use later is that each
$1$-cell in ${\cal S}_{i}$ has exactly two $0$-cells in its boundary.

Reducing the Cone Code: There is no upper bound on the length of a cycle other
than the trivial upper bound that it has length at most $|Q_{i}|$; indeed, if
the graph $G$ is a cycle graph, then this is the length of a cycle on that
graph. This means that the coboundary of a $-1$-cell in $\overline{\cal
B}_{i}$ may have weight $|Q_{i}|$, and hence we may produce $X$-stabilizers of
the cone code with weight up to $|w_{Z}|$ (of course, there may also already
have been some high weight $X$-stabilizers in code the induced code).

Further, it is possible that a given edge in $G_{i}$ attaches to
polylogarithmically many $2$-discs in ${\cal S}_{i}$ if that edge appears in
many cycles in the cycle basis. This can lead to a $1$-cell in the cone code
having polylogarithmically many $0$-cells in its boundary.

However, both these problems can be solved. We describe the procedure to solve
them. The result we call the “reduced cone code”.

To solve the second problem, let us say an “added $j$-cell” of the cone code
is a $j$-cell corresponding to $(j-1)$-cell in some $\overline{\cal B}_{i}$.
Thicken the cone code (dually, i.e., interchanging $X$ and $Z$), and then
choose heights for the added $0$-cells so that at most one such added $0$-cell
attaches to each $1$-cell. Here we are using thickening only to reduce the
number of added $0$-cells which attach to $1$-cells, and we are not concerned
with the number of other $0$-cells attaching to a $1$-cell. So, for any
$\epsilon>0$, this can (by the same argument as Lemma 4) be done by thickening
by an amount $\Theta(\log(|w_{Z}|)^{2+2\epsilon}|w_{Z}|^{\epsilon})$; that is,
here $|w_{Z}|$ plays the role of $N$ in lemma Lemma 4.

To solve the first problem, consider the subcomplex consisting just of a
single added $0$-cell of the cone code, the added $1$-cells in its coboundary,
and the added $2$-cells in their coboundary. Call that subcomplex ${\cal D}$.
Consider a single cycle in some graph $G_{i}$. Consider the cycle graph
containing just the edges in that cycle. Regard that graph as a $1$-complex
and attach a $2$-disc whose boundary is that cycle; call the result ${\cal
E}$. Then, ${\cal D}$ and ${\cal E}$ are the same complex, up to a change in
the dimension of cells, so that $j$-cells in ${\cal E}$ corresponding to
$(2-j)$-cells in ${\cal D}$, and up to transposing the boundary operator.
However, it is easy to see geometrically how to make ${\cal E}$ sparse, so
that every cell in ${\cal E}$ has only $O(1)$-cells in its boundary and
coboundary: simply cellulate the added $2$-disc. For example, labeling the
vertices $0,1,2,\ldots,w-1$ in order, add an edge between vertices $j$ and
$w-j$ for all $j$ with $0<j<w-j$.

###  III.1 Comparison of Reduced Cone Code and Induced Code

We now compare the reduced cone code and the induced code.

Finally, let us define a soundness factor $\lambda_{i}$. Since each
$\overline{\cal B}_{i}$ has trivial zeroth homology, any closed $0$-chain
$u\in\overline{\cal B}_{i}$ equals $\partial v$ for some $1$-chain
$v\in\overline{\cal B}_{i}$. Define $\lambda_{i}$ by

$\lambda_{i}={\rm max}_{u\in(\overline{\cal B}_{i})_{0},u\neq 0}\Bigl{(}{\rm
min}_{v\in{\overline{\cal B}_{i}}_{1},u=\partial
v}\frac{|u|}{|v^{\prime}|}\Bigr{)},$

where $|\cdot|$ denotes Hamming weight, and where $v^{\prime}$ is the
projection of $v$ into ${\cal B}_{i}$.

The soundness factor $\lambda_{i}$ can be lower bounded in terms of the
Cheeger constant of the graph $G_{i}$. If a graph $G$ is connected, define Let

$h(G)={\rm min}_{w,0<|w|\leq|V|/2}\frac{|\partial^{T}w|}{|w|},$

where the minimum is over all vertex chains222Here, by vertex chain, we mean a
$0$-chain on the graph. We use the term vertex chain because we want to refer
to $0$-cells of the graph as vertices. $w$ with Hamming weight $>0$ and at
most $|V|/2$, where $V$ is the set of vertices of the graph $G$. This is the
usual definition of a Cheeger constant: the ratio is the familiar ratio of
number of edges which are adjacent to one vertex in $w$ to the number of
vertices in $w$, except we have used $\partial^{T}$ rather that $\partial$ (as
is more common notation in graph theory) to be consistent with notation in
terms of complexes.

If the graph $G$ is not connected, we define its Cheeger constant to be the
minimum of the Cheeger constants of its connected components.

Then:

######  Lemma 7.

$\lambda_{i}\geq h(G_{i}).$ (8)

###### Proof.

Let $v$ be some choice of $1$-chain in the definition of $\lambda_{i}$, with
$v^{\prime}$ the projection of $v$ on ${\cal B}_{i}$. Without loss of
generality, assuming $|v^{\prime}|\leq|V_{i}|/2$, where $V_{i}$ is the vertex
set of $G_{i}$; if $|v^{\prime}|>|V_{i}|>2$, add the sum of all $1$-cells to
$v$, which does not change $\partial v$.

Suppose for some edge of $G_{i}$, $v$ vanishes on one vertex attached to that
edge, but is nonvanishing on the other vertex attached to that edge. Then
$\partial v$ equals $1$ on the $0$-cell corresponding to the given edge. Let
$w$ be the vertex chain on the graph corresponding to $v^{\prime}$ so
$|w|=|v^{\prime}|$; then $|\partial^{T}w|$ is lower bounded by $h(G_{i})|w|$
and $|u|\geq|\partial^{T}w|$. ∎

We have

######  Lemma 8.

Let $\epsilon>0$. Let
$\ell=\Theta(\log(|w_{Z}|)^{2+2\epsilon}|w_{Z}|^{\epsilon})$. Let parameters
without a tilde denote parameters of the induced code. Let parameters with a
tilde denote parameters of the reduced cone code. Let $w^{\prime}_{Z}$ denote
parameters of code $C^{\prime}$. Then,

  * 1.

$\tilde{N}\leq O(N+\sum_{i}|Q_{i}|q_{X})\ell$.

  * 2.

$\tilde{K}=K$.

  * 3.

$\tilde{w}_{Z}\leq q_{X}+1+w^{\prime}_{Z}+O(1)$.

  * 4.

$\tilde{q}_{Z}\leq q_{Z}+O(1)$.

  * 5.

$\tilde{w}_{X}={\rm max}(w_{X},O(1))$.

  * 6.

$\tilde{q}_{X}={\rm max}(q_{X},O(1))$.

  * 7.

$\tilde{d}_{X}\geq d_{X}$.

  * 8.

$\tilde{d}_{Z}\geq d_{Z}\lambda\ell$, where $\lambda={\rm min}(1,{\rm
min}_{i}\lambda_{i})\geq{\rm min}(1,{\rm min}_{i}h(G_{i}))$.

###### Proof.

It is convenient to consider two more codes. In each complex ${\cal S}_{i}$,
cellulate all the added $2$-discs at once, (using the same cellulation as done
for each individual disc when defining the reduced cone code) to define some
complex we call $\hat{\cal B}_{i}$. Then, define $\hat{B}=\oplus_{i}\hat{\cal
B}_{i}$ and define a code by coning with the obvious chain map from $\hat{\cal
B}$ to ${\cal A}$. Call the resulting code the celled code. Thicken the celled
code by the same amount as in defining the reduced cone code, and call the
result the thick celled code.

Thus, one can think of the thick celled code as having, for every cellulated
$2$-disc in the reduced cone code, many copies of that cellulated $2$-disc.
Let $d$ label various discs in the reduced cone code, and let
$d_{1},d_{2},\ldots$ denote the corresponding copies of that disc in the thick
celled code. For any $1$-chain in the thick celled code, for any disc $d$, we
can add boundaries or coboundaries to push the chain off all the cells in the
interior of all but one copy $d_{a}$. In this way, the chain can be turned
into a chain that vanishes except on cells in the reduced cone code. Hence the
thick celled code has the same number of logical qubits as the reduced cone
code and the distance of the reduced cone code is at least as large as the of
the distance of the thick celled code, as every chain in the cone code defines
in an obvious way a chain in the thick celled code. In turn, the $X$-distance
of the thick celled code is that same that of the celled code, while the
$Z$-distance is increased proportional to the amount $\ell$ we thicken.

So, in all proofs of distance, we will prove distance of the celled code, and
the result for the reduced cone code will follow.

For notational convenience, let ${\cal Q}_{i}$ denote the space $({\cal
B}_{i})_{1})$, let ${\cal X}_{i}$ denote the space $({\cal B}_{i})_{0}$. Let
$\hat{{\cal Q}}_{i}$ denote the space $(\hat{{\cal B}}_{i})_{1})$, let
$\hat{\cal X}_{i}$ denote the space $(\hat{\cal B}_{i})_{0}$, and let
$\hat{{\cal R}}_{i}$ denote the space $(\hat{\cal B}_{i})_{-1}$, where $Q,X,R$
refer to “qubit, $X$, relation”. Let ${\cal Q}_{i}^{\perp},{\cal
X}_{i}^{\perp}$ denote the subspaces of $\hat{\cal Q}_{i},\hat{\cal X}_{i}$
which vanish on ${\cal Q}_{i},{\cal X}_{i}$, so $\hat{\cal Q}_{i}={\cal
Q}_{i}\oplus{\cal Q}_{i}^{\perp}$ and similarly for $\hat{\cal X}_{i}$.

Given a space such as ${\cal Q}_{i}$, we write ${\cal Q}[-1]$ to denote the
space in $\operatorname{Cone}(f)$ corresponding to ${\cal Q}$, and similarly
for all other spaces defined in the paragraph above. Here the $-1$ in brackets
denotes the shift in dimension: for an arbitrary complex ${\cal D}$, define
the complex ${\cal D}[-1]$ to have its $(j+1)$-cells in one-to-one
correspondence with $j$-cells of ${\cal D}$, and with the boundary operator
defined in the obvious way.

We have:

  * 1.

There are $N$ $1$-cells in ${\cal A}$. Each graph $G_{i}$ has at most
$|Q_{i}||q_{X}|$ edges giving a total of $N+\sum_{i}|Q_{i}|q_{x})$ $1$-cells,
which gets multiplied by $\ell$ after thickening. We must also account for
cells in the interior of each attached disc. This weight is at most
$O(|Q_{i}|\log(|Q_{i}|))$ and does not get multiplied by $\ell$ because every
such disc gets attached at only one height.

  * 2.

This follows from the proof of item 7 below.

  * 3.

Each $Z$-stabilizer in ${\cal B}_{i}$ corresponds to some qubit $q$ in some
set $Q_{i}$, as well as some height along the interval used to thicken. The
cells in its boundary comprise three possibilities. First, the $1$-cell in
${\cal A}$ corresponding to that qubit $q$ at the given height. Second, any
$1$-cells in ${\cal B}_{i}$ corresponding to $X$-stabilizers in the boundary
of that qubit $q$ at the corresponding height, and there are at most $q_{X}$
such $X$-stabilizers. Third, if a disc is attached at the given height,
possibly some $1$-cells in the interior of that disc, but there are only
$O(1)$ such $1$-cells. The direct $Z$-stabilizers have weight bounded by
$w^{\prime}_{Z}$.

  * 4.

By construction of the cellulation of the disc, every edge in the cellulation
has one $O(1)$-vertices in its boundary. Every qubit in the cone code
corresponding to some $1$-cell of ${\cal A}$ is in its at most $q_{Z}$
stabilizers of the cone code.

  * 5.

All $X$-stabilizers correspond either to $X$-stabilizers of ${\cal A}$, which
have weight bounded by $w_{X}$, or $-1$-cells of $\hat{\cal B}_{i}$, which are
constructed to have weight $O(1)$.

  * 6.

By construction, same as item 5.

  * 7.

Consider the celled code. Any $1$-chain $u$ in $\operatorname{Cone}(f)$ is a
sum of a $1$-chain $q$ in ${\cal A}$ and some $0$-chains in $\hat{\cal
X}_{i}$. This $1$-chain $q$ has an obvious projection $q_{i}$ onto ${\cal
Q}_{i}$. For each $i$, for the coboundary of $u$ to vanish, there must be some
chain $v$ in ${\cal X}_{i}$ such that $\partial^{T}v$ is equal to $q_{i}$. To
see this, note that there is some chain $v$ in $\hat{\cal X}_{i}$ such that
$\partial^{T}v=q_{i}$. If the coboundary of $u$ vanishes on ${\cal
Q}_{i}^{\perp}$, we can add a coboundary of a chain in ${\cal R}_{i}$ to $v$
so that the result is supported in ${\cal X}_{i}$. To see this, regard $v$ as
an edge chain333An edge chain is our term for a $1$-chain on ${\cal S}$.. This
edge chain $v$ may have some support on edges of graph $G$ in the interior of
the attached disc which themselves attach to vertices in $G_{i}$. However, if
the chain is closed in the interior of the discs, we can add boundaries of
faces of $G_{i}$ to remove its support on those edges, pushing the chain off
the discs. Then, for the coboundary of $u$ to vanish on ${\cal Q}_{i}$, indeed
there must be some chain $v$ in ${\cal X}_{i}$ such that $\partial^{T}v$ is
equal to $q_{i}$.

Hence, $q$ must correspond also to a coclosed chain in the chain complex
corresponding to the induced code, i.e., an $X$-logical operator of the
induced code. Conversely, if $q$ is a coclosed chain in the chain complex of
the induced code, then such a chain $v$ does exist. Further, such a chain $v$
is unique up to adding coboundaries of a chain in ${\cal R}_{i}$ because each
$\overline{\cal B}_{i}$ has trivial zeroth homology.

By adding coboundaries of elements of ${\cal A}_{0}$, we can shift $q$ by
$X$-stabilizers of the induced code. This shows $\tilde{K}=K$: given $q$, $u$
is unique up to coboundaries, by adding coboundaries in the cone code, $q$ can
be shifted by coboundaries in the chain complex of the induced code, and $q$
must be coclosed in the chain complex of the induced code.

Further, if $u$ is nontrivial, then $q$ is nontrivial, and so in that case
$|u|\geq d_{X}$.

  * 8.

Consider the celled code. Let $u$ be any closed $1$-chain in
$\operatorname{Cone}(f)$, $u=u^{q}+\sum_{i}u^{x}$, where $u^{q}$ is in ${\cal
A}_{1}$ and $u^{x}_{i}\in\overline{\cal B}_{i}[-1]_{0}$. By assumption that
$\overline{\cal B}_{i}$ has trivial zeroth homology, we can add a boundary of
some $v^{q}_{i}\in{\cal B}_{i}[-1]_{1}$ to $u$, giving some chain $u^{\prime}$
whose projection onto ${\cal B}_{i}[-1]_{0}$ vanishes. We can choose further
$|v^{q}_{i}|\leq|V_{i}|/2$, as if not, simply add the sum of all cells to
$v^{q}_{i}$. By assumption on soundness, $|u^{\prime}|\leq|u|/\lambda$.

So, $u^{\prime}$ must correspond to a closed chain of the induced code.
Further, by adding a boundary of $v^{q}_{i}$, where $v^{q}_{i}$ is the sum of
all $2$ cells in ${\cal B}_{i}[-1]{1}$, we can shift $u^{\prime}$ by a
stabilizer of the induced code. Hence, if $|u^{\prime}|\leq d_{Z}$, we can add
stabilizers to make $u^{\prime}=0$. Hence, if $u$ is a nontrivial logical,
$|u|\geq d_{Z}\lambda$.

∎

###  III.2 Examples With Toric Code and Geometric Interpretation

Let us give a simple example of coning. We emphasize to the reader that this
example may be too simple. It shows how coning works, and it shows how in this
particular example coning corresponds to a familiar construction with the
toric code; however, the reader should not be misled into thinking that in
general coning has such a simple geometric interpretation.

Consider a toric code, i.e., a code defined by some cellulation of a surface,
with $X$-stabilizers, qubits, and $Z$-stabilizers associated with $0$-, $1$-,
and $2$-cells, respectively. Suppose we choose, however, a strange cellulation
of the surface in which one of the faces is a polygon with $n$-sides for some
very large $n$. We wish to induce this stabilizer, with other $Z$-stabilizers
being direct $Z$-stabilizers. Label qubits corresponding to edges on the
boundary of this face by integers $j\in\\{0,\ldots,n-1\\}$. There are $n$
$X$-stabilizers of the form $X_{j}X_{j+1}\ldots$, where the index $j$ is taken
to be periodic in $n$ so that $X_{n}=X_{0}$, and the dots $\ldots$ indicates
other qubits in the support of the stabilizer, other than those which
correspond to edges of this face. We wish to induce the $Z$-stabilizer
$Z_{0}Z_{1}\ldots Z_{n-1}$. See Fig. 1, A.

Figure 1: A: part of a cellulation of a toric code. We show a polygon
representing a high weight $Z$-stabilizer. B: The result with “rough” boundary
conditions if we use ${\cal B}_{1}$ rather than $\overline{\cal B}_{1}$ in the
cone construction. Solid lines represent qubits, vertices represent
$X$-stabilizer. There are $Z$-stabilizers on triples of lines inside the
polygon, corresponding to two neighboring edges entering the polygon and one
edge in the polygon between those edges. The dashed line shows the graph
$G_{1}$. The edges of this graph correspond to $0$-cells of ${\cal B}_{1}$ and
the vertices (shown as solid circles) correspond to $1$-cells. C: Cone code
with one additional high weight $X$-stabilizer. Note the relation with a dual
cellulation of B: the dashed line of B bounds the attached $2$-cell in ${\cal
S}_{1}$, which dually becomes a $0$-cell in C. D: Reduced cone code. Dashed
lines show the cellulation of complex ${\cal S}_{1}$. The resulting
stabilizers in the reduced cone code are on the dual cellulation.

Let $Q_{1}$ be the set of qubits correspoding to edges of this polygon. The
complex ${\cal B}_{1}$ has nontrivial first homology group. Indeed, the sum of
all $1$-cells has vanishing boundary. So, to follow the construction above, we
need to construct $\overline{\cal B}_{1}$. Suppose, however, that we did not
do this, and used ${\cal B}_{1}$ rather than $\overline{\cal B}_{1}$ to
construct the mapping cone. Let us see what goes wrong.

We will find that we have now an additional $n$ qubits, one for each vertex on
the polygon. Label these added qubits by $\overline{j}$ for
$j\in\\{0,\ldots,n-1\\}$. Then, the stabilizers $X_{j}X_{j+1}\ldots$ are
replaced by $X_{j}X_{j+1}X_{\overline{j}}\ldots$ in the cone code.
Additionally, we have $Z$-stabilizers
$Z_{\overline{j}}Z_{j+1}Z_{\overline{j+1}}$ for each $j$.

This is a familiar result: it is a puncture in a toric code with so-called
“rough” boundary conditions around the puncture. This may increase the
degeneracy of the ground state: if we create more than one such puncture, it
will increase the degeneracy, but a single such puncture does not. See Fig. 1,
B.

So, indeed we must construct $\overline{\cal B}_{1}$. In this case, we have a
single redundancy in $X$-stabilizers of ${\cal B}_{1}$. Adding this
redundancy, we find that the cone code adds one more $X$-stabilizer:
$\prod_{j}X_{\overline{j}}$. See Fig. 1, C.

The result is again a toric code, but now with a large $X$-stabilizer weight.
This weight can be reduced in weight by cellulating the added disc in ${\cal
S}_{1}$. It is a nice exercise to see that (because of the interchange
$j\leftrightarrow(2-j)$ of dimension of cells between ${\cal S}_{i}$ and the
cone code) the cellulation of a disc in ${\cal S}_{1}$ means that the reduced
cone code is a toric code with the dual cellulation (in the of a dual graph)
used to resolve the high weight $X$-stabilizer. See Fig. 1, D.

This example also shows the importance of the soundness factor $\lambda$. In
this case, the soundness factor $\lambda$ is of order $1/n$. To give an
example where this factor correctly estimates the effect on distance, consider
a toric code given by a cellulation of an $L$-by-$L$ torus (so that there are
$K=2$) logical qubits, using the usual cellulation with square $2$-cells.
Remove an $m$-by-$m$ patch of squares (including removing the edges inside the
patch), and replace that patch with a single large face, i.e., adding the
product of Pauli $Z$ operators on edges around that patch as a $Z$-stabilizer.
This is our desired induced code. Then, this is precisely the situation
considered above, with $m\propto n$. The toric code with square cells has
distance $L$. Removing that patch and replacing it with a single face can
reduce the distance $d_{X}$ because a coclosed $1$-chain can take a “shortcut”
going directly across the patch; indeed, if we had many such patches, we could
potentially reduce the distance by a factor proportional to $m$. However the
distance $d_{Z}$ is not reduced because a closed $1$-chain must “go around”
the patch without any shortcut. However, in the reduced cone code, the
distance $d_{Z}$ may also be reduced since closed $1$-chains can now also take
a “shortcut” across the patch, and if we had many such patches, the reduction
in distance could also be proportional to $m$, i.e., the distance may be
multiplied by something proportional to $\lambda$.

###  III.3 Unreasonable Codes

We now consider the case of unreasonable codes. We call the procedure
“connecting”.

Suppose we have some code $C$ that includes a stabilizer $S_{i}$ which is the
product of Pauli $Z$-operators on some set of qubits $Q_{i}$ such that the
graph $G_{Q_{i}}$ has two connected components (the generalization to more
connected components will be obvious, and will be given below), so that the
procedure above does not work.

For notational simplicity, first consider the case of a single such
stabilizer.

Define the “connected code” to be the following code: it has a new qubit,
called $r$. Instead of using the procedure above, do the following: pick one
qubit from each of the two connected components of $G_{Q_{i}}$. Call these
qubits $q_{1},q_{2}$. We modify the $X$-stabilizers, by multiplying every
$X$-stabilizer of $C$ that has support on $q_{1}$ or $q_{2}$ by $X_{r}$, i.e.,
the boundary of the cell corresponding to $r$ is the sum of boundaries of the
cells corresponding to $q_{1}$ and $q_{2}$. Let the connected code have the
same stabilizers as $C$, except add the stabilizer $Z_{q_{1}}Z_{q_{2}}Z_{r}$
and replace $S$ with $SZ_{1}Z_{2}Z_{r}$.

Now, on the connected code, rather than inducing the stabilizer on set
$Q_{i}$, induce a stabilizer on
$(Q_{i}\setminus\\{q_{1},q_{2}\\})\cup\\{r\\}$, i.e., induce $SZ_{1}Z_{2}r$.
Let this set $(Q_{i}\setminus\\{q_{1},q_{2}\\})\cup\\{r\\}$ be denoted
$Q^{\prime}_{i}$. For the connected code, the graph $G_{Q^{\prime}_{i}}$ is
connected, so coning works.

If $G_{Q_{i}}$ has $k>2$ connected components, the generalization is to define
the connected code by picking several pairs of distinct qubits
$q^{\prime}_{1},q_{2}$ and $q^{\prime}_{2},q_{3}$ and so on, up to
$q^{\prime}_{k-1}q_{k}$, with $q_{j},q^{\prime}_{j}$ in the $j$-th connected
component. Note that we have written the first pair as $q^{\prime}_{1},q_{2}$,
rather than $q_{1},q_{2}$. Then, add qubits $r_{1},r_{2},\ldots,r_{k-1}$ and
stabilizers $Z_{q^{\prime}_{a}}Z_{q_{a+1}}Z_{r_{a}}$ for each
$a\in\\{1,\ldots,k-1\\}$. Every $X$-stabilizer with support on
$q^{\prime}_{a}$ or $q_{a+1}$ will act also on $r_{a}$. Finally, induce
$Z$-stabilizer on
$Q_{i}\setminus\\{q^{\prime}_{1},q^{\prime}_{2},\ldots,q_{2},q_{3},\ldots\\}\cup\\{r_{1},r_{2},\ldots\\}$.
Again, the graph corresponding to this stabilizer for the connected code is
now connected.

If there are several $Z$-stabilizers $S_{i}$ with corresponding graphs
$G_{Q_{i}}$ which have more than one connected component, we do this same
procedure for each such stabilizer to define the connected code. For each such
stabilizer $S_{i}$, we add $k-1$ new qubits to define the connected code,
corresponding to the qubits called $r$ or $r_{1},r_{2},\ldots$ above. Call
these added qubits the “connecting qubits”.

Let us explain why this works. One may see that if we considers elements of
the stabilizer group of the connected code which are supported on qubits other
than the connecting qubits, then the resulting group is precisely the
stabilizer group of $C$ as desired. Further, given any $1$-chain, we can add a
boundary or boundary to make it vanish on all connecting qubits; indeed, for
each connecting qubit there is an $X$-type stabilizer and a $Z$-stabilizer,
both of which have support on that connecting qubit (and no other connecting
qubits). Now consider the effect on distance.

Consider any $Z$-logical operator of the connected code. If it has support on
$r$, we can multiply by stabilizer $Z_{q_{1}}Z_{q_{2}}Z_{r}$ to make it not
have support on $r$. Similarly, for any $X$-logical operator, if it has
support on $r$, we can multiply by any $X$-stabilizer acting on $q_{1}$ (or
$q_{2}$), so that the result does not have support on $r$. This multiplication
can change the weight, but it increases the weight of a $Z$-logical operator
by at most an $O(1)$ multiplicative factor and increases the weight of an
$X$-logical operator by an at most $w_{X}$ multiplicative factor. So, $d_{X}$
is reduced by an at most $O(w_{X})$ factor and $d_{Z}$ is reduced by an at
most $O(1)$ factor.

So, we may induce stabilizers even in unreasonable codes. Indeed:

######  Lemma 9.

The connected code has the same number of logical qubits as $C$. The number of
physical qubits of the connected code is $O(N)$. The $X$\- and $Z$-distances
of the connected code are $\Omega(d_{X}),\Omega(d_{Z})$ respectively.

To give some intuition for this connecting procedure, consider a toric code
again. Suppose the toric code is on a plane with several punctures with some
boundary conditions on each puncture. Suppose boundary conditions for the
punctures are chosen in some way so that the product of Pauli $Z$ around each
puncture is a logical operator. For $k\geq 2$ punctures, called
$1,2,\ldots,k$, let $L_{1},L_{2},\ldots,L_{k}$ be the corresponding products
of Pauli $Z$-operators. Suppose further that we wish to induce the product
$L_{1}L_{2}\ldots L_{k}$ as a $Z$-stabilizer, without separately inducing any
other stabilizers.

One natural way to do this is to attach a $k$-punctured sphere to those
$k$-punctures. This doesn’t quite work, but let’s delve into this further.
Suppose $k=2$, so we want to attach a twice punctured sphere. We can imagine
doing this in two steps: first use a “pair of pants” to turn the two punctures
into a single puncture, then close the pair of pants with a disc. One simple
version of a pair of pants is the following: let $e_{1}$ be an edge in one
puncture, and $e_{2}$ be an edge in the other. Add two new edges $f,g$ so that
$e_{1},e_{2},f,g$ make a plaquette (this means that the edges $f,g$ are not
drawn in the plane!). This plaquettes means that we add a $Z$-stabilizer
$Z_{e_{1}}Z_{e_{2}}Z_{f}Z_{g}$. There is now a single closed loop obtained by
taking the two boundaries of the punctures, cutting out edges $e_{1},e_{2}$
from the punctures, and adding in edges $f,g$ and we can attach a disk to this
loop. Unfortunately, while this pair of pants operation turns the two
punctures into a single puncture, the result adds unwanted first homology.
Consider for example the toric code on a sphere, with two punctures, each
puncture consisting of a single plaquette. This code has a single logical
qubit (we have removed two $Z$-stabilizers from the sphere, but one of them is
redundant). Adding in the product of Pauli $Z$-operators around both punctures
does not change the stabilizer group in this case, so there should still be a
single logical qubit. However, the above pair of pants procedure instead
produces a torus which has two logical qubits. The trouble is indeed this
added extra loop. In FH , a similar issue was considered (see discussion in
section 1.3); the resolution there was roughly to consider higher dimensional
toric codes. Here our resolution is even simpler, replacing $f,g$ with a
single qubit. This can be understood (very heuristically) in two different
ways. One is to think of this pair of pants construction but restrict to the
subspace with $X_{f}=X_{g}$ which removes this unwanted first homology. The
other (even more heuristically, and perhaps this will not be useful to the
reader) is to think that it corresponds to considering higher dimensional
codes similar to the construction in FH .

Now let us discuss the application of connecting to implementing logical
Clifford operations which are composed of elementary logical CNOTs (i.e.,
logical Clifford which map Pauli $Z$ operators to products of Pauli $Z$) on
some arbitrary LDPC CSS stabilizer code $C$. First, as well-known, given two
copies of some code, the CNOT gate can be implemented transversally. Suppose
we have three or more copies of a code, labelled $1,2,3,\ldots$. If we start
with a maximally entangled state between copies 2 and 3, given by preparing
the logical qubits of 2,3 in Bell pairs and then applying an arbitrary
Clifford $U$ to 3, we can then apply a transversal CNOT from 1 to 2, measure
all qubits of 1 in the $X$ basis (hence measuring all the logical $X$
operators of $X$ in a fault tolerant way) and measure all qubits of 2 in the
$Z$ basis to teleport the state from 1 to 3, while applying the Clifford $U$.
The teleportation is up to some Pauli correction on the logical qubits of 3,
which can be implemented by a product of Paulis on the physical bits. This
reduces the task of implementing logical Cliffords to the task of preparing
appropriate entangled states between 2 and 3. However, such an entangled
state, for the given Cliffords, is the unique code state of a code $C_{ent}$
with no logical qubits: this code $C_{ent}$ is given by taking two copies of
the given stabilizer code and adding some additional stabilizers which are
products of logical operators between the copies; these additional stabilizers
include both $X$\- and $Z$-type stabilizers and so we need to induce both
such. We can use the combining procedure to implement these additional
stabilizers by constructing some reduced cone code for $C_{ent}$. Using the
methods of Section VI, we will see that we can assume that the soundness of
$C_{ent}$ is $\Omega(1)$. Remark: it would be interesting also to induce
stabilizers which are products of Pauli $X$ in one copy with Pauli $Z$ in
another to allow performing additional logical operations; we suspect that
this is possible but leave it open.

This leaves a few details to consider, which we only sketch here. First, the
added stabilizers to define the code $C_{ent}$ are not only high weight (which
we deal with using combining and coning as explained here) but may also lead
to a large $q_{Z}$. Indeed, $q_{Z}$ may potentially be as large as the number
of logical qubits of the code. So, it may be necessary to thicken the code
throughout to reduce $q_{Z}$ to $O(1)$.

Second, what we prepare is not the code state of $C_{ent}$, but rather of some
reduced cone code. This reduced cone code is given by some further thickening
of two copies of $C$, with some added qubits and added stabilizers, and also
some modification of the $X$-stabilizers of the thickened copies so that they
involve also the added qubits. Let us call the qubits of the reduced cone code
either “original” or “added”. We can then measure all the added qubits in the
$X$-basis, so that then the remaining original qubits are stabilized by the
thickened $C_{ent}$, up to some Pauli correction, depending on the outcome of
the measurement. So, this measurement produces the desired entangled state on
two thickened copies of $C$, so we should work with thickened copies of $C$
throughout, rather than $C$. From here on we will simply refer to $C$ and
$C_{ent}$ for brevity, rather than constantly repeating that the codes are
thickened.

A third detail is that one might also like to be able to measure some set of
the logical qubits of some code, while leaving the others unaffected. We can
do this by a generalization of the above procedure. Use four copies,
$1,2,3,4$, where 1 encodes some logical state of $C$ and $2,3,4$ are copies of
$C$ with some of the logical qubits of 2 in Bell pairs with the corresponding
logical qubits of 3 and the other logical qubits of 2 in Bell pairs with the
corresponding logical qubits of 4 (the logical qubits of 3,4 which are not in
Bell pairs with logical qubits of 2 may be taken to be in the logical $Z=+1$
state). Then, again CNOT from 1 to 2, and measure 1 and 2 as before, thus
teleporting some qubits of 1 to 3 and the other qubits of 1 to 4. Finally, one
may measure are physical qubits of 4 in the $Z$-basis (or $X$-basis) to
measure some subset of the logical qubits of the initial state of 1 in the
$Z$-basis (or $X$-basis) while leaving the others intact by teleporting them
to 3.

The most important question is whether this procedure is fault tolerant. One
model to analyze fault tolerance in is some kind of circuit model where qubits
are subject to noise while stabilizers are repeatedly measured, possibly with
noisy measurement of stabilizers. Of course, we do not have even an analysis
of fault tolerance for the code $C$ itself, much less $C_{ent}$: all we know
is that $C$ is a large distance code. So we may consider a simpler question:
suppose we prepare the reduced cone code assuming perfect syndrome
measurement, and then some number of errors are applied to the qubits of the
reduced cone code, and next we measure the added qubits of the reduced cone
code in the $X$-basis. We finally measure the stabilizers of the two copies of
$C$ (we cannot measure the additional stabilizers of $C_{ent}$ because those
are high weight). Errors applied to original qubits of the reduced cone code
correspond simply to errors on the two copies of $C$, and so these errors can
be corrected after the final stabilizer measurement if the number of them is
small enough compared to distance. $X$-errors on the added qubits of the
reduced cone code have no effect since we measure those qubits in the
$Z$-basis. What we must consider are $Z$-errors on the added qubits of the
reduced cone code. However, up to boundaries, these $Z$-errors on the added
qubits of the reduced cone code are equivalent to $Z$-errors on the original
qubits, with the total weight of the error on the original qubits being at
most multiplied by the inverse soundness factor. Since we may assume that the
soundness is $\Omega(1)$, this bounds the error weight on the original qubits,
so those errors can also be corrected after the final stabilizer measurement
if the number of errors on the added qubits was sufficiently small compared to
distance.

##  IV Putting It Together

We claim:

######  Theorem 1.

Let $C$ be any code, with some given parameters, $w_{X},w_{Z},q_{X},q_{Z}$.
Let ${\rm poly}({\rm dev})$ refer to a quantity that is polynomial in
$w_{X},w_{Z},q_{X},q_{Z}$, where “dev” is shorthand for “deviation from LDPC”.
Then there is an LDPC code, whose parameters we will denote with a tilde, such
that $\tilde{K}=K$, and with $\tilde{N}$ bounded by $N$ times ${\rm poly}({\rm
dev}){\rm polylog}(N)$ and with $\tilde{d}_{X},\tilde{d}_{Z}$ lower bounded by
$d_{X},d_{Z}$ divided by ${\rm poly}({\rm dev}){\rm polylog}(N)$.

If the input code is LDPC, with arbitrary $w_{Z},w_{X},q_{X},q_{Z}=O(1)$, we
may choose the tilde code to have $w_{X}\leq 5$, $q_{X}\leq 3$, $w_{Z}\leq 5$,
and $q_{Z}\leq 5$.

We do this by using copying, gauging, thickening, and coning. We will not
write tildes above parameters because we will be applying several different
transformations to the code, and it would then necessitate write multiple
tildes to keep track of all these steps. Instead, we write parameters without
tilde through, but we describe the parameters “before” and “after” various
steps.

First, we copy and gauge to reduce $q_{X},w_{X}$ to $O(1)$. Then thicken to
reduce $q_{Z}$ to $O(1)$. Note that since $q_{X},w_{X}$ are both $O(1)$ after
copying and gauging, after thickening all parameters $q_{X},w_{X},q_{Z}$ are
all $O(1)$; it was useful to do copying and gauging first, as if we thicken a
code with $w_{X}=\omega(1)$, then the resulting code will not have
$w_{Z}=O(1)$.

Finally, construct the reduced cone code to reduce $w_{Z}$ to $O(1)$.
Stabilizers corresponding to elements of ${\cal C}_{1}\otimes{\cal E}_{1}$ can
be direct if desired.

Let us track the parameters in detail, assuming that the input code is LDPC
(but with some large parameters). After copying and gauging we have
$w_{X},q_{X}\leq 3$. After thickening we have $w_{X}\leq 5$ and $q_{X}\leq 3$.
From Lemma 3, if the input code is LDPC so that $q_{Z}w_{Z}=O(1)$, we may take
any $w>0$ and still have $\ell=O(1)$. Taking $w=3$ we get a code with
$q_{Z}\leq 5$; there is no point in taking smaller $w$. For the reduced cone
code, we may cellulate the discs with pentagons so that still $w_{X}\leq 5$
and $q_{X}\leq 3$ and also we may have $q_{Z}\leq 5$. We pick code
$C^{\prime}$ to have no $Z$-stabilizers. Then, the reduced cone code may be
constructed to have $w_{Z}\leq 5$; see item 3 of Lemma 8, where the $O(1)$
constant may be taken to be $1$.

Importantly, the soundness parameter $\lambda$ of some code, when applying
coning, is in worst case $1/w_{Z}$, where here, $w_{Z}$ refers to the
parameter for the code input to the coning step, which $O({\rm poly}({\rm
dev}))$. In many applications $\lambda$ may be larger: see the next section.

An interesting question is to what extent the operations we have described are
homotopy equivalences of chain constants with bounded Lipchitz constantsHHO
(20). Such a result could be used to show efficient decoding algorithms for
these weight reduced codes.

##  V Coding Applications: Weight Reducing a Linear Distance Code

We consider the following construction. We choose $X$-stabilizers to be
random, of average weight $\Delta=\beta\log(N)$ on $N$ bits, for some constant
$\beta$. We choose there to be $N/2$ such stabilizers. The particular choice
of $N/2$ is arbitrary; we need $dN$ for some $d\in(0,1)$. We choose these
stabilizers as follows: the boundary operator from qubits to $X$-stabilizers
is an $N/2$-by-$N$ matrix, and each entry is chosen independently at random,
chosen to be $1$ with probability $\Delta/N$ and $0$ otherwise.

Remark: it is possible that we could instead start with $X$-stabilizers of
weight $O(1)$, by using some construction of a good classical LDPC code. We
choose the logarithmic weight as it simplifies some estimates. However,
starting with an LDPC classical code might improve the final distance
estimates by some logarithmic factors.

We will then add $Z$-stabilizers below, and use coning to weight reduce those
stabilizers.

We will pick $\beta$ so that the conclusions of various lemmas below follow.

###  V.1 A linear distance code with $w_{X},q_{X}=O(\log(N))$, but
$w_{Z},q_{X}=\Theta(N)$:

We begin by constructing a code with these properties and then use thickening
and coning to reduce $Z$-stabilizer weight.

######  Lemma 10.

For sufficiently large $\beta$, with high probability this classical code has
distance $\Theta(N)$.

###### Proof.

This is the essentially same proof prop 3.5 of HHO (20), which as noted there
is related to a standard property of LDPC codes, that they achieve the
Gilbert-Varshamov bound as degree $\rightarrow\infty$. We need $\beta$ large
enough to ensure that, with high probability, all vertices have large degree.
∎

Regard this classical code as a $1$-complex ${\cal A}$. So, the homology group
$H_{1}({\cal A})$ has rank $\geq N/2$ since there are $N/2$ $X$-stabilizers.
The rank may be larger if there are linear dependencies among these
stabilizers. Let $b_{j}({\cal A})$ denote the rank of $H_{j}({\cal A})$. We
have

######  Lemma 11.

For large enough $\beta$, with high probability, $b_{1}({\cal A})=N/2$. More
strongly, the expectation value of $2^{b_{1}({\cal A})-N/2}$ equals
$1+O(1/N^{100})$.

###### Proof.

The number of $0$-chains in $A$ with vanishing coboundary equals
$2^{b_{0}({\cal A})}$. By prop 3.4 of HHO (20), this number equals
$1+O(1/N^{100})$; this result is not in the statement of the lemma, but
follows from the proof which counts the number of nonzero chains with
nonvanishing coboundary. Remark: HHO (20) instead used $(3/4)N$ stabilizers
rather than $N/2$; the exact fraction of stabilizers is unimportant so long as
$\beta$ is large enough.

However, $b_{1}({\cal A})-N/2=b_{0}({\cal A})$, by Euler characteristic. ∎

Choose $N/4$ elements of $H_{1}({\cal A})$ independently and uniformly at
random (one can choose to include the trivial element or not; it only is
chosen with probability $o(2^{-N/2})$ so it does not matter if we include it
or not). The corresponding $Z$-type operators will be the $Z$-stabilizers of
the induced code.

######  Lemma 12.

With high probability these $Z$-stabilizers are linearly independent.

###### Proof.

$H_{1}({\cal A})$ has rank $k\geq(1-d)N)$. So, we can write the
$Z$-stabilizers in terms of a $k$-by-$N/4$ matrix over $F_{2}$. Columns of
this matrix are chosen independently and uniformly at random (including the
all $0$s column if we include the trivial element of $H_{1}({\cal A})$). So,
we must show that this matrix is full rank. The $(j+1)$-st column is linearly
dependent on the first $j$ columns with probability $\leq 2^{-(k-j)}\leq
2^{-N/4}$. By a union bound, the lemma follows. ∎

######  Lemma 13.

With high probability, this code has distances $d_{X},d_{Z}=\Theta(N)$.

###### Proof.

The lower bound on $d_{Z}$ follows immediately from lemma 10. That is, every
product of Pauli $Z$-operators that commutes with the $X$-stabilizers has high
weight.

Lower bounding $d_{X}$ is slightly different because it is not the case that
every product of Pauli $X$-operators that commutes with all $Z$-stabilizers
has high weight. Indeed, any $X$-stabilizer is a logarithmic weight operator
that commutes with all $Z$-stabilizers. So, we need to use the fact that a
logical $X$-operator is not a product of $X$-stabilizers, i.e., it corresponds
to a $1$-chain $u$ that represents a nontrivial element of $H^{1}({\cal A})$.
We now use an easy first moment argument. Fix ${\cal A}$. Fix $u$, and then
choose the $Z$-stabilizers. For each $Z$-stabilizer, we have chosen some
element of $H_{1}({\cal A})$ at random, and, since $u$ represents a nontrivial
element of $H^{1}({\cal A})$, with probability $1/2$ the chain $u$ has
nonvanishing inner product with the given element of $H_{1}({\cal A})$. So,
the probability that $u$ has vanishing coboundary is $2^{-N/4}$. The number of
elements of $H^{1}({\cal A})$ with weight at most $w$ is bounded by the number
of vectors of Hamming weight at most $w$. So, the expected number of $u$ with
weight at most $w$ is $\leq 2^{-N/4}\sum_{j=0}^{w}{N\choose w}$. For $w$
sufficiently small compared to $N$, this is exponentially smaller. ∎

###  V.2 Thickening and Coning

Thicken to reduce $q_{Z}$. By Lemma 4, we can, for any $\epsilon>0$, reduce
$q_{Z}$ to $O(1)$, while increasing from $N$ qubits to $O(N^{2+\epsilon})$
qubits, keeping $d_{Z}=\Theta(N)$ and making $d_{X}=\Theta(N^{1+\epsilon})$.
We will see that this suffices at the end of the construction to get a code on
$n$ qubits with distance $\Omega{n^{2/3}-\epsilon})$ for every $\epsilon>0$.
In order to ultimately get distance $\tilde{\Omega}(n^{2/3})$, we instead
reduce $q_{Z}$ to $O(\log(N))$ bu taking $\ell=\Theta(N)$.

We then apply coning to reduce $w_{Z}$. Surprisingly, the soundness parameters
are all $\Omega(\Delta)$:

######  Lemma 14.

For large enough $\beta$, with high probability, there is a choice of pairing
such that the graphs $G_{i}$ are connected (and hence with high probability
the code is connected), and with high probability there is a choice of pairing
such that the graphs $G_{i}$ are expanders, so that $h(G_{i})=\Omega(\Delta)$

###### Proof.

We will show that, for any given $Z$-stabilizer, there is a choice of pairing
such that the desired properties of the corresponding graph $G_{i}$ hold with
probability at least $1-o(1/N)$. Further, we will show that a random pairing
suffices. Then, by a union bound, the lemma follows.

Consider a $Z$-stabilizer. This is chosen to be a random element of
$H_{1}({\cal A})$, i.e., we chose ${\cal A}$ at random, and then chose an $N$
bit vector $v$ uniformly at random, such that $\partial v=0$, and then this
vector was the desired element of $H_{1}({\cal A})$. For given ${\cal A}$,
number of $v$ with $\partial v=0$ is $2^{b_{1}({\cal A})}$.

So, the probability distribution on pairs $v,{\cal A}$ is as follows: the
probability is nonvanishing iff $\partial v=0$, in which case the probability
is $2^{-b_{1}({\cal A})}$, multiplied by the a priori distribution on ${\cal
A}$. Call that a priori distribution $\rho({\cal A})$.

Suppose instead we had chosen a different a priori probability distribution
for ${\cal A}$. Suppose that we had chosen the probability distribution
$\rho^{\prime}({\cal A})$ defined to be proportional to $2^{b_{1}({\cal
A})}\rho({\cal A})$. We will show that the desired expansion occurs with high
probability given this a priori distribution $\rho^{\prime}({\cal A})$. This
will then imply the lemma: by lemma 11, with high probability for distribution
$\rho^{\prime}({\cal A})$ we have $b_{1}({\cal A})=N/2$ with probability
$1-O(1/N^{100})$ and so the total variation distance between
$\rho,\rho^{\prime}$ is $O(1/N^{100})$.

In the second step, consider the probability distribution on pairs $v,{\cal
A}$ given that ${\cal A}$ was chosen from $\rho^{\prime}({\cal A})$. We now
find that the probability is nonvanishing iff $\partial v=0$, in which case
the probability equal $\rho({\cal A})$. Fix some nonzero $v$. Choose a random
pairing. This induces a random graph, with vertices corresponding to nonzero
entries of $v$. This random graph depends on only on a submatrix of the
boundary operator, the submatrix containing columns corresponding to nonzero
entries of $v$. These entries of the submatrix are chosen independently, with
each entry chosen to equal $1$ with probability $\Delta/N$, and then
conditioned on there being an even number of $1$s in each row. Each row then
adds a number of edges to the graph equal to one half the number of $1$s in
that row, and, for given number of $1$s, the edges are added between uniformly
random pairs of vertices subject to the requirement that all edges added by a
given row are between distinct vertices. However, different rows can add edges
between the same vertices. Thus, this is almost, but not quite the same as the
model of an Erdös-Renyi random graph, due to the possibility of multi-edges
and due to some correlation between edges added in a given row. Nevertheless,
it is a standard argument that the resulting graph has the given edge
expansion properties with high probability, indeed with probability $o(1/N)$
for large enough $\beta$.

We give this argument for completeness. We restrict to the case that
$|v|=\Theta(N)$ for simplicity, since with high probability all $v$ with
$\partial v=0$ have that. Let $w\leq v$, with $0<|w|\leq|v|/2$ define some
subset of vertices of the graph. Consider the submatrix of the boundary
operator defined by columns in $v$, i.e., those in the support of $v$. For any
row, let $n^{\perp}$ denote the number of $1$s in columns in $v-w$ , and let
$n$ denote the number of $1$s in columns in $w$. Then, with probability
$1-o(1/N)$, every row of the given submatrix has $n^{\perp}=\Delta\Theta(1)$.
Consider two cases, $|w|>|v|/100$ or $|w|\leq|v|/100$. In the first case, for
large enough $\beta$, with probability $1-O(1/N^{100})$ every row also has
$n=\Delta\Theta(1)$, and with probability $1-O(1/N^{100})$, there are
$\Delta\Theta(1)$ pairs from a column in $w$ to a column in $v-w$. Hence,
there are $\Delta N\Theta(1)$ edges from vertices in $w$ to those in $v-w$,
showing the result in this case.

If instead $|w|\leq|v|/100$, consider the following model for a random
pairing: pick a vertex in $w$, pair it randomly (possibly with a vertex in
$v-w$ or in $w$). Pick the next unpaired vertex (in some arbitrary order) in
$w$, pair it randomly, and continue until all vertices in $w$ are paired. The
pairing of any remaining vertices in $v-w$ does not matter but can be done in
the same way. Then, the probability that on a given step we pair a vertex in
$w$ with another vertex in $w$ is strictly smaller than $1$; in our case it is
at most $1/99$. Imagine a counter that starts at $0$ and is incremented by $2$
every time we pair vertices in $w$, so that it counts the number of vertices
in $w$ paired with a vertex in $v$ If we consider instead a model in which for
each vertex in $w$ with a $1$ in the given row, the counter is incremented by
$2$ with probability $1/99$, the probability that the counter is incremented
is at least as large whenever we consider a previously unpaired vertex, plus
in this second model the counter may be incremented when considering vertices
which have already been paired. That is, in the first model if the counter has
some given probability of reaching some given count $c$, in the second model,
the probability of reaching that count is at least as large. This second model
makes the counter easier to estimate as events become uncorrelated. However,
in this model, with probability $O(1/N^{100})$, the total number of pairings
of vertices in $w$, summed over all rows, is at most $\Delta|w|$ times a
constant much smaller than $1$. On the other hand, with probability
$O(1/N^{100})$, the total number of $1$s over all rows, in a column in $w$, is
at least $0.99\Delta|w|$. So, there must be at least $\Theta(1)\Delta|w|$
pairings between a vertex in $w$ and one not in $w$. ∎

So, we have

######  Theorem 2.

There is a family of LDPC quantum codes on $N$ qubits with distances
$d_{X},d_{Z}=\tilde{\Omega}(N^{2/3})$ and $\tilde{\Theta}(N^{2/3})$ logical
qubits.

###### Proof.

Let’s first go through the construction in the case that we had thickened (see
start of Section V.2) by $\ell=\Theta(N^{1+\epsilon})$. Then we will see that
we can slightly improve this by thickening only by $\ell=\Theta(N)$.

Thickening by $\ell=\Theta(N^{1+\epsilon})$, the reduced cone code has ${\rm
dev}=O(\log(N))$. It has $N=\tilde{O}(N^{2+\epsilon})$; note that
$\sum_{i}|Q_{i}|q_{X}$ is $\tilde{O}(N^{2+\epsilon})$. The reduced cone code
has distance $d_{X}=\tilde{\Omega}(N^{2+\epsilon})$ and
$d_{Z}=\tilde{\Omega}(N)$ and $K=\Theta(N)$. The increase in distance $d_{X}$
comes from the thickening by $\ell$; see lemma 2. The reduced cone code can be
reduced to an LDPC code by Theorem 1 at the cost of a polylogarithmic increase
in $N$ and polylogarithmic reduction in $d_{X},d_{Z}$. Apply distance
balancing to obtain a code on $\tilde{O}(N^{3+\epsilon})$ qubits with both
distances $d_{X},d_{Z}=\tilde{\Omega}(N^{2+\epsilon})$. The original distance
balancing of Has (17) does not increase the number of logical qubits; the
distance balancing of EKZ20a  improves the rate, giving
$\Theta(N^{2+\epsilon})$ logical qubits.

So, this gives a distance scaling as the $2/3-\epsilon$ power of the number of
physical qubits, for any $\epsilon>0$.

In order to slightly improve this, to a distance scaling as the $2/3$ power of
the number of physical qubits up to polylogs, let’s instead thicken by
$\ell=\Theta(N)$. Then, again the reduced cone code has ${\rm dev}=O(\log(N))$
but $N=\tilde{O}(N^{2})$ and $d_{X}=\tilde{\Omega}(N^{2})$ and
$d_{Z}=\tilde{\Omega}(N)$. Reduce to an LDPC code by Theorem 1, and apply
distance balancing to get finally distance
$d_{X},d_{Z}=\tilde{\Omega}(N^{2/3})$. The reason that the reduced thickening
helps here is that when we thickened the first time, we had $w_{Z}=\Theta(N)$.
However, after constructing the reduced cone code, the thickenings used in
Theorem 1 had only $w_{Z}=O(\log(N))$. ∎

##  VI Improving Soundness

Much of the work in the above section was devoted to showing that the
soundness factors $h(G)$ were not small. That relied on a random construction
of the code. In this section, we describe a procedure to increase the
soundness factor to $\Omega(1)$, at the cost of at most a constant factor
increase in number of physical qubits and constant factor reduction in
distance. If the code is not reasonable, one should first apply the
construction of Section III.3 to define the connected code, and then apply
this construction here to the connected code.

We call the procedure here “improving soundness”. Consider a reasonable code
$C$. For each $i$, construct ${\cal B}_{i}$ as before in coning. Define graph
$G_{i}$ as before. Then, define a new complex ${\cal B}^{\prime}_{i}$ and new
graph $G^{\prime}_{i}$ as follows. The graph $G^{\prime}_{i}$ is defined by
adding edges to $G_{i}$; the graphs $G^{\prime}_{i}$ and $G_{i}$ have the same
vertex set and every edge of $G_{i}$ is an edge of $G^{\prime}_{i}$. Edges are
added only between vertices in the same connected component. We add these
edges so that $h(G^{\prime}_{i})=\Omega(1)$. By standard constructions of
expanders, this can be done by increasing the degree of each vertex by $O(1)$.

The complex ${\cal B}^{\prime}_{i}$ has the same set of $1$-cells as does
${\cal B}_{i}$, but it has some added $0$-cells, corresponding to the added
edges. The complex ${\cal B}^{\prime}_{i}$ is defined from $G^{\prime}_{i}$ in
the obvious way. $0$-cells of ${\cal B}^{\prime}_{i}$ correspond to edges of
$G^{\prime}_{i}$ and $1$-cells correspond to vertices of $G^{\prime}_{i}$,
with a $0$-cell in the boundary of a $1$-cell if the corresponding edge has
the corresponding vertex in its boundary. Define a chain map
$f^{\prime}_{i}:{\cal B}^{\prime}_{i}\rightarrow{\cal A}$ so that
$f^{\prime}_{i}$ vanishes on the added $0$-cells and otherwise agrees with
$f_{i}$.

Then, proceed as before, with complexes replaced with their primed version:
construct $\overline{\cal B}^{\prime}_{i}$ from ${\cal B}^{\prime}_{i}$,
construct $\overline{f}^{\prime}_{i}$ from $f_{i}$, and so on.

In this way, we obtain a reduced cone code with the same properties as Lemma
8, except the soundness factor is $\Omega(1)$.

Remark: this procedure allows a simplification of the construction of the
previous section, as there is no need to worry about bounding the soundness of
the various graphs as in Lemma 14. However, I did not discover this improving
soundness construction until after doing the construction of the previous
section, so I leave it as is.

Remark: further, this procedure allows a partial derandomization of the
construction of the previous section and allows an improvement in the polylogs
in the distance, as the code defining ${\cal A}$ can be chosen to be any good
classical LDPC code.

Remark: this procedure adds some number of extra qubits to the reduced cone
code, corresponding to edges added to each $G^{\prime}_{i}$. However, this
procedure adds also $X$-stabilizers, as the complex ${\cal B}^{\prime}_{i}$
will have a larger zeroth homology group than ${\cal B}_{i}$ does.

Acknowledgments— I thank M. Freedman, J. Haah, and G. Zémor for useful
discussions.

## References

  * AH [04] Geir Agnarsson and Magnús M Halldórsson.  Strong colorings of hypergraphs.  In International Workshop on Approximation and Online Algorithms, pages 253–266. Springer, 2004.
  * BE [20] N. Breuckman and J. Eberhardt.  Balanced product quantum codes.  arXiv preprint arXiv:2012.09271, 2020.
  * BH [14] Sergey Bravyi and Matthew B Hastings.  Homological product codes.  In Proceedings of the forty-sixth annual ACM symposium on Theory of computing, pages 273–282, 2014.
  * [4] Shai Evra, Tali Kaufman, and Gilles Zémor.  Decodable quantum LDPC codes beyond the $\sqrt{n}$ distance barrier using high dimensional expanders.  Technical Report 2004.07935, arXiv, 2020.
  * [5] Shai Evra, Tali Kaufman, and Gilles Zémor.  Decodable quantum ldpc codes beyond the $\sqrt{n}$ distance barrier using high dimensional expanders.  arXiv preprint arXiv:2004.07935, 2020.
  * [6] M. H. Freedman and M. B. Hastings.  Building manifolds from quantum codes.
  * FML [02] Michael H. Freedman, David A. Meyer, and Feng Luo.  $Z_{2}$-systolic freedom and quantum codes.  In Mathematics of quantum computation, Comput. Math. Ser., pages 287–320. Chapman & Hall/CRC, Boca Raton, FL, 2002.
  * Has [17] Mathew B Hastings.  Weight reduction for quantum codes.  Quantum Information & Computation, 17(15-16):1307–1334, 2017.  arXiv:1611.03790.
  * HHO [20] Matthew B Hastings, Jeongwan Haah, and Ryan O’Donnell.  Fiber bundle codes: Breaking the $N^{1/2}\operatorname{polylog}(N)$ barrier for quantum ldpc codes.  arXiv preprint arXiv:2009.03921, 2020.
  * KT [20] Tali Kaufman and Ran J. Tessler.  Quantum LDPC codes with $\Omega(\sqrt{n}\log^{k}n)$ distance, for any $k$.  Technical Report 2008.09495, arXiv, 2020.
  * MT [10] Robin A Moser and Gábor Tardos.  A constructive proof of the general lovász local lemma.  Journal of the ACM (JACM), 57(2):1–15, 2010.
  * [12] https://ncatlab.org/nlab/show/quasi-isomorphism.
  * PK [20] Pavel Panteleev and Gleb Kalachev.  Quantum ldpc codes with almost linear distance.  arXiv preprint arXiv:2012.04068, 2020.
  * [14] https://mathoverflow.net/questions/38853/bounds-on-strong-vertex-colourings-of-regular-hypergraphs.
  * TZ [14] Jean-Pierre Tillich and Gilles Zémor.  Quantum LDPC codes with positive rate and minimum distance proportional to the square root of the blocklength.  IEEE Trans. Inform. Theory, 60(2):1193–1202, 2014.