# Quantum XYZ Product Codes

Anthony Leverrier  Inria, France<EMAIL_ADDRESS>Simon Apers
CNRS, IRIF, Université Paris Cité<EMAIL_ADDRESS>Christophe Vuillot
Inria, France<EMAIL_ADDRESS>
###### Abstract

We study a three-fold variant of the hypergraph product code construction,
differing from the standard homological product of three classical codes. When
instantiated with 3 classical LDPC codes, this “XYZ product” yields a _non
CSS_ quantum LDPC code which might display a large minimum distance. The
simplest instance of this construction, corresponding to the product of 3
repetition codes, is a non CSS variant of the 3-dimensional toric code known
as the Chamon code. The general construction was introduced in Denise
Maurice’s PhD thesis, but has remained poorly understood so far. The reason is
that while hypergraph product codes can be analyzed with combinatorial tools,
the XYZ product codes also depend crucially on the algebraic properties of the
parity-check matrices of the three classical codes, making their analysis much
more involved.

Our main motivation for studying XYZ product codes is that the natural
representatives of logical operators are two-dimensional objects. This
contrasts with standard hypergraph product codes in 3 dimensions which always
admit one-dimensional logical operators. In particular, specific instances of
XYZ product codes with constant rate _might_ display a minimum distance as
large as $\Theta(N^{2/3})$. While we do not prove this result here, we obtain
the dimension of a large class of XYZ product codes, and when restricting to
codes with dimension 1, we reduce the problem of computing the minimum
distance to a more elementary combinatorial problem involving binary
3-tensors. We also discuss in detail some families of XYZ product codes that
can be embedded in three dimensions with local interaction. Some of these
codes seem to share properties with Haah’s cubic codes and might be
interesting candidates for self-correcting quantum memories with a logarithmic
energy barrier.

##  1 Introduction and summary

There is a large interest in quantum low-density parity-check (LDPC) codes,
both for their relevance for building fault-tolerant quantum computers and for
their nontrivial topological properties. Despite this, many questions are
still open: Can quantum LDPC codes have linear minimum distance? Do there
exist quantum LDPC codes that are locally testable? Can quantum LDPC codes be
embedded in 3 _physical_ dimensions and describe self-correcting quantum
memories? We study these questions for a family of quantum LDPC codes called
quantum XYZ product codes, which are a non-CSS, 3-fold variant of the
hypergraph product code, derived from a triple of classical codes with parity-
check matrices $H_{1},H_{2},H_{3}$. They were initially described in [29] and
as a special case include the Chamon code [14, 8]. We conjecture that this
family includes codes that have constant rate and minimum distance
$\Theta(N^{2/3})$. As a step towards this conjecture we show that, under
certain conditions, the dimension and the distance of the code are determined
by the tensor Sylvester equation (over $\mathbbm{F}_{2}$):

$(H_{1}H_{1}^{T}\otimes\mathbbm{1}\otimes\mathbbm{1})X=(\mathbbm{1}\otimes
H_{2}H_{2}^{T}\otimes\mathbbm{1})X=(\mathbbm{1}\otimes\mathbbm{1}\otimes
H_{3}H_{3}^{T})X+R.$

For $R=0$ this equation characterizes the code dimension. For
$R=R(H_{1},H_{2},H_{3})\neq 0$ it characterizes the minimum distance. More
precisely, the distance is given by how closely (in Hamming weight) the
equation can be satisfied. This observation stresses the algebraic nature of
the code family. A particular subclass of interest are the cyclic XYZ product
codes where $H_{1},H_{2},H_{3}$ are circulant matrices. We study the simplest
code in this family (beyond the Chamon code), for which we show the distance
is likely upper bounded by $\sqrt{N}$. We also show the existence of fractal
operators (as in Haah’s cubic code [21]) for cyclic XYZ product codes. Such
operators exclude local testability.

###  1.1 Quantum LDPC codes

While specific classes of quantum LDPC codes such as surface codes [26] are
rather well understood, they suffer from inherent limitations of their
parameters: for instance their minimum distance is upper bounded by the square
root of their length [6]. In fact, beating this bound turned out to be very
challenging, even for general LDPC codes that need not be embeddable on a
finite-dimensional lattice. More precisely, an old construction due to
Freedman, Meyer and Luo gives a minimum distance $\Theta(N^{1/2}\log^{1/4}N)$
[18], and only very recently new constructions based on high-dimensional
expanders have brought polylogarithmic improvements [15, 24]. These were
holding the record until the recent breakthrough of Ref. [23] which introduced
_fiber bundle codes_ , a variant of the hypergraph product codes relying on a
_twisted_ homological product. A particular instance of fiber bundle codes was
shown to display a minimum distance of $\Theta(N^{3/5})$, up to
polylogarithmic factors. See also [9] for an explicit construction with the
same parameters. Even more recently, Panteleev and Kalachev showed that a
generalization of fiber bundle codes, named _lifted product codes_ [31] (and
originally introduced in Ref. [30] in a more restrictive version) have an
almost linear minimum distance, $d=\Theta(n/\log n)$, with a logarithmic
dimension, $k=\Theta(\log n)$. Combining this construction with the balancing
trick of Hastings [22], one obtains codes such that $kd^{2}=\Theta(n^{2})$.
See Ref. [10] for a recent review of the current state-of-the-art on quantum
LDPC codes.

It is a daunting open question to understand whether there exist quantum LDPC
codes with both a large rate and minimum distance. Recall that in the
classical setting, LDPC codes with constant rate and linear minimum distance
are easy to obtain, for instance by picking a sparse parity-check matrix at
random. Expansion properties of the resulting code will exclude the existence
of low-weight operators with zero syndrome. The quantum case is significantly
more complex, in particular because we cannot simply exclude low-weight
operators with zero syndrome. Indeed, any quantum LDPC code will have such
operators (corresponding to the generators of the code). Rather, the challenge
is to exclude low-weight _logical_ operators (i.e., operators that send one
codeword to a different one). Recall that a quantum stabilizer code [20] of
length $N$ is defined as the common $+1$ eigenspace of a set
$\\{g_{1},\ldots,g_{m}\\}$ of commuting Pauli operators acting on
$(\mathbbm{C}^{2})^{\otimes N}$, that is, the space

$\mathcal{Q}:=\mathrm{span}\\{|\psi\rangle\in(\mathbbm{C}^{2})^{\otimes
N}\>:\>g_{i}|\psi\rangle=|\psi\rangle,\forall i\in[m]\\}.$

Such a code is said to be _LDPC_ if all the generators $g_{i}$ act
nontrivially on at most a constant number of qubits, and if each qubit is only
acted on by a constant number of generators. With this language, a quantum
LDPC stabilizer code also corresponds to the ground space of the local
Hamiltonian $H=\frac{1}{m}\sum_{i=1}^{m}\Pi_{i}$, with
$\Pi_{i}=\frac{1}{2}(\mathbbm{1}-g_{i})$.

If we denote by $\mathcal{S}:=\langle g_{1},\ldots,g_{m}\rangle$ the
stabilizer group of the code, then the logical operators correspond to the set
$N(\mathcal{S})\setminus\mathcal{S}$ where ${N}(\mathcal{S})$ is the
normalizer of $\mathcal{S}$. The code dimension is
$k=|N(\mathcal{S})/\mathcal{S}|$ and the minimum distance $d_{\min}$ of the
code is given by the minimum weight (i.e. the number of qubits on which it
acts nontrivially) of an operator that leaves the code space globally
invariant, but which is not in the stabilizer group:

$\displaystyle d_{\min}=\min\\{|w|\>:\>w\in
N(\mathcal{S})\setminus\mathcal{S}\\}.$ (1)

This quantity can be particularly challenging to compute for quantum LDPC
codes since most low-weight operators in $N(\mathcal{S})$ effectively belong
to the stabilizer group $\mathcal{S}$ and therefore do not affect the
distance. Quantum CSS codes offer a much simplified setup: these codes
correspond to stabilizer codes for which the generators are either products of
Pauli-$X$ operators $\sigma_{1}=\left[\begin{smallmatrix}0&1\\\
1&0\end{smallmatrix}\right]$ and the identity $\mathbbm{1}$, or products of
Pauli-$Z$ operators $\sigma_{3}=\left[\begin{smallmatrix}1&0\\\
0&-1\end{smallmatrix}\right]$ and the identity $\mathbbm{1}$ [12, 35, 36].
These families are easier to study because the commutation relations required
to make the stabilizer Abelian simply need to be checked between $X$-type and
$Z$-type generators. In particular, such quantum codes can be described by a
pair of classical codes.

######  Definition 1 (CSS code).

A quantum CSS code with parameters $\llbracket N,k,d_{\min}\rrbracket$ is a
pair of classical codes
$\mathcal{C}_{X},\mathcal{C}_{Z}\subseteq\mathbbm{F}_{2}^{N}$ such that
$\mathcal{C}_{X}^{\perp}\subseteq\mathcal{C}_{Z}$, or equivalently
$\mathcal{C}_{Z}^{\perp}\subseteq\mathcal{C}_{X}$. The code space corresponds
to the linear span of
$\left\\{\sum_{z\in\mathcal{C}_{Z}^{\perp}}|x+z\rangle\>:\>x\in\mathcal{C}_{X}\right\\}$,
where $\left\\{|x\rangle\>:\>x\in\mathbbm{F}_{2}^{N}\right\\}$ is the
canonical basis of $(\mathbbm{C}^{2})^{\otimes N}$.

The dimension of the code is given by
$\dim(\mathcal{C}_{X}/\mathcal{C}_{Z}^{\perp})=\dim\mathcal{C}_{X}+\dim\mathcal{C}_{Z}-N$
and its minimum distance is given by

$d_{\min}^{(\text{CSS})}=\min(d_{X},d_{Z}),$

with
$d_{X}=\min\\{|w|\>:\>w\in\mathcal{C}_{X}\setminus\mathcal{C}_{Z}^{\perp}\\}$
and
$d_{Z}=\min\\{|w|\>:\>w\in\mathcal{C}_{Z}\setminus\mathcal{C}_{X}^{\perp}\\}$.
Here, $|w|$ stands for the Hamming weight of the word $w$. All the code
constructions with large distance mentioned above are instances of CSS codes
[18, 25, 15, 24, 23]. An appealing property of CSS codes is that they can
alternatively be described using chain complexes. A chain complex (of length
3) is described by 3 binary vector spaces $C_{0},C_{1},C_{2}$ together with
_boundary operators_ $\partial_{1},\partial_{2}$, and is depicted as

$C_{2}\xrightarrow{\partial_{2}}C_{1}\xrightarrow{\partial_{1}}C_{0}.$

The boundary operators are such that $\partial_{1}\partial_{2}=0$. In this
case, the classical codes $\mathcal{C}_{X}$ and $\mathcal{C}_{Z}$ defining the
CSS code are given by

$\mathcal{C}_{X}=\ker\partial_{1}\quad\text{and}\quad\mathcal{C}_{Z}=(\mathrm{Im}\,\partial_{2})^{\perp}=\ker\partial_{2}^{T}.$

The condition that $\mathcal{C}_{Z}^{\perp}\subseteq\mathcal{C}_{X}$ now
naturally follows from the condition that $\partial_{1}\partial_{2}=0$. The
qubits correspond to the space $C_{1}$, while the $X$\- and $Z$-check
operators correspond to $C_{0}$ and $C_{2}$, respectively.

One might intuitively expect that non-CSS codes offer better prospects in
terms of possible minimum distance, albeit at the cost of making their
analysis more involved. It turns out that this is not the case, as was
observed by Ref. [7]: starting from any non CSS code of parameters $\llbracket
n,k,d\rrbracket$, one can construct a CSS code with essentially the same
asymptotic parameters111The hyperbicycle codes of [27] give an example where
the non CSS version can display slightly better parameters than the standard
CSS construction of hypergraph product codes [38].:

$\llbracket n_{\text{CSS}}=4n,k_{\text{CSS}}=2k,d_{\text{CSS}}=2d\rrbracket,$

and generators of weight at most doubled compared to the original code (we
detail this construction in Section 3.3). This fact, together with their a
priori more involved analysis, explains why non CSS codes have been mostly
ignored as an approach to devise quantum LDPC codes with large distance222We
note, however, that non CSS codes are investigated in the context of quantum
fault-tolerance where their non CSS nature offers interesting properties in
terms of resistance to biased noise for instance [2]. For instance, the XZZX
code of Ref. [2] is a 2-dimensional version of the Chamon code.. A notable
exception is the _Chamon code_ [14] which was initially introduced as a three-
dimensional quantum Hamiltonian with intriguing topological properties and
later analyzed in depth by Bravyi, Leemhuis and Terhal [8]. This code shares
with the 3D toric code the fact that it can be embedded in three dimensions
with local interaction: the generators have weight 6 and act on their two
neighboring qubits in each spatial direction with either $X$-, $Y$-, or
$Z$-type Pauli operators. Interestingly, while the 3D toric code admits
string-like logical operators (and thus has a minimum distance upper bounded
by $N^{1/3}$), the natural logical operators of the Chamon code are membrane-
like, giving some hope that the minimum distance could be much larger.
Unfortunately, the Chamon code is known to have distance only $O(\sqrt{N})$.
This follows from the fact that certain “flexible” string operators of the
Chamon code live in a plane orthogonal to the $[1,1,1]^{T}$ direction of the
lattice and that the topology of this plane is identical to a 2-dimensional
toric code, hence there exists a noncontractible loop (corresponding to a
logical operator) of length at most $\sqrt{N}$. Whether this upper bound is
tight or not is still an open question, as far as we know. Note that this
upper bound only applies to the _stabilizer version_ of the Chamon code. It
also makes sense to study _subsystem code_ versions where not all logical
qubits are used to encode information, with the hope that the chosen qubits
necessarily have large weight logical operators. While [8] shows that the
subsystem code version still display a $\sqrt{N}$ upper bound for the minimum
distance for some choice of parameters, it is not excluded that better choices
would lead to distance as large as $\Theta(N^{2/3})$. An important aspect of
the analysis of [8] is that the properties of the Chamon code have an
intrinsic algebraic nature, suggesting that the code is very different from
its toric code cousin. This shows up very clearly when computing the quantum
dimension of the Chamon code: if the code is defined on a lattice of size
$n_{1}\times n_{2}\times n_{3}$ then its dimension is

$k_{\text{Chamon}}=4\gcd(n_{1},n_{2},n_{3}).$

Recall on the other hand that the dimension of topological codes such as the
surface code only depend on the genus of the surface (number of holes) and are
independent of the lattice size. The algebraic properties of the parity-check
matrix essentially show up because the product of the three Pauli matrices is
proportional to the identity:
$\sigma_{1}\sigma_{2}\sigma_{3}=i\mathbbm{1}_{2}$, with
$\sigma_{2}=\left[\begin{smallmatrix}0&-i\\\ i&0\end{smallmatrix}\right]$.
Because of this, nontrivial relations might occur among the code generators,
and this is essentially what $k_{\text{Chamon}}$ above counts since the Chamon
code has as many generators as qubits. This is in contrast to typical CSS
codes, where the generators involve only $X$\- and $Z$-type Pauli operators.

###  1.2 Hypergraph Product codes and generalizations

_Hypergraph product codes_ [38] are a constant-rate generalization of the
toric code obtained by taking the (homological) product of two classical
codes. In particular, the product of two good classical LDPC codes yields a
quantum code with constant rate and minimum distance $\Theta(\sqrt{N})$. At
the moment, no quantum LDPC code family is known to beat this bound while
displaying a constant rate. Such codes could be useful to perform quantum
computation in a fault-tolerant manner with a constant overhead in terms of
qubits [16]. Hypergraph product codes can be understood as a special instance
of the homological product of two chain complexes of length two [17, 5].
Concretely, consider two classical codes $\mathcal{C}_{1}=\ker H_{1}$ and
$\mathcal{C}_{2}=\ker H_{2}$ described by their parity-check matrices $H_{i}$
of size $m_{i}\times n_{i}$ for $i=1,2$. The hypergraph product code
associated to these codes is given by the quantum CSS code associated to the
3-complex:

$\mathbbm{F}_{2}^{n_{1}\times
n_{2}}\xrightarrow{(H_{1}\otimes\mathbbm{1},\mathbbm{1}\otimes
H_{2})}(\mathbbm{F}_{2}^{m_{1}\times n_{2}}\oplus\mathbbm{F}_{2}^{n_{1}\times
m_{2}})\xrightarrow{1\otimes
H_{2}+H_{1}\otimes\mathbbm{1}}\mathbbm{F}_{2}^{m_{1}\times m_{2}}.$

We note that by considering the homological product of two random complexes of
length 3 (i.e., random CSS codes), Bravyi and Hastings [5] showed the
existence of CSS codes with linear minimum distance. Unfortunately the
construction requires generators of weight $\Theta(\sqrt{N})$ and therefore do
not satisfy the LDPC condition.

The 2-dimensional toric code is a special instance of the hypergraph product
code construction corresponding to the product of two repetition codes. It is
straightforward to generalize the hypergraph product code construction to
$D$-fold homological products [13, 41, 32], and the special case of the
repetition code will naturally yield the $D$-dimensional toric code.

###  1.3 XYZ product codes

In her PhD thesis, Denise Maurice noticed that one could also consider a
different generalization of the hypergraph product code that would yield a non
CSS code when applied to 3 classical codes [29]. The idea is to associate a
different code to each of the $X$-, $Y$\- or $Z$-Pauli checks (see Fig. 1).
She noted that this XYZ product yields the Chamon code when the three
classical codes are repetition codes333Ref. [8] also suggested some
generalizations of the Chamon code replacing the repetition code by symmetric
circulant matrices with even row weight. We will consider a closely related
construction in Section 6 but with circulant matrices of odd weight.. She also
gave lower bounds on the dimension of general XYZ product codes, but warned
that these were not tight because they ignored potential relations between the
generators caused by $XYZ=i\mathbbm{1}$. Consequently, she could not give non
trivial lower bounds on the minimum distance, because this would at least
require to know how many logical operators exist. Finally, she established a
general upper bound on the minimum distance of the form $O(N^{2/3})$.

Figure 1: 3D structure of the XYZ product code: qubits are indexed by the
3-tensors $A,B,C,D$, generators by $S,T,U,V$. The $x$, $y$ and $z$ labels are
shorthand for the operators $H_{1}\otimes\mathbbm{1}\otimes\mathbbm{1}$,
$\mathbbm{1}\otimes H_{2}\otimes\mathbbm{1}$ and
$\mathbbm{1}\otimes\mathbbm{1}\otimes H_{3}$, respectively.

In addition to difficulties to compute the quantum dimension of XYZ product
codes, their non CSS nature also makes the understanding of the minimum
distance more complex: in particular, it is not possible to restrict the
analysis to $X$-type or $Z$-type logical operators similarly to the CSS case,
and one must a priori consider all possible logical operators. We discuss in
Section 3.3 a possible CSS variant of the XYZ product codes that could be
better suited for a distance analysis. However, this CSS version involves 4
times as many qubits and also a lot of new generators, and consequently turns
out not be much easier to study. The interest behind this code construction is
however that it might break the $\sqrt{N}$ bound for the minimum distance. The
reason for which hypergraph product codes have a $\sqrt{N}$ distance is that
there exist logical operators that basically correspond to codewords of one of
the two classical codes. With the XYZ product, the hope is that the third code
acting with $Y$-Pauli operators along the third coordinate will force low-
weight logical operators to be a product of two out of the three classical
codes. Indeed, the natural logical operators have exactly this form. The
problem then is to understand whether there exist equivalent logical operators
(differing by an element of the stabilizer group) with a much lower weight.
This is for instance the case for the Chamon code since the minimum distance
is only $O(N^{1/2})$.

