# Tradeoff Constructions for Quantum Locally Testable Codes

Adam Wills Hon Hai Research Institute, Taipei. Email:
<EMAIL_ADDRESS>Ting-Chun Lin Department of Physics, University of
California San Diego, CA, and Hon Hai Research Institute, Taipei. Email:
<EMAIL_ADDRESS>Min-Hsiu Hsieh Hon Hai Research Institute, Taipei. Email:
<EMAIL_ADDRESS>
###### Abstract

In this work, we continue the search for quantum locally testable codes
(qLTCs) of new parameters by presenting three constructions that can make new
qLTCs from old. The first analyses the soundness of a quantum code under
Hastings’ weight reduction construction for qLDPC codes [1] to give a weight
reduction procedure for qLTCs. Secondly, we exhibit the ‘identity product’:
the first product construction that is known to preserve both the soundness
and locality of the inputted quantum code. This can be used to grow the
dimension of a quantum code, where now the tradeoff is put onto the distance.
Finally, we apply the AEL distance amplification construction [2] to the case
of qLTCs for the first time which could, in future, be used to convert high-
distance qLTCs into linear distance qLTCs.

These constructions can be used on as-yet undiscovered qLTCs to obtain new
parameters, but we are able to apply these presently to the hypersphere
product code [3] and the hemicubic code [4] to obtain many previously unknown
parameters. In particular, the only previously known codes to have inverse
polylogarithmic soundness, polynomial distance and polynomial dimension have
polynomial locality. We obtain such codes with constant locality.

##  1 Introduction

Informally, a code, be it classical or quantum, is described as locally
testable if one can determine, by acting only on a small subset of the bits or
qubits (ideally constant in size), whether a given word is a valid codeword or
not. There are consequences of this notion in many areas, most importantly in
the theory of probabilistically checkable proofs (PCPs), where locally
testable codes (LTCs) find their origin. Indeed, the celebrated PCP theorem
was proved with the aid of certain classical LTCs [5, 6, 7]. Quantum locally
testable codes (qLTCs) were thus first introduced [8] in the hope that they
might aid in the conversion of the qPCP conjecture into a qPCP theorem [9],
although it is very much open whether this is possible, or indeed whether the
conjecture is true. qLTCs garnered further attention in 2015 when it was
proved in [10] that the existence of a qLTC of certain parameters would imply
the well-known NLTS conjecture [11]. While the NLTS conjecture was resolved
independently [12], such qLTCs are still desired to provide an alternative
proof of the NLTS theorem.

For the benefit of these problems and others, a search has been initiated for
quantum locally testable codes of new parameters, in the hope of eventually
writing down an optimal qLTC. In this paper, we will present constructions
that can turn one qLTC into another that exhibits different parameters. These
methods find immediate applications on some of the few qLTCs that are known to
exist, producing qLTCs of previously unknown parameters, and will likely
continue to find applications as more qLTCs are discovered.

###  1.1 Overview of Previous Results

When talking about qLTCs, one considers four parameters: the soundness,
dimension, distance and locality, and asks how each of these parameters scale
for a given code as the code length diverges to infinity. The dimension and
distance are both standard parameters of error-correcting codes, being
respectively the number of encoded logical qubits and the minimum weight of a
logical error. We deal exclusively in quantum locally testable CSS codes, for
which the distance is often expressed as $d=\min(d_{X},d_{Z})$, where $d_{X}$
and $d_{Z}$ are the X - and Z - distances: the minimum weights of X - type and
Z - type logical errors respectively.

Soundness and locality are both important to us as they measure the degree of
a code’s local testability, although locality is also very important in the
area of fault tolerance. For a CSS code with parity-check matrices $H_{X}$ and
$H_{Z}$ respectively associated with the X - stabilisers and Z - stabilisers,
the locality is defined as the maximum row or column weight of either $H_{X}$
or $H_{Z}$. For soundness, we first give a definition for classical codes and
then the definition for quantum CSS codes will follow. We say that a classical
code with parity-check matrix $H\in\mathbb{F}_{2}^{s\times t}$ is locally
testable with soundness $\rho$ if for every $x\in\mathbb{F}_{2}^{t}$,
$\frac{|Hx|}{s}\geq\rho\frac{d(x,\ker(H))}{t}$, where
$d(x,\ker(H))=\min\\{|z|\text{ s.t. }x+z\in\ker(H)\\}$. There is then a
general definition of local testability for quantum codes given in [8], but
this is rather involved. For now, it suffices to simply say that there is a
result specialising this definition (Fact 17 of [10]) which tells us that, up
to constant factors, a quantum CSS code is locally testable with soundness
$\rho$ if and only if the classical codes defined by $H_{X}$ and $H_{Z}$ are
locally testable with soundness $\rho$ according to the previous classical
definition.

For an optimal qLTC, the existence of which is currently very much unknown,
the soundness is as large as a constant, whereas the locality is as small as a
constant. Having these two both being constant gives a “true” locally testable
code, because the number of qubits acted on in testing a given word is
constant. Additionally, for an optimal code, the distance and dimension are
both as large as linear. While few qLTCs are known to exist, the history of
qLDPC construction, where we care about only dimension, distance and locality,
is full and rich due to the hope of using qLDPCs for fault-tolerant quantum
computation.

Work on constructing quantum LDPC codes originated with Kitaev’s toric code
[13]. Some 20 years of effort went into the improvement of the dimension and
distance of these codes under the condition of their being LDPC (having
constant locality), until the eventual discovery of good qLDPC codes111A code
is said to be good if it has linear dimension and linear distance., that being
codes with optimally scaling dimension, distance and locality, in [14].
Further constructions were found following this, both full [15, 16], as well
as partial [17]. A major feature of the journey towards better qLDPC codes was
the so-called “square-root distance barrier”, which was the difficulty
experienced in constructing an LDPC quantum code with distance meaningfully
exceeding a square-root, specifically, exceeding $\sqrt{N}\text{polylog}(N)$.
Aside from the toric code itself, the codes of Freedman, Meyer and Luo in [18]
exhibit this, giving distance $\sqrt{N}\sqrt[4]{\log(N)}$, which was the
highest known distance for a qLDPC code for around 20 years, however this code
has constant dimension. Meanwhile, the hypergraph product codes of Tillich and
Zémor [19] gave constant locality with square-root distance and linear
dimension. The square-root distance barrier was eventually broken with the
discovery of the fiber bundle codes due to Hastings, Haah and O’Donnell [20],
followed by the introduction of the lifted product [21] and the balanced
product [22]; good qLDPC codes were discovered shortly after [14].

On the classical side, the existence of good LDPC codes has been known for a
long time [23], although the existence of optimal classical locally testable
codes, known as $c^{3}$ \- LTCs, was not proved until 2021 in [24], shortly
before the independent resolution in [14], after which further constructions
were exhibited [15, 25].

There are only four papers prior to the present work that aimed to construct
qLTCs. The first two papers were from Hastings in 2016 [3] and Leverrier et
al. in 2019 [4], which presented respectively the hyersphere product code and
the hemicubic code. As is suggested by their names, these are both obtained
from geometric constructions. Because of the similarity in the nature of their
construction, and the similarity in their parameters, it makes sense for us to
group these two together under the label “geometric constructions”. Their
parameters are shown in the central column of Table 1.

|  Geometric Constructions [3, 4] |  Double Distance Balancing Applied to the Geometric Constructions [26]
---|---|---
Physical Qubits | $N$ | $\Theta(Nt^{2})$
Soundness | $\Omega\left(\frac{1}{\text{polylog}(N)}\right)$ | $\Omega\left(\frac{1}{\text{polylog}(N)t^{2}}\right)$
Distance | $\Theta\left(\sqrt{N}\right)$ | $\Theta(\sqrt{N}t)$
Dimension | $\Theta(1)$ | $\Theta(t^{2})$
Locality | $\mathcal{O}(\log(N))$ | $\mathcal{O}(\log(N))$
Table 1: The qLTCs of [3] and [4] are grouped under the name “geometric
constructions” for brevity, although it would be remiss of us to not mention
that the latter code exhibits a hard-won improvement in its soundness by a
logarithmic factor over the former: from
$\Omega\left(\frac{1}{\log(N)^{2}}\right)$ to
$\Omega\left(\frac{1}{\log(N)}\right)$.

The third paper aiming to construct qLTCs [27] had the primary aim of
constructing codes with constant soundness. The authors start with the CSS
code defined by the parity-check matrices

$H_{Z}=[I_{n}|I_{n}]\hskip 28.45274ptH_{X}=[\hat{H}|\hat{H}]$ (1)

where $I_{n}$ is an $n\times n$ identity matrix and $\hat{H}$ is a parity-
check matrix for a classical $c^{3}$ \- LTC. This code has constant soundness,
constant locality and linear dimension, although constant X - distance and
linear Z - distance, meaning it has the major deficiency of having constant
overall distance. This is presently the only known example of a “true” quantum
locally testable code: one with constant soundness and locality. By performing
various operations on this code, the authors obtain other codes of improved
distance, although for all these codes, as the distance grows, the locality
increases (or the soundness drops) by the same amount as the distance is
improved, meaning that polynomial distance cannot be obtained without either a
polynomial locality or an inverse polynomial soundness. In particular, the
authors obtain another code with constant soundness and non-constant locality
(although constant average locality) by distance balancing the above code
using a modified parity-check matrix for the repetition code222The method
behind distance balancing is described in Section 2.3.. This distance
balancing procedure allows one to raise the overall distance of the quantum
code, and is shown to preserve its soundness333Here, and throughout this work,
saying a quantity is ‘preserved’ means that it is preserved up to constant
factors., but does so at the expense of its locality. Additionally, this
result on soundness preservation applies only to the particular classical and
quantum codes in question.

A previous result on distance balancing [28] showed that when distance
balancing any quantum code with the usual parity-check matrix for the $t$-bit
repetition code, we obtain the lower bound of
$\Omega\left(\frac{\rho}{t}\right)$ in terms of the soundness of the original
quantum code $\rho$. We generalised this in our previous work [26] to say that
when distance balancing any quantum code with any classical code of length
$t$, the same lower bound may be obtained -
$\Omega\left(\frac{\rho}{t}\right)$ \- on the soundness of the new quantum
code. This allows one to distance balance using a good classical LDPC code,
which has the benefit over distance balancing with the repetition code that
the dimension scaling of the quantum code will improve over the course of
distance balancing, rather than worsening. As a distance balancing procedure
alone, this construction may yield new parameters, for example when applied to
the code described at the start of the previous paragraph. However, there is
another, more general application of this idea that can potentially yield many
more new parameters, which goes by the name ‘double distance balancing’.

Double distance balancing is a procedure that was originally used in the
construction of quantum LDPC codes [21], but we give it a name here for the
first time simply so we have something to refer to it by. Applied to any code,
even one with already-balanced distances, one may distance balance once, and
then again dually, using a good classical LDPC code. This has the effect of
growing the dimension of the quantum code at hand, and causing its distance to
tend towards a square-root, regardless of where it starts from. This procedure
was applied to the geometric constructions in [26] to obtain the parameters
shown in the right-hand column of Table 1. This procedure can be applied to
any qLTC, either currently existing, or yet to be discovered, to potentially
discover many codes, whose parameters exhibit a tradeoff compared to those of
the inputted code.

###  1.2 Overview of Our Results

The motivation behind the present work is to present constructions that can
facilitate the rapid exploration of the parameter space of quantum locally
testable codes. While it is hoped that one day a truly optimal quantum locally
testable code will be written down, it is unclear how long this would take,
and it is worth noting that it took some 30 years to construct optimal
classical locally testable codes. Therefore, it is worth having tools that
allow us to fill out the four-dimensional parameter space as quickly as
possible, allowing for the identification of difficult parameter regimes in
which research can be focused much more quickly than would be possible by
constructing many individual codes.

We exhibit three constructions for this task: weight reduction, the identity
product and distance amplification. Putting these on a par with the double
distance balancing construction applied to qLTCs [26], we obtain a suite of
four “tradeoff” constructions that can be applied to existing, or future
quantum locally testable codes, to potentially quickly discover many new
parameters. The identity product and double distance balancing are also both
continuous, meaning that they can be applied in a graded way rather than
discretely, like the weight reduction and distance amplification procedures.
Therefore from a ‘point in parameter space’, by which we mean one list of
parameters representing one code, one can obtain an ‘area’ or ‘volume in
parameter space’ i.e. many sets of parameters representing many codes.

With the exception of the distance amplification construction, the procedures
are very general and can be applied to most qLTCs. The distance amplification
construction can be used to produce qLTCs of linear distance, although would
not produce a code of interest if applied to a code that did not already have
quite high distance, for example whose relative distance (distance divided by
code length) does not exceed inverse polynomial. Such a qLTC is not presently
known to exist, and therefore the distance amplification construction is the
only one of these results that does not find immediate applications in the
discovery of codes with new parameters. Nevertheless, it is included because
it may be usable in future for the discovery of a qLTC of linear distance.

For the first, and most difficult to prove, of our results, we analyse the
soundness of a quantum code as it undergoes the weight reduction procedure of
Hastings published in 2021 [1], which we must modify slightly to be usable in
our case. [1] replaces the former weight reduction paper [28] from 2016, which
contained an error. [28] did, however, analyse the soundness of quantum codes
under its procedures, and applied this result to the hypersphere product code
to conclude the existence of a new qLTC of constant locality, although this
does not now hold given the error in this paper. The newer paper [1] does not
contain an analysis of soundness under its constructions, possibly because the
constructions in this latter work are significantly more involved than those
of the former. Such an analysis is performed in Section 3 to obtain the result
of Theorem 1.1.

######  Theorem 1.1 (Informal).

Given a quantum locally testable CSS code on $N$ physical qubits, there is,
under reasonable assumptions on this code, another qLTC of constant locality,
whose dimension is equal to that of the first code, and whose number of
physical qubits, distances and soundness differ from those of the first code
by at most a polynomial factor in the original code’s weights and $\log(N)$.

A formal statement of Theorem 1.1 is presented in Lemma 19 in Section 3.4.

For our second result, we are motivated by the desire to be able to grow the
dimension of a quantum locally testable code in such a way as to preserve both
its local testability properties: its soundness and locality. Such a change in
parameters can be achieved by a simple construction of ‘duplicating’ the code.
However, knowing that all previously known distance balancing results cause a
worsening of soundness or locality, even for individual codes, we are
motivated by a desire to achieve this with a homological product, as this is
of greater interest for the study of qLTCs under product constructions. We
achieve this with the ‘identity product’, where the tradeoff now is put onto
the distance scaling of the code. This is the first product construction for
qLTCs that has been shown to preserve both soundness and locality, either for
general quantum codes or in individual cases.

######  Theorem 1.2 (Informal).

Given a quantum locally testable CSS code on $N$ physical qubits and of
dimension $K$, there is, under reasonable assumptions on this code, another
qLTC with the same distance, soundness and locality acting on $Nn$ physical
qubits and of dimension $Kn$, all up to constant factors, for any
$n\in\mathbb{N}$.

A formal statement of Theorem 1.2 is presented in Lemma 4.1 in Section 4.

Finally, we apply the AEL distance amplification procedure [2] to qLTCs for
the first time which could be used in future to obtain qLTCs of linear
distance. However, we emphasise again that this would only be a potentially
useful procedure when applied to codes of relative distance exceeding an
inverse polynomial, and in fact cannot be applied at all to codes with
constant distance. Nevertheless, we have:

######  Theorem 1.3 (Informal).

Given a quantum locally testable CSS code on $N$ physical qubits with locality
$w$ and non-constant distance $d$, let $\Delta=\frac{d}{N}$ be the relative
distance of this code. There is, under reasonable assumptions on this code,
another qLTC of the same number of physical qubits, up to a constant, the same
dimension, linear distance, with locality and soundness differing by at most a
polynomial factor in $\frac{1}{\Delta}$ and $w$.

A formal statement of Theorem 1.3 is presented in Lemma 5.3 in Section 5.

A very brief overview of the available tradeoff constructions is presented in
Table 2.

|  Weight Reduction |  Identity Product |  Distance Amplification |  Double Distance Balancing
---|---|---|---|---
|  Theorem 1.1 Present Work |  Theorem 1.2 Present Work |  Theorem 1.3 Present Work |  Corollary 1.1 [26]
Soundness | $\searrow$ | $\longrightarrow$ | $\searrow$ | $\searrow$
Distance | $\searrow$ | $\searrow$ | $\mapsto\Theta(N)$ | $\longrightarrow\Theta(\sqrt{N})$
Dimension | $\searrow$ | $\nearrow$ | $\longrightarrow$ | $\nearrow$
Locality | $\mapsto\Theta(1)$ | $\longrightarrow$ | $\nearrow$ | $\longrightarrow$
Table 2: This table is intended to give only the essential details of the
available tradeoff constructions. Arrows $\nearrow$, $\longrightarrow$ and
$\searrow$ indicate a rise, preservation, or falling of the scaling of a given
parameter in terms of the number of physical qubits (not the actual value) for
a typical qLTC, under the assumptions of the given result. $\mapsto X$
indicates that the scaling becomes $X$ immediately, whereas $\longrightarrow
X$ indicates that the scaling tends towards $X$, irrespective of its initial
value.