More formally, the XYZ product code construction is a generalization of the
hypergraph product code involving a third classical code which will enforce
Pauli $Y$-type constraints. Given three parity-check matrices $H_{1}$, $H_{2}$
and $H_{3}$, we first define a chain complex, depicted in Figure 2.

Figure 2: _Chain complex_ representation of the XYZ product codes. The $x$,
$y$ and $z$ labels are shorthand for the operators
$H_{1}\otimes\mathbbm{1}\otimes\mathbbm{1}$, $\mathbbm{1}\otimes
H_{2}\otimes\mathbbm{1}$ and $\mathbbm{1}\otimes\mathbbm{1}\otimes H_{3}$,
respectively.

We proceed similarly to the hypergraph product code construction. We identify
the resulting vector with 3-tensors

$A\in\mathbbm{F}_{2}^{n_{1}\times n_{2}\times n_{3}},\quad
B\in\mathbbm{F}_{2}^{n_{1}\times m_{2}\times m_{3}},\quad
C\in\mathbbm{F}_{2}^{m_{1}\times n_{2}\times m_{3}},\quad
D\in\mathbbm{F}_{2}^{m_{1}\times m_{2}\times n_{3}},$

which will index the qubits, and 3-tensors

$S\in\mathbbm{F}_{2}^{m_{1}\times n_{2}\times n_{3}},\quad
T\in\mathbbm{F}_{2}^{n_{1}\times m_{2}\times n_{3}},\quad
U\in\mathbbm{F}_{2}^{n_{1}\times n_{2}\times m_{3}},\quad
V\in\mathbbm{F}_{2}^{m_{1}\times m_{2}\times m_{3}},$

which will index the checks. The total number of qubits is

$\displaystyle
N=\underbrace{n_{1}n_{2}n_{3}}_{n_{A}}+\underbrace{n_{1}m_{2}m_{3}}_{n_{B}}+\underbrace{m_{1}n_{2}m_{3}}_{n_{C}}+\underbrace{m_{1}m_{2}n_{3}}_{n_{D}}.$
(2)

A general stabilizer element is a tensor over the Pauli group written
abstractly as

$\displaystyle\begin{bmatrix}{\cal A}\\\ {\cal B}\\\ {\cal C}\\\ {\cal
D}\end{bmatrix}=\begin{bmatrix}\mathcal{X}^{\dagger}&\mathcal{Y}^{\dagger}&\mathcal{Z}^{\dagger}&\cdot\\\
\mathcal{Y}&\mathcal{X}&\cdot&\mathcal{Z}^{\dagger}\\\
\mathcal{Z}&\cdot&\mathcal{X}&\mathcal{Y}^{\dagger}\\\
\cdot&\mathcal{Z}&\mathcal{Y}&\mathcal{X}^{\dagger}\end{bmatrix}\begin{bmatrix}S\\\
T\\\ U\\\ V\end{bmatrix}=:\Gamma(S,T,U,V).$ (3)

Here we introduced the operators444The dimension of the identity operator
$\mathbbm{1}$ will vary depending on the context.

$\mathcal{X}=\sigma_{1}^{H_{1}\otimes\mathbbm{1}\otimes\mathbbm{1}},\qquad\mathcal{Y}=\sigma_{2}^{\mathbbm{1}\otimes
H_{2}\otimes\mathbbm{1}},\qquad\mathcal{Z}=\sigma_{3}^{\mathbbm{1}\otimes\mathbbm{1}\otimes
H_{3}}.$

We use the convention that an adjoint $\mathcal{X}^{\dagger}$ denotes the
operator
$\mathcal{X}^{\dagger}=\sigma_{1}^{H_{1}^{T}\otimes\mathbbm{1}\otimes\mathbbm{1}}$,
a product $\mathcal{Y}S$ denotes $\sigma_{2}^{(\mathbbm{1}\otimes
H_{2}\otimes\mathbbm{1})S}$, and a sum $\mathcal{Y}S+\mathcal{X}T$ denotes the
_product_ $\sigma_{2}^{(\mathbbm{1}\otimes
H_{2}\otimes\mathbbm{1})S}\sigma_{1}^{(H_{1}\otimes\mathbbm{1}\otimes\mathbbm{1})T}$.
We call the resulting stabilizer code the XYZ product code, and we refer to it
by the shorthand ${\cal Q}(H_{1},H_{2},H_{3})$.

###  1.4 Our results

We initiate a systematic study of the XYZ product codes and establish a number
of results. Unfortunately, we do not manage to establish the code dimension in
the most general case, nor do we succeed in proving record-breaking lower
bounds on the minimum distance. In fact, even proving a bound of the form
$\omega(N^{1/3})$ for the minimum distance appears to be challenging. We note
that Ref. [8] claims that such a result for the Chamon code would appear in a
future work of one of the authors, but has not as far as we know.

####  1.4.1 Validity of the XYZ product code construction

A stabilizer code is characterized by its stabilizer group
$\mathcal{S}=\langle g_{1},\ldots,g_{m}\rangle$ that should satisfy two
properties: it should be Abelian, meaning that any pair of generators
$g_{i},g_{j}\in\mathcal{P}^{\otimes N}$ should commute, $[g_{i},g_{j}]=0$, and
it should not contain $-\mathbbm{1}$. Note that indeed,
$-\mathbbm{1}\in\mathcal{S}$ immediately implies that any codeword
$|\psi\rangle$ should be stabilized by $-\mathbbm{1}$ and therefore
$|\psi\rangle=-|\psi\rangle=0$. We prove in Lemma 3 that the stabilizer group
of the XYZ product codes is Abelian, and this follows directly from the fact
that the construction is a 3-fold version of the hypergraph product code
construction. Proving that the stabilizer group does not contain
$-\mathbbm{1}$ turns out to be much more challenging, however, and this is
already a nontrivial result in the case of the Chamon code [8]. While this
question does not show up for CSS construction since a product of $\sigma_{1}$
or $\sigma_{3}$ commuting generators can never pick a nontrivial phase, this
is no longer the case for general stabilizers involving $\sigma_{2}$ operators
since for instance $\sigma_{1}\sigma_{2}\sigma_{3}=i\mathbbm{1}$.

While we do not prove that $-\mathbbm{1}\notin\mathcal{S}$ in the general case
of the XYZ product of three arbitrary parity-check matrices
$H_{1},H_{2},H_{3}$, we establish this fact for a special case of interest
where the code dimension is 1 (see Lemma 16). The corresponding codes are the
ones we focus on in most of the paper since they offer the best hope for
displaying a large minimum distance.

Moreover we show that in the case where $-\mathbbm{1}\in\mathcal{S}$ there is
always a way to choose a well defined stabilizer code from $\mathcal{S}$. This
stabilizer code is given by making consistent choices for each elements of
$\mathcal{S}$ of whether the code space should belong to its $+1$\- or
$-1$-eigenspace. The parameters $\llbracket n,k,d\rrbracket$ of the stabilizer
code obtained are independent of the choices for the signs, see Section 3.2.
We also show that using a standard transformation due to [7], one can exhibit
a CSS version of the XYZ product code which is readily well defined whether or
not $-\mathbbm{1}\in\mathcal{S}$ and has parameters $\llbracket
4n,2k,2d\rrbracket$, see Section 3.3.

Our result concerning the dimension in Section 4 should be interpreted as
usual in the cases where $-\mathbbm{1}\not\in\mathcal{S}$. In a case where
$-\mathbbm{1}\in\mathcal{S}$ then our results would apply to the well defined
stabilizer code resulting from any consistent choice of signs for the
generators of the XYZ product construction.

####  1.4.2 Dimension of the XYZ product codes

Consider parity-check matrices $H_{i}$ of size $m_{i}\times n_{i}$ for
$i\in\\{1,2,3\\}$. The dimension of the resulting XYZ product code
$\mathcal{Q}(H_{1},H_{2},H_{3})$ is given by the number of physical qubits
minus the number of independent generators. If $r$ is the number of
“relations” between the generators, then the dimension $k$ of the code is
given by

$\displaystyle k$ $\displaystyle=(n_{1}-m_{1})(n_{2}-m_{2})(n_{3}-m_{3})+r.$

We show that the number of relations is given by the number of solutions to
the following linear system over $\mathbbm{F}_{2}$:

$\displaystyle H_{1}^{T}S$ $\displaystyle=H_{2}^{T}T$
$\displaystyle=H_{3}^{T}U$ (4) $\displaystyle H_{1}T$ $\displaystyle=H_{2}S$
$\displaystyle=H_{3}^{T}V$ $\displaystyle H_{1}U$ $\displaystyle=H_{2}^{T}V$
$\displaystyle=H_{3}S$ $\displaystyle H_{1}^{T}V$ $\displaystyle=H_{2}U$
$\displaystyle=H_{3}T$

where $H_{1}$ is shorthand for $H_{1}\otimes\mathbbm{1}\otimes\mathbbm{1}$ and
similarly for $H_{2},H_{3}$. While the general case seems out of reach for the
moment, we compute the dimension of the XYZ product code when the three
parity-check matrices are invertible.

######  Theorem 2.

If the parity-check matrices $H_{1}$, $H_{2}$ and $H_{3}$ are invertible, then
the dimension of the XYZ product code is equal to the number of solutions of
the tensor Sylvester equation

$H_{1}H_{1}^{T}X=H_{2}H_{2}^{T}X=H_{3}H_{3}^{T}X,$

which is equal to

$\sum_{i,j,k}\mathrm{deg}(\mathrm{gcd}(p^{1}_{i},p^{2}_{j},p^{3}_{k})),$

where $p^{\ell}_{i}$ is the characteristic polynomial of the $i$-th Jordan
block of $H_{i}H_{i}^{T}$.

This is established by proving a tensor version of the Cecioni-Frobenius
theorem (Theorem 9) which originally counted the number of solutions to the
(homogeneous) matrix Sylvester equation $AX=XB$.

Since one of our goals is to better understand the distance properties of XYZ
product codes, it makes sense to first focus our attention on codes with
dimension 1. We provide sufficient conditions for this (see Corollary 5). In
particular, by the theorem above, it is sufficient that the three parity-check
matrices $H_{1},H_{2},H_{3}$ are invertible and that the matrices
$H_{1}H_{1}^{T},H_{2}H_{2}^{T},H_{3}H_{3}^{T}$ have a unique common eigenvalue
(each with geometric multiplicity 1).

####  1.4.3 Minimum distance of the XYZ product codes

For an XYZ product code with dimension 1 it is sufficient to consider each of
the 3 logical operators ($X$, $Y$, $Z$-logical operators) to compute the
minimum distance. We first give a $\Omega(N^{1/3})$ lower bound on the
distance (Lemma 17) via a standard argument. Our main result is a proof that
the minimum distance is equivalent to an elementary combinatorial problem
involving binary 3-tensors. More precisely, in the slightly simpler case where
the parity-check matrices are sparse and symmetric (in addition to the
conditions above), the minimum distance is given (up to a constant) by the
following quantity (see Theorem 22):

$\displaystyle\min_{(i,j,k)\in(1,2,3)}\min_{M}\big{(}|(H_{i}^{2}+H_{j}^{2})M|+|(H_{i}^{2}+H_{k}^{2})M+R|\big{)}$
(5)

where $R$ is the 3-tensor $R_{i,j,k}=\delta_{k,1}$, $|.|$ is the Hamming
weight of the tensor, and we minimize over permutations of indices $(i,j,k)$
and binary 3-tensors $M\in\mathbbm{F}_{2}^{n_{1}\times n_{2}\times n_{3}}$.
Equivalently, we may ask how closely we can approximate the heterogeneous
tensor Sylvester equation

$H_{i}^{2}M=H_{j}^{2}M=H_{k}^{2}M+R$

for $(i,j,k)\in(1,2,3)$. It is clear, by taking $M=0$, that the minimum
distance is at most $O(N^{2/3})$. Intuitively, it seems unlikely that the
minimum in Eqn. (5) can be much lower than $N^{2/3}$. For the second term in
(5) to be $o(N^{2/3})$, the tensor $M$ should be dense, that is
$|M|=\Omega(N)$. This implies in turn that each slice $M_{k}$ (perpendicular
to the $z$-direction) should be very structured in order to get
$|(H_{i}^{2}+H_{j}^{2})M_{k}|=o(N^{1/3})$. In that sense it seems likely that
for a generic choice of $H_{1},H_{2},H_{3}$, the minimum of Eqn. (5) is
$\Theta(N^{2/3})$, but proving this claim has remained elusive so far.

Expansion properties of the base codes are often helpful to prove nontrivial
bounds on the distance, e.g. for quantum expander codes [28] or for lower
bounding the cohomological distance of fiber bundle codes [23], but seem
unable to get us past $\Omega(N^{1/3})$ for the XYZ product codes. We also
note that the probabilistic method which was successfully applied in [17] and
[23] for instance, is difficult to implement here, because of the algebraic
nature of some of the XYZ product code properties.

####  1.4.4 Cyclic XYZ product codes, and 3-dimensional embeddings

A special class of XYZ product codes that can be analyzed in greater detail
corresponds to taking classical cyclic codes, that is codes defined by
circulant parity-check matrices. Such matrices can be conveniently described
by a polynomial formalism since they are polynomials in the matrix

$\Omega_{n}=\left[\begin{smallmatrix}0&0&\ldots&0&1\\\ 1&0&&&0\\\
\vdots&\ddots&&&\vdots\\\ 0&&&1&0\end{smallmatrix}\right],$

satisfying $(\Omega_{n})^{n}=\mathbbm{1}$. In other words, a circulant matrix
is described by a polynomial over the finite ring
$\mathbbm{F}_{2}[x]/(x^{n}+1)$. In this setup, the XYZ code becomes
translation invariant. In addition, if the parity-check matrices are local in
1 dimension, then the resulting XYZ product code can be embedded on a three-
dimensional lattice with local interactions. This is a simple generalization
of the Chamon code also suggested in Ref. [8].

For these codes, computing the minimum distance _seems_ easier. A general
3-tensor corresponds to a polynomial
$P(x,y,z)\in\mathbbm{F}_{2}[x,y,z]/(x^{n_{1}}+1,y^{n_{2}}+1,z^{n_{3}}+1)$. The
interpretation of the polynomial is that the presence of some arbitrary
monomial $x^{i}y^{j}z^{k}$ in $P$ means that there is a 1 in the cell indexed
by $(i,j,k)$ in the binary tensor. For instance, the natural $Z$-logical
operator, corresponding to a full horizontal plane of $\sigma_{3}$ operators,
is described by the polynomial
$R(x,y,z)=\sum_{i=0}^{n_{1}-1}\sum_{j=0}^{n_{2}-1}x^{i}y^{j}$. In that case,
the minimum distance is given, up to constant factors, by an optimization
problem of the form:

$\min_{P}\big{(}|(P_{1}(x)+P_{2}(y))P(x,y,z)|+|(P_{1}(x)+P_{3}(z))P(x,y,z)+R(x,y)|\big{)}.$

In particular, the general form of polynomials $P(x,y)$ such that
$|(P_{1}(x)+P_{2}(y))P(x,y)|$ is small is rather well understood. It is a sum
of _fractal operators_ $(P_{1}+P_{2})^{2^{p}-1}$ since

$(P_{1}(x)+P_{2}(y))(P_{1}(x)+P_{2}(y))^{2^{p}-1}=(P_{1}(x)+P_{2}(y))^{2^{p}}=P_{1}(x^{2^{p}})+P_{2}(y^{2p}))$

where we used that $P(x)^{2}=P(x^{2})$ over $\mathbbm{F}_{2}[x]$. Since the
code is LDPC, we get that

$\left|(P_{1}(x)+P_{2}(y))(P_{1}(x)+P_{2}(y))^{2^{p}-1}\right|=O(1).$

We note that the existence of such fractal operators (which are also central
in the study of Haah’s cubic code [21] for instance) immediately show that the
codes are not locally testable since there exist large weight errors with
constant weight syndromes.

In Section 7, we consider a specific instance of the XYZ product code
associated to parity-check matrices
$H_{i}=\mathbbm{1}_{n_{i}}+\Omega_{n_{i}}+\Omega_{n_{i}}^{T}$. If the
$n_{i}$’s are odd and no multiple of 3, we show that the code dimension is

$4(\gcd(n_{1},n_{2},n_{3})-1)+1.$

Choosing the $n_{i}$’s to be coprime yields a single logical qubit and the
optimization problem takes the simple form

$\min_{P}|(1+xy)(1+x/y)P|+|(1+xz)(1+x/z)P+R|,$

which can be analyzed in some detail. Unfortunately, it seems that many
choices of $n_{i}$’s lead to a distance $O(N^{1/3})$ suggesting that higher
weight polynomials (weight 5) may be required to reach much larger distances.

The existence of fractal operators also hints at the possibility that some of
these codes might display a large (logarithmic) energy barrier, and therefore
be potentially useful as self-correcting quantum memories [11, 37]. While we
do not have a general answer to these questions at the moment, we prove in
Section 7 that 3D codes obtained by taking identical circulant parity-check
matrices have a constant energy barrier, even if the $n_{i}$’s are coprime.
Such codes are therefore unable to passively store quantum information.

###  1.5 Open questions

Our work leads to a large number of open questions, and we give a few below:

  * •

The most obvious question is whether specific instances of XYZ product codes
do achieve a minimum distance of $\Theta(N^{2/3})$. If this is the case, is it
also possible when restricting to codes that are embeddable in 3 dimensions?
If so, this would saturate an upper bound due to Bravyi and Terhal [6]. It
would also be interesting to understand how the distance behaves when the code
dimension increases. For instance, it is easy to get quantum codes with
constant rate (linear code dimension) by taking full rank rectangle parity-
check matrices of size $m\times n$ with $m/n$ bounded away from 0 or 1, but it
is even less clear what the distance is in that case.

  * •

It would be interesting to also study the lifted product variant of the XYZ
product codes, following the work of [31]. This could in principle yield codes
of distance beyond $N^{2/3}$.

  * •

It would also be nice to understand whether there exist triples of parity-
check matrices such that the XYZ product code $\mathcal{Q}(H_{1},H_{2},H_{3})$
is not a valid stabilizer code, because $-\mathbbm{1}$ belongs to the
stabilizer group.

  * •

Another open question is to determine the dimension of the XYZ product code in
the general case. In particular, the case where $H_{i}H_{i}^{T}$ is not full
rank appears harder to analyze. We comment on the difficulties of getting a
full solution to this problem right before Section 4.1.

  * •

The Chamon code initially appeared in literature on quantum many-body systems.
Similarly, the models corresponding to cyclic XYZ product codes embeddable in
3 dimensions may display interesting properties. For instance, the appearance
of fractal operators is reminiscent of Haah’s cubic code and raises the
question of whether some XYZ product codes display some form of self-
correction, or a logarithmic energy barrier scaling? A first step in this
direction would be to show that some variants do not have any string logical
operators.

  * •

Replacing qubits by qudits, or considering XYZ-type products in higher
dimensions also appears as a potentially fruitful avenue of research. For
instance, a, XYZ-type product in $2D+1$ dimensions can be defined in exactly
the same fashion as soon as we have $2D+1$ mutually anticommuting operators,
which is possible by replacing each qubit by $D$ qubits.

  * •

A question that we did not explore at all is that of decoding XYZ product
codes. In particular, it is tempting to try to adapt decoders that work well
for hypergraph product codes, for instance the small-set-flip decoder [28].
Maybe better decoders are also possible for the topological XYZ product codes
embedded in 3 dimensions?

### Organization

Section 2 introduces in detail the hypergraph product code construction which
is essential for the XYZ product code construction that we present in Section
3. We also discuss a CSS version of the construction and compare it with the
other 3-fold hypergraph product code constructions that have already appeared
in the literature. Section 4 is devoted to the study of the dimension of the
XYZ product code and Section 5 to its minimum distance. We consider cyclic,
translation-invariant instances of the code in Section 6 and study in more
detail the simplest such instance in Section 7.

### Acknowledgments

We would like to thank Benjamin Audoux, Alain Couvreur, Denise Maurice,
Barbara Terhal, Jean-Pierre Tillich and Gilles Zémor for many fruitful
discussions on quantum LDPC codes. Most of this work was done while SA was in
the CWI-Inria lab. AL and CV acknowledge support from the ANR through the
QuantERA project QCDA and from the Plan France 2030 through the project
ANR-22-PETQ-0006.

##  2 Preliminaries and notations

###  2.1 Notations

  * •

The Pauli group on one qubit is $\mathcal{P}=\langle X,Y,Z\rangle$ where
$X,Y=iXZ,Z$ are the Pauli matrices given by

$X=\begin{pmatrix}0&1\\\ 1&0\end{pmatrix},\quad Y=\begin{pmatrix}0&-i\\\
i&0\end{pmatrix},\quad Z=\begin{pmatrix}1&0\\\ 0&-1\end{pmatrix}.$

  * •

We will overload the variables $X,Y,Z$ and sometimes write
$\sigma_{1},\sigma_{2},\sigma_{3}$ instead of $X,Y,Z$ to avoid any confusion
or when it is convenient.

  * •

The multi-qubit Pauli group on $n$ qubits, $\mathcal{P}_{n}$, consists in
tensor product of single-Pauli operators.

  * •

We will denote the $n\times n$ identity matrix as $\mathbbm{1}_{n}$ and often
use just $\mathbbm{1}$ where the dimension should be clear from context.

  * •

We will manipulate tensors of binary numbers as well as tensors of Pauli
operators. We use standard capital roman letters to denote binary tensors
like, $A$, $B$, $C$, $D$, $S$, $T$, $U$, $V$, $M$, and calligraphic letters
for Pauli tensors like $\mathcal{A}$, $\mathcal{B}$, $\mathcal{C}$,
$\mathcal{D}$, $\mathcal{S}$, $\mathcal{T}$, $\mathcal{U}$, $\mathcal{V}$. For
instance given a binary tensor $A$, we can define a Pauli tensor of the same
dimension $\mathcal{A}$ as

$\mathcal{A}=\sigma_{1}^{A},$ (6)

where this notation means that for any entry where $A$ is $1$, respectively
$0$, $\mathcal{A}$ has a Pauli $\sigma_{1}$, respectively $\mathbbm{1}$, at
the corresponding entry.

  * •

The Hamming weight of a binary tensor $A$ is the number of nonzero entries in
$A$ and is denoted $\left|A\right|$.

  * •

The Pauli weight of a Pauli tensor $\mathcal{A}$ is the number of entries that
are not the identity and is also denoted as $\left|\mathcal{A}\right|$. In the
case of (6) for instance the Hamming weight of $A$ and the Pauli weight of
$\mathcal{A}$ coincide.

  * •

The commutator of two Pauli tensors of the same dimensions, $\mathcal{A}$ and
$\mathcal{B}$, is $-\mathbbm{1}$ if they anti-commute and $+\mathbbm{1}$ if
they commute and is denoted as $[\mathcal{A},\mathcal{B}]$. Computing it can
be done using the following

$[\mathcal{A},\mathcal{B}]=\mathcal{A}\cdot\mathcal{B}\cdot\mathcal{A}^{-1}\cdot\mathcal{B}^{-1},$
(7)

where the product is taken element wise and the right hand side is therefore
always either $+\mathbbm{1}$ or $-\mathbbm{1}$.

###  2.2 Hypergraph Product code

As mentioned in the introduction, CSS codes are naturally expressed as chain
complexes of length 3 or subcomplex of length 3 taken from longer chain
complexes. This point of view hints at constructing codes out of two chain
complexes, as short as length 2, using the homological product of chain
complexes. Length 2 chain complexes then just correspond to classical codes.
This was first proposed by Tillich and Zemor in [38] under the name hypergraph
product codes. Generalizations and further studies of this construction have
been made to consider longer initial chain complexes in [5, 3].

More specifically, we can derive the hypergraph product code from a pair of
classical parity-check matrices $H_{1}$ and $H_{2}$. If we interpret these
binary matrices as length 2 chain complexes, then the hypergraph product code
is described as depicted in Figure 3.

Figure 3: “Chain complex” representation of the hypergraph product code. The
$x$ label corresponds to the operator $H_{1}\otimes\mathbbm{1}$ and the $y$
label corresponds to the operator $\mathbbm{1}\otimes H_{2}$.

We identify the resulting vector spaces with matrices or 2-tensors $A$, $B$,
$S$ and $T$. If $H_{i}$ has dimension $m_{i}\times n_{i}$, for $i=1,2$, then
these tensors have dimensions

$A\in\mathbbm{F}_{2}^{n_{1}\times n_{2}},\quad
B\in\mathbbm{F}_{2}^{m_{2}\times m_{3}},\quad S\in\mathbbm{F}_{2}^{m_{1}\times
n_{2}},\quad T\in\mathbbm{F}_{2}^{n_{1}\times m_{2}}.$

The boundary operators indexed $x$ and $y$ correspond to operators
$H_{1}\otimes\mathbbm{1}$ and $\mathbbm{1}\otimes H_{2}$. The boundary
operators of the resulting chain complex are hence
$\partial=[H_{1}\otimes\mathbbm{1},\mathbbm{1}\otimes H_{2}]^{T}$ and
$\partial^{\prime}=[\mathbbm{1}\otimes H_{2},H_{1}\otimes\mathbbm{1}]$, and we
have the boundary condition $\partial^{\prime}\,\partial=2H_{1}\otimes
H_{2}=0$.

We can derive a quantum code from this chain complex by associating qubits to
the matrix elements of $A$ and $B$, and checks to the matrix elements of $S$
and $T$. We will describe a general check on the qubits in $A$ and $B$ by a
tensor over the Pauli group

$\begin{bmatrix}{\cal A}\\\ {\cal
B}\end{bmatrix}\in\begin{bmatrix}\mathcal{P}^{n_{1}\times n_{2}}\\\
\mathcal{P}^{m_{1}\times m_{2}}\end{bmatrix}.$

The checks are generated by the binary tensors $S$ and $T$. Usually the code
is chosen to be of the CSS type by choosing one between $S$ and $T$ to
represent $X$-type checks and the other $Z$-type checks. Here we are going to
consider a Clifford equivalent code which will generalize more easily to the
XYZ product codes with checks of mixed $X$ and $Y$ types. The checks generated
by $S$ correspond to $\sigma_{1}$ checks on the qubits in $A$ with pattern
$(H_{1}^{T}\otimes\mathbbm{1})S$, and $\sigma_{2}$ checks on the qubits in $B$
with pattern $(\mathbbm{1}\otimes H_{2})S$. Similarly, the checks from $T$
correspond to $\sigma_{1}$ checks on $B$ with pattern
$(H_{1}\otimes\mathbbm{1})T$ and $\sigma_{2}$ checks on $A$ with pattern
$(\mathbbm{1}\otimes H_{2}^{T})T$. For a general check $(S,T)$, we use the
shorthand

$\begin{bmatrix}{\cal A}\\\ {\cal
B}\end{bmatrix}=\begin{bmatrix}\sigma_{1}^{(H_{1}^{T}\otimes\mathbbm{1})S}\;\sigma_{2}^{(\mathbbm{1}\otimes
H_{2}^{T})T}\\\ \sigma_{2}^{(\mathbbm{1}\otimes
H_{2})S}\;\sigma_{1}^{(H_{1}\otimes\mathbbm{1})T}\end{bmatrix}.$

We will often write this more abstractly as

$\begin{bmatrix}{\cal A}\\\ {\cal
B}\end{bmatrix}=\begin{bmatrix}\mathcal{X}^{\dagger}&\mathcal{Y}^{\dagger}\\\
\mathcal{Y}&\mathcal{X}\end{bmatrix}\begin{bmatrix}S\\\ T\end{bmatrix}$

where we introduce the operators
$\mathcal{X}=\sigma_{1}^{H_{1}\otimes\mathbbm{1}}$ and
$\mathcal{Y}=\sigma_{2}^{\mathbbm{1}\otimes H_{2}}$. We let a dagger
$\mathcal{X}^{\dagger}$ denote
$\mathcal{X}^{\dagger}=\sigma_{1}^{H_{1}^{T}\otimes\mathbbm{1}}$, a product
$\mathcal{X}S$ should be interpreted as
$\sigma_{1}^{(H_{1}\otimes\mathbbm{1})S}$ and a sum
$\mathcal{Y}S+\mathcal{X}T$ corresponds to a product
$\sigma_{2}^{(\mathbbm{1}\otimes
H_{2})S}\;\sigma_{1}^{(H_{1}\otimes\mathbbm{1})T}$.

Pairs of checks indexed by tensors of the type $(S,0)$ and $(S^{\prime},0)$
(or $(0,T)$ and $(0,T^{\prime})$) always commute as they are the same Pauli
type on the same blocks. One then simply needs to check that any pair of
checks, indexed by tensors $(S,0)$ and $(0,T)$, also commutes. Note first that
for any 2-tensors $A$ and $B$, it holds that

$[\sigma_{1}^{A},\sigma_{2}^{B}]=(-1)^{\sum_{i,j}A_{ij}B_{ij}}\mathbbm{1}=(-1)^{\mathrm{tr}(A^{T}B)}\mathbbm{1},$

since the corresponding operators anticommute iff the supports of $A$ and $B$
have an odd overlap. The commutator of the tensors indexed by $(S,0)$ and
$(0,T)$, given by

$\begin{bmatrix}{\cal A}_{1}\\\ {\cal
B}_{1}\end{bmatrix}=\begin{bmatrix}\sigma_{1}^{(H_{1}^{T}\otimes\mathbbm{1})S}\\\
\sigma_{2}^{(\mathbbm{1}\otimes
H_{2})S}\end{bmatrix},\qquad\begin{bmatrix}{\cal A}_{2}\\\ {\cal
B}_{2}\end{bmatrix}=\begin{bmatrix}\sigma_{2}^{(\mathbbm{1}\otimes
H_{2}^{T})T}\\\ \sigma_{1}^{(H_{1}\otimes\mathbbm{1})T}\end{bmatrix},$

can be computed as follows:

$\displaystyle\left[\begin{bmatrix}{\cal A}_{1}\\\ {\cal
B}_{1}\end{bmatrix},\begin{bmatrix}{\cal A}_{2}\\\ {\cal
B}_{2}\end{bmatrix}\right]$
$\displaystyle=(-1)^{\mathrm{tr}(S^{T}(H_{1}\otimes\mathbbm{1})(\mathbbm{1}\otimes
H_{2}^{T})T+S^{T}(\mathbbm{1}\otimes
H_{2}^{T})(H_{1}\otimes\mathbbm{1})T)}\mathbbm{1}=\mathbbm{1}.$

Remark that if the two classical codes $H_{1}$ and $H_{2}$ are repetition
codes then one gets the so called $XZZX$ toric code (or more precisely $XYYX$
here) that has been recently highlighted for its good performance against all
types of Pauli noise [2].

##  3 The XYZ product code construction

###  3.1 XYZ product code

The XYZ product code construction is a generalization of the hypergraph
product code involving a third classical code which will enforce Pauli
$Y$-type constraints, thus making the quantum code _not CSS_. Given three
parity-check matrices $H_{1}$, $H_{2}$ and $H_{3}$, we again start by defining
a chain complex, depicted in Figure 4.

Figure 4: “Chain complex” representation of the XYZ product codes. The $x$
label corresponds to the operator $H_{1}\otimes\mathbbm{1}\otimes\mathbbm{1}$,
the $y$ label to the operator $\mathbbm{1}\otimes H_{2}\otimes\mathbbm{1}$ and
the $z$ label to the operator $\mathbbm{1}\otimes\mathbbm{1}\otimes H_{3}$.

We proceed similarly to the hypergraph product code construction. We identify
the resulting vector spaces with 3-tensors

$A\in\mathbbm{F}_{2}^{n_{1}\times n_{2}\times n_{3}},\quad
B\in\mathbbm{F}_{2}^{n_{1}\times m_{2}\times m_{3}},\quad
C\in\mathbbm{F}_{2}^{m_{1}\times n_{2}\times m_{3}},\quad
D\in\mathbbm{F}_{2}^{m_{1}\times m_{2}\times n_{3}},$

which will index the qubits, and 3-tensors

$S\in\mathbbm{F}_{2}^{m_{1}\times n_{2}\times n_{3}},\quad
T\in\mathbbm{F}_{2}^{n_{1}\times m_{2}\times n_{3}},\quad
U\in\mathbbm{F}_{2}^{n_{1}\times n_{2}\times m_{3}},\quad
V\in\mathbbm{F}_{2}^{m_{1}\times m_{2}\times m_{3}},$

which will index the checks. The total number of qubits is

$\displaystyle
N=\underbrace{n_{1}n_{2}n_{3}}_{n_{A}}+\underbrace{n_{1}m_{2}m_{3}}_{n_{B}}+\underbrace{m_{1}n_{2}m_{3}}_{n_{C}}+\underbrace{m_{1}m_{2}n_{3}}_{n_{D}}.$
(8)

A general stabilizer element is a tensor over the Pauli group written
abstractly as

$\displaystyle\begin{bmatrix}{\cal A}\\\ {\cal B}\\\ {\cal C}\\\ {\cal
D}\end{bmatrix}=\begin{bmatrix}\mathcal{X}^{\dagger}&\mathcal{Y}^{\dagger}&\mathcal{Z}^{\dagger}&\cdot\\\
\mathcal{Y}&\mathcal{X}&\cdot&\mathcal{Z}^{\dagger}\\\
\mathcal{Z}&\cdot&\mathcal{X}&\mathcal{Y}^{\dagger}\\\
\cdot&\mathcal{Z}&\mathcal{Y}&\mathcal{X}^{\dagger}\end{bmatrix}\begin{bmatrix}S\\\
T\\\ U\\\ V\end{bmatrix}=:\Gamma(S,T,U,V).$ (9)

Here we introduced the operators555We repeat that the dimension of the
identity operator $\mathbbm{1}$ will vary depending on the context.

$\mathcal{X}=\sigma_{1}^{H_{1}\otimes\mathbbm{1}\otimes\mathbbm{1}},\qquad\mathcal{Y}=\sigma_{2}^{\mathbbm{1}\otimes
H_{2}\otimes\mathbbm{1}},\qquad\mathcal{Z}=\sigma_{3}^{\mathbbm{1}\otimes\mathbbm{1}\otimes
H_{3}}.$

We again use the convention that an adjoint $\mathcal{X}^{\dagger}$ denotes
the operator
$\mathcal{X}^{\dagger}=\sigma_{1}^{H_{1}^{T}\otimes\mathbbm{1}\otimes\mathbbm{1}}$,
a product $\mathcal{Y}S$ denotes $\sigma_{2}^{(\mathbbm{1}\otimes
H_{2}\otimes\mathbbm{1})S}$, and a sum $\mathcal{Y}S+\mathcal{X}T$ denotes the
product $\sigma_{2}^{(\mathbbm{1}\otimes
H_{2}\otimes\mathbbm{1})S}\sigma_{1}^{(H_{1}\otimes\mathbbm{1}\otimes\mathbbm{1})T}$.
We call the resulting stabilizer code the XYZ product code, and we refer to it
by the shorthand ${\cal Q}(H_{1},H_{2},H_{3})$. In Figure 5 we give a slightly
alternative representation of the code or chain complex. It better reflects
how we will be able to embed the code into 3D for certain choices of
$H_{i}$’s.

Figure 5: 3D structure of the XYZ product code: qubits indexed by the
3-tensors $A,B,C,D$, generators by $S,T,U,V$.

Let us establish that the resulting stabilizer group is Abelian.

######  Lemma 3.

The stabilizer group of the XYZ product code is Abelian.

As noted before, one also needs to prove that $-\mathbbm{1}$ is not in the
stabilizer group to show that the code is readily a well defined stabilizer
code. This question turns out to be rather subtle and we will discuss two
possible solutions in the following: fixing the $\pm 1$ phases of the
generators, or considering the CSS version of the XYZ product code (see
Sections 3.2 and 3.3 for details).

###### Proof.

With $\Gamma$ as in (9), consider two arbitrary elements of the stabilizer

$({\cal A}_{1},{\cal B}_{1},{\cal C}_{1},{\cal
D}_{1})^{T}=\Gamma(S_{1},T_{1},U_{1},V_{1})\quad\text{ and }\quad({\cal
A}_{2},{\cal B}_{2},{\cal C}_{2},{\cal
D}_{2})^{T}=\Gamma(S_{2},T_{2},U_{2},V_{2}).$

We can compute their commutator:

$\displaystyle[({\cal A}_{1},{\cal B}_{1},{\cal C}_{1},{\cal
D}_{1})^{T},({\cal A}_{2},{\cal B}_{2},{\cal C}_{2},{\cal D}_{2})^{T}]$
$\displaystyle=[({\cal A}_{1},{\cal B}_{1})^{T},({\cal A}_{2},{\cal
B}_{2})^{T}]+[({\cal A}_{1},{\cal C}_{1})^{T},({\cal A}_{2},{\cal
C}_{2})^{T}]$ $\displaystyle\quad+[({\cal A}_{1},{\cal D}_{1})^{T},({\cal
A}_{2},{\cal D}_{2})^{T}]+[({\cal B}_{1},{\cal C}_{1})^{T},({\cal B}_{2},{\cal
C}_{2})^{T}]$ $\displaystyle\quad+[({\cal B}_{1},{\cal D}_{1})^{T},({\cal
B}_{2},{\cal D}_{2})^{T}]+[({\cal C}_{1},{\cal D}_{1})^{T},({\cal C}_{2},{\cal
D}_{2})^{T}].$

Now each of these small commutators corresponds to a commutator between
$X$-type and $Z$-type generators in the standard hypergraph product code
construction (see Section 2.2). Consequently they all vanish. ∎

We can alternatively use the notation $({\cal A},{\cal B},{\cal C},{\cal
D})\in\mathcal{P}^{n_{A}+n_{B}+n_{C}+n_{D}}$ to denote a Pauli error. Its
syndrome can then be abstractly written as

$\begin{bmatrix}S\\\ T\\\ U\\\
V\end{bmatrix}=\begin{bmatrix}\mathcal{X}&\mathcal{Y}^{\dagger}&\mathcal{Z}^{\dagger}&\cdot\\\
\mathcal{Y}&\mathcal{X}^{\dagger}&\cdot&\mathcal{Z}^{\dagger}\\\
\mathcal{Z}&\cdot&\mathcal{X}^{\dagger}&\mathcal{Y}^{\dagger}\\\
\cdot&\mathcal{Z}&\mathcal{Y}&\mathcal{X}\end{bmatrix}*\begin{bmatrix}{\cal
A}\\\ {\cal B}\\\ {\cal C}\\\ {\cal
D}\end{bmatrix}=:\Sigma*\begin{bmatrix}{\cal A}\\\ {\cal B}\\\ {\cal C}\\\
{\cal D}\end{bmatrix}.$

We call $\Sigma$ the “parity-check” operator of the XYZ product code. The star
product $*$ between a pair of Pauli operators is

$\sigma_{i}*\sigma_{j}=\delta_{i\neq j},$

and we extend it to a pair of tensors of equal size (say $\mathcal{X}*{\cal
A}$) by taking the star product elementwise. The product gives 0 where two
Pauli operators commute, and it gives 1 where they commute. This implies that
$\mathcal{X}$ detects only errors that do not commute with $X$ (and similarly
for $\mathcal{Y}$, $\mathcal{Z}$).