While we hope that the main use of these results will be to as-yet
undiscovered codes, there are several new parameter regimes in which we may
immediately construct codes using these results. The obvious present use cases
for the weight reduction procedure are the geometric constructions.
Technically, applying the tradeoff constructions to these two codes separately
gives new parameters in each case, because the hypersphere product code has a
better locality by a double logarithmic factor, whereas the hemicubic code has
a better soundness by a logarithmic factor, but this is unnecessary detail,
and we apply the construction only to the hemicubic code for simplicity. The
identity product also gives nice new parameters when applied to these
constructions, because it can raise their previously constant dimension and
preserve their local testability properties. These two can be used in
combination, and further double distance balancing can also be employed, to
give many new parameters in the form of a volume in parameter space, as
previously described. The results of this are shown in Table 3.

| Hemicubic Code [4] |  IP and DDB Applied to Hemicubic Code |  IP, DDB and WR Applied to Hemicubic Code
---|---|---|---
Physical Qubits | $N$ | $\Theta(Nt_{1}t_{2}^{2})$ | $\mathcal{O}(N\text{polylog}(Nt_{1}t_{2}^{2})t_{1}t_{2}^{2})$
Soundness | $\Omega\left(\frac{1}{\log(N)}\right)$ | $\Omega\left(\frac{1}{\log(N)t_{2}^{2}}\right)$ | $\Omega\left(\frac{1}{\text{polylog}(Nt_{1}t_{2}^{2})t_{2}^{2}}\right)$
Distance | $\Theta\left(\sqrt{N}\right)$ | $\Theta(\sqrt{N}t_{2})$ | $\Omega\left(\frac{\sqrt{N}t_{2}}{\text{polylog}(Nt_{1}t_{2}^{2})}\right)$
Dimension | $\Theta(1)$ | $\Theta(t_{1}t_{2}^{2})$ | $\Theta(t_{1}t_{2}^{2})$
Locality | $\mathcal{O}(\log(N))$ | $\mathcal{O}(\log(N))$ | $\Theta(1)$
Table 3: The third column shows the new parameters obtained by applying the
identity product (IP) and double distance balancing (DDB) to the hemicubic
code, where the classical codes in these two constructions are of lengths
$t_{1}$ and $t_{2}$ respectively. The final column shows the new parameters of
the code obtained by then applying weight reduction (WR) also. We note that
the hemicubic code can be checked to satisfy all necessary assumptions
throughout the application of these constructions. In particular, the
hemicubic code has a number of X - and Z - stabilisers scaling linearly with
its code length.

Many specific examples of these parameters can be extracted by setting $t_{1}$
and $t_{2}$ to various different values but we mention one in particular. By
setting $t_{2}=1$ and $t_{1}=N^{\alpha}$ for some $\alpha>0$, we can obtain
qLTCs of inverse polylogarithmic soundness, polynomial distance and polynomial
dimension with constant locality. Previously, the only known codes with
inverse polylogarithmic soundness, polynomial distance and polynomial
dimension had polynomial locality.

###  1.3 Structure of the Paper

The paper is structured as follows. Section 2 presents the necessary
preliminaries. In particular, Sections 2.1 and 2.2 give the broad background
on quantum CSS codes and local testability, while Section 2.3 defines the
homological product, which is necessary to understand the constructions of
Sections 3 and 4. Section 2.4 gives the necessary preliminary information on
Hastings’ weight reduction constructions. This is necessary to understand
Section 3, which gives the analysis of a qLTC under this weight reduction
procedure, along with the necessary minor modifications to this procedure for
our case. Section 4 then defines the identity product - a procedure for
growing the dimension of a qLTC while preserving its soundness and locality,
but at the expense of its distance. A brief and informal geometric
interpretation of this is provided in Section 4.1. Finally, the AEL distance
amplification construction is defined and applied to qLTCs in Section 5.
Appendix A gives tables relevant to Section 3 to present the full, detailed,
changes in parameters.

###  1.4 Further Directions

There are many open problems that these results raise; we list only a few.
Chief amongst these is the search for qLTC constructions of new parameters
that may, or may not, be inputtable to the tradeoff constructions of the
present work to produce codes of previously unknown parameters. In particular,
an important next step is to obtain a qLTC of constant soundness, constant
locality and scaling distance, where currently the only know code of constant
soundness and constant locality also has constant distance [27].

On the tradeoff constructions themselves, it would be interesting to see if
the weight reduction procedure applied here to qLTCs could be used for a
weight reduction of more general chain complexes while obtaining a lower bound
on properties analogous to soundness. Additionally, between double distance
balancing and the identity product, there is some sacrifice made for raising
the dimension of a qLTC. It would be interesting to see if there were another
procedure that could do the same with a better tradeoff, perhaps not arising
from the distance balancing procedure.

##  2 Preliminaries

###  2.1 Quantum CSS Codes

We review the relevant information on the homological formulation of quantum
CSS codes but recommend [29], along with its references, for further detail.

A quantum CSS code on qubits is equivalent to a three-term chain complex of
vector spaces over the binary field, which may be written generally as

$C=\left(\mathbb{F}_{2}^{N_{Z}}\overset{H_{Z}^{T}}{\longrightarrow}\mathbb{F}_{2}^{N}\overset{H_{X}}{\longrightarrow}\mathbb{F}_{2}^{N_{X}}\right).$
(2)

where $N_{Z}$, $N$ and $N_{X}$ are respectively the number of Z - stabilisers,
qubits, and X - stabilisers of the code. The idea behind this equivalence is
to define parity-check matrices $H_{Z}\in\mathbb{F}_{2}^{N_{Z}\times N}$ and
$H_{X}\in\mathbb{F}_{2}^{N_{X}\times N}$ by the stabilisers of this code; a
row of $H_{Z}$, for example, denotes the support of one Z - stabiliser. Then
the condition $H_{X}\cdot H_{Z}^{T}=0$ is necessary and sufficient for
commutativity of the stabilisers. Throughout, when describing a quantum CSS
code by a three-term chain complex, the bottom ‘zeroth’ space will always be
that of the X - stabilisers, the ‘first’ space will be that of the qubits and
the top ‘second’ space will be that of the Z - stabilisers. Given a code or
chain complex such as $C$, the ‘code associated with the X - stabilisers of
$C$’ is the classical code $\ker(H_{X})$ and similarly for the Z -
stabilisers. Given that a quantum CSS code is nothing more than two classical
codes satisfying a compatibility condition, it will sometimes be natural to
conflate the terms ‘qubits’ and ‘bits’ in certain proofs, where appropriate,
because often our proofs are only proofs about classical codes associated with
various sets of stabilisers, and the bits of these classical codes are
representative of qubits in the quantum code.

It is possible to ‘take the dual’ of the chain complex $C$ to give the new
chain complex

$C^{*}=\left(\mathbb{F}_{2}^{N_{X}}\overset{H_{X}^{T}}{\longrightarrow}\mathbb{F}_{2}^{N}\overset{H_{Z}}{\longrightarrow}\mathbb{F}_{2}^{N_{Z}}\right).$
(3)

which has the effect of swapping the role of X and Z. Taking the dual of more
general chain complexes can be done by reversing the order of the spaces and
taking the dual of all the linear maps.

Throughout, we will endeavour to avoid using excessive homological language -
nevertheless we define the following terms. We recall that the term ‘chain’ is
standard terminology for an element of a space in a chain complex, whereas a
‘cell’ refers to an element of some special basis of one of the spaces, which
is always the standard basis of a binary vector space for us. Therefore, for
example, a 1-cell in the chain complex of Equation (2) refers to an individual
qubit, whereas a 0-chain in this chain complex refers to a collection of X -
stabilisers. It will be important in certain places to ensure a distinction
between a ‘stabiliser’, which is a generator of the stabiliser code
represented by individual 0-cells or 2-cells, and a ‘member of the stabiliser
group’, which is a product of generators of the stabiliser code represented by
0-chains or 2-chains. We recall also that, for a chain complex $X$ with spaces
$X_{i}$ and boundary maps $\partial_{i}:X_{i}\rightarrow X_{i-1}$, we refer to
i-cycles as the i-chains that are in $\ker\partial_{i}$ and i-cocyles as the
i-chains that are in $\ker\partial_{i+1}^{T}$. i-boundaries and
i-coboundaries, also called trivial i-cycles and i-cocyles, are respectively
the i-chains that are elements of $\operatorname{im}\partial_{i+1}$ and
$\operatorname{im}\partial_{i}^{T}$. For the chain complex $C$, we note that
1-cycles represent Z - operators that commute with all the X - stabilisers,
while 1-boundaries represent members of the Z - stabiliser group. Similarly,
1-cocyles represent X - operators that commute with all the Z - stabilisers,
while 1-coboundaries represent members of the X - stabiliser group.

It will be common for the spaces of chain complexes such as $C$ to be direct
sums of smaller spaces, for example
$\mathbb{F}_{2}^{N}=\mathbb{F}_{2}^{A}\oplus\mathbb{F}_{2}^{B}$ or
$\mathbb{F}_{2}^{N_{X}}=\mathbb{F}_{2}^{C}\oplus\mathbb{F}_{2}^{D}$. In this
case, when we refer to “qubits in $\mathbb{F}_{2}^{A}$”, we are referring to
the qubits represented by basis elements of $\mathbb{F}_{2}^{A}$, and
similarly “X - stabilisers in $\mathbb{F}_{2}^{C}$” is shorthand for the X -
stabilisers represented by basis elements of $\mathbb{F}_{2}^{C}$, etc.

We now define the parameters of our codes that are important to us. The X -
and Z - distances of the code are the minimum weights of logical X - type and
Z - type errors. These are

$d_{X}=\min\left\\{|v|:v\in\ker(H_{Z})\setminus\text{im}(H_{X}^{T})\right\\}$
(4)

and

$d_{Z}=\min\left\\{|v|:v\in\ker(H_{X})\setminus\text{im}(H_{Z}^{T})\right\\}$
(5)

which may be described homologically as the minimum weights of non-trivial
elements of first cohomology and first homology respectively. The distance of
the code is then the minimum of these two: $d=\min\\{d_{X},d_{Z}\\}$, which is
the minimum weight of a logical error of our code. Another important parameter
of the code is its dimension, the number of logical qubits which it may
encode, which is

$K=\dim\left(\ker(H_{X})/\operatorname{im}(H_{Z}^{T})\right)$ (6)

i.e. the dimension of the first homology group. Sometimes, the literature
refers to rate and relative distance, which are respectively dimension divided
by code length and distance divided by code length.

Important quantities in this work will be the ‘weights’ of the quantum code,
also sometimes referred to as the localities. Following the notation of [28]
and [1], we define

$\displaystyle w_{X}$ $\displaystyle=\text{max row weight}(H_{X})$ (7)
$\displaystyle w_{Z}$ $\displaystyle=\text{max row weight}(H_{Z})$ (8)
$\displaystyle q_{X}$ $\displaystyle=\text{max column weight}(H_{X})$ (9)
$\displaystyle q_{Z}$ $\displaystyle=\text{max column weight}(H_{Z}).$ (10)

$w_{X}$ is therefore the maximum weight of an X - stabiliser, and similarly
for $w_{Z}$, whereas $q_{X}$ is the maximum number of X - stabilisers acting
on a given qubit, and similarly for $q_{Z}$. The overall ‘locality’ of the
code is defined as

$w=\max\\{w_{X},w_{Z},q_{X},q_{Z}\\}.$ (11)

In places, we will describe a code as ‘high weight’ or ‘low weight’, which
simply means that it has non-constant locality or constant locality
respectively. Similarly, to describe a given stabiliser as ‘high weight’ means
that its support is super-constant in size.

All of the quantities $N$, $N_{X}$, $N_{Z}$, $d_{X}$, and so on, will be
standard for all quantum codes. We will often refer to the parameters of
various codes with different decorations, for example decorating all
parameters of a particular code with a prime or a tilde. Typically, the term
‘code’ really refers to an infinite family of codes whose length (number of
physical qubits) tends to infinity. We measure the size of the parameters that
are important to us in terms of their asymptotic scaling in terms of the code
length, $N$. The optimal scaling of dimension and distance is $\Theta(N)$,
i.e. linear, whereas the optimal scaling of locality is constant, $\Theta(1)$,
which is to say that it is not “scaling”. A code with these three parameters
“scaling” simultaneously optimally, is referred to as a good LDPC code.

###  2.2 Classical and Quantum Local Testability

We will now review the relevant definitions in the area of local testability
for both classical and quantum codes.

There are multiple notions of local testability on the classical side, with
relations between them, but one in particular has become adopted in the recent
quantum literature [4, 14, 27]. Given a classical code described by some
parity-check matrix $H\in\mathbb{F}_{2}^{s\times t}$, the code is said to be
locally testable with soundness $\rho$ if for every $x\in\mathbb{F}_{2}^{t}$,

$\frac{|Hx|}{s}\geq\rho\frac{d(x,\ker(H))}{t}$ (12)

where $d(x,\ker(H))=\min\\{|z|\text{ s.t. }x+z\in\ker(H)\\}$ is the distance
of the word $x$ from the code. The idea behind this is that one may check, up
to a success probability $\frac{d(x,\ker(H))}{t}$, whether a given word $x$ is
in the codespace or not, by checking a subset of the checks of $H$ chosen at
random. If we see even one that is violated, we may conclude that
$x\notin\ker(H)$, whereas if we see them all satisfied, we will return
$x\in\ker(H)$. Since $\frac{|Hx|}{s}$ is the probability that a randomly
chosen check is violated, in order to be correct with the desired success
probability, we check $\mathcal{O}\left(\frac{1}{\rho}\right)$ checks. We say
also that the given classical code has locality $w$ if all of the rows and
columns of $H$ have weight at most $w$444It is common in the case of classical
codes to only define locality in terms of maximum row weight. However, it
makes sense to define it here in terms of column weights too, particularly for
when we take products. For example, with this definition, we can say that the
locality of a quantum code defined via a homological product between a quantum
code and a classical code scales with the worse of the two localities of the
inputted codes; see Section 2.3..

Quantum locally testable codes were first defined in [8] for general quantum
codes, although the definition specialises to the case of stabiliser codes as
follows [10]. Given the generators of a stabiliser group $g_{1},...,g_{m}$,
one may define a stabiliser code. With the projectors $\Pi_{i}=(I-g_{i})/2$
being onto the $+1$-eigenspaces of each $g_{i}$, the codespace is exactly the
0-eigenspace of $\sum_{i=1}^{m}\Pi_{i}$. Calling this codespace $C$, the
t-fattening of $C$ is the vector space defined by

$C_{t}=\text{span}\\{(A_{1}\otimes...\otimes A_{n})\ket{\psi}\text{ s.t.
}\ket{\psi}\in C,|\\{i\in\\{1,...,n\\}:A_{i}\neq I\\}|\leq t\\}.$ (13)

We then let $\Pi_{C_{t}}$ be the projector onto the vector space $C_{t}$, from
which we define the distance observable from $C$ as

$D_{C}=\sum_{t\geq 1}t\left(\Pi_{C_{t}}-\Pi_{C_{t-1}}\right).$ (14)

This allows us to say that the stabiliser code is locally testable with
soundness $\rho$ if the operator inequality

$\frac{1}{m}\sum_{i=1}^{m}\Pi_{i}\succeq\frac{\rho}{n}D_{C}$ (15)

holds true. When dealing with CSS codes, which we do exclusively, the
following lemma allows us to only worry about the above classical definition
of local testability, rather than the general definition for stabiliser codes,
or any other classical definition.

######  Lemma 2.1 (Fact 17 of [10]).

Let $C$ be a quantum CSS code defined by the parity-check matrices $H_{X}$ and
$H_{Z}$. If $C$ is locally testable with soundness $\rho$, then the classical
codes defined by the parity-check matrices $H_{X}$ and $H_{Z}$ are locally
testable with soundness at least $\rho/2$. Conversely, if the classical codes
defined by the parity-check matrices $H_{X}$ and $H_{Z}$ are locally testable
with soundness $\rho$, then $C$ is locally testable with soundness $\rho$.

Throughout, we use $\rho_{X}$ to denote the soundness of the X - operators of
a given CSS code, and $\rho_{Z}$ to denote the soundness of the Z - operators
of a given CSS code. Therefore, $\rho_{X}$ is the soundness of the code
associated with the Z - stabilisers, $\ker(H_{Z})$, whereas $\rho_{Z}$ is the
soundness of the code associated with the X - stabilisers,
$\ker(H_{X})$555This is the opposite convention to that used in our previous
work, [26], however we feel it is the best one because it brings the
soundnesses into line with the distances - $d_{X}$ is the minimum weight of a
logical X - type error, etc.. As with distance, dimension and locality, we
measure the size of the soundness in terms of its asymptotic scaling in terms
of the code length. Ideally, the soundness is $\Theta(1)$, and therefore does
not “scale”. A code with simultaneously optimally “scaling” distance,
dimension, locality and soundness, is called a $c^{3}$ \- LTC.

Many of our proofs will therefore be showing the classical soundness of
$\ker(H)$ for some parity-check matrix $H\in\mathbb{F}_{2}^{s\times t}$. In
order to show that this code has soundness $\rho$, we will usually simply
consider a general bit string $u\in\mathbb{F}_{2}^{t}$ and show that
$\frac{|Hu|}{s}\geq\rho\frac{d(u,\ker(H))}{t}$. However, it will be common for
us, at the start of such a proof, to add some other bit string $v$ to $u$ and
claim that we can do so without loss generality. We can do this because these
bit strings will always be in the space $\ker(H)$ for whatever $H$ we are
talking about; for such a bit string $v$, $d(u+v,\ker(H))=d(u,\ker(H))$ and
$H(u+v)=Hu$. In terms of Pauli operators, if we are considering $u$ to
represent some Z - operator, we may add without loss of generality bit strings
$v$ corresponding to Z - operators that commute with all X - stabilisers. This
means both Z - logical operators and Z - stabilisers. Note also that if $u$
represents some Z - operator, then $|H_{X}u|$ is the number of violated X -
stabilisers. Many of our proofs will be in terms of a number of violated
stabilisers.