Now we can check that the syndrome of a stabilizer vanishes by computing the
operator $\Sigma*\Gamma$:

$\Sigma*\Gamma=\left[\begin{smallmatrix}\mathcal{X}*\mathcal{X}^{\dagger}+\mathcal{Y}^{\dagger}*\mathcal{Y}+\mathcal{Z}^{\dagger}*\mathcal{Z}&\mathcal{X}*\mathcal{Y}^{\dagger}+\mathcal{Y}^{\dagger}*\mathcal{X}&\mathcal{X}*\mathcal{Z}^{\dagger}+\mathcal{Z}^{\dagger}*\mathcal{X}&\mathcal{Y}^{\dagger}*\mathcal{Z}^{\dagger}+\mathcal{Z}^{\dagger}*\mathcal{Y}^{\dagger}\\\
\mathcal{X}^{\dagger}*\mathcal{Y}+\mathcal{Y}*\mathcal{X}^{\dagger}&\mathcal{X}^{\dagger}*\mathcal{X}+\mathcal{Y}^{\dagger}*\mathcal{Y}+\mathcal{Z}*\mathcal{Z}^{\dagger}&\mathcal{Y}*\mathcal{Z}^{\dagger}+\mathcal{Z}^{\dagger}*\mathcal{Y}&\mathcal{X}^{\dagger}*\mathcal{Z}^{\dagger}+\mathcal{Z}^{\dagger}*\mathcal{X}^{\dagger}\\\
\mathcal{X}^{\dagger}*\mathcal{Z}+\mathcal{Z}*\mathcal{X}^{\dagger}&\mathcal{Y}^{\dagger}*\mathcal{Z}+\mathcal{Z}*\mathcal{Y}^{\dagger}&\mathcal{X}^{\dagger}*\mathcal{X}+\mathcal{Y}^{\dagger}*\mathcal{Y}+\mathcal{Z}*\mathcal{Z}^{\dagger}&\mathcal{X}^{\dagger}*\mathcal{Y}^{\dagger}+\mathcal{Y}^{\dagger}*\mathcal{X}^{\dagger}\\\
\mathcal{Y}*\mathcal{Z}+\mathcal{Z}*\mathcal{Y}&\mathcal{X}*\mathcal{Z}+\mathcal{Z}*\mathcal{X}&\mathcal{X}*\mathcal{Y}+\mathcal{Y}*\mathcal{X},&\mathcal{X}*\mathcal{X}^{\dagger}+\mathcal{Y}*\mathcal{Y}^{\dagger}+\mathcal{Z}*\mathcal{Z}^{\dagger}\end{smallmatrix}\right]=0,$

where we used that e.g. $\mathcal{X}*\mathcal{X}^{T}=0$ (because the
$\sigma_{1}$-operators commute) and that
$\mathcal{X}*\mathcal{Y}+\mathcal{Y}*\mathcal{X}=2\mathcal{X}*\mathcal{Y}=0$
(recall that the dimensions of $\mathcal{X}$ depend on its position in the
matrix).

###  3.2 The case of $-\mathbbm{1}\in\mathcal{S}$

The usual prescription to define a stabilizer code is to pick an Abelian
subgroup of the $n$-qubit Pauli group $\mathcal{S}\subset\mathcal{P}_{n}$
which does not contain $-\mathbbm{1}$. With such a choice it is guaranteed
that there exists a common $+1$ eigenspace to all the elements of
$\mathcal{S}$ which is defined to be the code space. As mentioned above, for
the XYZ product code construction, we are only able to prove that
$-\mathbbm{1}\not\in\mathcal{S}$ in some restricted cases. We show however,
that $-\mathbbm{1}\in\mathcal{S}$ is not in fact a problem to define a code.

If $\mathcal{S}$ contains $-\mathbbm{1}$ then there cannot be a common
$+1$-eigenspace to all the elements in $\mathcal{S}$. Nevertheless, the
generators of $\mathcal{S}$ are Hermitian operators, i.e., observables of the
system, and the fact that $\mathcal{S}$ is Abelian ensures that they are all
simultaneously diagonalizable and can therefore be measured simultaneously.
That $-\mathbbm{1}$ is in $\mathcal{S}$ simply prevents the measurement
outcomes to all be $+1$. To still use such a group to define a code one just
has to settle on a consistent convention for which elements of $\mathcal{S}$
should yield $+1$ and which ones $-1$ when measured.

To explain in more details how to make this choice consider an Abelian
subgroup $\mathcal{S}\subset\mathcal{P}_{n}$ which contains $-\mathbbm{1}$. We
can consider $\mathcal{S}$ up to phases by looking at the quotient subgroup
$\mathcal{S}^{\pm}=\mathcal{S}/\langle-\mathbbm{1}\rangle$, since
$\langle-\mathbbm{1}\rangle$ is a normal subgroup of $\mathcal{S}$. We can
first pick an independent generating set for $\mathcal{S}^{\pm}$:

$\left\langle
g^{\pm}_{1},\ldots,g^{\pm}_{n-k}\right\rangle=\mathcal{S}^{\pm}.$ (10)

Then for each generator $g^{\pm}_{i}\in\mathcal{S}^{\pm}$ choose any
corresponding representative $g_{i}\in\mathcal{S}$ (there are two choices
$g_{i}$ and $-g_{i}$). They give directly an independent generating set for
$\mathcal{S}$:

$\mathcal{S}=\left\langle-\mathbbm{1},g_{1},\ldots,g_{n-k}\right\rangle.$

The subgroup $\tilde{\mathcal{S}}=\left\langle
g_{1},\ldots,g_{n-k}\right\rangle$ is a valid stabilizer subgroup of
$\mathcal{S}$ since it does not contain $-\mathbbm{1}$ (by the independence
assumption on the $g_{i}$’s) and we can finally define the code to be the
stabilizer code stabilized by $\tilde{\mathcal{S}}$. If the initial
$\mathcal{S}$ was given by an original generating set

$\mathcal{S}=\left\langle g_{1}^{\rm orig.},\ldots,g_{m}^{\rm
orig.}\right\rangle,$

for some $m$, then for each of them, either $+g_{i}^{\rm
orig.}\in\tilde{\mathcal{S}}$ or $-g_{i}^{\rm orig.}\in\tilde{\mathcal{S}}$
and checking which is the case allows to keep the original checks and sets the
convention to be adopted for syndrome measurements and error correction. The
dimension of the code is given by the number of independent generators of
$\mathcal{S}^{\pm}$ and is independent of the choice of signs for
$\tilde{\mathcal{S}}$, provided that they are consistent. Similarly the
minimal distance is independent of the choice of signs, since commutation
relations are not modified by signs, so that the parameters $\llbracket
n,k,d\rrbracket$ are always well defined even if $-\mathbbm{1}\in\mathcal{S}$.

A practical way to obtain a basis for $\mathcal{S}^{\pm}$ in (10) is to use
the mapping to CSS codes described below in Section 3.3, Eq. (11). This
mapping forgets phases and allows one to simply find a basis for
$\mathcal{S}^{\pm}$ using standard binary linear algebra.

###  3.3 A CSS version of the construction

The XYZ product code construction yields a stabilizer code which is not CSS.
In particular each generator involves all three Pauli matrices. Besides there
is no generic transversal Clifford operation that can transform it into a CSS
code since each qubit is a priori acted on by different stabilizer generators
with the three different types of Pauli. However, the potentially good
asymptotic parameters of the XYZ product code are not tied to this non-CSS
nature, and we can in fact derive a CSS code with the same parameters up to
constant factors. A recipe to turn any $\llbracket n,k,d\rrbracket$ stabilizer
code into a $\llbracket 4n,2k,d\rrbracket$ CSS stabilizer code was devised in
[7] using a Majorana fermion code as an intermediary code. The transformation
also preserves locality and LDPC properties. We recall it here directly,
skipping the intermediary Majorana fermion code.

The gist of the idea is to emulate the one-qubit Pauli group (ignoring phases)
with just one type of Pauli operators acting on four qubits using the
following mapping that we denote $\phi_{i}$ for $i\in\\{1,2,3\\}$ for each
choice of Pauli:

$\begin{tabular}[]{l c c
c}$\phi_{i}:$&$\mathcal{P}$&$\longrightarrow$&$\mathcal{P}^{\otimes 4}$\\\
&$\mathbbm{1}$&$\mapsto$&$\mathbbm{1}\otimes\mathbbm{1}\otimes\mathbbm{1}\otimes\mathbbm{1}$\\\
&$\sigma_{1}$&$\mapsto$&$\sigma_{i}\otimes\sigma_{i}\otimes\mathbbm{1}\otimes\mathbbm{1}$\\\
&$\sigma_{2}$&$\mapsto$&$\sigma_{i}\otimes\mathbbm{1}\otimes\sigma_{i}\otimes\mathbbm{1}$\\\
&$\sigma_{3}$&$\mapsto$&$\sigma_{i}\otimes\mathbbm{1}\otimes\mathbbm{1}\otimes\sigma_{i}$\end{tabular}.$
(11)

Note that the product of the three mapped Pauli operators is the four-body
Pauli $\sigma_{i}\otimes\sigma_{i}\otimes\sigma_{i}\otimes\sigma_{i}$. This
indicates that this operator should be enforced as a stabilizer. With this
stabilizer taken into account, the mapping correctly reproduces the
multiplicative law of the group but not the commutation relations which become
trivial. The commutation relation between two mapped elements with a different
choice of Pauli for the mapping are correctly reproduced

$\displaystyle\forall
i,j,k,\ell\in\\{1,2,3\\}\quad\phi_{i}(\sigma_{j})\phi_{k}(\sigma_{\ell})$
$\displaystyle=(-1)^{\delta_{i\neq
k}\delta_{j\neq\ell}}\phi_{k}(\sigma_{\ell})\phi_{i}(\sigma_{j})$ (12)
$\displaystyle\phi_{i}(\mathbbm{1})\phi_{k}(\sigma_{\ell})$
$\displaystyle=\phi_{k}(\sigma_{\ell})\phi_{i}(\mathbbm{1}).$ (13)

The mapping can be straightforwardly extended to the multi-qubit Pauli group
mapping independently each single-qubit Pauli which we also denote
$\phi_{i}:\mathcal{P}^{\otimes n}\longrightarrow\mathcal{P}^{\otimes 4n}$.

We can now describe the transformation from a $\llbracket n,k,d\rrbracket$
stabilizer code $\mathcal{C}$ to a $\llbracket
n_{\text{CSS}}=4n,k_{\text{CSS}}=2k,d_{\text{CSS}}=2d\rrbracket$ CSS code
$\mathcal{C}_{\text{CSS}}$ in three steps:

  1. 1.

For each qubit of the original code, create four qubits.

  2. 2.

Enforce $\sigma_{1}\otimes\sigma_{1}\otimes\sigma_{1}\otimes\sigma_{1}$ and
$\sigma_{3}\otimes\sigma_{3}\otimes\sigma_{3}\otimes\sigma_{3}$ as stabilizers
on each group of four qubits created.

  3. 3.

For each stabilizer generator of the original code, say
$S\in\mathcal{P}^{\otimes n}$, enforce $\phi_{1}(S)$ and $\phi_{3}(S)$ as
stabilizers.

The number of qubits in the new code is indeed $n_{\text{CSS}}=4n$. It is a
valid stabilizer code per Eqn. (12) and (13) and it is CSS since all the
stabilizers created with $\phi_{1}$ are fully $X$-type and the ones created
with $\phi_{3}$ fully $Z$-type. To compute the dimension of the new code we
have to count the number of independent stabilizers. The four body stabilizers
added at step 2 form $2n$ independent stabilizers. With these stabilizers
taken into account, the mapping then correctly reproduces the multiplicative
law of the Pauli group, hence step 3 creates twice as many independent
stabilizers as in the original code, that is $2(n-k)$. This makes for
$k_{\text{CSS}}=4n-2n-2(n-k)=2k$ logical qubits. Finally for the distance, any
logical Pauli operator of $\mathcal{C}_{\text{CSS}}$ has to commute with the
four-body checks of step 2 and hence act on an even number of qubits from each
group of four representing one original qubit. Hence it can always be mapped
to a logical operator of the original code which has to have weight at least
$d$ and we conclude that $d_{\text{CSS}}=2d$.

This establishes the following:

######  Lemma 4 ([7]).

A $\llbracket n,k,d\rrbracket$ stablizer code can be mapped to a $\llbracket
4n,2k,d\rrbracket$ CSS code with generator weights not larger than twice the
weights of the original code.

This results apply directly to XYZ products codes when
$-\mathbbm{1}\not\in\mathcal{S}$. In the case where
$-\mathbbm{1}\in\mathcal{S}$ the initial stabilizer code with parameters
$\llbracket n,k,d\rrbracket$ to consider is any given by a consistent choice
of signs for the generators as explained in Sec. 3.2. The mapping to a CSS
code with parameters $\llbracket 4n,2k,2d\rrbracket$ can be directly applied
to the original set of generators as the mapping forgets phases.

###  3.4 Comparison with 3-fold Hypergraph Product codes

Other approaches have used the structure given by $\mathbb{F}_{2}$ chain
complexes, including ones build from $D$-fold hypergraph products, in order to
build quantum stabilizer codes such as D-dimensional color codes [4] or
quantum pin codes [39] but our approach is completely different here. The
3-fold hypergraph product code construction described for instance in Refs.
[41, 42, 32] is maybe the closest to the XYZ product code construction and we
now explain how they differ.

The 3-fold hypergraph product code makes use of the same chain complex
structure as described in Figure 4, although not in the same way. First it
discards one of the ends of the complex, say $A$, and associates qubits with
only one level of the complex: the blocks $B$, $C$ and $D$ here. Then one uses
the blocks $S$, $T$ and $U$ as $Z$-type stabilizers and block $V$ as $X$-type
stabilizers with exactly the same incidence structure but therefore different
Pauli operators.

One can also take as an example the difference between the 3D toric code and
the Chamon code which are instances of 3-fold hypergraph products and XYZ
product codes respectively when the three classical codes are repetition
codes. In that case the chain complex is most conveniently described by a 3D
cubic lattice where $A$ are the vertices; $S$, $T$ and $U$ are the edges in
the $x$, $y$ and $z$ directions respectively; $B$, $C$ and $D$ are the faces
perpendicular to the $x$, $y$ and $z$ directions respectively; and $V$ are the
cubes. This is schematically represented in Figure 6. On this structure the 3D
toric code consists in putting qubits on the faces, $Z$-checks on the four
faces surrounding each edge and $X$-checks on the six faces surrounding each
cube, see Figure 6 on the left. On the other hand, the Chamon code consists in
putting qubits on the faces as well as on the vertices and having checks
defined by the edges and cubes in the following way. Each cube, or edge
respectively, is surrounded by six faces, or four faces and two vertices
respectively. The checks act with the Pauli $X$, $Y$ or $Z$ respectively, on
the elements away from them in the $x$, $y$ or $z$ direction respectively, see
Figure 6 on the right.

Figure 6: Geometrical interpretation of the blocks when the three classical
codes are repetition codes as well as the Pauli operator chosen for the
stabilizer of the 3D toric code left and Chamon code right.

When the three classical codes are local in 1D then both construction will
therefore be local in 3D, using for example this cubic lattice to lay out the
qubits. We will study these configurations in detail in Sections 6 and 7.

##  4 Dimension of the XYZ product codes

In this section, we compute the dimension of the XYZ product codes by finding
the number of independent generators. As mentioned before, the XYZ product
code is readily well defined if it can be shown that $-\mathbbm{1}$ does not
belong to the stabilizer group. If it were the case that $-\mathbbm{1}$ is in
the group then the following result would apply to the stabilizer code
obtained from consistently choosing the signs of the generators to turn it
into a stabilizer group (see Section 3.2) or with a factor $2$ to the mapped
CSS version of the code (see Section 3.3).

If $r$ is the number of “relations” between the generators, then the number of
independent generators is $n_{S}+n_{T}+n_{U}+n_{V}-r$. The dimension $k$ of
the code is then given by the formula

$\displaystyle k$
$\displaystyle=n_{A}+n_{B}+n_{C}+n_{D}-n_{S}-n_{T}-n_{U}-n_{V}+r$
$\displaystyle=(n_{1}-m_{1})(n_{2}-m_{2})(n_{3}-m_{3})+r.$

Specific to the XYZ product code is the occurrence of nontrivial relations
between generators of different type. This is because there are generators of
$\sigma_{1}$, $\sigma_{2}$ as well as $\sigma_{3}$ type, and we have that
$\sigma_{1}\sigma_{2}\sigma_{3}\propto\mathbbm{1}$. This does not occur in CSS
constructions. Specifically we find a relation between a set of generators if
the $\sigma_{1}$-, the $\sigma_{2}$\- and the $\sigma_{3}$-checks coincide in
each of the blocks. This corresponds to a solution $(S,T,U,V)$ of the “Pauli
system”

$\begin{bmatrix}\mathcal{X}^{\dagger}&\mathcal{Y}^{\dagger}&\mathcal{Z}^{\dagger}&\cdot\\\
\mathcal{Y}&\mathcal{X}&\cdot&\mathcal{Z}^{\dagger}\\\
\mathcal{Z}&\cdot&\mathcal{X}&\mathcal{Y}^{\dagger}\\\
\cdot&\mathcal{Z}&\mathcal{Y}&\mathcal{X}^{\dagger}\end{bmatrix}\begin{bmatrix}S\\\
T\\\ U\\\
V\end{bmatrix}=\begin{bmatrix}(\mathcal{X}^{\dagger}S)(\mathcal{Y}^{\dagger}T)(\mathcal{Z}^{\dagger}U)\\\
(\mathcal{Y}S)(\mathcal{X}T)(\mathcal{Z}^{\dagger}V)\\\
(\mathcal{Z}S)(\mathcal{X}U)(\mathcal{Y}^{\dagger}V)\\\
(\mathcal{Z}T)(\mathcal{Y}U)(\mathcal{X}^{\dagger}V)\end{bmatrix}\propto\mathbbm{1}.$

Now consider the shorthand notation
$H_{1}=H_{1}\otimes\mathbbm{1}_{\ell_{2}}\otimes\mathbbm{1}_{\ell_{3}}$,
$H_{2}=\mathbbm{1}_{\ell_{1}}\otimes H_{2}\otimes\mathbbm{1}_{\ell_{3}}$ and
$H_{3}=\mathbbm{1}_{\ell_{1}}\otimes\mathbbm{1}_{\ell_{2}}\otimes H_{3}$,
where $\ell_{i}\in\\{n_{i},m_{i}\\}$ will be chosen so that the dimensions
match, similar to the previous section. Then e.g. the condition
$(\mathcal{X}^{\dagger}S)(\mathcal{Y}^{\dagger}T)(\mathcal{Z}^{\dagger}U)\propto\mathbbm{1}$
becomes equivalent to $H_{1}^{T}S=H_{2}^{T}T=H_{3}^{T}U$. By the same
argument, we can reexpress the “Pauli system” using the linear system (over
$\mathbb{F}_{2}$)

$\displaystyle H_{1}^{T}S$ $\displaystyle=H_{2}^{T}T$
$\displaystyle=H_{3}^{T}U$ (14) $\displaystyle H_{1}T$ $\displaystyle=H_{2}S$
$\displaystyle=H_{3}^{T}V$ $\displaystyle H_{1}U$ $\displaystyle=H_{2}^{T}V$
$\displaystyle=H_{3}S$ $\displaystyle H_{1}^{T}V$ $\displaystyle=H_{2}U$
$\displaystyle=H_{3}T$

We only managed to determine the number of solutions to this linear system
(and hence the code dimension) under certain constraints on the parity-check
matrices. The following theorem is a special case (which follows from
combining Corollary 8 with Theorem 9), and it nicely demonstrates the
algebraic nature of the code family. We let $p^{\ell}_{i}$ denote the
characteristic polynomial of the $i$-th Jordan block (over the algebraic
closure $\overline{\mathbb{F}}_{2}$) of $H_{\ell}H_{\ell}^{T}$, for
$\ell=1,2,3$.

######  Theorem 2.

If the parity-check matrices $H_{1}$, $H_{2}$ and $H_{3}$ are invertible, then
the dimension of the XYZ product code is equal to the number of solutions of
the tensor Sylvester equation

$H_{1}H_{1}^{T}X=H_{2}H_{2}^{T}X=H_{3}H_{3}^{T}X,$

which is equal to

$\sum_{i,j,k}\mathrm{deg}(\mathrm{gcd}(p^{1}_{i},p^{2}_{j},p^{3}_{k})).$

Using the more elementary notion of similarity invariant from abstract algebra
[33], this can be equivalently expressed as

$\sum_{i,j,k}\mathrm{deg}(\mathrm{gcd}(h^{1}_{i},h^{2}_{j},h^{3}_{k})),$

where $h^{\ell}_{1},\dots,h^{\ell}_{n}$ are the similarity invariants of
$H_{\ell}H_{\ell}^{T}$ for $\ell=1,2,3$. From Theorem 2 we get the following
corollary, which provides a useful condition for the code to have dimension 1.

######  Corollary 5.

If the parity-check matrices $H_{1}$, $H_{2}$ and $H_{3}$ are invertible and
the matrices $H_{1}H_{1}^{T},H_{2}H_{2}^{T}$ and $H_{3}H_{3}^{T}$ have a
unique common eigenvalue 1, each with geometric multiplicity 1, then the XYZ
product code has dimension 1.

Before going into the proofs, we comment on some obstacles towards a full
solution of the dimension question. We feel that also in the general, non-
invertible case the dimension will be largely determined by the tensor
Sylvester equation. Indeed, if we consider (14) over the complex numbers
instead of over $\mathbb{F}_{2}$, then we can use the Moore-Penrose pseudo-
inverse in the proof of Claim 7 to show that a solution to the Sylvester
equation always implies a solution to the full system. Over $\mathbb{F}_{2}$,
however, there does not exist in general a Moore-Penrose inverse, and the
argument breaks down. This is closely tied to the fact that over
$\mathbb{F}_{2}$ potentially
$\mathrm{rank}(H_{1})>\mathrm{rank}(H_{1}H_{1}^{T})$ (e.g., if
$H_{1}=[1\,1]$), see [40]. As a consequence, the Sylvester equation (involving
terms $H_{\ell}H_{\ell}^{T}$) no longer captures the “full picture”. Indeed,
if say $H_{1}=[1\,1],H_{2}=H_{3}=0$, then the (trivial) Sylvester equation has
a nonzero solution whereas the original system does not. In some sense, this
suggests that homological tools (in addition to the algebraic ones) might be
useful. Indeed, the extremal case $H_{1}H_{1}^{T}=0$ for $H_{1}\neq 0$
describes precisely the boundary condition of a chain complex, so that the
rank deficiency of $H_{1}H_{1}^{T}$ might signal nontrivial homological
properties.

Let us also mention here what needs to be proven to establish that the non-CSS
version of an XYZ product code is a valid stabilizer code. As already pointed
out, this would follow from the fact that $-\mathbbm{1}$ does not belong to
the stabilizer group. Any relation among the generators corresponds to a
choice of $(S,T,U,V)$ such that (14) holds. Assuming such a choice and
denoting by $n_{A},n_{B},n_{C},n_{D}$ the Hamming weight of the tensors
appearing in each of the 4 equations and $g_{S},g_{T},g_{U},g_{V}$ the
products of the generators of type $S,T,U,V$ among the relation, we want to
check that

$g_{S}g_{T}g_{U}g_{V}=\mathbbm{1}.$

Note that such a relation involves $n_{A}$ products of type
$\sigma_{1}\sigma_{2}\sigma_{3}=i\mathbbm{1}$ in $A$, $n_{B}$ products of type
$\sigma_{2}\sigma_{1}\sigma_{3}=-i\mathbbm{1}$ in $B$, $n_{C}$ products of
type $\sigma_{3}\sigma_{1}\sigma_{2}=i\mathbbm{1}$ in $C$ and $n_{D}$ products
of type $\sigma_{3}\sigma_{2}\sigma_{1}=-i\mathbbm{1}$ in $D$. The global
phase of $g_{S}g_{T}g_{U}g_{V}$ is therefore

$i^{n_{A}-n_{B}+n_{C}-n_{D}}$

which will be equal to 1 if and only if

$\displaystyle n_{A}-n_{B}+n_{C}-n_{D}=0\mod 4.$ (15)

Establishing that this holds for any relation among the generators would imply
that the XYZ product code is a valid stabilizer code.

###  4.1 Code dimension and a tensor Sylvester equation

The algebraic nature of the code becomes apparent when trying to analyze the
linear system in Eqn. (14). In particular, we get the following necessary
condition on any solution of the system, which is a variant on the
(homogeneous) Sylvester equation. Similar equations hold for the other
tensors.

######  Lemma 6 (Tensor Sylvester Equation).

If $(S,T,U,V)$ is a solution of (14) then necessarily

$H_{1}H_{1}^{T}V=H_{2}H_{2}^{T}V=H_{3}H_{3}^{T}V.$ (16)

###### Proof.

If $(S,T,U,V)$ is a solution of (14), then
$H_{1}H_{1}^{T}V=H_{1}H_{2}U=H_{2}H_{1}U=H_{2}H_{2}^{T}V$. Similarly,
$H_{2}H_{2}^{T}V=H_{2}H_{3}S=H_{3}H_{2}S=H_{3}H_{3}^{T}V$. ∎

Now let $s$ denote the number of independent nonzero solutions to (16). We can
show that, under additional conditions on the parity-check matrices, we can
get an explicit expression for the number of solutions as a function of $s$.
We denote $k_{\ell}=\mathrm{dim}(\ker(H_{\ell}))$ and
$k^{T}_{\ell}=\mathrm{dim}(\ker(H_{\ell}^{T}))$ for $\ell=1,2,3$.

######  Claim 7.

If $H_{2}H_{2}^{T}$ and $H_{3}H_{3}^{T}$ are invertible, then the number of
independent nonzero solutions to (14) is given by

$s+k^{T}_{1}k_{2}k_{3}.$

###### Proof.

We already showed that (16) is a necessary condition. However, it is also a
sufficient condition on $V$ since any solution $V$ to (16) describes a
solution to (14) by setting

$S=H_{3}^{T}(H_{3}H_{3}^{T})^{-1}H_{2}^{T}V,\quad
T=H_{3}^{T}(H_{3}H_{3}^{T})^{-1}H_{1}^{T}V,\quad
U=H_{2}^{T}(H_{2}H_{2}^{T})^{-1}H_{1}^{T}V,$

which is straightforward to verify. Now assume that we have an alternative
solution of the form $(S+S^{\prime},T+T^{\prime},U+U^{\prime},V)$, then
necessarily $S^{\prime}\in\ker(H_{1}^{T})\cap\ker(H_{2})\cap\ker(H_{3})$,
$T^{\prime}\in\ker(H_{1})\cap\ker(H_{2}^{T})\cap\ker(H_{3})=\varnothing$ and
$U^{\prime}\in\ker(H_{1})\cap\ker(H_{2})\cap\ker(H_{3}^{T})=\varnothing$
(using that by our assumption $H_{2}^{T}$ and $H_{3}^{T}$ have full rank). The
claim follows by noting that
$\mathrm{dim}(\ker(H_{1}^{T})\cap\ker(H_{2})\cap\ker(H_{3}))=k^{T}_{1}k_{2}k_{3}$
as a consequence of the tensor structure. ∎

By permutation symmetry, we reach a similar conclusion if the pairs
$H_{1}H_{1}^{T}$ and $H_{2}H_{2}^{T}$ or $H_{1}H_{1}^{T}$ and $H_{3}H_{3}^{T}$
are invertible. In fact, by considering the Sylvester equation on $S$, $T$ or
$U$ instead of on $V$, we get any of the 12 possibilities (invertibility of
pairs of the form $H_{\ell}H_{\ell}^{T}$ or $H_{\ell}^{T}H_{\ell}$). We have
the following corollary.

######  Corollary 8.

If $H_{2}H_{2}^{T}$ and $H_{3}H_{3}^{T}$ are invertible, then the dimension of
the code is given by

$(n_{1}-m_{1})(n_{2}-m_{2})(n_{3}-m_{3})+s+k_{1}^{T}k_{2}k_{3}.$

###  4.2 A tensor Cecioni-Frobenius theorem

In this section we will determine the number of solutions to the tensor
Sylvester equation (16) over some field $K$. To this end we derive a tensor
generalization of the Cecioni-Frobenius theorem which concerned the
(homogeneous) Sylvester equation $AX=XB$.

For square matrices $A\in K^{n\times n}$, $B\in K^{m\times m}$ and $C\in
K^{\ell\times\ell}$, consider the shorthand
$A=A\otimes\mathbbm{1}_{m}\otimes\mathbbm{1}_{\ell}$,
$B=\mathbbm{1}_{n}\otimes B\otimes\mathbbm{1}_{\ell}$,
$C=\mathbbm{1}_{n}\otimes\mathbbm{1}_{m}\otimes C$. We define the tensor
Sylvester equation (for 3-tensors) as

$AX=BX=CX,$ (17)

where $X\in K^{m\times n\times\ell}$. We are interested in the number of
independent solutions of this equation. We will prove the following tensor
Cecioni-Frobenius theorem, where $p^{A}_{i},p^{B}_{i},p^{C}_{i}$ denote the
characteristic polynomials of the $i$-th Jordan block of $A,B,C$, respectively
(over the algebraic closure $\overline{K}$).

######  Theorem 9 (Tensor Cecioni-Frobenius).

The number of independent solutions of $AX=BX=CX$ is

$\sum_{i,j,k=1}^{n}\mathrm{deg}(\mathrm{gcd}(p^{A}_{i},p^{B}_{j},p^{C}_{k})).$

Our proof runs somewhat parallel to the analysis in [19] for the regular
Cecioni-Frobenius theorem. We start with the following elementary fact:

######  Lemma 10.

The number of independent solutions of a linear system over some field $K$ is
equal to the number of independent solutions of the linear system considered
over the algebraic closure $\overline{K}$.

###### Proof.

The number of independent solutions of a linear system $Ax=b$ over some field
$K$ is equal to the dimension of the kernel of the augmented matrix $[A|b]$
(Rouché-Capelli theorem), which is equivalent for any field containing the
coefficients of $A$ and $b$. One way of seeing this is that the rank follows
from reducing $[A|b]$ to its reduced row echelon form, and all operations in
this transformation can be performed over the original field. ∎

By this lemma we can prove the tensor Cecioni-Frobenius theorem over a field
$K$ by proving it over the algebraic closure $\overline{K}$. This is helpful
because over $\overline{K}$ the matrices $A,B,C$ are similar to their Jordan
normal forms: i.e., there exist invertible $P_{A},P_{B},P_{C}$ such that

$A=P_{A}\Big{(}\bigoplus_{i}J^{A}_{i}\Big{)}P_{A}^{-1},\quad
B=P_{B}\Big{(}\bigoplus_{j}J^{B}_{j}\Big{)}P_{B}^{-1},\quad
C=P_{C}\Big{(}\bigoplus_{k}J^{C}_{k}\Big{)}P_{C}^{-1},$

where $\\{J^{A}_{i}\\},\\{J^{B}_{j}\\},\\{J^{C}_{k}\\}$ correspond to the
Jordan blocks of $A$, $B$, $C$, respectively. Through the change of variables
$X=(P_{A}\otimes P_{B}\otimes P_{C})Y$, the Sylvester equation (17) becomes
equivalent to

$\big{(}\bigoplus_{i}J^{A}_{i}\big{)}\,Y=\big{(}\bigoplus_{j}J^{B}_{j}\big{)}\,Y=\big{(}\bigoplus_{k}J^{C}_{k}\big{)}\,Y.$

Now partition $Y$ into blocks $Y_{ijk}$ according to the ranges of the Jordan
blocks of $A,B,C$. More specifically, let the intervals $n_{i}^{A}\subset[n]$,
$n_{j}^{B}\subset[m]$, $n_{k}^{C}\subset[\ell]$ denote to the rows of
$J_{i}^{A}$, $J_{j}^{B}$ and $J_{k}^{C}$, respectively (as part of the larger
matrices $\bigoplus_{i}J_{i}^{A}$, etc). Then the block $Y_{ijk}$ follows by
restricting the first index of $Y$ to $n_{i}^{A}$, the second index to
$n_{j}^{B}$ and the third index to $n_{k}^{C}$. The equation then splits up
into blocks: we effectively need that

$J^{A}_{i}\,Y_{ijk}=J^{B}_{j}\,Y_{ijk}=J^{C}_{k}\,Y_{ijk},\quad\forall i,j,k.$

This reduces the problem to the tensor Sylvester equation for Jordan blocks.

Let $J(\lambda,\alpha)$ denote a Jordan block of eigenvalue $\lambda$ and
dimension $\alpha$, and consider the equation

$J(\lambda,\alpha)X=J(\mu,\beta)X=J(\nu,\gamma)X,$ (18)

where we again omit tensor notation.

######  Lemma 11.

Equation (18) has no nonzero solution unless $\lambda=\mu=\nu$.

###### Proof.

Assume that there exists a nonzero solution $X\neq 0$. Note that $AX=BX=CX$
implies that $p(A)X=p(B)X=p(C)X$ for any polynomial $p$. Indeed, if say
$AX=BX$ then $A^{2}X=ABX=BAX=B^{2}X$, and by induction $A^{k}X=B^{k}X$ for any
integer $k$ (and hence $p(A)X=p(B)X$ for any polynomial $p$). The same
reasoning implies that $p(A)X=p(C)X$.

Now if we let $p_{A}$ be the characteristic polynomial of $A$, then

$p_{A}(A)X=p_{A}(B)X=p_{A}(C)X=0.$

Since $X\neq 0$ and $p_{A}=(x-\lambda)^{\alpha}$, this implies that
$\det(p_{A}(B))=0=\det(B-\lambda I)^{\alpha}$. $B$ must hence have an
eigenvalue $\lambda$, and so $\mu=\lambda$. An analogous reasoning proves that
$\nu=\lambda$. ∎

This shows that we should only consider the special case
$J(\lambda,\alpha)X=J(\lambda,\beta)X=J(\lambda,\gamma)X$. Since
$J(\lambda,\alpha)=\lambda I_{\alpha}+J(0,\alpha)$, this is equivalent to

$J(0,\alpha)X=J(0,\beta)X=J(0,\gamma)X.$ (19)

######  Lemma 12.

The number of independent solutions of (19) is
$\min\\{\alpha,\beta,\gamma\\}$.

###### Proof.

Without loss of generality, assume that
$\gamma=\min\\{\alpha,\beta,\gamma\\}$. The tensor operators
$J(0,\alpha)\otimes I\otimes I$, $I\otimes J(0,\beta)\otimes I$ and $I\otimes
I\otimes J(0,\gamma)$ effectively work as $x$-, $y$\- and $z$-shifts on the
entries of $X$, respectively. Indeed, componentwise the equation becomes

$X_{i+1,j,k}=X_{i,j+1,k}=X_{i,j,k+1},\quad\forall
i\in[\alpha],j\in[\beta],k\in[\gamma],$ (20)

where we set $X_{i,j,k}=0$ whenever $i>\alpha$, $j>\beta$ or $k>\gamma$.

Now pick any $(i,j,k)$ and set $x=X_{i,j,k}$. By (20) we get that
$X_{i^{\prime},j^{\prime},k^{\prime}}=x$ for every
$(i^{\prime},j^{\prime},k^{\prime})$ such that
$i^{\prime}+j^{\prime}+k^{\prime}=i+j+k$. Any solution can hence be described
by a (linear combination of) uniform planes:

$X_{i,j,k}=x_{i+j+k},$

for some set of values $\\{x_{\ell}\\}_{\ell\geq 3}$. Moreover, we must have
that $x_{\ell}=0$ whenever $\ell>\gamma+2$, since we set $X_{1,1,k}=0$
whenever $k>\gamma$. This implies that the number of independent solutions is
$\gamma=\min\\{\alpha,\beta,\gamma\\}$. ∎

Putting everything together, we decomposed any solution $Y$ as a direct sum of
blocks $Y_{ijk}$. A block $Y_{ijk}$ can be nonzero only if the Jordan blocks
$J_{i}^{A},J_{j}^{B},J_{k}^{C}$ correspond to the same eigenvalue. With
$\alpha_{i},\beta_{j},\gamma_{k}$ the dimensions of these blocks,
respectively, the number of independent solutions for $Y_{ijk}$ in this case
is
$\min\\{\alpha_{i},\beta_{j},\gamma_{k}\\}=\mathrm{deg}(\mathrm{gcd}(J_{i}^{A},J_{j}^{B},J_{k}^{C}))$.
Summing this up over all blocks, we get that the total number of independent
solutions is

$\sum_{i,j,k}\mathrm{deg}(\mathrm{gcd}(J_{i}^{A},J_{j}^{B},J_{k}^{C})).$

This proves the tensor Cecioni-Frobenius theorem.

###  4.3 Dimension of the modified Chamon code

The Chamon code on a lattice of size $n_{1}\times n_{2}\times n_{3}$ has
dimension $4\gcd(n_{1},n_{2},n_{3})$ [8]. It is described by the XYZ product
code with circulant matrices $H_{i}=\mathbbm{1}+\Omega_{n_{i}}$, for
$i=1,2,3$, where again $\Omega_{n_{i}}\ket{x}=\ket{x+1\mod n_{i}}$. If we are
interested in the minimum distance of the Chamon code, then in principle we
have to lower bound the weight of all $4^{4}-1=255$ logical operators. Here we
present a slight modification of the code which results in dimension 1 (and
hence only 3 logical operators). Specifically, we will consider the
$(n_{i}-1)\times n_{i}$ parity-check matrices $H_{i}$ obtained by deleting the
last row of $\mathbbm{1}+\Omega_{n_{i}}$, for $i=1,2,3$:

$[H_{i}]_{k,\ell}=[\mathbbm{1}+\Omega_{n_{i}}]_{k,\ell}\quad\text{for}\quad
k\in[n_{i}-1],\;\ell\in[n_{i}].$

We refer to the resulting XYZ code $\mathcal{Q}(H_{1},H_{2},H_{3})$ as the
modified Chamon code. We can prove the following lemma.

######  Lemma 13.

For $H_{1},H_{2},H_{3}$ defined as above,

  * •

$H_{i}^{T}$ has rank $n_{i}-1$.

  * •

If $n_{i}$ is odd then $H_{i}H_{i}^{T}$ is invertible.

  * •

If $\gcd(n_{i},n_{j})=1$ then the intersection of the spectra of
$H_{i}H_{i}^{T}$ and $H_{j}H_{j}^{T}$ are disjoint.

###### Proof.