We add a final note on our definition of classical local testability, Equation
(12). This definition includes the ‘dimensions’ of the parity-check matrix $s$
and $t$. This is now standard in the literature, but in other places they may
be simply omitted, for example [28], where the definition is replaced with
$|Hx|\geq\rho d(x,\ker(H))$. This makes some of our results look slightly
different to other works, like [28], that do not include them. We emphasise
that the difference is usually negligible, because typically $s$ will scale at
the same rate, or nearly the same rate, as $t$. For us, it means that many of
our soundness results look more complicated than they otherwise would,
including many dimensions such as $N$, $N_{X}$ and $N_{Z}$. This is mostly
more of an annoyance than anything, and reasonable assumptions on the codes in
question, for example $N=\Theta(N_{X})=\Theta(N_{Z})$, which is common, may
lead to such terms being forgettable. The most important features of our
various soundness bounds are almost always not the dimensions.

###  2.3 The Homological Product

The homological product is a tool that has been used, along with its
generalisations, for over a decade now to construct quantum CSS codes. It
first arose implicitly in the work of Tillich and Zémor in 2009 [19] and has
since been generalised to more elaborate product constructions [21, 22] that
yield better parameters. The basic homological product takes in two chain
complexes, $X$ and $Y$, and returns another chain complex $X\times Y$.
Supposing $X$ and $Y$ are both chain complexes over $\mathbb{F}_{2}$, the
resulting chain complex will be over the same field. We will also assume that
$X_{p}=0$ for $p<N$ and $Y_{q}=0$ for $q<N$, for some $N\in\mathbb{Z}$, where
$A_{p}$ denotes the $p$-th space of the chain complex $A$. The spaces of
$X\times Y$ are then defined via

$(X\times Y)_{p}=\bigoplus_{i=0}^{p}X_{i}\otimes Y_{p-i}.$ (16)

Denoting the boundary maps of the two input chains as
$\partial_{p}^{X}:X_{p}\rightarrow X_{p-1}$ and
$\partial_{p}^{Y}:Y_{p}\rightarrow Y_{p-1}$, the boundary map
$\partial_{p}^{X\times Y}$ of $X\times Y$ acts on product elements $u\otimes
v\in X_{i}\otimes Y_{p-i}$ via

$\partial_{p}^{X\times Y}(u\otimes v)=\left(\partial_{i}^{X}(u)\otimes
v\right)\oplus\left(u\otimes\partial_{p-i}^{Y}(v)\right).$ (17)

Its action on the whole space may then be determined by enforcing linearity.
It may be checked that this definition indeed yields a valid chain complex
$X\times Y$.

The only homological product that we will take in this work is that of a
3-term chain (a quantum CSS code) with a 2-term chain (a classical code) in
order to achieve the ‘distance balancing’ construction. This will arise twice:
first as a step in Hastings’ weight reduction methods in Section 2.4.3 and
second in the form of our ‘identity product’ construction in Section 4666Note
that, while we employ the distance balancing construction in both of these
cases, the intention behind using it is not actually to “balance distances” in
either case.. The idea behind the distance balancing construction is to
address the case in which a code has, for example, a very poor X - distance
and a better Z - distance, or vice versa. Because the overall distance is
defined as the minimum of these two, improving the X - distance at the expense
of the Z - distance yields an improved overall distance.

In order to distance balance a quantum code given by a chain complex
$C=\left(\mathbb{F}_{2}^{N_{Z}}\overset{H_{Z}^{T}}{\longrightarrow}\mathbb{F}_{2}^{N}\overset{H_{X}}{\longrightarrow}\mathbb{F}_{2}^{N_{X}}\right)$,
we use an auxiliary classical code with a parity-check matrix
$H\in\mathbb{F}_{2}^{s\times t}$, which may be thought of as a 2-term chain
complex
$R=\left(\mathbb{F}_{2}^{t}\overset{H}{\longrightarrow}\mathbb{F}_{2}^{s}\right)$.
The first step in the distance balancing procedure is to take the dual of the
latter chain complex to yield
$R^{*}=\left(\mathbb{F}_{2}^{s}\overset{H^{T}}{\longrightarrow}\mathbb{F}_{2}^{t}\right)$.
The second step is then to take the homological product of $C$ with $R^{*}$ to
yield a 4-term chain complex $C\times R^{*}$. Finally, we define our distance
balanced version of $C$, which we may call $C^{\prime}$, via the chain complex
formed from the last three terms of $C\times R^{*}$: $\left(C\times
R^{*}\right)_{2}$, $\left(C\times R^{*}\right)_{1}$ and $\left(C\times
R^{*}\right)_{0}$. This procedure was first considered by Hastings in 2016
with the ingredient classical code $R$ being only the repetition code [28],
and then generalised to the case of all classical codes by Evra, Kaufman and
Zémor in 2020 [30]. The scaling of the non-soundness parameters is given in
the following lemma. The requirement that the parity-check matrix of the
classical code has independent checks (meaning its rows are linearly
independent) is technically important, although generally non-restrictive.

######  Lemma 2.2 ([30, Theorem 4.2]).

In the above distance balancing construction, as long as the classical code
has independent checks,

$\displaystyle\dim(C^{\prime})$ $\displaystyle=\dim(C)\dim(R)$ (18)
$\displaystyle d_{X}(C^{\prime})$ $\displaystyle=d_{X}(C)d(R)$ (19)
$\displaystyle d_{Z}(C^{\prime})$ $\displaystyle=d_{Z}(C).$ (20)

Furthermore, under the reasonable assumption that $N_{X}=\mathcal{O}(N)$, the
number of physical qubits of $C^{\prime}$ is $\Theta(Nt)$. Finally, the
locality of the resulting quantum code scales with the worse of the localities
of the inputted quantum code $C$ and the classical code $R$, where here by the
locality of $R$ we mean the maximum row or column weight of $H$.

Notice that while the Z - distance appears to remain unchanged, it will become
worse in real terms (in its asymptotic scaling) since the number of physical
qubits rises. The above procedure may also be performed ‘dually’ (meaning we
take the dual of the quantum code before and after the procedure) to raise the
Z - distance at the expense of the X - distance. As for the soundness, it was
shown in our previous work [26] that under reasonable assumptions on the
quantum code, the soundness of $C^{\prime}$ may be written in terms of that of
$C$ as

$\rho(C^{\prime})=\Omega\left(\frac{\rho(C)}{t}\right)$ (21)

which gives a direct generalisation of the same result by Hastings [28] for
the case of $R$ being the t-bit repetition code.

###  2.4 Weight Reduction

In 2016, Hastings published the paper [28] providing constructions that could
weight reduce quantum codes i.e. reduce $q_{X}$, $q_{Z}$, $w_{X}$ and $w_{Z}$
to $\mathcal{O}$(1). In that paper, this went via two constructions: the
X-type generator splitting of Section IIA and the Z-type qubit splitting of
Section IIC. The first can reduce $w_{X}$ to $\mathcal{O}$(1) and the second
can reduce $q_{Z}$ to $\mathcal{O}$(1). It is then claimed in the paper that
both of these constructions preserve constant $w_{Z}$ and $q_{X}$ 777A
construction is said to preserve the constancy of a parameter if the constancy
of that parameter before the construction implies its constancy after the
construction.. This would lead to these two constructions alone being
sufficient for a full weight reduction of all four parameters to constant, as
follows:

  1. 1.

Use the X-type generator splitting to reduce $w_{X}$ to $\mathcal{O}$(1).

  2. 2.

Use the Z-type qubit splitting to reduce $q_{Z}$ to $\mathcal{O}$(1). This
construction does indeed preserve the constancy of $w_{X}$.

  3. 3.

Use the X-type generator splitting dually888To apply a construction dually
means to take the dual of the CSS code chain complex before and after the
procedure, thereby applying the construction with the roles of X and Z
swapped. to reduce $w_{Z}$ to $\mathcal{O}$(1). This would then preserve the
constancy of $w_{X}$ and $q_{Z}$.

  4. 4.

Use the Z-type qubit splitting dually to reduce $q_{X}$ to $\mathcal{O}$(1),
preserving the constancy of all other parameters.

Unfortunately, as observed by Zémor, Lemma 1 of that paper contains an error,
meaning that, during (non-dual) X-type generator splitting, constant $w_{Z}$
is not necessarily preserved. These constructions alone are therefore
insufficient for a full weight reduction of a quantum code of reducing all
four parameters to constant, because in step 3, reducing $w_{Z}$ may cause
$w_{X}$ to grow large. Fortunately, Hastings updated the paper with the
publication of [1]. In this paper, the X-type generator splitting and Z-type
qubit splitting are both re-used, but supplemented with additional
constructions. The X-type generator splitting is renamed to “gauging” and the
Z-type qubit splitting is renamed to “thickening and choosing heights”999This
construction really comes in two steps: first thickening, and second choosing
heights. These are two separate mathematical steps, but often the whole
construction is referred to by Hastings as simply “thickening”. It will be
important for us to emphasise the existence of both of these steps later on
and so we will refer to the whole construction as “thickening and choosing
heights”.. The two added constructions are called “copying” and “coning”. It
is shown in [1] that, as well as reducing the weights, each of these
constructions causes the number of physical qubits, dimension and distance to
change by a factor that is at most a polynomial in the original weights and
the logarithm of the original length. Then, these four together are sufficient
for a full reduction of all four parameters to constant as follows:

  1. 1.

Use copying to reduce $q_{X}$ to a constant.

  2. 2.

Use gauging to reduce $w_{X}$ to a constant. This preserves constant $q_{X}$.

  3. 3.

Use thickening and choosing heights to reduce $q_{Z}$ to a constant. This
preserves constant $q_{X}$ and $w_{X}$.

  4. 4.

Use coning to reduce $w_{Z}$ to a constant. This preserves constant $q_{X}$,
$w_{X}$ and $q_{Z}$ 101010The reader may wonder whether all four of these
constructions are, in fact, necessary. Could we not, for example, forget about
copying, and instead use thickening and choosing heights dually to reduce
$q_{X}$ in the first step? This is not possible, because dual thickening and
choosing heights cannot reduce $q_{X}$ to a constant as long as there is a
non-constant $w_{Z}$. Overall, this order of four constructions is quite
delicately constructed..

We comment that Hastings presents copying and gauging together, in one
combined construction, in [1], because using these two constructions together
leads to lower overhead. It will make sense for proving our results to
extricate these two constructions, but note that potentially slightly better
parameters in some cases could be obtained by considering them together. More
generally, our primary goal is to demonstrate a full weight reduction of any
qLTC, under reasonable restrictions, incurring a decrease in the soundness by
a factor that is at most a polynomial in the original weights and the
logarithm of the original length. Note, however, that in general this
polynomial is likely to have very large exponents. Particular cases may get
better parameters with closer analysis in cases where, for example, a subset
of the four weight parameters are already constant, there are only a few
stabilisers acting on a large number of qubits, or similar. Before showing the
constructions, we finally comment that in presenting some of the Lemmas from
[28] and [1], small changes have been made in the pursuit of greater detail,
but no changes made are particularly consequential.

Section 3 contains the necessary analyses of the soundness of quantum codes
under these constructions and there is a full analysis of putting all these
constructions together in Section 3.4 for a full weight reduction of a quantum
locally testable code.

####  2.4.1 Copying

Copying is a simple construction presented by Hastings to reduce $q_{X}$ to a
constant (indeed, it can reduce $q_{X}$ to at most 3). Again, this is
presented in [1] in conjunction with gauging, but we separate the two
constructions here.

Given an initial code $C$ for which we wish to reduce $q_{X}$ 111111We will
say that a parameter is “reduced” as shorthand for saying that it is “reduced
to a constant”. to produce another code $\tilde{C}$, copying goes as follows:

  1. 1.

Concatenate $C$ with a repetition code of length $q_{X}$ in the X - basis i.e.
a stabiliser code on $q_{X}$ qubits with stabilisers $X_{1}X_{2}$,
$X_{2}X_{3}$, …, $X_{q_{X}-1}X_{q_{X}}$. Explicitly,

    1. (a)

For every qubit $q$ of $C$, $\tilde{C}$ will have qubits labelled by $(q,j)$
for $j\in\\{1,...,q_{X}\\}$. These are the only qubits of $\tilde{C}$.

    2. (b)

For every Z - stabiliser in $C$, $Z_{q_{1}}...Z_{q_{w}}$, $\tilde{C}$ will
have a Z - stabiliser $\tilde{Z}_{q_{1}}...\tilde{Z}_{q_{w}}$, where by
$\tilde{Z}_{q_{i}}$ we mean $\Pi_{j=1}^{q_{X}}Z_{(q_{i},j)}$. These are the
only Z - stabilisers of $\tilde{C}$.

    3. (c)

For every X - stabiliser in $C$, $S=X_{q_{1}}...X_{q_{w}}$, $\tilde{C}$ will
have an X - stabiliser $\tilde{S}=X_{(q_{1},j(S,1))}...X_{(q_{w},j(S,w))}$ for
some $j(S,i)\in\\{1,...,q_{X}\\}$ to be specified. These are called the copied
X - stabilisers. Additionally, for each qubit $q$ in $C$, $\tilde{C}$ will
also have stabilisers
$X_{(q,1)}X_{(q,2)},X_{(q,2)}X_{(q,3)},...,X_{(q,q_{x}-1)}X_{(q,q_{X})}$.
These are called the new X - stabilisers. The copied and new X - stabilisers
are the only X - stabilisers of $\tilde{C}$.

  2. 2.

The $j(S,i)$ are chosen such that each qubit is acted on by at most one copied
X - stabiliser.

We explain the idea here in a more worded way, through which it will become
clear how the choice in step 2 is possible. The logical Z - operator of the
repetition code in the X - basis is the product of Z on all qubits i.e.
$\Pi_{j=1}^{q_{X}}Z_{j}$. For the logical X - operator, we have a choice of an
individual X operator on any one of the qubits i.e. $X_{j}$ for any $j$.
Therefore, when we concatenate our code $C$ with this repetition code, each Z
- stabiliser in $\tilde{C}$ is formed by simply repeating every physical Z in
any Z - stabiliser of $C$ $q_{X}$ times. On the other hand, each copied X -
stabiliser will have the same weight as the old X - stabiliser it came from -
we just take care that for every X - stabiliser acting on a given qubit $q$ in
$C$, of which there are at most $q_{X}$, each resulting copied X - stabiliser
acts on a different $(q,j)$.

We then have the following.

######  Lemma 2.3 (Extricated from Lemma 1, on Copying and Gauging, in [1]).

Let parameters with and without a tilde be those of $\tilde{C}$ and $C$
respectively, i.e. those after and before copying. Then

  1. 1.

$\tilde{N}=Nq_{X}$, $\tilde{N}_{X}=N_{X}+\Theta(Nq_{X})$,
$\tilde{N}_{Z}=N_{Z}$.

  2. 2.

$\tilde{K}$ = K.

  3. 3.

$\tilde{q}_{X}\leq 3$.

  4. 4.

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

  5. 5.

$\tilde{q}_{Z}=q_{Z}$.

  6. 6.

$\tilde{w}_{Z}=q_{X}w_{Z}$.

  7. 7.

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

  8. 8.

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

In Section 3.1, we will analyse the soundness of $\tilde{C}$ in terms of that
of $C$.

####  2.4.2 Gauging

Gauging has already been fully analysed on its own in [28] and so we take it
here as a black-box construction to reduce $w_{X}$. The reader can either see
this construction in conjunction with copying, in [1] or, what we recommend,
on its own, under the name of “X-type generator splitting” in Section IIA of
[28], and taking our Lemma 2.4 to replace Lemma 1 in that paper. The soundness
of gauging was also analysed in [28] in Lemma 6. This is the reason that we
wanted to separate copying and gauging: gauging already has a soundness
analysis while copying does not. Note that using the presented ingredients, it
would be straightforward to analyse the soundness of the combined copying and
gauging procedure of [1], and again this would likely lead to better
parameters, but we do not do this to avoid repeating too much of the gauging
soundness proof.

######  Lemma 2.4 (From [28], Lemma 1 ($\tilde{w}_{Z}$ is corrected) and Lemma
6).

Let parameters with and without a tilde be those of the code after and before
gauging respectively. Then

  1. 1.

$\tilde{N}=\mathcal{O}(Nq_{X})$ $(\tilde{N}\geq N)$,
$\tilde{N}_{X}=\mathcal{O}(N_{X}+Nq_{X})$, $\tilde{N}_{Z}=N_{Z}$.

  2. 2.

$\tilde{K}=K$.

  3. 3.

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

  4. 4.

$\tilde{w}_{X}\leq 3$.

  5. 5.

$\tilde{q}_{Z}\leq w_{X}q_{Z}$.

  6. 6.

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

  7. 7.

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

  8. 8.

$\tilde{d}_{X}\geq d_{X}\Theta\left(\frac{1}{w_{X}}\right)$.

  9. 9.

$\tilde{\rho}_{Z}\geq\frac{\tilde{N}}{\tilde{N}_{X}}\frac{N_{X}}{N}\rho_{Z}\frac{1}{1+w_{X}\left(q_{X}+\frac{N_{X}}{N}\rho_{Z}\right)}$.

  10. 10.

$\tilde{\rho}_{X}\geq\frac{\tilde{N}}{N}\rho_{X}$.