For the first bullet, note that the first $n_{i}-1$ rows of $H_{i}^{T}$
describe a Jordan block of size $n_{i}-1$ and eigenvalue 1. Such a Jordan
block has rank $n_{i}-1$, and therefore $H_{i}^{T}$ has rank $n_{i}-1$. For
the second and third bullets, note that
$H_{i}H_{i}^{T}=\omega_{n_{i}-1}+\omega^{T}_{n_{i}-1}$, where $\omega_{k}$ is
the $k\times k$ matrix with 1 on its upper diagonal 0 elsewhere. Now denote
the characteristic polynomial of $H_{i}H_{i}^{T}$ as
$p_{n_{i}}(x)=\mathrm{det}(x\mathbbm{1}_{n_{i}-1}+\omega_{n_{i}-1}+\omega_{n_{i}-1}^{T})$
(for $n_{i}\geq 2$). If we expand the determinant along the first row, we see
that

$p_{n+1}(x)=xp_{n}(x)+p_{n-1}(x).$

This recurrence holds for all $n\geq 1$ if we set $p_{0}(x)=0$ and
$p_{1}(x)=1$. The solution to this recurrence relation are the so-called
Fibonacci polynomials $p_{n+1}(x)=F_{n+1}(x)$. As a consequence, the
characteristic polynomial of $H_{i}H_{i}^{T}$ is exactly the Fibonacci
polynomial $F_{n_{i}}(x)$. A property of these polynomials is that $F_{k}$
divides $F_{\ell}$ over $\mathbbm{F}_{2}$ if and only if $k$ divides $\ell$.
In particular, this implies that if $n_{i}$ is odd ($\gcd(n_{i},2)=1$) then
$F_{2}(x)=x$ does not divide the characteristic polynomial of
$H_{i}H_{i}^{T}$, and hence the matrix is invertible. In addition,
$\gcd(F_{k},F_{\ell})=1$ whenever $\gcd(k,\ell)=1$, and this completes the
proof. ∎

######  Corollary 14.

If $n_{2}$ and $n_{3}$ are odd and $\gcd(n_{2},n_{3})=1$, then the modified
Chamon code has dimension 1.

###### Proof.

From Section 4 we know that the dimension of the XYZ product code is given by

$(n_{1}-m_{1})(n_{2}-m_{2})(n_{3}-m_{3})+r,$

with $r$ the number of solutions to system (14). For the modified Chamon code
this becomes $1+r$. Since $H_{2}H_{2}^{T}$ and $H_{3}H_{3}^{T}$ are
invertible, we can use Claim 7, which says that

$r=s+k_{1}^{T}k_{2}k_{3},$

with $s$ the number of solutions to the tensor Sylvester equation (16), and
$k_{i},k_{i}^{T}$ the dimension of the kernel of $H_{i},H_{i}^{T}$,
respectively. From Lemma 13 we have that $k_{1}^{T}=0$, so that $r=s$. By the
tensor Cecioni-Frobenius theorem (Theorem 9) we get that $s=0$ if there is no
common eigenvalue among the matrices $H_{1}H_{1}^{T}$, $H_{2}H_{2}^{T}$ and
$H_{3}H_{3}^{T}$. This is ensured by the last bullet in Lemma 13. ∎

##  5 Minimum distance of the XYZ product code

In this section, we study the minimum distance of XYZ product codes that
encode a single logical qubit. While some of these results (such as the lower
bound presented in Section 5.2) might hold in more generality, they are much
easier to show in the case where there is a single logical qubit. The reason
for this is that if there is a single logical qubit, there are only three
logical operators ($X$, $Y$ or $Z$-logical operators) whose weight we need to
bound to get the distance. To further simplify things, we will restrict to
triples $H_{1},H_{2},H_{3}$ in some particular set $\cal T$ of interest:

######  Definition 15.

The set of triples $\mathcal{T}$ contains all triples $(H_{1},H_{2},H_{3})$ of
invertible matrices of odd dimension that uniquely fix the all-ones vector
$u=(1,1,\ldots,1)^{T}$, and such that the intersection of the spectra of
$H_{1}H_{1}^{T},H_{2}H_{2}^{T}$ and $H_{3}H_{3}^{T}$ is otherwise empty. I.e.,

$H_{i}\in GL(n_{i},\mathbbm{F}_{2}),\quad\gcd(n_{i},2)=1,\quad
H_{i}x=H_{i}^{T}x=x\Leftrightarrow
x=u,\quad\bigcap_{i=1}^{3}\mathrm{Spec}(H_{i}H_{i}^{T})=\\{1\\}.$

By Corollary 5 the resulting codes have dimension equal to 1. We will show how
to reduce the problem of computing their minimum distance (up to constant
factors) to computing the optimum value of a simple combinatorial problem over
a binary tensor of order 3 (see Theorem 22).

Before that, we show that XYZ product codes obtained from triples on
$\mathcal{T}$ are well-defined stabilizer codes.

######  Lemma 16.

The stabilizer group associated with the XYZ product code of
$(H_{1},H_{2},H_{3})\in\mathcal{T}$ does not contain $-\mathbbm{1}$.

###### Proof.

In this setup, there is a single relation among the generators: the product of
all the generators is proportional to the identity operator. In particular,
the number of occurrences of products $\sigma_{1}\sigma_{2}\sigma_{3}$ is
equal to $n_{1}n_{2}n_{3}$ in each of the sets $A,B,C,D$, showing that Eqn.
(15) is satisfied and therefore the stabilizer does not contain
$-\mathbbm{1}$. ∎

###  5.1 Logical operators

The logical operators of an XYZ product code ${\cal Q}(H_{1},H_{2},H_{3})$
with $(H_{1},H_{2},H_{3})\in{\cal T}$ take a particularly simple form. With
$u=(1,1,\dots,1)^{T}$ and $e_{1}=(1,0,\dots,0)^{T}$, they can be represented
as

${\cal X}=\begin{bmatrix}\sigma_{1}^{e_{1}\otimes u\otimes u}\\\ 0\\\ 0\\\
\sigma_{1}^{e_{1}\otimes u\otimes u}\end{bmatrix},\qquad{\cal
Y}=\begin{bmatrix}\sigma_{2}^{u\otimes e_{1}\otimes u}\\\ 0\\\
\sigma_{2}^{u\otimes e_{1}\otimes u}\\\ 0\end{bmatrix},\qquad{\cal
Z}=\begin{bmatrix}\sigma_{3}^{u\otimes u\otimes e_{1}}\\\ \sigma_{3}^{u\otimes
u\otimes e_{1}}\\\ 0\\\ 0\end{bmatrix}.$

This corresponds to pairs of slices of $\sigma_{i}$ operators.

Figure 7: Representation of the logical errors. For clarity of exposition,
slight variants on the logical $\cal X$ and $\cal Z$ are shown (exchanging
$e_{1}$ for $e_{n_{i}}$ in the definition).

To see that they are fixed by the stabilizer group, it suffices to verify that

$\Sigma*{\cal X}=\begin{bmatrix}\mathcal{X}*\sigma_{1}^{e_{1}\otimes u\otimes
u}\\\ \mathcal{Y}*\sigma_{1}^{e_{1}\otimes u\otimes
u}+\mathcal{Z}^{\dagger}*\sigma_{1}^{e_{1}\otimes u\otimes u}\\\
\mathcal{Z}*\sigma_{1}^{e_{1}\otimes u\otimes
u}+\mathcal{Y}^{\dagger}*\sigma_{1}^{e_{1}\otimes u\otimes u}\\\
\mathcal{X}*\sigma_{1}^{e_{1}\otimes u\otimes
u}\end{bmatrix}=\begin{bmatrix}0\\\
(\sigma_{2}\ast\sigma_{1})^{e_{1}\otimes(H_{2}u)\otimes
u}+(\sigma_{3}*\sigma_{1})^{e_{1}\otimes u\otimes(H_{3}^{T}u)}\\\
(\sigma_{3}*\sigma_{1})^{e_{1}\otimes
u\otimes(H_{3}u)}+(\sigma_{2}*\sigma_{1})^{e_{1}\otimes(H_{2}^{T}u)\otimes
u}\\\ 0\end{bmatrix}=0,$

using that $H_{2}u=H_{2}^{T}u=H_{3}u=H_{3}^{T}u$. The same argument applies
for ${\cal Y}$ and ${\cal Z}$. Next we verify that they anticommute pairwise.
To this end, notice that the intersection of any pair of logical operators
corresponds to the intersection of exactly two perpendicular slices, which has
Hamming weight $n_{i}$ for some $i$. By our assumption that the $n_{i}$’s are
odd, this implies that they anticommute. Finally, we note that this implies
that they do not belong to the stabilizer group, because any pair of elements
in the stabilizer group commutes.

###  5.2 First lower bound on the minimum distance

Using a standard trick we can get a simple lower bound on the minimum distance
when $(H_{1},H_{2},H_{3})\in{\cal T}$. Recall that we can prove a lower bound
on the distance by proving a lower bound on the support of a logical error.

First we note that in fact the logical operator $\cal X$ has $2n_{1}$ disjoint
representatives:

${\cal X}\in\left\\{\begin{bmatrix}\sigma_{1}^{e_{i}\otimes u\otimes u}\\\
0\\\ 0\\\ \sigma_{1}^{e_{i}\otimes u\otimes
u}\end{bmatrix},\;\begin{bmatrix}0\\\ \sigma_{1}^{e_{i}\otimes u\otimes u}\\\
\sigma_{1}^{e_{i}\otimes u\otimes u}\\\
0\end{bmatrix}:i=1,2,\dots,n_{1}\right\\}.$

This corresponds to picking pairs of slices in $A$ and $D$ or $B$ and $C$, and
translating them in the $x$-direction. We get a similar set of representations
for $\cal Y$ and $\cal Z$.

Now let $\cal E$ denote a logical error. Then $\cal E$ has to anticommute (and
hence intersect) with each of the representatives of either $\cal X$, $\cal Y$
or $\cal Z$, since otherwise $\cal E$ is in the stabilizer group. Now assume
e.g. that it intersects with each of the $2n_{1}$ representatives of $\cal X$.
Since these representatives are all disjoint, this implies that $\cal E$ must
have Hamming weight at least $2n_{1}$. By a similar reasoning for $\cal Y$ and
$\cal Z$, we get the following lemma.

######  Lemma 17.

If $(H_{1},H_{2},H_{3})\in\cal T$, then the XYZ product code ${\cal
Q}(H_{1},H_{2},H_{3})$ has minimum distance

$d\geq 2\min\\{n_{1},n_{2},n_{3}\\}.$

In fact, this bound is tight as soon as two of the three parity-check matrices
coincide.

######  Lemma 18.

Let $H,H^{\prime}$ be parity-check matrices, with $H$ square of dimension $n$.
The minimum distance of the XYZ product code $\mathcal{Q}(H,H,H^{\prime})$ is
upper bounded by $n$.

###### Proof.

Consider the 3-dimensional tensor $\mathbbm{1}\otimes e_{1}$ corresponding to
a single horizontal layer equal to the identity $\mathbbm{1}_{n}$ and
$(n_{3}-1)$ horizontal layers identically equal to zero:

$\mathbbm{1}\otimes e_{1}(i,j,k):=\delta_{i,j}\delta_{k,1}.$

We take as a logical error

$\begin{bmatrix}{\cal A}&{\cal B}&{\cal C}&{\cal
D}\end{bmatrix}^{T}=\begin{bmatrix}\sigma_{3}^{\mathbbm{1}\otimes
e_{1}}&\sigma_{3}^{\mathbbm{1}\otimes e_{1}}&0&0\end{bmatrix}^{T},$

i.e., the product of $Z$-Pauli operators on cells of index $(i,i,1)$ for
$i\in[n]$ for qubits both in $A$ and $B$. This operator has intersection 1
(and hence anticommutes) with both $\cal X$ and $\cal Y$. On the other hand,
it is fixed by the stabilizer group:

$\Sigma*\begin{bmatrix}{\cal A}\\\ {\cal B}\\\ {\cal C}\\\ {\cal
D}\end{bmatrix}=\begin{bmatrix}(\sigma_{1}*\sigma_{3})^{H\otimes
e_{1}}+(\sigma_{2}*\sigma_{3})^{H\otimes e_{1}}\\\
(\sigma_{2}*\sigma_{3})^{H^{T}\otimes
e_{1}}+(\sigma_{1}*\sigma_{3})^{H^{T}\otimes e_{1}}\\\ 0\\\
0\end{bmatrix}=0.\qed$

###  5.3 A decoupling argument

If $n_{1}$, $n_{2}$ and $n_{3}$ are of the same order, then the previous
argument gives a lower bound of the form $\Omega(n_{i})=\Omega(N^{1/3})$. Here
we outline a strategy to proving a lower bound of the form $\Omega(N^{2/3})$.
We do so by minimizing the weight of the logical operators. Without loss of
generality, we can assume that the minimum weight of a logical operator is
reached for a $Z$-logical operator. This can always be enforced by suitably
permuting the three parity-check matrices, and we will therefore need to
consider all 6 permutations in the following.

Throughout the argument we will again assume that $(H_{1},H_{2},H_{3})\in\cal
T$, but also that the row and column weights of the $H_{i}$’s are bounded by
some $w\in O(1)$ (which is of course necessary to obtain an LDPC code). We
will also write a Pauli tensor $\mathcal{A}$ as

$\mathcal{A}=\begin{bmatrix}A_{x}&A_{y}&A_{z}\end{bmatrix}^{T}$

to mean that
$\mathcal{A}=(\sigma_{X})^{A_{x}}(\sigma_{Y})^{A_{y}}(\sigma_{Z})^{A_{z}}$. In
other words, $A_{x}$ is a binary tensor and we apply a Pauli-$X$ on each
element of the support of $A_{x}$. This decomposition is not unique: for
instance, for any binary tensor $M$, we have

$\begin{bmatrix}A_{x}&A_{y}&A_{z}\end{bmatrix}^{T}=\begin{bmatrix}A_{x}+M&A_{y}+M&A_{z}+M\end{bmatrix}^{T}.$

######  Lemma 19.

The (Pauli) weight of the Pauli operator $\mathcal{A}$ is given by

$|\mathcal{A}|=\frac{1}{2}(|A_{x}+A_{y}|+|A_{x}+A_{z}|+|A_{y}+A_{z}|).$

###### Proof.

Let subsets $S_{x},S_{y},S_{z}$ correspond to the supports of
$A_{x},A_{y},A_{z}$, respectively. Then the number of nontrivial Pauli
operators is given by

$\displaystyle|S_{x}\cup S_{y}\cup S_{z}|-|S_{x}\cap S_{y}\cap S_{z}|\ $
$\displaystyle=|S_{x}|+|S_{y}|+|S_{z}|-|S_{x}\cap S_{y}|-|S_{x}\cap
S_{z}|-|S_{y}\cap S_{z}|$ $\displaystyle=\frac{1}{2}(|S_{x}\triangle
S_{y}|+|S_{x}\triangle S_{z}|+|S_{y}\triangle S_{z}|),$

with $\triangle$ the symmetric difference. The lemma follows by noting that
e.g. $|S_{x}\triangle S_{y}|=|A_{x}+A_{y}|$. ∎

Now we can write the most general form of a $Z$-logical operator as the sum of
our previously defined logical operator $\cal Z$ (two horizontal slices of
Pauli-$Z$ in the sets $A$ and $B$), which we will here denote by $R$, and of
an arbitrary stabilizer element parametrized by tensors $(S,T,U,V)$:

$\displaystyle\mathcal{A}=\begin{bmatrix}xS\\\ yT\\\
zU+R\end{bmatrix}\quad\mathcal{B}=\begin{bmatrix}xT\\\ yS\\\
zV+R\end{bmatrix}\quad\mathcal{C}=\begin{bmatrix}xU\\\ yV\\\
zS\end{bmatrix}\quad\mathcal{D}=\begin{bmatrix}xV\\\ yU\\\ zT\end{bmatrix},$
(21)

where we use the shorthand $x=H_{1}\otimes\mathbbm{1}\otimes\mathbbm{1}$,
$y=\mathbbm{1}\otimes H_{2}\otimes\mathbbm{1}$ and
$z=\mathbbm{1}\otimes\mathbbm{1}\otimes H_{3}$. For simplicity we assume that
the parity-check matrices $H_{i}$ are all symmetric, but we will later remove
this assumption. The minimum distance $d_{\min}$ of the code is now given by
the minimum weight of this Pauli operator over all choices of $S,T,U,V$:

$d_{\min}=\min_{S,T,U,V}|\mathcal{A}|+|\mathcal{B}|+|\mathcal{C}|+|\mathcal{D}|.$

Using Lemma 19 we can rewrite this as

$2d_{\min}=\min_{S,T,U,V}\sum_{E\in\\{A,B,C,D\\}}|E_{xy}|+|E_{xz}|+|E_{yz}|,$

where $A_{xy}:=xS+yT,\,A_{xz}:=xS+zU+R,\,A_{yz}:=yT+zU+R$, etc. We will denote
by

${W}={W}(S,T,U,V):=\sum_{E\in\\{A,B,C,D\\}}|E_{xy}|+|E_{xz}|+|E_{yz}|,$

the quantity that we wish to minimize.

While we can independently optimize over the tensors $S,T,U,V$, the problem is
that the individual terms (e.g. $|A_{xy}|=|xS+zU+R|$) depend on pairs of
tensors. We will now argue how to lower bound the sum by a sum of “decoupled”
terms. To start, consider the term $|A_{xz}|+|C_{xz}|$ of $W$. By assumption,
the row and column weights of the $H_{i}$’s (and hence the $x,y,z$ operators)
are bounded by $w$. This implies that $|xE|\leq w|E|$, for any tensor $E$.
Applied to $A_{xz}$ and $C_{xz}$, this gives:

$\displaystyle|xS+zU+R|$
$\displaystyle\geq\frac{1}{w}|x^{2}S+xzU+xR|=\frac{1}{w}|x^{2}S+xzU+R|$
$\displaystyle|xU+zS|$ $\displaystyle\geq\frac{1}{w}|xzU+z^{2}S|,$

where we further exploited666As a side remark: this step is crucial for our
purpose but it does not hold for the Chamon code [14]. For that code, we would
get $|xR|=O(n)$ and therefore this approach would not be able to prove any
lower bound on the minimum distance of the Chamon code better than
$\Omega(N^{1/3})$. that $xR=R$. A triangle inequality finally yields:

$|A_{xz}|+|C_{xz}|\geq|A_{xz}+C_{xz}|=\frac{1}{w}|(x^{2}+z^{2})S+R|.$

As promised, this gives a term that only depends on a single tensor $S$. A
similar analysis allows to also decouple the following pairs:

$\begin{gathered}|A_{yz}|+|D_{yz}|\geq\frac{1}{w}|(y^{2}+z^{2})T+R|,\;\;|B_{xz}|+|D_{xz}|\geq\frac{1}{w}|(x^{2}+z^{2})T+R|,\\\
|B_{yz}|+|C_{yz}|\geq\frac{1}{w}|(y^{2}+z^{2})S+R|.\end{gathered}$

The remaining terms of $W$ can finally be bounded by

$|A_{xy}|+|B_{xy}|\geq\frac{1}{2w}(|(x^{2}+y^{2})S|+|(x^{2}+y^{2})T|),\;\;|C_{xy}|+|D_{xy}|\geq\frac{1}{2w}(|(x^{2}+y^{2})U|+|(x^{2}+y^{2})V|).$

Putting it all together, we get that

$\displaystyle W(S,T,U,V)\geq$
$\displaystyle\frac{1}{w}\big{(}|(x^{2}+z^{2})S+R|+|(y^{2}+z^{2})S+R|+|(x^{2}+z^{2})T+R|+|(y^{2}+z^{2})T+R|\big{)}$
$\displaystyle+\frac{1}{2w}\big{(}|(x^{2}+y^{2})S|+|(x^{2}+y^{2})T|+|(x^{2}+y^{2})U|+|(x^{2}+y^{2})V|\big{)}.$

Now if we minimize the right hand side over $S,T,U,V$ independently, then we
can simply set $U=V=0$ and $S=T$ to get

$\min_{S,T,U,V}W(S,T,U,V)\geq\min_{s}\frac{1}{w}(2|(x^{2}+z^{2})S+R|+2|(y^{2}+z^{2})S+R|+|(x^{2}+y^{2})S|).$

We have thus managed to decouple the four variables and reduced the
optimization problem to a single (tensor) variable problem. This proves the
following lemma (after replacing the shorthands $x,y,z$ by their explicit
forms).

######  Lemma 20.

Let $\\{H_{1},H_{2},H_{3}\\}\in\mathcal{T}$ such that $H_{i}=H_{i}^{T}$. Let
$w$ be an upper bound on the row weight of $H_{i}$. The minimum distance of
the XYZ product code $\mathcal{Q}(H_{1},H_{2},H_{3})$ satisfies

$\displaystyle d_{\min}$
$\displaystyle\geq\min_{(ijk)\in(123)}\min_{M}\frac{1}{w}\left(|(H_{i}^{2}+H_{k}^{2})M+R|+|(H_{j}^{2}+H_{k}^{2})M+R|+\frac{1}{2}|(H_{i}^{2}+H_{j}^{2})M|\right),$
$\displaystyle\geq\min_{(ijk)\in(123)}\min_{M}\frac{3}{4w}\left(|(H_{i}^{2}+H_{k}^{2})M+R|+|(H_{i}^{2}+H_{j}^{2})M|\right)$

The second inequality follows from a simple triangle inequality:

$\displaystyle|(x^{2}+z^{2})M$ $\displaystyle+R|+|(x^{2}+z^{2})M+R|$
$\displaystyle\geq\frac{3}{4}|(x^{2}+z^{2})M+R|+\frac{1}{4}(|(x^{2}+z^{2})M+R|+|(y^{2}+z^{2})M+R|)$
$\displaystyle\geq\frac{3}{4}|(x^{2}+z^{2})M+R|+\frac{1}{4}(|(x^{2}+y^{2})M|).$

The same analysis goes through essentially without modification in the non-
symmetric case, where we get the bounds

$\displaystyle|A_{xz}|+|C_{xz}|$
$\displaystyle\geq\frac{1}{w}|(xx^{T}+z^{T}z)s+r|,\qquad|A_{yz}|+|D_{yz}|\geq\frac{1}{w}|(yy^{T}+z^{T}z)t+r|,$
$\displaystyle|B_{xz}|+|D_{xz}|$
$\displaystyle\geq\frac{1}{w}|(x^{T}x+z^{T}z)t+r|,\qquad|B_{yz}|+|C_{yz}|\geq\frac{1}{w}|(y^{T}y+z^{T}z)s+r|,$

and we ignore the remaining terms in $W$.

######  Lemma 21 (Non-symmetric version).

The minimum distance of the XYZ product code associated with
$(H_{1},H_{2},H_{3})\in\mathcal{T}$ is bounded by

$\displaystyle d_{\min}\geq\min_{(ijk)\in(123)}\min_{S,T}\frac{1}{2w}\Big{(}$
$\displaystyle|(H_{i}H_{i}^{T}+H_{k}^{T}H_{k})S+R|+|(H_{j}^{T}H_{j}+H_{k}^{T}H_{k})S+R|$
$\displaystyle\quad+|(H_{i}^{T}H_{i}+H_{k}^{T}H_{k})T+R|+|(H_{j}H_{j}^{T}+H_{k}^{T}H_{k})T+R|\Big{)}.$

In the rest of this manuscript, we will focus on the symmetric case.

#### Tightness of the Argument

We now show that the argument above is essentially tight. For a tensor $M$
(with dimensions equal to the tensor $S$), consider the choice

$S=xyM,\quad T=x^{2}M,\quad U=yzM,\quad V=xzM.$

With these, we get the Pauli tensors

$\mathcal{A}=\begin{bmatrix}x^{2}yM\\\ x^{2}yM\\\
yz^{2}M+R\end{bmatrix},\qquad\mathcal{B}=\begin{bmatrix}x^{3}M\\\ xy^{2}M\\\
xz^{2}M+R\end{bmatrix},\qquad\mathcal{C}=\begin{bmatrix}xyzM\\\ xyzM\\\
xyzM\end{bmatrix},\qquad\mathcal{D}=\begin{bmatrix}x^{2}zM\\\ y^{2}zM\\\
x^{2}zM\end{bmatrix},$

which represents a valid logical $Z$ operator. Using Lemma 19 we can bound its
weight as follows (again using that $xR=yR=R$):

$\displaystyle|\mathcal{A}|$ $\displaystyle=|y((x^{2}+z^{2})M+R)|\leq
w|(x^{2}+z^{2})M+R|$ $\displaystyle|\mathcal{B}|$
$\displaystyle=\frac{1}{2}(|x(x^{2}+y^{2})M|+|x((x^{2}+z^{2})M+R)|+|x((y^{2}+z^{2})M+R)|)$
$\displaystyle\leq\frac{w}{2}\left(|(x^{2}+y^{2})M|+|(x^{2}+z^{2})M+R|+|(y^{2}+z^{2})M+R|\right)$
$\displaystyle|\mathcal{C}|$ $\displaystyle=0$ $\displaystyle|\mathcal{D}|$
$\displaystyle=|z(x^{2}+y^{2})M|\leq w|(x^{2}+y^{2})M|$

so that

$|\mathcal{A}|+|\mathcal{B}|+|\mathcal{C}|+|\mathcal{D}|\leq\frac{w}{2}(3|(x^{2}+y^{2})M|+3|(x^{2}+z^{2})M+R|+|(y^{2}+z^{2})M+R|).$

This gives us an upper bound on the minimum distance as a function of the
tensor $M$. If now we let $M$ be the tensor that minimizes the first
inequality in Lemma 20, we get the following.

######  Theorem 22 (Decoupling Theorem).

Let $(H_{1},H_{2},H_{3})\in\mathcal{T}$ be symmetric matrices with row weight
upper bounded by $w$. Define $d^{*}$ as the solution of the following
combinatorial problem:

$\displaystyle
d^{*}:=\min_{(ijk)\in(123)}\min_{M}\left(|(H_{i}^{2}+H_{k}^{2})M+R|+|(H_{j}^{2}+H_{k}^{2})M+R|+\frac{1}{2}|(H_{i}^{2}+H_{j}^{2})M|\right).$
(22)

Then the minimum distance $d_{\min}$ of the XYZ product code
$\mathcal{Q}(H_{1},H_{2},H_{3})$ satisfies

$\frac{d^{*}}{w}\leq d_{\min}\leq\frac{3}{2}wd^{*}.$

Note that defining $d^{*}$ with any two of the three terms in (22) only
changes the value by a constant factor.

###  5.4 Some obstructions to a lower bound

####  5.4.1 Permutation invariance

Here we show that the distance of an XYZ product code with
$(H_{1},H_{2},H_{3})\in\mathcal{T}$ is invariant upon arbitrary permutations
of rows and columns of the parity-check matrices. This indicates that we
cannot to improve the distance of the code by considering e.g. random
permutations of the rows or columns.

######  Lemma 23 (Permutation invariance).

Let $\pi_{i},\tau_{i}$ be permutations over $[n_{i}]$ for $i=1,2,3$, and
consider any triple $(H_{1},H_{2},H_{3})\in\mathcal{T}$. Then the distance of
codes $\mathcal{Q}(H_{1},H_{2},H_{3})$ and
$\mathcal{Q}(\pi_{1}H_{1}\tau_{1},\pi_{2}H_{2}\tau_{2},\pi_{3}H_{3}\tau_{3})$
coincide.

###### Proof.

First, note that if $(H_{1},H_{2},H_{3})\in\mathcal{T}$, then
$(\pi_{1}H_{1}\tau_{1},\pi_{2}H_{2}\tau_{2},\pi_{3}H_{3}\tau_{3})\in\mathcal{T}$
since multiplying $H_{i}$ by permutation matrices leaves it invertible, with
the same row and column weights. Moreover,
$(\pi_{i}H_{i}\tau_{i})(\pi_{i}H_{i}\tau_{i})^{T}=\pi_{i}H_{i}H_{i}^{T}\pi_{i}^{T}$
has the same spectrum as $H_{i}H_{i}^{T}$. Assume without loss of generality
that the minimum distance of $\mathcal{Q}(H_{1},H_{2},H_{3})$ corresponds to a
$Z$-logical operator and let $(S,T,U,V)$ be the choice of generators leading
to the minimum weight representative of the logical error, similarly to (21).
The logical operator admits the form (replacing the shorthands $x,y,z$ by
their explicit forms):

$\displaystyle A=\begin{bmatrix}H_{1}^{T}S\\\ H_{2}^{T}T\\\
H_{3}^{T}U+R\end{bmatrix}\quad B=\begin{bmatrix}H_{1}T\\\ H_{2}S\\\
H_{3}^{T}V+R\end{bmatrix}\quad C=\begin{bmatrix}H_{1}U\\\ H_{2}^{T}V\\\
H_{3}S\end{bmatrix}\quad D=\begin{bmatrix}H_{1}^{T}V\\\ H_{2}U\\\
H_{3}T\end{bmatrix}?$

We note that a representative of the $Z$-logical operator of the new code
$\mathcal{Q}(\pi_{1}H_{1}\tau_{1},\pi_{2}H_{2}\tau_{2},\pi_{3}H_{3}\tau_{3})$
is given by 2 full horizontal layers of Pauli-$Z$ operators in $A$ and $B$
with support $\tau_{3}^{T}R$. Defining
$S^{\prime},T^{\prime},U^{\prime}V^{\prime}$ as

$S^{\prime}=(\pi_{1}\otimes\tau_{2}^{T}\otimes\tau_{3}^{T})S,\;\;T^{\prime}=(\tau_{1}^{T}\otimes\pi_{2}\otimes\tau_{3}^{T})T,\;\;U^{\prime}=(\tau_{1}^{T}\otimes\tau_{2}^{T}\otimes\pi_{3})U,\;\;V^{\prime}=(\pi_{1}\otimes\pi_{2}\otimes\pi_{3})V,$

we obtain the following representative of the logical error:

$\displaystyle A^{\prime}$
$\displaystyle=\begin{bmatrix}(\pi_{1}H_{1}\tau_{1})^{T}S^{\prime}\\\
(\pi_{2}H_{2}\tau_{2})^{T}T^{\prime}\\\
(\pi_{3}H_{3}\tau_{3})^{T}U^{\prime}+\tau_{3}^{T}R\end{bmatrix}=(\tau_{1}^{T}\otimes\tau_{2}^{T}\otimes\tau_{3}^{T})\begin{bmatrix}H_{1}^{T}S\\\
H_{2}^{T}T\\\ H_{3}^{T}U+R\end{bmatrix}$ $\displaystyle B^{\prime}$
$\displaystyle=\begin{bmatrix}(\pi_{1}H_{1}\tau_{1})T^{\prime}\\\
(\pi_{2}H_{2}\tau_{2})S^{\prime}\\\
(\pi_{3}H_{3}\tau_{3})^{T}V^{\prime}+\tau_{3}^{T}R\end{bmatrix}=(\pi_{1}\otimes\pi_{2}\otimes\tau_{3}^{T})\begin{bmatrix}H_{1}T\\\
H_{2}S\\\ H_{3}^{T}V+R\end{bmatrix}$ $\displaystyle C^{\prime}$
$\displaystyle=\begin{bmatrix}(\pi_{1}H_{1}\tau_{1})U^{\prime}\\\
(\pi_{2}H_{2}\tau_{2})^{T}V^{\prime}\\\
(\pi_{3}H_{3}\tau_{3})S^{\prime}\end{bmatrix}=(\pi_{1}\otimes\tau_{2}^{T}\otimes\pi_{3})\begin{bmatrix}H_{1}U\\\
H_{2}^{T}V\\\ H_{3}S\end{bmatrix}$ $\displaystyle D^{\prime}$
$\displaystyle=\begin{bmatrix}(\pi_{1}H_{1}\tau_{1})^{T}V^{\prime}\\\
(\pi_{2}H_{2}\tau_{2})U^{\prime}\\\
(\pi_{3}H_{3}\tau_{3})T^{\prime}\end{bmatrix}=(\tau_{1}^{T}\otimes\pi_{2}\otimes\pi_{3})\begin{bmatrix}H_{1}^{T}V\\\
H_{2}U\\\ H_{3}T\end{bmatrix},$

which has the same weight as the minimal logical error of
$\mathcal{Q}(H_{1},H_{2},H_{3})$. ∎

####  5.4.2 Ruling out expansion-based arguments

It is tempting to consider the XYZ product built from classical expander
codes. Indeed, we might be able to use the expansion properties to get a good
lower bound on the minimum distance. Recall for instance that classical
expander codes have a linear minimum distance [34] and that quantum expander
codes (built from classical expander codes) saturate the $\Theta(\sqrt{N})$
upper bound for the distance of hypergraph product codes [28]. Even more so,
quantum expander codes have the property that any error $\mathcal{E}$ of
weight $O(N^{1/2})$ is expanding in the sense that its syndrome
$\sigma(\mathcal{E})$ is large:

$\forall\mathcal{E}\quad\text{s.t.}\quad|\mathcal{E}|\leq\gamma\sqrt{N},\quad|\sigma(\mathcal{E})|\geq
c|\mathcal{E}|,$

for some constants $\gamma,c>0$.

When taking the XYZ product of three classical expander codes of size
$n_{i}=\Theta(n)$, one could naively expect a similar phenomenon to hold for
errors of weight up to $N^{2/3}=n^{2}$. Unfortunately, it seems that for any
$\delta>0$ we can construct errors of weight
$n^{2-\delta}=\Theta(N^{2/3-\delta/3})$ for which the syndrome has weight777A
caveat is that it is not entirely clear at this point that the error cannot be
reduced modulo the stabilizer, although this seems unlikely. only $O(n)$.

The construction is algebraic in nature, and goes as follows: consider an
error operator that corresponds to two horizontal slices (not necessarily full
slices) of $Z$-errors in $A$ and $B$. Denote the support of the $Z$-errors on
these slices by the matrices or 2-tensors $P$ and $Q$, respectively. Then the
syndrome (in matrix notation) is given by the corresponding slices in $S$ and
$T$:

$S=H_{1}P+QH_{2},\qquad T=PH_{2}^{T}+H_{1}^{T}Q.$

We will define the error tensors $P$ and $Q$ as follows: for some matrix $X$,
let

$\displaystyle P$
$\displaystyle:=H_{1}^{T}\left(\sum_{\ell=0}^{k-1}(H_{1}H_{1}^{T})^{\ell}X(H_{2}H_{2}^{T})^{k-\ell-1}\right)H_{2}$
$\displaystyle Q$
$\displaystyle:=(H_{1}H_{1}^{T})\left(\sum_{\ell=0}^{k-1}(H_{1}H_{1}^{T})^{\ell}X(H_{2}H_{2}^{T})^{k-\ell-1}\right).$

Now we calculate the syndrome associated to error $(P,Q)$:

$\displaystyle S$ $\displaystyle=H_{1}P+QH_{2}=0$ $\displaystyle T$
$\displaystyle=PH_{2}^{T}+H_{1}^{T}Q$
$\displaystyle=H_{1}^{T}\left(\sum_{\ell=0}^{k-1}(H_{1}H_{1}^{T})^{\ell}X(H_{2}H_{2}^{T})^{k-\ell}+\sum_{\ell=0}^{k-1}(H_{1}H_{1}^{T})^{\ell+1}X(H_{2}H_{2}^{T})^{k-\ell-1}\right)$
$\displaystyle=H_{1}^{T}\left(X(H_{2}H_{2}^{T})^{k}+(H_{1}H_{1}^{T})^{k}X\right).$

The most important observation now is that almost all of the terms of the
original error cancel, and it seems likely that this will prevent expansion of
the errors. Indeed, assume that $X$ has Hamming weight $|X|\in O(1)$. By the
expansion of $H_{1}$ and $H_{2}$, we expect that the error weight $|P|+|Q|$
will increase more or less monotonically with $k$ (up to $\Theta(n^{2})$).
Hence there will be a range of $k$ such that the error has weight
$|P|+|Q|\in\omega(n)$. For the error in this range to be expanding, we need
that also the syndrome has weight $|S|+|T|\in\omega(n)$. However, as is
apparent from the expressions for $S$ and $T$, it always holds that the
syndrome weight $|S|+|T|\in O(n)$ (both terms in $T$ are supported on only
$O(1)$ rows or columns).

This construction shows that expansion arguments are unlikely to be useful in
the study of XYZ product codes: while it is easy to show that errors of weight
$O(N^{1/3})$ expand (simply by applying the same method as for the quantum
expander codes [28]), our argument suggests that similar methods fail for
errors of weight $\omega(N^{1/3})$.

###  5.5 XYZ product codes from parity-check matrices with even row/column
weight

Let us first focus on the Chamon code which provides a specific instance of
XYZ product code with parity-check matrices with rows and columns of weight 2.
Lemma 23 shows that the Chamon code has the same distance as
$\mathcal{Q}(H_{1},H_{2},H_{3})$ with
$H_{i}=\Omega_{n_{i}}+\Omega_{n_{i}}^{T}$ when the $n_{i}$’s are odd (so that
the map $\ell\to 2\ell\mod n_{i}$ corresponds to a permutation of $[n_{i}]$).
Let us consider for simplicity the case where $\gcd(n_{1},n_{2},n_{3})=1$
yielding a code of dimension 4 [8]. Any representation of the
$\overline{Z}_{i}$ logical operator ($i\in\\{1,2,3,4\\}$) takes the form

$\displaystyle A_{i}=\begin{bmatrix}H_{1}S\\\ H_{2}T\\\
H_{3}U+\delta_{i,1}R\end{bmatrix}\quad B_{i}=\begin{bmatrix}H_{1}T\\\
H_{2}S\\\ H_{3}V+\delta_{i,2}R\end{bmatrix}\quad
C_{i}=\begin{bmatrix}H_{1}U\\\ H_{2}V\\\
H_{3}S+\delta_{i,3}R\end{bmatrix}\quad D_{i}=\begin{bmatrix}H_{1}V\\\
H_{2}U\\\ H_{3}T+\delta_{i,4}R\end{bmatrix},$

where $(S,T,U,V)$ is an arbitrary stabilizer element and $\delta_{i,1}=1$ if
$i=1$ and 0 otherwise. In particular, the logical operator
$\overline{Z}_{1}\overline{Z}_{2}\overline{Z}_{3}\overline{Z}_{4}$ corresponds
to $(A_{1},B_{2},C_{3},D_{4})$. Its weight gives an _upper_ bound on the
distance $d$ of the Chamon code:

$\displaystyle d$ $\displaystyle\leq
w(\overline{Z}_{1}\overline{Z}_{2}\overline{Z}_{3}\overline{Z}_{4})$
$\displaystyle=\min_{S,T,U,V}(|A_{1}|+|B_{2}|+|C_{3}|+|D_{4}|)$
$\displaystyle\leq\min_{S=T=U=V}(|A_{1}|+|B_{2}|+|C_{3}|+|D_{4}|)$
$\displaystyle=d_{*}$

where we imposed the constraint $S=T=U=V$ in the third line and defined
$d_{*}$ as

$\displaystyle
d_{*}:=\min_{M}2\left(|(H_{1}+H_{2})M|+|(H_{1}+H_{3})M+R|+|(H_{2}+H_{3})M+R|\right).$
(23)

The argument generalizes immediately to any XYZ product code where
$H_{i}=H_{i}^{T}$, with odd $n_{i}$’s. The triangle inequality
$|A|+|B|+|C|+|D|\geq|A+B+C+D|$ also shows that