Note then that under the reasonable assumptions that $N_{X}=\Theta(N)$,
$\rho_{Z}=\mathcal{O}(1)$, and assuming that copying has already been
performed to get $q_{X}=\mathcal{O}(1)$, we have
$\tilde{\rho}_{Z}=\Omega\left(\frac{\rho_{Z}}{w_{X}}\right)$ and
$\tilde{\rho}_{X}\geq\rho_{X}$.

####  2.4.3 Thickening and Choosing Heights

Thickening and Choosing Heights was presented as “Z-type Qubit Splitting” in
Section IIC of [28] and under the present name in Section II of [1] and allows
for the reduction of the parameter $q_{Z}$. Both of these papers present a
full analysis of the construction’s non-soundness parameters. Further, [28]
presents an analysis of the soundness of the “thickening only” portion of the
construction, without a choice of heights being made, in its Lemma 7 .
Therefore, for thickening and choosing heights, our contribution is to analyse
the soundness under the choice of heights. It is because of this that we
emphasise the two steps in the name “thickening and choosing heights”, as
mentioned, rather than simply “thickening”, which is how Hastings often refers
to both steps collectively.

The first step of this construction, thickening, is exactly the distance
balancing construction, explained in Section 2.3, where the classical code
being used is the repetition code of length $l$121212Indeed, the discovery of
thickening for weight reduction doubled as the discovery of the distance
balancing procedure. This was followed by the distance balancing method of
Evra et al. [30] that allowed for the classical code to be general, not just
the repetition code. This allows good classical LDPC codes to be used, meaning
that the dimension of the quantum code does not drop when distance balancing..
We therefore take the chain complex of the inputted quantum code:
$C=\left(\mathbb{F}_{2}^{N_{Z}}\overset{H_{Z}^{T}}{\longrightarrow}\mathbb{F}_{2}^{N}\overset{H_{X}}{\longrightarrow}\mathbb{F}_{2}^{N_{X}}\right)$
and the chain complex of the classical repetition code,
$R=\left(\mathbb{F}_{2}^{l}\overset{H}{\longrightarrow}\mathbb{F}_{2}^{l-1}\right)$,
where

$H=\begin{pmatrix}1&1&0&0&\cdots&0&0\\\ 0&1&1&0&\cdots&0&0\\\
0&0&1&1&\cdots&0&0\\\ &&&&\ddots&&\\\ 0&0&0&0&\cdots&1&1\end{pmatrix}$ (22)

and take the homological product of $C$ with the dual of the latter complex,
$R^{*}$. This gives us the four-term chain complex shown in Figure 1.

$\mathbb{F}_{2}^{N_{Z}}\otimes\mathbb{F}_{2}^{l-1}$$\mathbb{F}_{2}^{N}\otimes\mathbb{F}_{2}^{l-1}$$\mathbb{F}_{2}^{N_{X}}\otimes\mathbb{F}_{2}^{l-1}$$\mathbb{F}_{2}^{N_{X}}\otimes\mathbb{F}_{2}^{l}$$\mathbb{F}_{2}^{N_{Z}}\otimes\mathbb{F}_{2}^{l}$$\mathbb{F}_{2}^{N}\otimes\mathbb{F}_{2}^{l}$$\oplus$$\oplus$$H_{Z}^{T}\otimes
I$$I\otimes H^{T}$$H_{Z}^{T}\otimes I$$H_{X}\otimes I$$I\otimes
H^{T}$$I\otimes H^{T}$$H_{X}\otimes
I$$\mathcal{C}^{\prime}_{3}$$\mathcal{C}^{\prime}_{2}$$\mathcal{C}^{\prime}_{1}$$\mathcal{C}^{\prime}_{0}$$\partial_{3}$$\partial_{2}$$\partial_{1}$
Figure 1: The homological product of $C$ with $R^{*}$, denoted $C^{\prime}$.
These diagrams can be “read off vertically”, meaning that, for example
$\mathcal{C}_{2}^{\prime}=\left(\mathbb{F}_{2}^{N_{Z}}\otimes\mathbb{F}_{2}^{l}\right)\oplus\left(\mathbb{F}_{2}^{N}\otimes\mathbb{F}_{2}^{l-1}\right)$.
The linear maps between $\mathcal{C}_{i}^{\prime}$ can also be read off
vertically, summing the images of any maps that map to the same space.

Finally, we define another quantum code from the final three terms of this
four-term chain complex i.e.
$\mathcal{C}_{2}^{\prime}\overset{\partial_{2}}{\longrightarrow}\mathcal{C}_{1}^{\prime}\overset{\partial_{1}}{\longrightarrow}\mathcal{C}_{0}^{\prime}$.
For clarity, Z - stabilisers are associated with basis elements of
$\mathcal{C}_{2}^{\prime}$, qubits are associated with basis elements of
$\mathcal{C}_{1}^{\prime}$ and X - stabilisers are associated with basis
elements of $\mathcal{C}_{0}^{\prime}$.

At this stage, $q_{Z}$ has not been reduced. Indeed, there will be a qubit
represented by some basis element in
$\mathbb{F}_{2}^{N}\otimes\mathbb{F}_{2}^{l}$ that will be acted on by $q_{Z}$
Z - stabilisers represented by basis elements in
$\mathbb{F}_{2}^{N_{Z}}\otimes\mathbb{F}_{2}^{l}$. What we now do, however, is
to remove most of the Z - stabilisers associated with basis elements of
$\mathbb{F}_{2}^{N_{Z}}\otimes\mathbb{F}_{2}^{l}$. This is the ‘choosing
heights’ step. Writing the standard basis of $\mathbb{F}_{2}^{l}$ as
$\left(w_{i}\right)_{i=1}^{l}$, for each basis element
$c\in\mathbb{F}_{2}^{N_{Z}}$, we pick one $k\in\\{1,...,l\\}$ and remove all
basis elements $c\otimes w_{k^{\prime}}$ for $k^{\prime}\neq k$, therefore
keeping $c\otimes w_{k}$131313The reason for the name ‘choosing heights’ is
that the chain complex for the repetition code may also be thought of as a
cellulation of an interval, and so taking this homological product can be
imagined as geometrically thickening the quantum code complex. In this second
‘height choice’ step, we are choosing a coordinate along that interval at
which to attach all of the 2-cells represented by basis elements of
$\mathbb{F}_{2}^{N_{Z}}$, rather than attaching them at every
coordinate/height..

After the choice of heights is made, the Z - stabilisers in
$\mathbb{F}_{2}^{N_{Z}}\otimes\mathbb{F}_{2}^{l}$ that do act on a qubit
$x_{a}\otimes w_{k}$ in $\mathbb{F}_{2}^{N}\otimes\mathbb{F}_{2}^{l}$ are
exactly those from the linear combination of basis elements
$H_{Z}(x_{a})\otimes w_{k}$ that are kept, rather than removed. Hastings shows
in both [28] and [1] that it is possible to take a large enough $l$, and make
a particular height choice, such that the $q_{Z}$ resulting from this
procedure is constant. Indeed, Hastings gives the following lemma.

######  Lemma 2.5 (Lemmas 2 and 4 of [1]).

Let parameters with and without a tilde be respectively those of the code
after and before “thickening and choosing heights”. Then, for any
$\epsilon>0$, one may take
$l=\Theta\left(q_{Z}^{1+\epsilon}\min(q_{Z}w_{Z},N)^{\mathcal{O}(\epsilon)}\right)$
and then there is a choice of heights such that

  1. 1.

$\tilde{N}=Nl+N_{X}(l-1)$, $\tilde{N}_{X}=N_{X}l$,
$\tilde{N}_{Z}=N_{Z}+N(l-1)$.

  2. 2.

$\tilde{K}=K$.

  3. 3.

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

  4. 4.

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

  5. 5.

$\tilde{q}_{Z}=\max\left(\mathcal{O}(1),w_{X}\right)$.

  6. 6.

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

  7. 7.

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

  8. 8.

$\tilde{d}_{X}=ld_{X}$.

As for the soundness, Hastings analyses the thickening portion only in [28].
We also note that, since thickening is exactly distance balancing with the
repetition code, the following lemma can also be seen as a special case of our
previous result [26], which applies to distance balancing with any classical
code.

######  Lemma 2.6 (Lemma 7 of [28]).

Let parameters with and without a prime be respectively those of the code
after and before thickening (only). Then,

  1. 1.

$\rho_{Z}^{\prime}\geq\frac{N^{\prime}}{N_{X}^{\prime}}\min\left(\frac{N_{X}\rho_{Z}}{N},1\right)\frac{1}{l}$.

  2. 2.

$\rho_{X}^{\prime}\geq\frac{N^{\prime}}{N_{Z}^{\prime}}\min\left(\frac{N_{Z}\rho_{X}}{N},1\right)\frac{1}{l}$.

where $N^{\prime}=Nl+N_{X}(l-1)$, $N_{X}^{\prime}=N_{X}l$ and
$N_{Z}^{\prime}=N_{Z}l+N(l-1)$. Note then that under the reasonable
assumptions that $N=\Theta\left(N_{X}\right)=\Theta\left(N_{Z}\right)$ and
$\rho_{Z}$, $\rho_{X}=\mathcal{O}(1)$, we have
$\rho_{Z}^{\prime}=\Omega\left(\frac{\rho_{Z}}{l}\right)$ and
$\rho_{X}^{\prime}=\Omega\left(\frac{\rho_{X}}{l}\right)$.

The analysis of the soundness of the code under the “choosing heights” step
can be found in Section 3.2.

####  2.4.4 Coning

The coning construction is introduced in [1] and forms the primary technical
contribution of that paper. This is the last of the four constructions and can
reduce $w_{Z}$ to constant, while preserving constant $q_{X}$, $w_{X}$ and
$q_{Z}$. The soundness of this construction is not analysed prior to the
present work: this analysis will be performed in Section 3.3. The reader may
find figures 3 to 6 in that section helpful for the understanding of the
exposition in this section.

Hastings gives the coning construction for all quantum CSS codes, but gives
the construction for “reasonable” and “unreasonable” codes (to be defined)
separately. The construction is most simple in the case of reasonable codes,
and these are the only codes that we will consider, although this is not a
major restriction. A code is called “reasonable” if there is no Z - logical
operator whose support is contained entirely within the support of some Z -
stabiliser. Therefore, any code whose Z - distance is at least equal to
$w_{Z}$ is reasonable. Any reasonable code has the following property:

######  Claim 2.1.

For a reasonable code, any Z - operator which is supported only on a subset of
the support of one of the Z - stabilisers, and commutes with all the X -
stabilisers, is a member of the stabiliser group141414We recall the difference
between a “stabiliser” and a “member of the stabiliser group”, as defined in
Section 2.1..

The proof of this is immediate, because any Z - operator commuting with all X
- stabilisers must be a Z - logical operator, or a member of the stabiliser
group, by definition.

As well as only considering reasonable codes, for the sake of simplicity in
our soundness proofs, we will present a slightly abridged version of Hastings’
coning construction in which there are no “direct Z - stabilisers” (to use the
language of [1]). Practically, what this means, is that we work with a “worst-
case scenario” in which we weight reduce all Z - stabilisers. In a specific
use-case, where there are only a few, or one, high weight Z - stabilisers
requiring weight reduction, an analysis more specific to that particular case
would likely yield better bounds; see the original construction in [1] for
this. We will attempt to keep our notation and language as similar as possible
to that paper for the sake of comparability.

To perform the coning construction, we must first start by defining new
“auxiliary” chain complexes that will ultimately allow us to “induce” the
effect of the high weight Z - stabilisers by only using constant weight Z -
stabilisers. Let us start by defining $N_{Z}$ two-term chain complexes,
$\left(\mathcal{B}_{i}\right)_{i=1}^{N_{Z}}$, which we will say each have
1-cells and 0-cells. For each Z - stabiliser of the original code, $C$, denote
the set of qubits on which that Z - stabiliser acts as $Q_{i}$. The 1-cells of
$\mathcal{B}_{i}$ are then defined to be $Q_{i}$ and the space they span is
denoted $\mathcal{Q}_{i}$, i.e.
$\left(\mathcal{B}_{i}\right)_{1}=\mathcal{Q}_{i}$, where all our vector
spaces are over the binary field.

Consider now, for each $i$, the set $S_{i}$, of X - stabilisers with some
support (not necessarily their whole support) on $Q_{i}$. By assumption on
commutativity, each element of $S_{i}$ must have even support on $Q_{i}$.
Therefore, for each stabiliser $S\in S_{i}$, we can choose some pairing of the
qubits in $Q_{i}$ on which it acts. Define the 0-cells in $\mathcal{B}_{i}$ to
be the set of tuples $(S,j)$ such that $S\in S_{i}$ and $j$ is a pair of
qubits in $Q_{i}$ on which $S$ acts. We will denote the set of 0-cells of
$\mathcal{B}_{i}$ by $X_{i}$ and the binary vector space they span as
$\mathcal{X}_{i}$ $\left(=\left(\mathcal{B}_{i}\right)_{0}\right)$. The
boundary operator of the complex going from $\left(\mathcal{B}_{i}\right)_{1}$
to $\left(\mathcal{B}_{i}\right)_{0}$ is then the obvious one: the boundary of
a qubit in $\left(\mathcal{B}_{i}\right)_{1}$ is then given by all the tuples
$(S,j)$ for which the given qubit is in the pair $j$. Notice that this means
that the size of the coboundary of any 0-cell is equal to 2.

We will now define a further chain complex, $\overline{\mathcal{B}_{i}}$, from
each $\mathcal{B}_{i}$. $\overline{\mathcal{B}_{i}}$ will be a 3-term chain
complex, considered to have 1-cells, 0-cells and -1-cells. In
$\overline{\mathcal{B}_{i}}$, the 1-cells, 0-cells and the boundary operator
going between them will be identical to those of $\mathcal{B}_{i}$. We add in
-1-cells to make $\overline{\mathcal{B}_{i}}$, as well as a boundary operator
going from the 0-cells to the -1-cells. The purpose of this is to construct a
chain complex, $\overline{\mathcal{B}_{i}}$, which has trivial zeroth
homology.

Let us see how to do this. First observe the following. Given that the
coboundary of any 0-cell in $\mathcal{B}_{i}$ has size 2, we can define a
graph $G_{i}$. This graph will have vertices identified with the 1-cells of
$\mathcal{B}_{i}$ and edges identified with the 0-cells of $\mathcal{B}_{i}$.
An edge will then join the two 1-cells which it has in its coboundary. With
this, we observe that the elements of zeroth cohomology in $\mathcal{B}_{i}$
151515By an element of zeroth cohomology in $\mathcal{B}_{i}$, we mean a co-
closed 0-chain. then correspond exactly to closed edge chains in $G_{i}$.
Employing the decongestion lemma [31], Hastings then argues that a basis of
simple cycles can be found for these closed edge chains. The “weight” of one
of these simple cycles is the number of edges that it contains; the sum of the
weights of the elements of this basis turns out to be
$\mathcal{O}\left(\left|Q_{i}\right|\log\left|Q_{i}\right|\right)$, noting
that the graph has $\left|Q_{i}\right|$ vertices. Further, it turns out that
each edge appears at most $\mathcal{O}(\log\left|Q_{i}\right|)$ times in the
basis.

We may then construct $\overline{\mathcal{B}_{i}}$ by adding a set of -1-cells
given by this basis. The coboundary of any of these -1-cells is given by the
set of edges in that simple cycle (recalling that 0-cells correspond to
edges). The set of -1-cells is denoted $R_{i}$ and the binary vector space
which they span is denoted $\mathcal{R}_{i}$
$\left(=\left(\overline{\mathcal{B}_{i}}\right)_{-1}\right)$.
$\overline{\mathcal{B}_{i}}$ is constructed to have trivial zeroth cohomology,
because any co-closed 0-chain corresponds to a closed edge chain in the graph
$G_{i}$, which then can be written as some combination of simple cycles,
meaning that the co-closed 0-chain is also a 0-coboundary. Because
$\overline{\mathcal{B}_{i}}$ has trivial zeroth cohomology, it has trivial
zeroth homology.

Adding these -1-cells to form $\overline{\mathcal{B}_{i}}$ admits a
geometrical interpretation. As explained, the complex $\mathcal{B}_{i}$ can be
thought of geometrically as the graph $G_{i}$. Adding these simple cycles as
-1-cells is then like geometrically adding 2-discs to the graph $G_{i}$ to
form a complex $\mathcal{S}_{i}$. This is potentially a little confusing as
the vertices, edges and discs in $\mathcal{S}_{i}$ are respectively 0-, 1- and
2-dimensional geometrical objects, but correspond to 1-, 0-, and -1-cells in
$\overline{\mathcal{B}_{i}}$; nevertheless, the geometrical picture will be
useful.

From here, we may define the “cone code”, $C_{cone}$. This will be a code that
has the high weight Z - stabilisers induced by low weight Z - stabilisers, and
will have all of the old X - stabilisers and qubits, but will now have
additional qubits and X - stabilisers. Unfortunately, these added X -
stabilisers may have high weight and, further, the new qubits may be acted on
by a large (non-constant) number of new X - stabilisers. Fortunately, we will
display a remedy for this by reducing the cone code to form the “reduced cone
code”.

The cone code has spaces corresponding to Z - stabilisers, qubits and X -
stabilisers respectively as follows:

$\displaystyle\left(\mathcal{C}_{cone}\right)_{2}$
$\displaystyle=\bigoplus_{i=1}^{N_{Z}}\mathcal{Q}_{i}$ (23)
$\displaystyle\left(\mathcal{C}_{cone}\right)_{1}$
$\displaystyle=\mathcal{C}_{1}\oplus\left(\bigoplus_{i=1}^{N_{Z}}\mathcal{X}_{i}\right)$
(24) $\displaystyle\left(\mathcal{C}_{cone}\right)_{0}$
$\displaystyle=\mathcal{C}_{0}\oplus\left(\bigoplus_{i=1}^{N_{Z}}\mathcal{R}_{i}\right)$
(25)

where $\mathcal{C}_{1}$ and $\mathcal{C}_{0}$ are the spaces of qubits and X -
stabilisers of the original code, respectively. We may then define the
boundary maps of the cone code by defining maps between the spaces
$\mathcal{Q}_{i}$, $\mathcal{C}_{1}$, $\mathcal{X}_{i}$, $\mathcal{C}_{0}$ and
$\mathcal{R}_{i}$, and then the boundary maps follow as usual by summing
images in the same space. The chain complex of the cone code is shown in
Figure 3 in Section 3.3. There are maps as follows:

  1. 1.

There is a map from $\mathcal{Q}_{i}$ to $\mathcal{X}_{i}$ for each $i$ as
inherited from $\overline{\mathcal{B}_{i}}$, i.e.
$\partial_{1}^{\overline{\mathcal{B}_{i}}}$.

  2. 2.

There is a map from $\mathcal{X}_{i}$ to $\mathcal{R}_{i}$ for each $i$ as
inherited from $\overline{\mathcal{B}_{i}}$, i.e.
$\partial_{0}^{\overline{\mathcal{B}_{i}}}$.

  3. 3.

There is a map from $\mathcal{C}_{1}$ to $\mathcal{C}_{0}$ as inherited from
the original code $C$, i.e. $H_{X}$.

  4. 4.

There is the obvious projection map from $\mathcal{Q}_{i}$ to
$\mathcal{C}_{1}$ for each $i$ (any qubit $q\in\mathcal{Q}_{i}$ is mapped to
$q\in\mathcal{C}_{1}$), denoted $\pi_{q}^{(i)}$.

  5. 5.

There is the obvious projection map from $\mathcal{X}_{i}$ to
$\mathcal{C}_{0}$ for each $i$ (any tuple $(S,j)$ is mapped to
$S\in\mathcal{C}_{0}$), denoted $\pi_{X}^{(i)}$.

The boundary maps of the cone code, $\partial_{i}^{C_{cone}}$, are formed from
these maps. At this point, the cone code does have the action of the high
weight Z - stabilisers induced by low weight Z - stabilisers, but now, as
mentioned, there are two problems. First, X - stabilisers in $\mathcal{R}_{i}$
may act on up to $\left|Q_{i}\right|$ qubits in $\mathcal{X}_{i}$, making them
high weight stabilisers. Second, qubits in $\mathcal{X}_{i}$ may be acted on
by up to $\mathcal{O}(\log\left|Q_{i}\right|)$ stabilisers in
$\mathcal{R}_{i}$, meaning that they are potentially acted on by a non-
constant number of X - stabilisers. It is possible to “reduce the cone code”
to solve both of these problems. The second problem has an easy solution, and
we solve this one first. The solution is simply to thicken and choose heights
dually, to reduce $q_{X}$ (where we only need to choose heights for the
stabilisers coming from $\mathcal{R}_{i}$, not $\mathcal{C}_{0}$). This
procedure is described (non-dually, for the reduction of $q_{Z}$) in Section
2.4.3. Hastings argues that it is possible that for any $\epsilon>0$, one may
thicken by an amount
$l=\Theta\left(\log\left(w_{Z}\right)^{2+2\epsilon}w_{Z}^{\epsilon}\right)$
and choose heights to make it such that at most one stabiliser in
$\mathcal{R}_{i}\otimes\mathcal{E}_{0}$ is attached to any given qubit in
$\mathcal{X}_{i}\otimes\mathcal{E}_{0}$. The resulting chain complex is
depicted in Figure 4.

All that is left to address is some potentially high weight X - stabilisers,
coming from $\mathcal{R}_{i}$, each attached at one height. We may think of
these geometrically as potentially high weight discs, attached to a large
number of edges coming from $\mathcal{X}_{i}$. The idea is to “cellulate”
these discs, adding edges going across the disc, and potentially vertices in
the disc, to break up the large disc into many smaller faces, thus re-
introducing a constant $w_{X}$. There are many ways this cellulation could be
done. One example given by Hastings is, if the vertices within a disc are
labelled $0,...,w-1$, one may add an edge between vertices $j$ and $w-j$ for
all $j$ with $0<j<w-j-1$. For this cellulation, no additional vertices need to
be added. This particular cellulation will be important to us, and so it is
depicted in Figure 5, and the chain complex that results is depicted in Figure
6. Note that every disc must be cellulated and they are each cellulated at
whatever height they are attached, thus the edges (and vertices if they are
added) are only added at the heights at which they are needed. The end result
is the “reduced cone code”.

From this construction, we have the following:

######  Lemma 2.7 (Adapted161616Note that we have the lemma in this form
because we do not take any direct stabilisers, as mentioned. Furthermore,
Hastings gives $\tilde{d}_{Z}$ in terms of a parameter $\lambda$, for which we
take a trivial lower bound $\frac{1}{w_{Z}}$. from Lemma 8 of [1]).

Let parameters with and without a tilde be respectively those of the reduced
cone code and the code pre-coning. Then, for any $\epsilon>0$, letting
$l=\Theta\left(\log\left(w_{Z}\right)^{2+2\epsilon}w_{Z}^{\epsilon}\right)$,
we have

  1. 1.

$\tilde{N}=\mathcal{O}\left(l\left(N+w_{Z}q_{X}w_{X}N_{Z}\right)\right)$,
$\tilde{N}_{X}=\mathcal{O}\left(l\left(N+w_{Z}q_{X}w_{X}N_{Z}+N_{X}\right)\right)$,
$\tilde{N}_{Z}=\mathcal{O}(N_{Z}w_{Z}l)$.

  2. 2.

$\tilde{K}=K$.

  3. 3.

$\tilde{q}_{X}=\max\left(q_{X}+\mathcal{O}(1),\mathcal{O}(1)\right)$.

  4. 4.

$\tilde{w}_{X}=\max\left(\mathcal{O}\left(w_{X}^{2}q_{Z}\right),\mathcal{O}(1)\right)$.

  5. 5.

$\tilde{q}_{Z}=\max\left(q_{Z},\mathcal{O}(1)\right)$.

  6. 6.

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

  7. 7.

$\tilde{d}_{Z}\geq\frac{d_{Z}l}{w_{Z}}$.

  8. 8.

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

The analysis of the soundness of this construction, under the assumption of
the code being reasonable, will be performed in Section 3.3. We also mention
that in order to draw our conclusions on the soundness of the code under
coning, we take a larger value of $l$ here,
$l=\Theta\left(w_{Z}\log(w_{Z})q_{X}\right)$, where these un-decorated
parameters are those of the code pre-coning, as is explained in Section 3.3.2.

##  3 Quantum Soundness Under Weight Reduction

Our objective is to analyse the soundness of a quantum code under each of the
weight reduction constructions, as necessary, so that we may obtain a lower
bound on the soundness of a quantum code after a full weight reduction in
terms of its soundness before weight reduction. A full analysis of a weight
reduction of a qLTC will be presented in Section 3.4.

It will be common to represent X and Z - operators by bit strings in the
obvious way: a Z - operator (for example) on $\tilde{N}$ qubits may be
represented by a bit string $u\in\mathbb{F}_{2}^{\tilde{N}}$, where there is a
Pauli Z in the Z - operator exactly wherever $u$ has a 1. With this
equivalence, it makes sense to conflate our thinking about $u$ as a bit string
and as an operator, often conflating the bits on which the bit string is
defined with the qubits on which the operator is defined. We then refer to $u$
as being “in a given quantum code” if it commutes with all the X - stabilisers
of that quantum code i.e. it is in the classical code defined by the X -
stabilisers of that code. We will also talk about “putting u in a quantum
code” to refer to the process of flipping bits in $u$ such that it is “in the
quantum code”. We will often specify a process by which this will occur. For
example, many of our soundness proofs will go via a line of reasoning as
follows:

  1. 1.

Specify a method by which we put a bit string in a post-construction code, for
example the post-copying code. The number of bits flipped in this method
provides an upper bound on the distance of $u$ from the post-construction
code.

  2. 2.

We will then argue that flipping this many bits in $u$ implies that a certain
number of stabilisers must have been violated by $u$ in the first place, from
which we can deduce soundness.

The equivalent of all of the above will be true for X - operators also. Note
that the soundness in question is deduced because in our definition of
soundness, $\frac{|Hx|}{m}\geq\rho\frac{d(x,\ker H)}{n}$, $|Hx|$ translates to
a number of violated stabilisers of a given type.

Finally, note that we give our soundness lower bounds in full for the sake of
giving the greatest detail, but we say that this is at risk of hiding the most
important features of each bound. In particular, the presence of code lengths
and numbers of stabilisers often adds greater detail than will be needed -
generally $N$, $N_{X}$ and $N_{Z}$ will scale at the same rate, or nearly at
the same rate. Assumptions like this, as well as the reasonable assumption
that the soundness is at most a constant at all stages of the construction,
will bring out the important features of the lower bound, which is how many
factors of each weight the given soundness is decreased by in some step of the
construction.

###  3.1 Copying

We now analyse the soundness of a quantum code under the copying construction
of Section 2.4.1. Let us recall here that $\rho_{X}$ is the soundness of the
classical code associated with the Z - stabilisers and $\rho_{Z}$ is the
soundness of the classical code associated with the X - stabilisers.

######  Lemma 3.1.

Let parameters with and without a tilde be those of the code after and before
copying respectively. Then

$\tilde{\rho}_{Z}\geq\frac{\tilde{N}}{\tilde{N}_{X}}\frac{\rho_{Z}}{q_{X}\rho_{Z}+\frac{N}{N_{X}}q_{X}\left(q_{X}^{2}+1\right)}.$
(26)

###### Proof.

Let us denote the quantum code before and after copying as $C$ and $\tilde{C}$
respectively. Consider a Z - operator on the new set of qubits represented by
some bit string $u\in\mathbb{F}_{2}^{\tilde{N}}$. We label the $\tilde{N}$
physical qubits of the new code as $(q,j)$ where $q$ labels a qubit in $C$ and
$j\in\\{1,...,q_{X}\\}$. For a given $q$, we refer to all the qubits $(q,j)$
as a block of qubits in $\tilde{C}$. We can then label blocks of qubits in
$\tilde{C}$ by $q$ i.e. the same set of labels as those that label qubits in
$C$.

We say that $u$ is uniform on a given block $q$ if

$u(q,j)=1\text{ for some $j$ }\implies u(q,i)=1\text{ for all
}i\in\\{1,...,q_{X}\\}$ (27)

i.e. it is either all zeros or all ones on that block. Then, in order for a
bit string $u$ to be in the code $\tilde{C}$, it is necessary that it is
uniform on every block. This is because it must commute with all the
stabilisers of the form $X_{(q,i)}X_{(q,i+1)}$. Given a bit string $u$ that is
uniform on every block, we may define a bit string
$\hat{u}\in\mathbb{F}_{2}^{N}$, where $\hat{u}(q)=u(q,j)$. Then $u$ is in the
code if and only if it is uniform on every block and the corresponding
$\hat{u}$ is in the code $C$ (the second condition ensures commutativity with
the encoded stabilisers of $C$).

We can put $u$ into the code $\tilde{C}$ as follows. For every block $q$ on
which $u$ is not uniform, set $u(q,k)=1$ for all $k$ if at least half of the
bits in that block are 1, and set $u(q,k)=0$ for all $k$ otherwise. In doing
this, suppose that $f$ bits are flipped. The resulting bit string is uniform
on every block and so we may define a corresponding $\hat{u}$. It is then
possible to put $\hat{u}$ in the code $C$ by flipping as few bits as are
needed. This entails flipping $d(\hat{u},\ker H_{X})$ bits in $\hat{u}$, where
$\ker H_{X}$ refers to the classical code defined by the X - stabilisers of
$C$. We may then finish putting $u$ in the code by flipping, for every bit $q$
in $\hat{u}$ that gets flipped, all the bits $(q,i)$ in $u$ for every $i$.
Denoting also the classical code defined by the X - stabilisers of $\tilde{C}$
as $\ker\tilde{H}_{X}$, we then have

$d(u,\ker\tilde{H}_{X})\leq f+q_{X}d(\hat{u},\ker H_{X}).$ (28)

Let us consider two cases. First, consider the case for which $f\geq\alpha
q_{X}d(\hat{u},\ker H_{X})$, for some positive number $\alpha$ to be later
determined. Then

$d(u,\ker\tilde{H}_{X})\leq f\left(\frac{\alpha+1}{\alpha}\right).$ (29)

When we flip the $f$ bits in $u$, there must be bits flipped in at least
$\frac{f}{q_{X}}$ blocks. If $u$ is non-uniform in a given block $q$, at least
one of the stabilisers of the form $X_{(q,i)}X_{(q,i+1)}$ is violated.
Therefore, $u$ violates at least

$\frac{f}{q_{X}}\geq\frac{\alpha}{\alpha+1}\frac{d(u,\ker\tilde{H}_{X})}{q_{X}}$
(30)

stabilisers. Now consider the case $f\leq\alpha q_{X}d(\hat{u},\ker H_{X})$,
for which we have

$d(u,\ker\tilde{H}_{X})\leq(1+\alpha)q_{X}d(\hat{u},\ker H_{X}).$ (31)

$\hat{u}$ is at a distance $d(\hat{u},\ker H_{X})$ from $\ker H_{X}$, and
therefore violates at least $\frac{\rho_{Z}N_{X}}{N}d(\hat{u},\ker H_{X})$ X -
stabilisers of $C$.

Because there are $f$ bits flipped in $u$ in the first stage of putting $u$ in
the code, there are bits flipped in at most $f$ blocks of $u$. This means that
$u$ is non-uniform in at most $f$ blocks. Thus there are at least $N-f$
uniform blocks in $u$. On any uniform block $q$, we can deduce the value of
$\hat{u}(q)$. Consider the set of such qubits in $C$ for which $u$ is uniform
on the corresponding block. Call this set $S$, where we know that $|S|\geq
N-f$. There are at most $q_{X}\left(N-|S|\right)$ X - stabilisers of $C$
supported anywhere outside of $S$, and therefore at least
$N_{X}-q_{X}\left(N-|S|\right)\geq N_{X}-q_{X}f$ X - stabilisers of $C$
supported entirely within $S$. There are therefore at least

$\frac{\rho_{Z}N_{X}}{N}d(\hat{u},\ker
H_{X})-q_{X}f\geq\left(\frac{\rho_{Z}N_{X}}{N}-q_{X}^{2}\alpha\right)d(\hat{u},\ker
H_{X})$ (32)

X - stabilisers of $C$ that are violated by $\hat{u}$ and supported entirely
within $S$. For every such X - stabiliser of $C$, the corresponding encoded X
- stabiliser in $\tilde{C}$ is violated by $u$. As such, we know that at least

$\left(\frac{\rho_{Z}N_{X}}{N}-q_{X}^{2}\alpha\right)d(\hat{u},\ker
H_{X})\geq\left(\frac{\rho_{Z}N_{X}}{N}-q_{X}^{2}\alpha\right)\frac{d(u,\ker\tilde{H}_{X})}{q_{X}(1+\alpha)}$
(33)

X - stabilisers in $\tilde{C}$ are violated by $u$. We now choose $\alpha$ to
make the right-hand sides of Equations (30) and (33) equal. This is
$\alpha=\frac{\rho_{Z}N_{X}}{N\left(q_{X}^{2}+1\right)}$. From this, we have
that at least

$\frac{\rho_{Z}N_{X}}{q_{X}\rho_{Z}N_{X}+Nq_{X}\left(q_{X}^{2}+1\right)}d(u,\ker\tilde{H}_{X})$
(34)

stabilisers in $\tilde{C}$ are violated in both cases, from which we deduce
the required soundness. ∎

######  Lemma 3.2.

Let parameters with and without a tilde be those of the code after and before
copying respectively. Then

$\tilde{\rho}_{X}\geq q_{X}\rho_{X}.$ (35)

###### Proof.

We use the same language and notation as in the previous lemma of blocks of
qubits etc. Consider an X - operator on the new set of qubits represented by
some bit string $u\in\mathbb{F}_{2}^{\tilde{N}}$. Without loss of generality,
$u$ is supported at most once on each block. The reason for this is that
$\tilde{C}$ has stabilisers of the form $X_{(q,i)}X_{(q,i+1)}$. For some $q$,
the bit strings corresponding to these stabilisers for this $q$ may be added
together to give any bit string of even weight on this block. Adding such a
bit string to $u$ within each block $q$ can reduce the support of $u$ within
that block to at most one point.

From $u$, we may define a corresponding bit string
$\hat{u}\in\mathbb{F}_{2}^{N}$. If $u$ is supported in some place on a block
$q$, then we set $\hat{u}(q)=1$. Otherwise, $\hat{u}(q)=0$. Then, $u$ is in
the code $\tilde{C}$ if and only if the corresponding $\hat{u}$ is in the code
$C$. From this, we may put $\hat{u}$ in the code $C$ by flipping as few bits
in it as are necessary. This will be $d(\hat{u},\ker H_{Z})$, where $\ker
H_{Z}$ denotes the classical code defined by the Z - stabilisers of $C$. We
may then put $u$ in the code $\tilde{C}$ following the way that $\hat{u}$ is
put in the code $C$: if a bit $q$ in $\hat{u}$ is flipped from 1 to 0, then
flip the bit that is set to 1 for $u$ in the block $q$ to 0. If a bit $q$ in
$\hat{u}$ is flipped from 0 to 1, flip any bit in $u$ in the block $q$ to 1.
Thus, $d(u,\ker\tilde{H}_{Z})\leq d(\hat{u},\ker H_{Z})$.