$d_{*}\leq w(\overline{Z}_{1})$

by setting $M=S+T+U+V$. This does not directly lead to a lower bound on the
minimum distance, however, because one needs to consider all $4^{k}-1$
possible logical operators of the code.

##  6 Cyclic 3D XYZ code and polynomial formalism

We focus in this section on translation-invariant codes. In the next section,
we will study in greater detail one of the simplest instances of such codes,
which can be embedded with local interaction in 3 dimensions.

In order to get a translation invariant code, it is possible to take parity-
check matrices which are circulant matrices. A square matrix of dimension is
called circulant when every row is shifted by one element w.r.t. the preceding
row. Such a matrix can be described by a polynomial $H=P(\Omega)$ in the
permutation matrix $\Omega$, defined by $\Omega|j\rangle=|j+1\mod n\rangle$
(so that $\Omega^{n}=\mathbbm{1}_{n}$). Alternatively, these operators can be
described even more concisely using a polynomial formalism where we describe
$\Omega$ using a variable $x$, and a circulant matrix $H=P(\Omega)$ is
described by the polynomial $P(x)\in\mathbbm{F}_{2}[x]/(1+x^{n})$ (i.e., the
polynomial ring over $\mathbbm{F}_{2}$ with $x^{n}=1$).

With this formalism we wish to revisit the question about the minimum
distance, and in particular the decoupling argument (Section 5) which showed
that the minimum distance problem reduces to a problem about 3-tensors. In the
polynomial formalism we describe such an $n_{1}\times n_{2}\times n_{3}$
tensor by a multivariate polynomial

$P(x,y,z)\in\mathbbm{F}_{2}[x,y,z]/(x^{n_{1}}+1,y^{n_{2}}+1,z^{n_{3}}+1)=:\mathbbm{F}_{2}[x,y,z]/I,$

using the shorthand $I$ for the ideal $(x^{n_{1}}+1,y^{n_{2}}+1,z^{n_{3}}+1)$.
The presence of a monomial $x^{i}y^{j}z^{k}$ in $P$ denotes the presence of a
1 in position $(i,j,k)$ of the tensor. As an example, consider the natural
$Z$-logical operator ($R$ in Section 5) corresponding to a full horizontal
slice. In the polynomial formalism we can describe it using the polynomial

$R(x,y,z)=\sum_{i=0}^{n_{1}-1}\sum_{j=0}^{n_{2}-1}x^{i}y^{j}.$

If we want that the code can be embedded in 3 dimensions with local
interactions, then it suffices to pick polynomials $P_{i}$ (describing the
$H_{i}$’s) of the form

$\displaystyle P_{1}(x)$ $\displaystyle=1+\sum_{i\in\mathcal{I}}x^{i}+x^{-i}$
$\displaystyle P_{2}(y)$ $\displaystyle=1+\sum_{j\in\mathcal{J}}y^{j}+y^{-j}$
$\displaystyle P_{3}(z)$ $\displaystyle=1+\sum_{k\in\mathcal{K}}z^{k}+z^{-k},$

with
$\max(i\>:\>i\in\mathcal{I}),\max(j\>:\>j\in\mathcal{J}),\max(k\>:\>k\in\mathcal{K})=O(1)$.
Note that $x^{-i}$ corresponds to $x^{n_{1}-i}$. Here, we restrict to
“symmetric” polynomials (satisfying the symmetry $x\leftrightarrow x^{-1}$)
for simplicity. The fact that each of the sets
$\mathcal{I},\mathcal{J},\mathcal{K}$ has constant size is equivalent to
saying that the quantum code is LDPC. Indeed, the weight of a generator will
be $3+2(|\mathcal{I}|+|\mathcal{J}|+|\mathcal{K}|)$.

Now we are ready to revisit the decoupling argument. Define the polynomial
$Q_{1}$ by

$\displaystyle
Q_{1}(x)=(1+P_{1}(x))^{2}:=\sum_{i\in\mathcal{I}}x^{2i}+x^{-2i},$ (24)

and similarly for $Q_{2}$ and $Q_{3}$. Using these polynomials, and Theorem
22, we see that the minimum distance (up to constant factors, see the remark
below Theorem 22) is given by

$\min_{P\in\mathbbm{F}_{2}[x,y,z]/I}\Big{(}|(Q_{1}+Q_{2})P|+|(Q_{1}+Q_{3})P+R|\Big{)},$

where we omit the variables for conciseness. This minimum is at most equal to
$|R|=n_{1}n_{2}$, which is achieved by setting $P=0$. The main question is
whether there exists a choice for $P$ such that the distance is significantly
less. While we will not solve this question here, it is interesting to
understand which properties a polynomial $P$ should display to get a small
weight for $(Q_{1}+Q_{2})P$.

###  6.1 Fractal operators

For simplicity, we would like to focus on a choice of polynomials that ensures
that the dimension of the quantum code is equal to 1. As explained in Section
5, taking a triple $(H_{1},H_{2},H_{3})\in\mathcal{T}$ ensures that the map

$\Phi_{12}\>:\>P(x,y)\mapsto(Q_{1}(x)+Q_{2}(y))P(x,y)$

is almost bijective on $F_{2}[x,y]/(x^{n_{1}}+1,y^{n_{2}}+1)$. In fact, the
image is equal to all polynomials with even weight and the kernel of the map
has dimension 1:

$\ker\Phi_{12}=\left\\{0,\sum_{i=0}^{n_{1}-1}\sum_{j=0}^{n_{2}-1}x^{i}y^{j}\right\\}.$

To understand the structure of polynomials such that $|\Phi_{12}(P)|$ is
small, it is useful to recall the Froebenius endomorphism $F$ on the
polynomial ring, which is given by

$F(p(x,y))=p(x^{2},y^{2}),$

with the property that $F(P+Q)=F(P)+F(Q)$. In particular, it implies that

$(Q_{1}(x)+Q_{2}(y))^{2^{k}}=(Q_{1}(x))^{2^{k}}+(Q_{2}(y))^{2^{k}}=Q_{1}(x^{2^{k}})+Q_{2}(y^{2^{k}}),$

and hence

$\Phi_{12}\big{(}(Q_{1}(x)+Q_{2}(y))^{2^{k}-1}\big{)}=(Q_{1}(x)+Q_{2}(y))^{2^{k}}=Q_{1}(x^{2^{k}})+Q_{2}(y^{2^{k}}).$

This gives the bound

$\displaystyle\left|\Phi_{12}\left((Q_{1}(x)+Q_{2}(y))^{2^{k}-1}\right)\right|=\big{|}Q_{1}(x^{2^{k}})+Q_{2}(y^{2^{k}})\big{|}\leq|Q_{1}(x)|+|Q_{2}(y)|.$

Note that we do not get an equality in general because cancellations might
occur modulo $n_{1}$ or $n_{2}$. A polynomial of the form
$(Q_{1}(x)+Q_{2}(y))^{2^{k}-1}$ will be referred to as a _fractal operator_.

It is also interesting to understand what polynomials $P$ are such that
$|(Q_{1}+Q_{3})P+R|$ is small. For this, taking a fractal operator is not
sufficient: while $(Q_{1}+Q_{3})P$ might have some support on the support of
$R$, it also has support on the complement of $R$. However, defining
$m_{3}:=2^{n_{3}-1}-1$, $P_{13}(x,z):=(Q_{1}(x)+Q_{3}(z))^{m_{3}}+1$, and
$\Phi_{13}$ in analogy to $\Phi_{12}$, we get:

$\displaystyle\Phi_{13}(P_{13}(x,z))$
$\displaystyle=(Q_{1}(x)+Q_{3}(z))P_{13}(x,z)$
$\displaystyle=(Q_{1}(x)+Q_{3}(z))^{m_{3}+1}+Q_{1}(x)+Q_{3}(z)$
$\displaystyle=(Q_{1}(x)+Q_{3}(z))^{2^{n_{3}-1}}+Q_{1}(x)+Q_{3}(z)$
$\displaystyle=Q_{1}(x)^{2^{n_{3}-1}}+Q_{1}(x)+Q_{3}(z)^{2^{n_{3}-1}}+Q_{3}(z)$
$\displaystyle=Q_{1}(x)^{2^{n_{3}-1}}+Q_{1}(x)+Q_{3}(z^{2^{n_{3}-1}})+Q_{3}(z)$
$\displaystyle=Q_{1}(x)^{2^{n_{3}-1}}+Q_{1}(x)$

where the last equality follows from the fact that $2^{n_{3}-1}=1\mod n_{3}$
and therefore $z^{2^{n_{3}-1}}=z$ on the ring
$\mathbbm{F}_{2}[z]/(z^{n_{3}}+1)$. We get that $\Phi_{13}(P_{13})$ is
supported on a single row (in the $x$-direction), having weight at most
$n_{1}$.

Now in order to get a polynomial $P$ such that $|(Q_{1}+Q_{3})P+R|$ is small,
one could therefore choose a polynomial of the form

$P(x,y,z)=\sum_{y=0}^{n_{2}-1}y^{j}P_{j}(x,z),$

which corresponds to $y$-translates of the $x$-$z$ planes $P_{j}(x,z)$. If we
choose $P_{j}(x,z)$ close to polynomials of the form $S_{j}(x)P_{13}(x,z)$,
then the weight of $S_{j}(x)(Q_{1}(x)^{2^{n_{3}-1}}+Q_{1}(x))$ is close to
$n_{1}$ (by our former argument), which in turn implies that
$|(Q_{1}+Q_{3})P+R|$ is small. At the same time, writing this polynomial as
$P(x,y,z)=\sum_{k=0}^{n_{3}-1}z^{k}P_{k}(x,y)$, one asks whether each $P_{k}$
can be a small sum of fractal operators, to ensure that $|(Q_{1}+Q_{2})P_{k}|$
is small. It is tempting here to try to argue that if $P$ was chosen so that
$|(Q_{1}+Q_{3})P+R|$ is small, then there must exist some choice of $Q_{2}$
for which the $|(Q_{1}+Q_{2})P_{k}|$ cannot all be small. Formalizing a
probabilistic argument along these lines may be an approach to proving the
existence of XYZ product codes with distance $\Theta(N^{2/3})$ but appears to
be a complicated problem.

In the next section, we will argue that taking $Q_{1}=Q_{2}=Q_{3}$, but
distinct $n_{i}$’s (which is for instance the case of the original Chamon’s
code) may often lead to the existence of low-weight logical operators, and
therefore a distance possibly as small as $\Theta(N^{1/3})$.

We remark that the existence of fractal operators which can have a linear
weight but a constant-weight syndrome shows that the cyclic XYZ product codes
investigated here cannot be locally testable [1].

###  6.2 Embedding in 3-dimensional space

Let us quickly remark on the possibility to locally embed such a code in three
dimensions. We consider a lattice of size $n_{1}\times n_{2}\times n_{3}$ with
boundary conditions. Putting 4 qubits per site (one qubit of each type,
$A,B,C,D$), one obtains a topological code with generators of weight
$d_{1}+d_{2}+d_{3}$, where $d_{i}$ is the weight of $P_{i}$. To ensure that
the quantum code admits geometrically local generators, it is sufficient that
the three classical codes are local in 1 dimension.

##  7 The simplest 3D XYZ code

A general upper bound on the distance for 3-dimensional topological codes is
$d=O(N^{2/3})$ [6] and it is an open question whether this bound is tight or
whether the correct value is $O(N^{1/2})$ as suggested by all known code
constructions. We try to shed new light on this question by investigating one
of the simplest XYZ product codes embeddable in 3 dimensions. Let ${\cal
Q}(H_{1},H_{2},H_{3})$ be the XYZ product code derived from the parity-check
matrices

$H_{i}=\mathbbm{1}_{n_{i}}+\Omega_{n_{i}}+\Omega_{n_{i}}^{T},$

with $\Omega_{n_{i}}|j\rangle=|j+1\mod n_{i}\rangle$. The only freedom in the
code construction is the choice of the triple $(n_{1},n_{2},n_{3})$. We will
first compute the dimension of this 3D XYZ code when the $n_{i}$’s are odd and
not multiples of 3. The formula for the dimension is similar to that of the
Chamon code, but with what looks like an extra qubit. By taking the $n_{i}$’s
to be coprime, we can ensure that only this logical qubit is encoded, and so
the code has dimension 1. For this particular case we show that most choices
of $n_{i}$’s lead to a distance upper bounded by $N^{1/3}$. While this does
not rule out the existence of families of $n_{i}$’s leading to a larger
distance, it strongly suggests that taking slightly more complicated parity-
check matrices will be required to beat the $\sqrt{N}$ barrier. Indeed, recall
from Lemma 23 that permuting the rows and columns of the parity-check matrices
does not change the minimum distance. As a consequence, any circulant matrices
with columns of weight 3 will lead to the same distance, and columns of weight
5 will probably be necessary to get better parameters.

######  Remark 24.

Ref. [8], which focused on the Chamon code, also suggested some
generalizations where the repetition code would be replaced by symmetric
circulant matrices with even row weight. Unfortunately, the decoupling
argument of Theorem 22 does not apply in that case since the 3-tensor $R$
corresponding to a single horizontal plane of 1s is not stabilized by
circulant matrices of even weight.

###  7.1 Dimension of the 3D XYZ code

Using Theorem 2 we can prove the following claim on the dimension of the 3D
XYZ code.

######  Claim 25.

If $n_{1}$, $n_{2}$ and $n_{3}$ are odd and no multiples of 3, then the
dimension of the 3D XYZ code is

$4(\gcd(n_{1},n_{2},n_{3})-1)+1.$

To prove the claim, first fix some $n$ and let
$H=\mathbbm{1}+\Omega+\Omega^{T}$ be the corresponding matrix of dimension
$n$. We can prove the following lemma.

######  Lemma 26.

Assume $n$ is odd and let $z$ be a primitive $n$-th root of unity888A solution
of $z^{n}=1$ such that $z^{k}\neq 1$ for $k<n$. Such a root always exists when
$n$ is odd.. Then the matrix $H=\mathbbm{1}+\Omega+\Omega^{T}$ is
diagonalizable (over the algebraic closure of $\overline{\mathbb{F}}_{2}$)
with eigenvalues

$1,1+z+z^{-1},\dots,1+z^{n-1}+z^{-n+1}.$

It is invertible if and only if $n$ is not a multiple of 3.

###### Proof.

First we note that the characteristic polynomial of $\Omega$ is $x^{n}+1$, so
that its eigenvalues are given by the $n$-th roots of unity. Over any field of
characteristic 2, if $n$ is odd then there exist $n$ distinct roots of unity
$1,z,z^{2},\dots,z^{n-1}$. This implies that $\Omega$ is diagonalizable with
eigenvalues $1,z,\dots,z^{n-1}$. The first claim then follows by noting that
$\Omega^{T}=\Omega^{-1}$, and that $\Omega^{-1}$ is diagonal in the same basis
with eigenvalues $1,z^{-1},\dots,z^{-n+1}$.

$H$ will be invertible if there is no $0\leq k\leq n-1$ such that
$1+z^{k}+z^{n-k}=0$. This is equivalent to $1+z^{k}+z^{2k}=0$, and combining
these equations shows that necessarily $z^{2k}=z^{n-k}$, or equivalently
$z^{3k}=z^{n}=1$. Since $z$ is a primitive root, this implies that $k=n/3$ or
$k=2n/3$, so that there is a solution if and only if $n$ is a multiple of 3. ∎

Now assume that the $n_{i}$’s are odd and no multiples of 3, ensuring that the
$H_{i}$’s are invertible. Moreover, $H_{i}^{2}$ and $H_{i}$ are similar if $n$
is odd. From Theorem 2 it follows that the dimension of the code is
$\sum_{i,j,k}\mathrm{deg}(\mathrm{gcd}(p^{1}_{i},p^{2}_{j},p^{3}_{k}))$ with
$p^{1}_{i},p^{2}_{j},p^{3}_{k}$ the characteristic polynomials of the Jordan
blocks of $H_{1}^{2},H_{2}^{2},H_{3}^{2}$ (respectively). By the lemma above
the Jordan blocks are 1-dimensional and hence the dimension is simply

$\sum_{i,j,k}\mathrm{deg}(\mathrm{gcd}(p^{1}_{i},p^{2}_{j},p^{3}_{k}))=\sum_{i=0}^{n_{1}-1}\sum_{j=0}^{n_{2}-1}\sum_{k=0}^{n_{3}-1}\mathbf{1}(\lambda_{n_{1}}^{i}=\lambda_{n_{2}}^{j}=\lambda_{n_{3}}^{k}),$

where $\lambda_{n_{i}}^{j}=1+z_{n_{i}}^{j}+z_{n_{i}}^{-j}$ with $z_{n_{i}}$ a
primitive $n_{i}$-th root of unity. This corresponds to the number of
solutions to the equation

$x^{a}+x^{-a}=y^{b}+y^{-b}=z^{c}+z^{-c}$

for $0\leq a<n_{1}$, $0\leq b<n_{2}$, $0\leq c<n_{3}$ and $x,y,z$ primitive
$n_{1}$-, $n_{2}$\- and $n_{3}$-th roots of unity. By the following lemma this
proves Claim 25.

######  Lemma 27.

Let $x,y,z$ be primitive $k$-, $\ell$-, and $m$-th roots of unity
(respectively). Then the number of solutions to the equation
$x^{a}+x^{-a}=y^{b}+y^{-b}=z^{c}+z^{-c}$ (with $0\leq a<k$, $0\leq b<\ell$ and
$0\leq c<m$) is equal to $4(\gcd(k,\ell,m)-1)+1$

###### Proof.

First we show that the number of solutions is $4(q-1)+1$ with $q$ the number
of solutions to the equation $x^{a}=y^{b}=z^{c}$ (with $0\leq a<k$, $0\leq
b<l$ and $0\leq c<m$). To this end we use that $x+1/x=y+1/y$ (for $x,y\neq 0$)
implies that $x=y$ or $x=1/y$. To see this, note that $x+1/x=y+1/y$ is
equivalent to $x^{2}+(y+1/y)x+1=(x+y)(x+1/y)=0$. On its turn, this implies
that $x^{a}+x^{-a}=y^{b}+y^{-b}=z^{c}+z^{-c}$ is equivalent to $x^{a}=y^{\pm
b}=z^{\pm c}$ (for some choice of the signs). The number of solutions to
$x^{a}=y^{\pm b}=z^{\pm c}$ is then given by $4(q-1)+1$ where $q$ is the
number of solutions to $x^{a}=y^{b}=z^{c}$. Indeed, every solution $(a,b,c)$
of $x^{a}=y^{b}=z^{c}$ with $a,b,c\neq 0$ gives rise to 4 distinct solutions
$(a,\pm b,\pm c)$ of $x^{a}=y^{\pm b}=z^{\pm c}$ (using that $y^{b}\neq
y^{-b},z^{c}\neq z^{-c}$ for $0<b<\ell$ and $0<c<m$). On the other hand, if
either $a=0$, $b=0$ or $c=0$ then necessarily $a=b=c=0$ (since the roots are
primitive), so this case corresponds to a single solution of
$x^{a}=y^{b}=z^{c}$, and it gives rise to only 1 solution to $x^{a}=y^{\pm
b}=z^{\pm c}$.

Next we show that the number of solutions $(a,b,c)$ to $x^{a}=y^{b}=z^{c}$ is
$q=\gcd(k,\ell,m)$. First note that if $(a,b,c)$ is a solution then
$x^{ak}=x^{a\ell}=x^{am}=1$. Hence $a\ell=qk$ and $am=rk$ for integers $q$ and
$r$. This implies that $am\ell=mqk=rk\ell$ is a common multiple of $k\ell$,
$\ell m$ and $km$. Moreover every $a<k$ defines a unique such common multiple