$\hat{u}$ violates at least $\frac{\rho_{X}N_{Z}}{N}d(\hat{u},\ker H_{Z})$ Z -
stabilisers in $C$. For every Z - stabiliser that $\hat{u}$ violates in $C$,
$u$ violates one in $\tilde{C}$. Thus, $u$ violates at least
$\frac{\rho_{X}N_{Z}}{N}d(u,\ker\tilde{H}_{Z})$ Z - stabilisers in
$\tilde{C}$, from which we deduce the required soundness using
$\tilde{N}=q_{X}N$ and $\tilde{N}_{Z}=N_{Z}$. ∎

###  3.2 Thickening and Choosing Heights

Our objective now is to have an analysis of soundness under the full
“Thickening and Choosing Heights” construction used to reduce $q_{Z}$. We
recall from Section 2.4.3 that the soundness of a quantum code under the
thickening portion is already known. It is therefore left for us to analyse
the soundness of the quantum code under the choice of heights. We recall that
our original quantum code chain complex
$C=\left(\mathbb{F}_{2}^{N_{Z}}\overset{H_{Z}^{T}}{\longrightarrow}\mathbb{F}_{2}^{N}\overset{H_{X}}{\longrightarrow}\mathbb{F}_{2}^{N_{X}}\right)$
becomes the chain complex
$\mathcal{C}_{2}^{\prime}\overset{\partial_{2}}{\longrightarrow}\mathcal{C}_{1}^{\prime}\overset{\partial_{1}}{\longrightarrow}\mathcal{C}_{0}^{\prime}$
during thickening, as shown in Figure 2, where $H$ is the usual parity-check
matrix associated with a length $l$ classical repetition code, as shown in
Equation (22). We then, in the height-choice step, for each basis element
$v\in\mathbb{F}_{2}^{N_{Z}}$, pick one $k\in\\{1,...,l\\}$, and remove all
basis elements $v\otimes w_{k^{\prime}}$ (where $\left(w_{i}\right)_{i=1}^{l}$
forms the standard basis for $\mathbb{F}_{2}^{l}$) in
$\mathbb{F}_{2}^{N_{Z}}\otimes\mathbb{F}_{2}^{l}$ for which $k^{\prime}\neq
k$, but keeping $v\otimes w_{k}$. We therefore keep all the qubits and X -
stabilisers of the thickened code, but keep only a subset of the Z -
stabilisers. Therefore, we have immediately that

######  Fact 3.1.

$\tilde{\rho}_{Z}=\rho^{\prime}_{Z}$, where $\tilde{\rho}_{Z}$ refers to the
soundness of the Z - operators of the code after thickening and choosing
heights and $\rho^{\prime}_{Z}$ refers to the same for the code after
thickening but before choosing heights.

$\mathbb{F}_{2}^{N_{Z}}\otimes\mathbb{F}_{2}^{l-1}$$\mathbb{F}_{2}^{N}\otimes\mathbb{F}_{2}^{l-1}$$\mathbb{F}_{2}^{N_{X}}\otimes\mathbb{F}_{2}^{l-1}$$\mathbb{F}_{2}^{N_{X}}\otimes\mathbb{F}_{2}^{l}$$\mathbb{F}_{2}^{N_{Z}}\otimes\mathbb{F}_{2}^{l}$$\mathbb{F}_{2}^{N}\otimes\mathbb{F}_{2}^{l}$$\oplus$$\oplus$$H_{Z}^{T}\otimes
I$$I\otimes H^{T}$$H_{Z}^{T}\otimes I$$H_{X}\otimes I$$I\otimes
H^{T}$$I\otimes H^{T}$$H_{X}\otimes
I$$\mathcal{C}^{\prime}_{3}$$\mathcal{C}^{\prime}_{2}$$\mathcal{C}^{\prime}_{1}$$\mathcal{C}^{\prime}_{0}$$\partial_{3}$$\partial_{2}$$\partial_{1}$
Figure 2:

We now turn to the soundness of the X - operators.

######  Lemma 3.3.

Let parameters with and without a tilde refer to those of the code after and
before “thickening and choosing heights” respectively. Let parameters with a
prime refer to those of the code after thickening but before choosing heights.
Then

$\tilde{\rho}_{X}\geq\frac{N_{Z}^{\prime}}{\tilde{N}_{Z}}\frac{\rho_{X}^{\prime}}{1+w_{Z}q_{Z}l}.$
(36)

and since $\tilde{N}_{Z}\leq N^{\prime}_{Z}$, we have
$\tilde{\rho}_{X}\geq\Omega\left(\frac{\rho^{\prime}_{X}}{w_{Z}q_{Z}l}\right)$.

###### Proof.

Even though some Z - stabilisers are removed during the choosing of heights,
it turns out that the thickened code, $C^{\prime}$, and the code after
thickening and choosing heights, $\tilde{C}$, have the same Z - stabiliser
group. This fact was used by Hastings to determine the dimension and the
distance of $\tilde{C}$, and we use it here to determine the soundness. The
idea is as follows. Consider a stabiliser that is removed from the list of
stabilisers of $C^{\prime}$ when forming $\tilde{C}$, $v\otimes w_{m}$. We
will show that this is still in the Z - stabiliser group of $\tilde{C}$, even
if it is not now a “stabiliser” (i.e. not in the designated list of
stabilisers). Indeed, consider an element $v\otimes
p\in\mathcal{C}^{\prime}_{3}=\mathbb{F}_{2}^{N_{Z}}\otimes\mathbb{F}_{2}^{l-1}$,
where $p$ is of the form $(0,0,...,0,0,1,1,...,1,1,0,0,...,0,0)$ and satisfies
$H^{T}(p)=w_{k}+w_{m}$171717For example, if $m>k$ then $p$ has 1’s from the
$k$’th to the $(m-1)$’th place.. We then have

$\partial_{3}(v\otimes p)=\left(v\otimes w_{k}+v\otimes
w_{m},H_{Z}^{T}(v)\otimes p\right).$ (37)

All of the basis elements in this linear combination represent Z - stabilisers
in the thickened code. Note that there are two basis elements within $v\otimes
w_{k}+v\otimes w_{m}$ but generally more than two in $H_{Z}^{T}(v)\otimes p$.
Furthermore, the Z - stabiliser $v\otimes w_{k}$ is kept during the choosing
of heights, as are all the Z - stabilisers within the linear combination of
basis elements $H_{Z}^{T}(v)\otimes p$. This implies that the Z - stabiliser
given by $v\otimes w_{m}$ is still in the stabiliser group after choosing
heights because $\partial_{2}\partial_{3}(v\otimes p)=0$ and so

$\partial_{2}\left((v\otimes w_{m},0)\right)=\partial_{2}\left(v\otimes
w_{k},H_{Z}^{T}(v)\otimes p\right).$ (38)

Thus, the Z - stabiliser corresponding to $v\otimes w_{m}$ is the same as the
product of the Z - stabilisers corresponding to $v\otimes w_{k}$ and all those
in the linear combination $H_{Z}^{T}(v)\otimes p$. Thus, $\ker H_{Z}^{\prime}$
and $\ker\tilde{H}_{Z}$ are the same spaces, where the former refers to the
classical code defined by the Z - stabilisers of the code after thickening
(only), and the latter refers to the same thing after choosing heights.

We may now consider an X - operator represented by some bit string
$u\in\mathbb{F}_{2}^{\tilde{N}}$ i.e. some physical X - operator on the code
after choosing heights. We may just as well consider this to be some physical
X - operator on the code after thickening and indeed $d(u,\ker
H_{Z}^{\prime})=d(u,\ker\tilde{H}_{Z})$ because, again, $\ker
H_{Z}^{\prime}=\ker\tilde{H}_{Z}$. In $C^{\prime}$, $u$ will violate at least

$\frac{N_{Z}^{\prime}}{N^{\prime}}\rho_{X}^{\prime}d(u,\ker H_{Z}^{\prime})$
(39)

Z - stabilisers. The question now is how many of these stabilisers are removed
when choosing heights. Consider a Z - stabiliser $v\otimes w_{m}$ that is
violated in $C^{\prime}$ but removed when forming $\tilde{C}$. At least one of
the stabilisers in the linear combination of basis elements $\left(v\otimes
w_{k},H_{Z}^{T}(v)\otimes p\right)$ must be violated, because the Z -
stabilizer corresponding to $v\otimes w_{m}$ is the product of the Z -
stabilizers corresponding to $\left(v\otimes w_{k},H_{Z}^{T}(v)\otimes
p\right)$, and the X - operator $u$ cannot anti-commute with a product of Z -
stabilisers without anti-commuting with at least one of them. This observation
will allow us to translate a number of violated stabilisers in $C^{\prime}$ to
a number of violated stabilisers in $\tilde{C}$, but there is one
complication. Given two stabilisers violated in $C^{\prime}$, $v_{1}\otimes
w_{m_{1}}$ and $v_{2}\otimes w_{m_{2}}$, but removed when forming $\tilde{C}$,
these two stabilisers may have some overlap in their linear combinations
$\left(v_{1}\otimes w_{k_{1}},H_{Z}^{T}\left(v_{1}\right)\otimes p_{1}\right)$
and $\left(v_{2}\otimes w_{k_{2}},H_{Z}^{T}\left(v_{2}\right)\otimes
p_{2}\right)$, and so we cannot necessarily conclude that for each stabiliser
violated in $C^{\prime}$ but removed when forming $\tilde{C}$, there is at
least one violated in $\tilde{C}$. We must adjust this argument as follows.

We first ask: when can there be overlap between the linear combinations
$\left(v_{1}\otimes w_{k_{1}},H_{Z}^{T}\left(v_{1}\right)\otimes p_{1}\right)$
and $\left(v_{2}\otimes w_{k_{2}},H_{Z}^{T}\left(v_{2}\right)\otimes
p_{2}\right)$? If $v_{1}=v_{2}$, then $v_{1}\otimes w_{k_{1}}=v_{2}\otimes
w_{k_{2}}$, and there is certainly overlap. Thus assume that $v_{1}\neq
v_{2}$. In this case, in order for there to be overlap between the two linear
combinations, there must be some overlap between $H_{Z}^{T}(v_{1})$ and
$H_{Z}^{T}(v_{2})$. Given a $v_{1}\in\mathbb{F}_{2}^{N_{Z}}$, there may be at
most $w_{Z}q_{Z}$ $v_{2}^{\prime}s$ such that $H_{Z}^{T}(v_{1})$ and
$H_{Z}^{T}(v_{2})$ have some overlap.

Thus, given a stabiliser $v_{1}\otimes w_{m_{1}}$ that is violated in
$C^{\prime}$ but removed when forming $\tilde{C}$, we may conclude that there
is some Z - stabiliser violated in $\tilde{C}$. Then, however, we exclude all
of the stabilisers $v_{2}\otimes w_{m_{2}}$ that are violated in $C^{\prime}$
but removed when forming $\tilde{C}$ that have some overlap in their linear
combination with $v_{1}\otimes w_{k_{1}}$. This means excluding at most
$w_{Z}q_{Z}l$ stabilisers. After this, we may look at the non-excluded
stabilisers of the form $v_{3}\otimes w_{m_{3}}$ that are violated in
$C^{\prime}$ but removed when forming $\tilde{C}$. Picking one of these, its
violation must imply the violation of some Z - stabiliser in $\tilde{C}$. We
then exclude all of the stabilisers that have some overlap in their linear
combination with $v_{1}\otimes w_{m_{1}}$ or $v_{3}\otimes w_{m_{3}}$, and
continue in this way. Ultimately, we may conclude that having a certain number
of stabilisers violated in $C^{\prime}$ that are removed when forming
$\tilde{C}$ implies the violation of at least a $\frac{1}{w_{Z}q_{Z}l}$
fraction of this many stabilisers in $\tilde{C}$.

To conclude the proof, let us say that the X - operator $u$ violates
$V_{1}+V_{2}$ Z - stabilisers in $C^{\prime}$, where $V_{1}$ is the number
that are removed when forming $\tilde{C}$ and $V_{2}$ is the number that are
kept. If $V_{1}\leq w_{Z}q_{Z}lV_{2}$, then the number of Z - stabilisers
violated in $\tilde{C}$ is at least

$V_{2}\geq\frac{V_{1}+V_{2}}{1+w_{Z}q_{Z}l}\geq\frac{N_{Z}^{\prime}}{N^{\prime}}\rho_{X}^{\prime}\frac{d(u,\ker
H_{Z}^{\prime})}{1+w_{Z}q_{Z}l}$ (40)

and we get the required soundness in this case. If instead $V_{1}\geq
w_{Z}q_{Z}lV_{2}$, then the number of Z - stabilisers violated in $\tilde{C}$
is at least

$\frac{V_{1}}{w_{Z}q_{Z}l}\geq\frac{V_{1}+V_{2}}{1+w_{Z}q_{Z}l}\geq\frac{N_{Z}^{\prime}}{N^{\prime}}\rho_{X}^{\prime}\frac{d(u,\ker
H_{Z}^{\prime})}{1+w_{Z}q_{Z}l}$ (41)

again giving the required soundness. ∎

###  3.3 Coning

We now provide a full analysis of soundness of a quantum code under the coning
construction, which is the construction used to reduce $w_{Z}$ while
preserving the constancy of all other parameters. This construction was
presented in Section 2.4.4. We will do this incrementally, first determining a
lower bound on the soundness of the cone code in terms of that of the code
pre-coning, and then determining a lower bound on the soundness of the reduced
cone code. We recall that the reduced cone code is formed from the cone code
first by (dually) thickening and choosing heights to reduce $q_{X}$, and then
by cellulating the added 2-discs. We recall that we have an analysis of the
soundness of a quantum code under the process of thickening and choosing
heights from Lemma 2.6 and from Section 3.2. It will therefore suffice to
analyse the soundness of the cone code, and then analyse the soundness under
the cellulation step. However, we mention that we will end up taking a larger
value of $l$ for the thickening and choosing heights here than the one used by
Hastings to reduce $q_{X}$ to a constant,
$l=\Theta\left(\log\left(w_{Z}\right)^{2+2\epsilon}w_{Z}^{\epsilon}\right)$,
as in Lemma 2.7. This will be for the benefit of our proof of soundness under
the cellulation step, as we will go on to explain.

####  3.3.1 Soundness of the Cone Code

######  Lemma 3.4.

Let parameters with and without a prime refer to those of the cone code and
the code pre-coning respectively. Then

$\rho^{\prime}_{Z}\geq\frac{N^{\prime}}{N_{X}^{\prime}}\frac{\rho_{Z}}{w_{Z}q_{X}w_{X}\rho_{Z}+\frac{N}{N_{X}}+w_{Z}q_{X}w_{X}\frac{N}{N_{X}}}.$
(42)

###### Proof.

For ease of reference, the structure of the chain complex of the cone code is
shown in Figure 3.

${\mathcal{Q}_{N_{Z}}}$${\mathcal{X}_{N_{Z}}}$${\mathcal{R}_{N_{Z}}}$${\oplus}$${\oplus}$${\oplus}$${\vdots}$${\vdots}$${\vdots}$${\oplus}$${\oplus}$${\oplus}$${\mathcal{Q}_{1}}$${\mathcal{X}_{1}}$${\mathcal{R}_{1}}$${\oplus}$${\oplus}$${\mathcal{C}_{1}}$${\mathcal{C}_{0}}$${\left(\mathcal{C}_{cone}\right)_{2}}$${\left(\mathcal{C}_{cone}\right)_{1}}$${\left(\mathcal{C}_{cone}\right)_{0}}$$\scriptstyle{\partial^{\overline{\mathcal{B}_{N_{Z}}}}_{1}}$$\scriptstyle{\pi_{q}^{(N_{Z})}}$$\scriptstyle{\partial^{\overline{\mathcal{B}_{N_{Z}}}}_{0}}$$\scriptstyle{\pi_{X}^{(N_{Z})}}$$\scriptstyle{\partial^{\overline{\mathcal{B}_{1}}}_{1}}$$\scriptstyle{\pi_{q}^{(1)}}$$\scriptstyle{\partial^{\overline{\mathcal{B}_{1}}}_{0}}$$\scriptstyle{\pi_{X}^{(1)}}$$\scriptstyle{H_{X}}$$\scriptstyle{\partial^{C_{cone}}_{2}}$$\scriptstyle{\partial^{C_{cone}}_{1}}$
Figure 3: The chain complex of the cone code. The spaces of the cone code,
$\left(\mathcal{C}_{cone}\right)_{i}$, can be read off by “direct summing
vertically”. The boundary maps can also be determined by reading off the maps
vertically and summing images in the same space.
$\partial_{1}^{\overline{\mathcal{B}_{i}}}$ and
$\partial_{0}^{\overline{\mathcal{B}_{i}}}$ are the boundary maps of the chain
complex $\overline{\mathcal{B}_{i}}$, while $H_{X}$ is a boundary map coming
from the chain complex of the pre-coning code. $\pi_{q}^{(i)}$ and
$\pi_{X}^{(i)}$ are the obvious projection maps.

Let us consider some physical Z - operator in the cone code, represented by
some bit string $u\in\left(\mathcal{C}_{cone}\right)_{1}$. Hereafter, we will
refer to the cone code as $C^{\prime}$, rather than $C_{cone}$, for brevity.
Let us write $u=(u_{1},u_{2})$ for $u_{1}\in\mathcal{C}_{1}$ and
$u_{2}=\bigoplus_{i=1}^{N_{Z}}u_{2}^{(i)}\in\bigoplus_{i=1}^{N_{Z}}\mathcal{X}_{i}$,
where $u_{2}^{(i)}\in\mathcal{X}_{i}$. For each $\overline{\mathcal{B}_{i}}$,
consider $d(u_{2}^{(i)},\ker\partial_{0}^{\overline{\mathcal{B}_{i}}})$.
$\exists$ $v_{2}^{(i)}\in\ker\partial_{0}^{\overline{\mathcal{B}_{i}}}$ such
that
$\left|u_{2}^{(i)}+v_{2}^{(i)}\right|=d(u_{2}^{(i)},\ker\partial_{0}^{\overline{\mathcal{B}_{i}}})$.
$\overline{\mathcal{B}_{i}}$ has trivial zero-th homology, and therefore
$v_{2}^{(i)}\in\operatorname{im}\partial_{1}^{\overline{\mathcal{B}_{i}}}$
i.e. $\exists$ $w_{2}^{(i)}\in\mathcal{Q}_{i}$ such that
$\partial_{1}^{\overline{\mathcal{B}_{i}}}w_{2}^{(i)}=v_{2}^{(i)}$. Adding the
Z - stabiliser corresponding to $\bigoplus_{i=1}^{N_{Z}}w_{2}^{(i)}$ then
shows us that without loss of generality, we may say that our Z - operator $u$
satisfies

$\left|u_{2}^{(i)}\right|=d(u_{2}^{(i)},\ker\partial_{0}^{\overline{\mathcal{B}_{i}}})$
(43)

and, in particular,
$u_{2}^{(i)}\in\ker\partial_{0}^{\overline{\mathcal{B}_{i}}}\iff
u_{2}^{(i)}=0$.

We may then put $u$ in the cone code as follows. Suppose that there are
exactly $f$ bits in $u_{2}$ set to 1. We flip all of these bits to 0. Then, we
flip the smallest number of bits in $u_{1}$ required to put it in $\ker
H_{X}$, which will be $d(u_{1},\ker H_{X})$ bits. The result will be in the
cone code. Therefore, we have

$d(u,\ker H^{\prime}_{X})\leq d(u_{1},\ker H_{X})+f$ (44)

where $H^{\prime}_{X}$ is the parity-check matrix associated with the X -
stabilisers of the cone code, i.e. $H^{\prime}_{X}=\partial_{1}^{C_{cone}}$.

Consider first the case that $f\leq\alpha d(u_{1},\ker H_{X})$ for some
positive number $\alpha$ to be determined. Then

$d(u,\ker H^{\prime}_{X})\leq(1+\alpha)d(u_{1},\ker H_{X}).$ (45)

$u_{1}$ violates at least $\rho_{Z}\frac{N_{X}}{N}d(u_{1},\ker H_{X})$ X -
stabilisers in the pre-coning code, $C$. Consider the $f$ bits that get
flipped from 1 to 0 in $u_{2}$ when we put $u$ in the code. Each of these bits
is in some set $X_{i}$ (the set of basis elements of $\mathcal{X}_{i}$) and is
labelled by some tuple $(T,j)$ for T some X - stabiliser of $C$ and j some
qubit pair. Consider the following subset, S, of the X - stabilisers of $C$:
an X - stabiliser, $T$, is in S if none of the $f$ bits in $u_{2}$ contain $T$
in their tuple. We have $|S|\geq N_{X}-f$ and then the number of X -
stabilisers of $C$ that are violated by $u_{1}$ and that are in S is at least

$\displaystyle\rho_{Z}\frac{N_{X}}{N}d(u_{1},\ker H_{X})-f$
$\displaystyle\geq\left(\rho_{Z}\frac{N_{X}}{N}-\alpha\right)d(u_{1},\ker
H_{X})$ (46)
$\displaystyle\geq\frac{1}{1+\alpha}\left(\rho_{Z}\frac{N_{X}}{N}-\alpha\right)d(u,\ker
H_{X}^{\prime}).$ (47)

At least this many X - stabilisers are violated by $u$ in the cone code,
because an X - stabiliser in $C$ violated by $u_{1}$ which is also in $S$ must
be violated by $u$ (as a basis element of $\mathcal{C}_{0}$ in the cone code).

Consider now the case where $f\geq\alpha d(u_{1},\ker H_{X})$. Then

$d(u,\ker H_{X}^{\prime})\leq f\left(\frac{1+\alpha}{\alpha}\right).$ (48)

There are at most $w_{Z}q_{X}w_{X}$ elements in $X_{i}$. Therefore, there are
at least $\frac{f}{w_{Z}q_{X}w_{X}}$ of the $\mathcal{X}_{i}$ on which $u_{2}$
is supported. If $u_{2}$ is supported in some $\mathcal{X}_{i}$ then there
must be at least one violated stabiliser in $\mathcal{R}_{i}$, again because
$u_{2}^{(i)}=0\iff
u_{2}^{(i)}\in\ker\partial_{0}^{\overline{\mathcal{B}_{i}}}$. There are
therefore at least

$\frac{f}{w_{Z}q_{X}w_{X}}\geq\frac{\alpha}{\alpha+1}\frac{1}{w_{Z}q_{X}w_{X}}d(u,\ker
H_{X}^{\prime})$ (49)

X - stabilisers violated by $u$ in $C^{\prime}$. We let $\alpha$ be such that
the right-hand sides of Equation (47) and (49) are equal, which turns out to
be

$\alpha=\frac{w_{Z}q_{X}w_{X}}{1+w_{Z}q_{X}w_{X}}\frac{\rho_{Z}N_{X}}{N}.$
(50)

With this choice, there are at least

$\frac{\rho_{Z}}{w_{Z}q_{X}w_{X}\rho_{Z}+\frac{N}{N_{X}}+w_{Z}q_{X}w_{X}\frac{N}{N_{X}}}d(u,\ker
H_{X}^{\prime})$ (51)

X - stabilisers violated by $u$, from which we deduce the required soundness.
∎

######  Lemma 3.5.

Let parameters with and without a prime refer to those of the cone code and
the code pre-coning respectively. Then, assuming that the code pre-coning is
reasonable,

$\rho_{X}^{\prime}\geq\frac{N^{\prime}}{N_{Z}^{\prime}}\frac{N_{Z}}{N}\frac{\rho_{X}}{1+\frac{N_{Z}}{N}\rho_{X}w_{Z}q_{X}w_{X}+q_{Z}w_{Z}q_{X}w_{X}}.$
(52)

###### Proof.

Consider some X - operator in the cone code represented by some bit string
$u\in\left(\mathcal{C}_{cone}\right)_{1}$ where, again, we will refer to the
cone code as $C^{\prime}$ rather than $C_{cone}$ from here on. We again write
$u=(u_{1},u_{2})$ where $u_{1}\in\mathcal{C}_{1}$ and
$u_{2}=\bigoplus_{i=1}^{N_{Z}}u_{2}^{(i)}\in\bigoplus_{i=1}^{N_{Z}}\mathcal{X}_{i}$,
for $u_{2}^{(i)}\in\mathcal{X}_{i}$. Given $u_{1}$, consider the projection of
$u_{1}$ into $\mathcal{Q}_{i}$. Call it $q_{i}$. Then $u$ is in the cone code
if and only if

$q_{i}=\left(\partial_{1}^{\overline{\mathcal{B}_{i}}}\right)^{T}\left(u_{2}^{(i)}\right).$
(53)

We note that this is only possible if $q_{i}$ has even support for every $i$,
because the coboundary of every basis element in $\mathcal{X}_{i}$ has size 2
and $q_{i}$ is expressed as a linear combination of such coboundaries. Note
further that $q_{i}$ has even support if and only if $u_{1}$ satisfies the
stabiliser labelled by $i\in\\{1,...,N_{Z}\\}$. With $H_{Z}$ the parity-check
matrix associated with the Z - stabilisers of the pre-coning code, $u_{1}$
violates at least $\frac{N_{Z}}{N}\rho_{X}d(u_{1},\ker H_{Z})$ Z - stabilisers
in the pre-coning code, $C$.

We may now put $u_{1}$ in the code $C^{\prime}$ as follows. First flip
$d(u_{1},\ker H_{Z})$ bits in $u_{1}$ to put $u_{1}$ in the pre-coning code.
Let the codeword of $\ker H_{Z}$ that it becomes be denoted $u_{1}^{\prime}$.
Let the projection of $u_{1}^{\prime}$ into $\mathcal{Q}_{i}$ be
$q_{i}^{\prime}$. We want to argue that $\exists$
$u_{2}^{\prime(i)}\in\mathcal{X}_{i}$ such that
$q_{i}^{\prime}=\left(\partial_{1}^{\overline{\mathcal{B}_{i}}}\right)^{T}\left(u_{2}^{\prime(i)}\right)$.
This is true, as follows.

First, $q_{i}^{\prime}$ must have even support because $u_{1}^{\prime}$ is a
codeword of $\ker H_{Z}$ and so commutes with all stabilisers of $C$. Consider
the graph $G_{i}$ as defined in Section 2.4.4. $q_{i}^{\prime}$ represents a
set of vertices in that graph of even size. Therefore, if $G_{i}$ is
connected, we can always find a set of edges in $G_{i}$ (i.e. an element of
$\mathcal{X}_{i}$), $u_{2}^{\prime(i)}$, such that
$q_{i}^{\prime}=\left(\partial_{1}^{\overline{\mathcal{B}_{i}}}\right)^{T}\left(u_{2}^{\prime(i)}\right)$.
What if $G_{i}$ is disconnected? We need to have it such that $q_{i}^{\prime}$
has even support on every connected component of $G_{i}$, or we will not be
able to find any valid $u_{2}^{\prime(i)}$. However, $q_{i}^{\prime}$ must
have even support on every connected component of $G_{i}$ because of the
following claim.

######  Claim 3.1.

The product of Z’s over all the vertices (qubits) in a connected component of
$G_{i}$ is a member of the stabiliser group of $C$.

###### Proof.

The Z - operator in question has an even overlap with every X - stabiliser of
$C$ by construction of $G_{i}$. By Claim 2.1, this Z - operator is a member of
the stabiliser group of $C$ because it is supported entirely on a subset of
some Z - stabiliser, and we assume the code to be reasonable. ∎

The X - operator represented by the bit string $u_{1}^{\prime}$ must therefore
commute with the product of Z - operators over the vertices of any connected
component of $G_{i}$, because $u_{1}^{\prime}$ is a codeword of $\ker H_{Z}$,
and as a result $q_{i}^{\prime}$ must have even support on every connected
component of $G_{i}$. Thus, indeed $\exists$
$u_{2}^{\prime(i)}\in\mathcal{X}_{i}$ such that
$\left(\partial_{1}^{\overline{\mathcal{B}_{i}}}\right)^{T}\left(u_{2}^{\prime(i)}\right)=q_{i}^{\prime}$.

Having flipped $d(u_{1},\ker H_{Z})$ bits in $\mathcal{C}_{1}$ to turn $u_{1}$
into $u_{1}^{\prime}$, we finish putting $u$ in the cone code by flipping the
minimum number of bits in $u_{2}$ required to put $(u_{1}^{\prime},u_{2})$ in
the cone code, which we have demonstrated is indeed possible by turning each
$u_{2}^{(i)}$ into $u_{2}^{\prime(i)}$. Suppose that in doing this, we flip
$f$ bits in $u_{2}$. Then

$d(u,\ker H_{Z}^{\prime})\leq d(u_{1},\ker H_{Z})+f$ (54)

where $H_{Z}^{\prime}$ is the parity-check matrix associated with the Z -
stabilisers of the cone code. Let us suppose first that $f\leq\alpha
d(u_{1},\ker H_{Z})$ for some positive number $\alpha$ to be determined. Then
$d(u,\ker H_{Z}^{\prime})\leq(1+\alpha)d(u_{1},\ker H_{Z})$.

As mentioned, $u_{1}$ violates at least $\frac{N_{Z}}{N}\rho_{X}d(u_{1},\ker
H_{Z})$ Z - stabilisers in $C$. Then, for each of these stabilisers labelled
by some $i\in\\{1,...,N_{Z}\\}$, $q_{i}$ has odd support so $\nexists$
$u_{2}^{(i)}$ such that
$q_{i}=\left(\partial_{1}^{\overline{\mathcal{B}_{i}}}\right)^{T}\left(u_{2}^{(i)}\right)$
and therefore for each such $i$, at least one Z - stabiliser of $C^{\prime}$
in $\mathcal{Q}_{i}$ is violated. Thus, at least

$\frac{N_{Z}}{N}\rho_{X}d(u_{1},\ker
H_{Z})\geq\frac{1}{1+\alpha}\frac{N_{Z}}{N}\rho_{X}d(u,\ker H_{Z}^{\prime})$
(55)

Z - stabilisers are violated in $C^{\prime}$.

Suppose now that $f\geq\alpha d(u_{1},\ker H_{Z})$. Then $d(u,\ker
H_{Z}^{\prime})\leq f\left(\frac{\alpha+1}{\alpha}\right)$. Consider the set
$S$ of Z - stabilisers of $C$ which have no support on any of the
$d(u_{1},\ker H_{Z})$ bits that get flipped to turn $u_{1}$ into
$u_{1}^{\prime}$. Since at most $q_{Z}d(u_{1},\ker H_{Z})$ Z - stabilisers may
have support on those bits, $|S|\geq N_{Z}-q_{Z}d(u_{1},\ker H_{Z})$.
Furthermore, since $|X_{i}|\leq w_{Z}q_{X}w_{X}$, there must be at least
$\frac{f}{w_{Z}q_{X}w_{X}}$ sets $\mathcal{X}_{i}$ in which bits get flipped.
As such, there are at least

$\frac{f}{w_{Z}q_{X}w_{X}}-q_{Z}d(u_{1},\ker
H_{Z})\geq\left(\frac{1}{w_{Z}q_{X}w_{X}}-\frac{q_{Z}}{\alpha}\right)f$ (56)

Z - stabilisers for which there are bits flipped in the corresponding
$\mathcal{X}_{i}$ and the bits on which they are supported are not flipped in
$C_{1}$ to turn $u_{1}$ into $u_{1}^{\prime}$. For any such Z - stabiliser
labelled by $i\in\\{1,...,N_{Z}\\}$, there must be at least one Z - stabiliser
of the cone code in $\mathcal{Q}_{i}$ violated, because it means that while
$q_{i}$ did have even support, $u_{2}^{(i)}$ did not satisfy
$q_{i}=\left(\partial_{1}^{\overline{\mathcal{B}_{i}}}\right)^{T}\left(u_{2}^{(i)}\right)$.
This is true because $f$ is the minimum number of bits we flip in $u_{2}$ to
turn $(u_{1}^{\prime},u_{2})$ into a codeword of $\ker H_{Z}^{\prime}$, and
therefore bits would not be flipped in some $\mathcal{X}_{i}$ for which
$u_{2}^{(i)}$ did already satisfy
$q_{i}=\left(\partial_{1}^{\overline{\mathcal{B}_{i}}}\right)^{T}\left(u_{2}^{(i)}\right)$.
There are therefore at least

$\left(\frac{1}{w_{Z}q_{X}w_{X}}-\frac{q_{Z}}{\alpha}\right)f\geq\left(\frac{1}{w_{Z}q_{X}w_{X}}-\frac{q_{Z}}{\alpha}\right)\frac{\alpha}{\alpha+1}d(u,\ker
H_{Z}^{\prime}).$ (57)

Z - stabilisers violated by $u$ in $C^{\prime}$. We then let $\alpha$ be such
that the right-hand sides of Equations (55) and (57) are equal. This is
$\alpha=\left(\frac{N_{Z}}{N}\rho_{X}+q_{Z}\right)w_{Z}q_{X}w_{X}$ and then
the number of Z - stabilisers in $C^{\prime}$ violated by $u$ is at least

$\frac{1}{1+\frac{N_{Z}}{N}w_{Z}q_{X}w_{X}+q_{Z}w_{Z}q_{X}w_{X}}\frac{N_{Z}}{N}\rho_{X}d(u,\ker
H_{Z}^{\prime})$ (58)

from which we deduce the required soundness. ∎

####  3.3.2 Soundness of the Reduced Cone Code

We will now establish a lower bound on the soundness of the reduced cone code
in terms of that of the cone code. As discussed, forming the reduced cone code
comes with steps of “thickening and choosing heights” and “cellulating”, but
we already understand the change in soundness under the “thickening and
choosing heights” step. There is a mild complication in the fact that we only
“choose heights” for the X - stabilisers in
$\mathcal{R}_{i}\otimes\mathcal{E}_{0}$, not those in
$\mathcal{C}_{0}\otimes\mathcal{E}_{0}$, but we can easily take account of
this by changing the value of $N_{X}$ used. The chain complex of the cone code
after thickening and choosing heights is depicted in Figure 4.

${\mathcal{Q}_{N_{Z}}\otimes\mathcal{E}_{0}}$${\mathcal{X}_{N_{Z}}\otimes\mathcal{E}_{0}}$${\widetilde{\mathcal{R}_{N_{Z}}\otimes\mathcal{E}_{0}}}$${\oplus}$${\oplus}$${\oplus}$${\vdots}$${\vdots}$${\vdots}$${\oplus}$${\oplus}$${\oplus}$${\mathcal{Q}_{1}\otimes\mathcal{E}_{0}}$${\mathcal{X}_{1}\otimes\mathcal{E}_{0}}$${\widetilde{\mathcal{R}_{1}\otimes\mathcal{E}_{0}}}$${\oplus}$${\oplus}$${\mathcal{C}_{1}\otimes\mathcal{E}_{0}}$${\mathcal{C}_{0}\otimes\mathcal{E}_{0}}$${\oplus}$${\oplus}$${\left(\mathcal{C}_{cone}\right)_{2}\otimes\mathcal{E}_{1}}$${\left(\mathcal{C}_{cone}\right)_{1}\otimes\mathcal{E}_{1}}$
Figure 4: The chain complex of the cone code after thickening and choosing
heights. The tildes on the $\mathcal{R}_{i}\otimes\mathcal{E}_{0}$ denote the
fact that heights have been chosen in these spaces, i.e. that for every basis
element $c\in\mathcal{R}_{i}$, we keep one and only one basis element of the
form $c\otimes w_{k}$, where $\left(w_{i}\right)_{i=1}^{l}$ forms the standard
basis for $\mathcal{E}_{0}$. To make the diagram as simple as is possible, we
have abbreviated various sets of spaces into
$\left(\mathcal{C}_{cone}\right)_{i}$.

There will, however, be one slightly greater complication for us, and that is
that we will thicken the cone code more than Hastings does. For the benefit of
our later soundness proof, we will want to take a large enough $l$ and choose
heights such that not only are qubits in
$\mathcal{X}_{i}\otimes\mathcal{E}_{0}$ acted on by at most one X - stabiliser
in $\widetilde{\mathcal{R}_{i}\otimes\mathcal{E}_{0}}$, which is what [1]
does, but also each Z - stabiliser in $\mathcal{Q}_{i}\otimes\mathcal{E}_{0}$
has overlap with at most one X - stabiliser in
$\widetilde{\mathcal{R}_{i}\otimes\mathcal{E}_{0}}$. Let us now demonstrate
that this is possible, in the style of an argument in [1]. This argument will
go via “strong hypergraph colouring”. The idea is as follows. Define a
hypergraph181818A hypergraph is a pair $(V,E)$ of a set of vertices, $V$, and
a set of “hyperedges”, $E$, which is a set of subsets of $V$., where vertices
correspond to X - stabilisers of the cone code in $\mathcal{R}_{i}$, and
hyperedges correspond to Z - stabilisers of the cone code in
$\mathcal{Q}_{i}$. A hyperedge corresponding to a Z - stabiliser will contain
all the vertices corresponding to the X - stabilisers with which it has some
overlap. Colouring the vertices of the hypergraph with $l$ colours, the
objective behind strong hypergraph colouring is to make it such that no
hyperedge contains two vertices of the same colour. Then, colouring the
vertices corresponds to choosing heights for the stabilisers in
$\widetilde{\mathcal{R}_{i}\otimes\mathcal{E}_{0}}$, and achieving a strong
hypergraph colouring will make it such that no two X - stabilisers in
$\widetilde{\mathcal{R}_{i}\otimes\mathcal{E}_{0}}$ have overlap with the same
Z - stabiliser in $\mathcal{Q}_{i}\otimes\mathcal{E}_{0}$.

We then use the trivial upper bound [32] that a hypergraph can be strongly
coloured by a number of colours scaling with its maximum edge degree
multiplied by its maximum vertex degree, which for us is
$l=\Theta\left(w_{Z}q_{X}\log w_{Z}\right)$ colours, where these un-decorated
parameters refer to those of the code pre-coning. Note that choosing heights
such that no Z - stabiliser in $\mathcal{Q}_{i}\otimes\mathcal{E}_{0}$ has
overlap with more than one X - stabiliser in
$\widetilde{\mathcal{R}_{i}\otimes\mathcal{E}_{0}}$ will automatically make it
such that every qubit in $\mathcal{X}_{i}\otimes\mathcal{E}_{0}$ will be acted
on by at most one X - stabiliser in
$\widetilde{\mathcal{R}_{i}\otimes\mathcal{E}_{0}}$, assuming every qubit in
$\mathcal{X}_{i}$ is acted on by some Z - stabiliser in $\mathcal{Q}_{i}$,
which we see is true by the construction of $\overline{\mathcal{B}_{i}}$.

With this done, we may now cellulate the added 2 - discs, which we recall is
necessary to turn the added X - stabilisers into low weight stabilisers. We do
this according to the simple cellulation shown in Figure 5 for every disc,
where note in particular that no vertices are added, and therefore no Z -
stabilisers are added in the cellulation step. The resulting chain complex -
that of the reduced cone code - is shown in Figure 6.

$\longmapsto$ Figure 5: The cellulation that we use for all discs. The high
weight X - stabiliser represented by the left-hand disc is replaced by many
low weight X - stabilisers, represented by the new faces on the right-hand
side. Note that while new qubits have been added in the form of new edges, no
new Z - stabiliser (vertices) have been added.
${\mathcal{X}_{N_{Z}}\otimes\mathcal{E}_{0}}$${\oplus}$${\mathcal{Q}_{N_{Z}}\otimes\mathcal{E}_{0}}$${\widetilde{\mathcal{X}^{\perp}_{N_{Z}}\otimes\mathcal{E}_{0}}}$${\oplus}$${\oplus}$${\vdots}$${\vdots}$${\widetilde{\hat{\mathcal{R}}_{N_{Z}}\otimes\mathcal{E}_{0}}}$${\oplus}$${\oplus}$${\oplus}$${\mathcal{Q}_{1}\otimes\mathcal{E}_{0}}$${\mathcal{X}_{1}\otimes\mathcal{E}_{0}}$${\vdots}$${\oplus}$${\oplus}$${\widetilde{\mathcal{X}^{\perp}_{1}\otimes\mathcal{E}_{0}}}$${\widetilde{\hat{\mathcal{R}}_{1}\otimes\mathcal{E}_{0}}}$${\oplus}$${\oplus}$${\mathcal{C}_{1}\otimes\mathcal{E}_{0}}$${\mathcal{C}_{0}\otimes\mathcal{E}_{0}}$${\oplus}$${\oplus}$${\left(\mathcal{C}_{cone}\right)_{2}\otimes\mathcal{E}_{1}}$${\left(\mathcal{C}_{cone}\right)_{1}\otimes\mathcal{E}_{1}}$
Figure 6: The chain complex of the reduced cone code, after each disc has been
cellulated. The spaces
$\widetilde{\mathcal{X}_{i}^{\perp}\otimes\mathcal{E}_{0}}$ are those spanned
by the edges added to all of the discs in
$\widetilde{\mathcal{R}_{i}\otimes\mathcal{E}_{0}}$. Note that we have used
cellulations here that do not add vertices to the discs i.e. do not add Z -
stabilisers to the code.

######  Lemma 3.6.

Let parameters with two primes denote those of the cone code after thickening
and choosing heights. Let un-decorated parameters refer to those of the code
pre-coning. Let parameters with a tilde refer to those of the reduced cone
code. Then

$\tilde{\rho}_{Z}\geq\frac{\tilde{N}}{\tilde{N}_{X}}\frac{N_{X}^{\prime\prime}}{N^{\prime\prime}}\frac{\rho_{Z}^{\prime\prime}}{1+w_{Z}\left(\frac{N_{X}^{\prime\prime}\rho_{Z}^{\prime\prime}}{N^{\prime\prime}}+1\right)}.$
(59)

###### Proof.

We recall that the chain complex is thickened enough and heights are chosen
such that each Z - stabiliser in $\mathcal{Q}_{i}\otimes\mathcal{E}_{0}$ has
overlap with at most one X - stabiliser in
$\widetilde{\mathcal{R}_{i}\otimes\mathcal{E}_{0}}$. Letting the cone code
after thickening and choosing heights be denoted $C^{\prime\prime}$ and the
reduced cone code be denoted $\tilde{C}$, choose some Z - operator in the
reduced cone code represented by some bit string
$u\in\mathbb{F}_{2}^{\tilde{N}}$. Without loss of generality, we may say that
$u$ is not supported on any of the spaces
$\widetilde{\mathcal{X}^{\perp}_{i}\otimes\mathcal{E}_{0}}$, which are the
spaces of “internal edges” of the discs, i.e. those edges that are added in
the cellulation step, as opposed to the external edges of the discs, i.e.
those that were already there. This is true because we can without loss of
generality add to $u$ the boundaries of various Z - stabilisers in
$\mathcal{Q}_{i}\otimes\mathcal{E}_{0}$. If $u$ is supported on some internal
edge, we can add to $u$ the boundary of one of the Z - stabilisers represented
by a vertex on the end of this edge to remove $u$’s support on that internal
edge. Because the chain complex was thickened such that each Z - stabiliser in
$\mathcal{Q}_{i}\otimes\mathcal{E}_{0}$ has overlap with at most one X -
stabiliser in $\widetilde{\mathcal{R}_{i}\otimes\mathcal{E}_{0}}$, each vertex
is in contact with at most one internal edge in any disc, and as such we can
indeed push $u$’s support off of the internal edges.

With this done, $u$ is without loss of generality supported only on the qubits
of $C^{\prime\prime}$. We will use our lower bound on the soundness of
$C^{\prime\prime}$, the cone code post thickening and choosing heights, to
establish a lower bound on the soundness of the reduced cone code. For this,
we will now show how to put $u$ in $\tilde{C}$. Let
$\hat{u}\in\mathbb{F}_{2}^{N^{\prime\prime}}$ be the projection of $u$ into
the $N^{\prime\prime}$ bits corresponding to the qubits of $C^{\prime\prime}$.
We can flip $d(\hat{u},\ker H_{X}^{\prime\prime})$ bits in $\hat{u}$ to put
$\hat{u}$ in $C^{\prime\prime}$, where $H_{X}^{\prime\prime}$ is the parity-
check matrix associated with the X - stabilisers of $C^{\prime\prime}$, the
cone code after thickening and choosing heights. We flip the bits in $u$
corresponding to these bits. Then, $\hat{u}$ must satisfy all of the X -
stabilisers in $C^{\prime\prime}$, however, $u$ may not necessarily satisfy
all of the X - stabilisers in $\tilde{C}$. The reason for this is that, in
satisfying all of the X - stabilisers of $C^{\prime\prime}$, $\hat{u}$ must
have even support on the external edges of every disc. However, even with this
being true, $\hat{u}$ may have odd support on the boundaries of some of the
surfaces of the cellulated disc i.e. some X - stabilisers in
$\widetilde{\hat{\mathcal{R}_{i}}\otimes\mathcal{E}_{0}}$, the space of
cellulated discs (see Figure 6), may be violated.

We may, however, satisfy these stabilisers only by flipping bits in $u$
corresponding to internal edges. This will not affect any other X -
stabilisers, because, as shown in Figure 6, qubits in
$\widetilde{\mathcal{X}_{i}^{\perp}\otimes\mathcal{E}_{0}}$ are only acted on
by X - stabilisers in
$\widetilde{\hat{\mathcal{R}_{i}}\otimes\mathcal{E}_{0}}$. Furthermore,
because $\hat{u}$ has even support on the external edges of the whole disc,
there must now be an even number of violated stabilisers represented by faces
in $\widetilde{\hat{\mathcal{R}_{i}}\otimes\mathcal{E}_{0}}$. Because every
internal edge in each disc is adjacent to two faces, any even number of these
violated stabilisers may be fixed by flipping bits in $u$ corresponding to
internal edges of the discs. This finishes putting $u$ in $\tilde{C}$.

Suppose that in this latter step, $f$ bits of $u$ are flipped in total that
correspond to internal edges of various discs. Then

$d(u,\ker\tilde{H}_{X})\leq d(\hat{u},\ker H_{X}^{\prime\prime})+f$ (60)

where $\tilde{H}_{X}$ denotes the parity-check matrix associated with the X -
stabilisers of the reduced cone code. Let us consider first the case that
$f\leq\alpha d(\hat{u},\ker H_{X}^{\prime\prime})$ for some positive number
$\alpha$ to be determined. In this case,
$d(u,\ker\tilde{H}_{X})\leq(1+\alpha)d(\hat{u},\ker H_{X}^{\prime\prime})$.
$\hat{u}$ violates at least
$\frac{N^{\prime\prime}_{X}}{N^{\prime\prime}}\rho_{Z}^{\prime\prime}d(\hat{u},\ker
H_{X}^{\prime\prime})$ X - stabilisers in $C^{\prime\prime}$. For every X -
stabiliser that is violated by $\hat{u}$ in $C^{\prime\prime}$, at least one
is violated by $u$ in $\tilde{C}$, because $\hat{u}$ having odd support on the
external edges of a given disc implies that $u$ has odd support on the
boundary of at least one of the faces in the cellulation of that disc.
Therefore, $u$ violates at least

$\frac{N^{\prime\prime}_{X}}{N^{\prime\prime}}\rho_{Z}^{\prime\prime}d(\hat{u},\ker
H_{X}^{\prime\prime})\geq\frac{1}{1+\alpha}\frac{N^{\prime\prime}_{X}}{N^{\prime\prime}}\rho_{Z}^{\prime\prime}d(u,\ker\tilde{H}_{X})$
(61)

X - stabilisers in $\tilde{C}$. Suppose now that $f\geq\alpha d(\hat{u},\ker
H^{\prime\prime}_{X})$. Then we have $d(u,\ker\tilde{H}_{X})\leq
f\left(\frac{\alpha+1}{\alpha}\right)$. Because there are at most $w_{Z}$
external edges around one of the discs, there are at most $w_{Z}$ internal
edges in a cellulated disc. There are therefore at least $\frac{f}{w_{Z}}$
discs which have their internal edge bits flipped when we put $u$ in the code.
Furthermore, there are at most $d(\hat{u},\ker H_{X}^{\prime\prime})$ discs
which have their external edge bits flipped when we put $u$ in the code. There
are therefore at least

$\frac{f}{w_{Z}}-d(\hat{u},\ker H_{X}^{\prime\prime})\geq
f\left(\frac{1}{w_{Z}}-\frac{1}{\alpha}\right)$ (62)

discs with inner edge bits flipped and no external edge bits flipped. For such
a disc, at least one of the X - stabilisers given by the faces of that
cellulated disc must have been violated by $u$ and so $u$ violates at least

$\left(\frac{1}{w_{Z}}-\frac{1}{\alpha}\right)\frac{\alpha}{\alpha+1}d(u,\ker\tilde{H}_{X})$
(63)

X - stabilisers in $\tilde{C}$. We now let $\alpha$ be such that the right-
hand sides of Equations (61) and (63) are equal. This turns out to be
$\alpha=w_{Z}\left(\frac{N_{X}^{\prime\prime}\rho_{Z}^{\prime\prime}}{N^{\prime\prime}}+1\right)$.
Then, there are at least

$\frac{N_{X}^{\prime\prime}}{N^{\prime\prime}}\frac{\rho_{Z}^{\prime\prime}}{1+w_{Z}\left(\frac{N_{X}^{\prime\prime}\rho_{Z}^{\prime\prime}}{N^{\prime\prime}}+1\right)}d(u,\ker\tilde{H}_{X})$
(64)

X - stabilisers violated by $u$ in $\tilde{C}$, from which we deduce the
required soundness. ∎

######  Lemma 3.7.

Let parameters with two primes denote those of the cone code after thickening
and choosing heights. Let parameters with a tilde be those of the reduced cone
code. Then

$\tilde{\rho}_{X}\geq\frac{\tilde{N}}{N^{\prime\prime}}\rho_{X}^{\prime\prime}.$
(65)

###### Proof.

Let us consider some X - operator represented by some bit string
$u\in\mathbb{F}_{2}^{\tilde{N}}$. Without loss of generality, $u$ is not
supported on internal edges of any cellulated disc. This is because, if $u$ is
supported on the internal edge of some disc, we can add the boundary of some
collection of faces in that disc to push the support of $u$ onto the external
edges of that disc. Because the set of Z - stabilisers of the reduced cone
code, $\tilde{C}$, is the same as that of the cone code post-thickening and
choosing heights, $C^{\prime\prime}$, we can put $u$ in $\tilde{C}$ simply by
flipping $d(u,\ker H_{Z}^{\prime\prime})$ bits in it, and therefore
$d(u,\ker\tilde{H}_{Z})\leq d(u,\ker H_{Z}^{\prime\prime})$, abusing notation
slightly to view $u$ simultaneously as a vector in
$\mathbb{F}_{2}^{\tilde{N}}$ supported only on the $N^{\prime\prime}$ bits of
$C^{\prime\prime}$, and as a vector in $\mathbb{F}_{2}^{N^{\prime\prime}}$.

As an operator in $C^{\prime\prime}$, $u$ will violate at least
$\frac{N_{Z}^{\prime\prime}}{N^{\prime\prime}}\rho_{X}^{\prime\prime}d(u,\ker
H_{Z}^{\prime\prime})$ Z - stabilisers in that code, and this many are then
also violated by $u$ in $\tilde{C}$, again because $u$ is not supported on any
of the spaces $\widetilde{\mathcal{X}_{i}^{\perp}\otimes\mathcal{E}_{0}}$. $u$
therefore violates at least

$\frac{N_{Z}^{\prime\prime}}{N^{\prime\prime}}\rho_{X}^{\prime\prime}d(u,\ker\tilde{H}_{Z})$
(66)

Z - stabilisers in $\tilde{C}$ and using $\tilde{N}_{Z}=N_{Z}^{\prime\prime}$,