%% LyX 1.6.10 created this file.  For more info, see http://www.lyx.org/.
%% Do not edit unless you really know what you are doing.
\documentclass[english]{IEEEtran}
\usepackage[T1]{fontenc}
\usepackage[latin9]{inputenc}
\usepackage{amsthm}
\usepackage{graphicx}
\usepackage{amssymb}

\makeatletter
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Textclass specific LaTeX commands.
\theoremstyle{plain}
\newtheorem{thm}{Theorem}
\theoremstyle{definition}
\newtheorem{defn}[thm]{Definition}
\theoremstyle{remark}
\newtheorem{rem}[thm]{Remark}
\theoremstyle{plain}
\newtheorem{lem}[thm]{Lemma}
\theoremstyle{plain}
\newtheorem{cor}[thm]{Corollary}

\makeatother

\usepackage{babel}

\begin{document}

\title{A Good Family of Quantum Low-Density Parity-Check Codes}


\author{Reina Riemann%
\thanks{Reina Riemann. Computer Science and Artificial Intelligence Laboratory.
Massachusetts Institute of Technology. Cambridge, MA 02139, USA. e-mail:
riemann@mit.edu%
} and Peter Shor%
\thanks{Peter Shor. Department of Mathematics. Massachusetts Institute of
Technology. Cambridge, MA 02139, USA. e-mail: shor@math.mit.edu%
}}

\maketitle
~
\begin{abstract}
We present a good family of quantum low-density parity-check error-correcting
codes. This family is derived from regular Platonic surfaces. We present
a logarithmic lower bound on their shortest noncontractible cycle
and therefore on the distance of the family of codes. We show the
asymptotical low-density of their matrices, and show their asymptotical
nonzero rate. We simulate their good decoding performance. This family
answers a conjecture proposed by MacKay about the existence of families
of quantum low-density parity-check (LDPC) codes with nonzero rate,
growing minimum distance and a practical decoder.

~

Index Terms---Low-density parity-check codes, message passing decoding,
quantum codes. 

~
\end{abstract}

\section{Introduction}

~

From a theoretical perspective a good family of error-correcting codes
corrects errors in proportion to the block length of the codes and
has a practical decoder \cite{mackaygoodcodes}. For example classical
low-density parity-check codes (LDPC), first introduced by Gallager
\cite{gallager}, approach the Gilbert-Varshamov bound and have a
practical decoder. LDCP codes have reemerged as one of the most influential
coding schemes. Their sparse local parity-check dependencies imply
low decoding complexity when using local iterative message-passing
decoding algorithms. Classical LDPC and LDPC-like codes decoded with
message-passing decoders are used in practice such as in internet
and mobile media broadcast, optical networking and other applications.

The development of quantum information theory paves the way to the
development of quantum computers extending the notion of classical
channels and error-correcting codes \cite{QuantumInformationTheory}.
The existence of good quantum error-correcting codes was shown non-constructively
by Calderbank and Shor \cite{shorgood}. In 2003, MacKay \cite{mackayquantum}
introduced some promising individual examples of quantum LDPC codes.
MacKay's codes are dual-containing stabilizer codes whose matrix representation
is sparse. Several theoretical questions were raised by this work
including a conjecture about the existence of good families of sparse-graph
quantum error-correcting codes with nonzero rate, growing minimum
distance and a practical decoder. We answer this conjecture by presenting
one such family here.

We present a family of good sparse quantum error-correcting codes
with asymptotic logarithmic distance.We show their asymptotical sparsity,
non-zero rate, and their decoding performance with belief propagation.
These codes are derived from sparse graphs, induced by tessellations
of topological surfaces, and are therefore a type of low-density parity-check
(LDPC) code. Note that while most known LDPC codes are derived from
regular graphs, there are known classical LDPC codes derived from
irregular graphs \cite{mackaryirregular}.

The low-density parity-check families of quantum codes that we present
are generalizations of Kitaev's codes \cite{kitaevquantum} to surfaces
of genus $g$ that encode $2g$ qubits, as explained in section III.
Kitaev's topological codes are a class of stabilizer codes derived
from lattices on surfaces of single genus, or tori, with asymptotical
zero rate.

In section II we give definitions, background and notation used in
this paper. In section III we review stabilizer quantum error-correcting
codes, topological quantum error-correcting codes and their generalization
to tessellations on 2-manifolds. In section IV we describe the family
of Platonic graphs and surfaces. We present a quantum code derived
from $\pi_{7}$ and a good family of Platonic quantum low-density
parity-check codes. We derive the asymptotical low-density of their
matrices and their rate. In section V we provide a logarithmic lower
bound on their distance. In section VI we present decoding simulations
using belief propagation. In section VII we provide our insights and
conclusions.

~


\section{\label{sec:Definitions}Definitions}

~

In this section we introduce the topological graph-theoretical definitions
used in the quantum error-correcting codes families of codes that
we present in this paper. Let $G=(V,\, E)$ ~be a graph, where $V$
is a set of vertices, and $E$, a set of edges.

$\:$ 
\begin{defn}
If a graph $G$ can be drawn on a $2-dimensional$ $manifold$ or
surface $M$ without edge crossing, then it is said to be $embedded$
on this manifold.
\end{defn}
$\,$

The family of quantum error-correcting codes that we present is derived
from embeddings of graphs on 2-dimensional surfaces.

~ 
\begin{defn}
An embedding of a graph is a $tessellation$ of a surface. 
\end{defn}
~ 
\begin{defn}
The $genus$ of a graph $G$ is the smallest genus of a $2-dimensional$
manifold $M$ in which the graph can be embedded. 
\end{defn}
$\,$

The genus of the surfaces on which these graphs are embedded is related
to the number of qubits that can be encoded as explained in the next
section, topological quantum error-correcting codes.

~ 
\begin{defn}
A $planar$ graph is a graph that can be embedded in a surface of
genus $0,$ that is the plane. 
\end{defn}
$\,$ 
\begin{defn}
The $girth$ of a graph is the length of its shortest cycle. 
\end{defn}
$\:$ 
\begin{defn}
The $shortest$ $noncontractible$ $cycle$ of a graph of genus $g$
is the length of the shortest cycle or closed path that is not a face
of the induced tessellation. A face is one of the open discs derived
from the difference between the two dimensional manifold $M$ and
the embedded graph. 
\end{defn}
$\,$

Furthermore the shortest noncontractible cycle of a graph is related
to the number of errors that the code can correct as we explain in
the next section.

~


\section{\label{sec:Topological-Quantum-Error-correcting}Topological Quantum
Error-correcting Codes}

~

Topological codes are a class of stabilizer codes associated with
tessellations of manifolds. Stabilizer codes can be described in terms
of group theory or of binary vector spaces. In terms of group theory
a codeword is the $+1$ eigenstate of the group generated by a stabilizer
set.

In terms of binary vector spaces, a stabilizer code is described by
a pair of binary matrices whose rows represent generators, and whose
columns represent different qubits. One matrix is associated with

\begin{eqnarray*}
X & = & \left[\begin{array}{cc}
0 & 1\\
1 & 0\end{array}\right]\end{eqnarray*}


and the other matrix with 

\begin{eqnarray*}
Z & = & \left[\begin{array}{cc}
1 & 0\\
0 & -1\end{array}\right]\end{eqnarray*}


Simultaneous entries in both matrices are associated with 

\begin{eqnarray*}
Y & = & \left[\begin{array}{cc}
0 & -i\\
i & 0\end{array}\right]\end{eqnarray*}


Multiplication of generators is equivalent to vector addition $mod$
2. Elements of the stabilizer group have to commute with each other,
otherwise they stabilize the trivial space.

Using MacKay's notation \cite{mackayquantum}, let $a_{i}|b_{i}$
denote a binary vector, where $a_{i}$ is in row $i$ of the matrix
of a stabilizer parity check matrix associated with $X$ errors and
$b_{i}$ is in the matrix associated with $Z$ errors. Let $a_{j}|b_{j}$
be another such vector, then the condition that two stabilizer generators
commute is equivalent to the following product:

\begin{eqnarray*}
a_{i}\centerdot b_{j} & +a_{j}\centerdot b_{i}\equiv & 0\; mod\;2\end{eqnarray*}


The binary vector view of stabilizer codes emphasizes connections
between classical and quantum error correcting codes.

Kitaev's toric codes are defined by an $L\times L$ lattice on the
torus. The encoding qubits are associated with edges of this lattice.
The related stabilizer quantum error-correcting code check operators
are associated with faces and vertices as follows:

\begin{eqnarray*}
Z^{face} & = & \prod_{e\in face}Z_{e}\\
X^{vertex} & = & \prod_{e\in vertex}X_{e}\end{eqnarray*}


The vertex and face operators commute because they either act on disjoint
qubits or on an even number of qubits in common. Let $e$ be the number
of edges, $v$ the number of vertices and $f$ the number of faces
of a given grid. By Euler's equation, these toric codes encode $2$
qubits. Since the number of logical qubits remains constant as the
number of encoding qubits increases, their asymptotic rate is zero.

In order to generalize toric codes to higher genus surfaces, we study
tessellations of an orientable 2-manifold of genus $g$. Furthermore
a noncontractible cycle in the tessellation or dual tessellation commutes
with the stabilizer group of the code because it is a cycle. Nevertheless
it is not contained in the stabilizer group. Therefore the distance
of the code is the length of the shortest non-contractible cycle in
the tessellation.

We decode the family of topological codes using belief propagation
by simulating the 4-ary symmetric channel as two independent binary
symmetric channels in the belief propagation section. Therefore we
calculate the independent asymptotical rate of $X^{vertex}$ and $Z^{facce}$
in the next section.

~

The rate for the $Z^{face}$ is

\[
\frac{e-(f-1)}{e}\]


The rate for the $X^{vertex}$ is

\[
\frac{e-(v-1)}{e}\]


And the topological rate for the respective code is

\[
\frac{e-(f-1)-(v-1)}{e}\]


~


\section{\label{sec:Platonic-Surfaces-and}Platonic Quantum Low-Density Parity-Check
Codes}

~


\subsection{Platonic Graph And Surfaces}

~

$Platonic$ $Graphs$ $\pi_{n}$ are generalizations of the Platonic
solids \cite{spectralgeometry}. They are characterized by regular
tessellations of Riemann surfaces or 2-manifolds, which are called
$Platonic$ $Surfaces$ $S_{n}$.

~ 
\begin{defn}
$Platonic\; Graphs$ $\pi_{n}$ are determined by vertices and edges.
A vertex of $\pi_{n}$ is defined by a pair of integers $\left({a\atop b}\right)$
such that $\left({a\atop b}\right)\sim\left({-a\atop -b}\right).$
The pair is taken projectively, that is, $gcd(a,b)=1.$ An edge joins
two vertices, $\left({a\atop b}\right)$ and $\left({c\atop d}\right)$
iff $det\left[\begin{array}{cc}
a & c\\
b & d\end{array}\right]=\pm1$ $mod$ $n.$ 
\end{defn}
~

Furthermore any two vertices have two paths of length two note that
the $Platonic$ $Graphs$ have the two-step property \cite{spectralgeometry},
that is, any two vertices have exactly two paths of length two, associating
$\pi_{n}$ to a unique triangulated topological 2-manifold. Also note
that $n$ does not have to be a prime number. When $n\geqslant6,$
we obtain a tessellation of a surface of $genus\geqslant1.$

The first few Platonic graphs are the tetrahedron $\pi_{3},$ the
octahedron $\pi_{4},$ and the icosahedron $\pi_{5}.$ The Dual Platonic
graphs, $\pi'_{n}$, have a vertex for each triangular face in $\pi_{n},$
and an edge between two vertices iff the respective $\pi_{n}$ faces
are adjacent. The first few dual Platonic Graphs are the tetrahedron
$\pi'_{3}$ (self-dual), the cube $\pi'_{4}$, and the dodecahedron
$\pi'_{5}$.

~ 
\begin{rem}
For $p$ odd prime, the graph $\pi_{p}$ has $\frac{p^{2}-1}{2}$
vertices. Let $v_{p}$ be the number of vertices of $\pi_{p}$, then
there are $\frac{v_{p}.p}{2}$ edges $e_{p},$ and $\frac{v_{p}.p}{3}$
faces $f_{p}$. For $\pi'_{n}$, there are $v'_{p}=f_{p}$, $e'_{p}=e_{p},$
and $f'_{p}=v_{p}.$ 
\end{rem}
~


\subsection{\label{sec:Platonic-Surface-Quantum-LDPC}Platonic Quantum Low-Density
Parity-Check Codes }

~

In this section we give a specific example of a quantum LDPC code
derived from $\pi_{7}$, and an infinite family of good LDPC codes
derived from Platonic Surfaces. We calculate their asymptotic rate,
analyze their sparsity and provide a lower bound on their distance,
the length of its shortest non-contractible cycle

~


\subsubsection*{Example}

~

The Platonic quantum code derived from $\pi_{7}$ has $\frac{p^{2}-1}{2}=24$
vertices $v_{p}$, $\frac{v_{p}.p}{3}=56$ faces, and $\frac{v_{p.}p}{2}=84$
edges, and that it follows that $g=3$ is the genus of the surface.
It has quantum rate 1/14. For $\pi'_{7},$ there are $56$ vertices,
$24$ faces, and $84$ edges, and its shortest non-contractible cycle
is of length $8$. 

~


\subsection{Family of Platonic Quantum Low-Density Parity-Check Codes}

$\,$

In general we derive a family of quantum LDPC codes from the dual
Platonic graphs $\pi'_{p},$ analyze their rate and the next section
we provide a bound on their distance of the length of the shortest
non-contractible cycle.

~


\subsection{Asymptotic nonzero classical rate for the platonic family of quantum
error-correcting codes}

$\:$ 
\begin{rem}
\label{thm:TheZfacecheck}The $Z^{face}$ check operator of a dual
Platonic quantum LDPC error-correcting code has rate approaching $1$
for $p$ odd prime. 
\end{rem}
~

\begin{eqnarray*}
lim_{p\rightarrow\infty} & \frac{e'_{p}-(f'_{p}-1)}{e'_{p}} & =\\
lim_{p\rightarrow\infty} & \frac{\frac{p^{3}-p}{4}-\left(\frac{p^{2}-1}{2}-1\right)}{\frac{p^{3}-p}{4}} & =\\
 & 1\end{eqnarray*}


$\,$ 
\begin{rem}
\label{thm:TheXvertexcheck}The $X^{vertex}$ check operator of a
dual Platonic quantum LDPC error-correcting code has rate approaching
$\frac{1}{3}$, for $p$ odd prime. 
\end{rem}
~

\begin{eqnarray*}
lim_{p\rightarrow\infty} & \frac{e'_{p}-(v'_{p}-1)}{e'_{p}} & =\\
lim_{p\rightarrow\infty} & \frac{\frac{p^{3}-p}{4}-\left(\frac{p^{3}-p}{6}-1\right)}{\frac{p^{3}-p}{4}} & =\\
 & \frac{1}{3}\end{eqnarray*}


$\,$ 
\begin{rem}
\label{thm:The-average-combined}The average combined rate of the
$X^{vertex}$ and $Z^{face}$ operators approaches $\frac{2}{3}$,
for $p$ odd prime. 
\end{rem}
~

\begin{eqnarray*}
lim_{p\rightarrow\infty} & \frac{2e'_{p}-(f'_{p}+v'_{p}-2)}{2e'} & =\\
lim_{p\rightarrow\infty} & 1-\frac{f'_{p}+v'_{p}+-2}{2e'_{p}} & =\\
lim_{p\rightarrow\infty} & 1-\frac{1}{p}-\frac{1}{3}+\frac{1}{p^{3}-p} & =\\
 & \frac{2}{3}\end{eqnarray*}


~


\subsection{Asymptotic nonzero quantum rate for the platonic family of quantum
error-correcting codes}

~ 
\begin{rem}
\label{thm:The-average-combined-1}The quantum rate of the platonic
family of quantum error-correcting codes approaches $\frac{1}{3}$,
for $p$ odd prime.

~ 
\end{rem}
\begin{eqnarray*}
lim_{p\rightarrow\infty} & \frac{e'_{p}-(f'_{p}-1)-(v'_{p}-1)}{e'} & =\\
lim_{p\rightarrow\infty} & 1-\frac{f'_{p}+v'_{p}+2}{e'_{p}} & =\\
lim_{p\rightarrow\infty} & 1-\frac{\frac{p^{2}-1}{2}+\frac{p^{3}-p}{6}+2}{\frac{p^{3}-p}{4}} & =\\
 & \frac{1}{3}\end{eqnarray*}


~


\subsection{Sparsity Analysis for the Platonic quantum LDPC error-correcting
codes}

$\:$ 
\begin{rem}
Let $w_{f}$ be the weight of the $Z^{face}$ check operators of a
dual Platonic quantum LDPC error-correcting code, and let $e_{p}$
be the corresponding number of encoding qubits for prime $p$, then
$\frac{w_{f}}{e_{p}}$ converges to a $c.p^{-2}$.

~

\begin{eqnarray*}
lim_{p\rightarrow\infty} & \frac{p}{e_{p}} & =\\
lim_{p\rightarrow\infty} & \frac{p}{\frac{v_{p}.p}{2}} & =\\
lim_{p\rightarrow\infty} & \frac{p}{\frac{p^{2}-1}{4}p} & =\\
 & c.p^{-2}\end{eqnarray*}

\end{rem}
$\:$ 
\begin{rem}
Let $w_{v}=3$ be the weight of the $Z^{vertex}$ check operators
of a dual Platonic quantum LDPC error-correcting code, and let $e_{p}$
be the corresponding number of encoding qubits for prime $p$, then
$\frac{w_{v}}{e_{p}}$ converges to zero.

~

\begin{eqnarray*}
lim_{p\rightarrow\infty} & \frac{3}{e_{p}} & =\\
 & 0\end{eqnarray*}

\end{rem}
~


\section{\label{sec:Shortest-non-contractible-cycle}Shortest non-contractible
cycle bound for the dual Platonic surfaces $snc(\pi_{p}^{'})$}

$\;$

We show that the shortest non-contractible cycle of the family of
dual platonic graphs $\pi'_{p}$ grows logarithmically in the size
of their genus. In order to improve the distance of $\pi_{p}$ we
obtain subfamilies of Platonic codes by subtessellating them up to
$log(p)$ levels of recursion. See decoding simulation section.

~

We derive the $\pi'_{p}$ bound by regarding these graphs as quotient
of $T_{3},$ the infinite cubic tree \cite{Biggs-1}. Vertices in
$T_{3}$ are labeled with unordered triplets of irreducible rational
numbers, $\left(\left({a\atop b}\right)\left({c\atop d}\right)\left({e\atop f}\right)\right)$.
This labeling is known as a $Farey$ $Tree$. See figure 1 .

~ 
\begin{defn}
We define the following binary tree $B.$ The root of $B$ is $\left(\left({0\atop 1}\right)\left({1\atop 2}\right)\left({1\atop 1}\right)\right).$
For a vertex $\left(\left({a\atop b}\right)\left({c\atop d}\right)\left({e\atop f}\right)\right)$
in $B$, its left child is $\mbox{\ensuremath{\left(\mbox{\ensuremath{\left({a\atop b}\right)\left({a+c\atop b+d}\right)\left({c\atop d}\right)}}\right)}}$
and its right child is $\left(\left({c\atop d}\right)\left({c+e\atop d+f}\right)\left({e\atop f}\right)\right)$. 
\end{defn}
~ 
\begin{defn}
$T_{3}$ is defined recursively by generalizing the labels of the
following rooted binary tree $B.$ $B_{0}$ is $B$ and $B_{n}$ is
obtained from $B$ by adding $n$ to the pairs, i.e. $\left({a\atop b}\right)$
is relabeled as $\left({(a+n)\atop b}\right).$ $T_{3}$ is obtained
by adjoining the root of a copy $B_{n}$ to $\left(\left({1\atop 0}\right)\left({n\atop 1}\right)\left({n+1\atop 1}\right)\right)$.

~

%
\begin{figure}
\includegraphics[scale=0.47]{figures/fareytree}

\caption{Farey Tree}


%
\end{figure}

\end{defn}
~

In the girth of a family of 3-regular graphs, the triplets $T(p)$,
by mapping each pair $\left({a\atop b}\right)$ to $a.b^{-1}mod$
p. If b = 0, then $a.b^{-1}mod$~p is mapped to $\infty.$ We obtain
the dual Platonic graphs $\pi'$ from $T_{3}$ under the equivalence
$\left({a\atop b}\right)\sim\mbox{\ensuremath{\left({-a\atop -b}\right)}}mod\; p$.
Using $T_{3},$ we show that the shortest non-contractible cycle in
the graph, for large $p$ prime, is bounded by $p^{2}\leq Fibonacci(snc(\pi'_{p})+2)$.
We provide lemmas about the rooted binary tree $B$ and prove a lemma
about a needed symmetry of the tree before proving the distance theorem.

~ 
\begin{lem}
\label{lem:For-any-vertex}For any vertex $\left(\left({a\atop b}\right)\left({c\atop d}\right)\left({e\atop f}\right)\right)$
in $B$,

\begin{eqnarray*}
b\centerdot c-a\centerdot d & = & d\centerdot e-c\centerdot f=1.\end{eqnarray*}
 \end{lem}
\begin{cor}
For each pair $\left({a\atop b}\right),$

\begin{eqnarray*}
gcd(a,b) & = & 1.\end{eqnarray*}
 \end{cor}
\begin{lem}
\label{lem:The-largest-fib}The largest $b$ in a pair $\left({a\atop b}\right)$
at level $r$, is $Fibonacci(r+2).$

~ 
\end{lem}
In addition we further observe that there is a symmetry of the tree
$B$ that preserves the level of the vertices and induces a reflection
on the tree. The symmetry is given by $\left({b-a\atop b}\right)$
on each pair. In the following lemma we use $x,$ as short for $\left({a\atop b}\right),$
and $\left(1-x\right)$ as short for $\left({b-a\atop b}\right).$

~ 
\begin{lem}
\label{lem:6 symmetry}Let $\left(\left(x\right)\left(y\right)\left(z\right)\right)$
be a vertex $v$, then the involution $i$ that takes $v$ to $\left(\left(1-z\right)\left(1-y\right)\left(1-x\right)\right)$
is a reflection of the tree $B$. 
\end{lem}
~

Proof. We prove this lemma by induction. Note that the root of $B$,
$\left(\left({0\atop 1}\right)\left({1\atop 2}\right)\left({1\atop 1}\right)\right)$,
is a fixed point of the symmetry. Assume that the symmetry holds for
all vertices in $B$ at levels less than $n.$ Let $v=\left(\left({a\atop b}\right)\left({c\atop d}\right)\left({e\atop f}\right)\right),$
be a vertex at level $n-1.$ Denote the involution on $v$, as $i(v)=\left(\left({f-e\atop f}\right)\left({d-c\atop d}\right)\left({b-a\atop b}\right)\right).$
Denote the left descendant of $v$ as $v_{left}$, and the right descendant
as $v_{right}.$ Then,

\begin{eqnarray*}
v_{left} & = & \left(\left({a\atop b}\right)\left({a+c\atop b+d}\right)\left({c\atop d}\right)\right)\end{eqnarray*}


and

\begin{eqnarray*}
v_{right} & = & \left(\left({c\atop d}\right)\left({c+e\atop b+f}\right)\left({e\atop f}\right)\right)\end{eqnarray*}


Under the involution, the results are:

\begin{eqnarray*}
i(v_{left}) & = & \left(\left({d-c\atop d}\right)\left({b+d-c-a\atop b+d}\right)\left({b-a\atop b}\right)\right)\end{eqnarray*}


and

\begin{eqnarray*}
i(v_{right}) & = & \left(\left({f-e\atop f}\right)\left({b+f-c-e\atop b+f}\right)\left({d-c\atop d}\right)\right)\end{eqnarray*}
 which implies that $i(v_{left})=(i(v))_{right}$, and $i(v_{right})=(i(v))_{left}$.~

~ 
\begin{thm}
For large $p$ prime, $p^{2}\leq$Fibonacci ($snc(\pi_{p}^{'})$+2).

~ 
\end{thm}
Proof. Because $\pi'_{p}$ is vertex transitive, we consider only
the cycles from $\left(\left({1\atop 0}\right)\left({0\atop 1}\right)\left({1\atop 1}\right)\right)$.
A set of three pairs $\left(\left({a\atop b}\right)\left({c\atop d}\right)\left({e\atop f}\right)\right)$
corresponds to a vertex in $\pi'_{p}$ and a face in $\pi_{p}.$ Each
individual pair corresponds to a vertex in $\pi_{p}.$ The order of
the pairs within a set does not matter. Therefore, there are six ways
in which a vertex in $T_{3}$ can reduce to $\left(\left({1\atop 0}\right)\left({0\atop 1}\right)\left({1\atop 1}\right)\right)$,
that is all 6 permutations of 3 pairs. In addition, the reflection
proved in lemma \ref{lem:6 symmetry} allows us to consider only 4
cases. Note that under this symmetry, the following cases are equivalent
$\left(\left({0\atop 1}\right)\left({1\atop 1}\right)\left({1\atop 0}\right)\right)$
$\sim$ $\left(\left({1\atop 0}\right)\left({0\atop 1}\right)\left({1\atop 1}\right)\right),$
and $\left(\left({1\atop 1}\right)\left({0\atop 1}\right)\left({1\atop 0}\right)\right)$
$\sim$ $\left(\left({1\atop 0}\right)\left({1\atop 1}\right)\left({0\atop 1}\right)\right).$

~

Case $\left(\left({0\atop 1}\right)\left({1\atop 0}\right)\left({1\atop 1}\right)\right)$

~

\[
\left(\begin{array}{c}
a\centerdot p+e\centerdot p+1\\
f\centerdot p+b\centerdot p+1+g\end{array}\right)\]


In order for this pair to reduce to $\left({1\atop 0}\right)$, we
have that $g=-1.$ By applying lemma \ref{lem:For-any-vertex}, we
get a contradiction.

~

Case $\left(\left({1\atop 0}\right)\left({1\atop 1}\right)\left({0\atop 1}\right)\right)$

~

We get a similar reduction to the previous case

~

Case $\left(\left({1\atop 0}\right)\left({0\atop 1}\right)\left({1\atop 1}\right)\right)$

~

A vertex that reduces to $\left(\left({1\atop 0}\right)\left({0\atop 1}\right)\left({1\atop 1}\right)\right)$
must be of the form:

\[
\left(\left({a\centerdot p\mp1\atop b\cdot p}\right)\left(\begin{array}{c}
a\centerdot p+e\centerdot p\\
b\centerdot p+f\centerdot p\mp1\end{array}\right)\left(\begin{array}{c}
e\centerdot p\mp1\\
f\centerdot p\mp1\end{array}\right)\right)\]


~

For simplicity let $c=a+e$ and $d=b+f.$ Then by applying lemma \ref{lem:For-any-vertex}
to the first two pairs, we get:

\[
b\centerdot c\centerdot p^{2}-(a\centerdot p\pm1)\centerdot(dp\mp1)=1\]


which implies that

\[
\mp d=(a\centerdot d-b\centerdot c)\centerdot p\mp a\]


Let $a\centerdot d-b\centerdot c=g.$ Then a vertex that reduces to
$\left(\left({1\atop 0}\right)\left({0\atop 1}\right)\left({1\atop 1}\right)\right)$
has the following form:

\[
\left(\left({a\centerdot p\pm1\atop b\centerdot p}\right)\left({c\centerdot p\atop g\centerdot p^{2}\mp a\centerdot p\mp1}\right)\left({e\centerdot p\mp1\atop f\centerdot p\mp1}\right)\right)\]


~

Case $\left(\left({1\atop 1}\right)\left({1\atop 0}\right)\left({0\atop 1}\right)\right)$

~

We get a similar reduction.

~

Therefore by lemma \ref{lem:For-any-vertex}

\[
p^{2}\leq Fibonacci(girth(\pi'_{p})+2)\]


Therefore for large $p,$ $girth(\pi'_{p})<p,$ where $p$ is the
size of the faces on the surface of the tessellations, and therefore
for large $p$, $snc(\pi'_{p})=girth(\pi'_{p}).$

$\:$


\section{\label{sec:Simulation-results}Belief-propagation decoding}

~

%
\begin{figure*}
\includegraphics[clip]{figures/codes_with_pentsubdivision2}

\label{Flo:shannon-GVB}\caption{Simulation results for the quantum error-correcting codes derived
from Platonic surfaces. The $Y$ coordinate is the code rate. The
$X$ coordinate represents the flip probability $f_{m}$ at which
the probability of decoding block error is $10^{-4}$ (0.9999 threshold).
All simulation labels start at Platonic $n=6.$ For more information
about the labels, read the section simulation results. The smooth
curve shown in blue is the Shannon limit, and the dotted curve shown
in blue is the Gilbert-Varshamov bound for dual-containing quantum
error-correcting codes.}
%
\end{figure*}


~

We decode the platonic codes using belief propagation by simulating
the 4-ary symmetric channel as two independent binary symmetric channels
in order to make them comparable to MacKay's sparse-graph quantum
codes \cite{mackayquantum}. Each decoding simulation round either
finds the correct decoding or a block error. Block error probability
is calculated as a function of the flip probability $f_{m}$ \cite{mackayquantum}.
This is the probability with which we independently flip each bit.
In particular we show the flip probability $f_{m}$ at which the probability
of decoding error is $10^{-4}(.9999)$.

We provide a summary of the simulated decodings of the Platonic codes
and derived subfamilies in figure \ref{Flo:shannon-GVB}. The smooth
curve shown in the figure is the Shannon limit and the dotted curve
is the Gilbert-Varshamov bound for dual-containing quantum error-correcting
codes \cite{mackayquantum}.

All simulation labels start at Platonic $n=6.$ The red line represents
the Platonic quantum codes without subtessellations. Their $Z^{face}$
parity-check simulations starting at $n=6,$ are labeled $faces6,$
and each additional matrix is denoted by a circle. Note that their
rate approaches $1$ as shown in remark \ref{thm:TheZfacecheck}.
Their $X^{vertex}$ parity-check simulations are labeled $stars6,$
and each additional matrix is denoted by a star. Their rate approaches
$\frac{1}{3}$ as shown in remark\ref{thm:TheXvertexcheck}.

Their $Z^{face}$ and $X^{vertex}$ average simulation performance
is labeled as $comb6$ and each additional code decoding simulation
is denoted by a dot. Their rate approaches $\frac{2}{3}$ as shown
in remark \ref{thm:The-average-combined}. The average performance
of the Platonic quantum codes without subtessellations is better than
the Platonic quantum codes with subtessellations.

We also obtain subfamilies of Platonic codes by subtessellating the
Platonic $n-gons$. Each face in $\pi'_{n}$ for $n\geqslant6$ is
subtessellated with pentagons in order to obtain better distance parameters.
We obtain two subfamilies depending on the alignment of the subtessellations,
both random and symmetric, and on the depth of the recursion. Symmetric
subtessellations have neighboring $n-gons$ whose subtessellations
are aligned.

The black line represents Platonic quantum codes with randomly aligned
pentagon subtessellations. Their $Z^{face}$ parity-check simulations
are labeled as $rp6,$ and each additional matrix is denoted by a
circle. Their $X^{vertex}$ parity-check simulations are labeled $rp6,$
and each additional matrix is denoted by a star. Their $X^{vertex}$
and $Z^{face}$ average simulation performance starting at $n=6$
is labeled $rp6,$ and each additional code decoding simulation is
denoted by a dot.

The purple line represents Platonic quantum codes with symmetrically
aligned pentagon subtessellations, labeled as $ap6,$ and the blue
line represents codes with higher-level pentagon subtessellations,
labeled as $a2p6$. The average decoding of the Platonic quantum codes
without subtessellations is better than that of the Platonic quantum
codes with subtessellations.

~

~

~


\section{\label{sec:Discussion-and-open}Conclusion and open problems}

~

We have addressed Mackay's conjecture about the existence of good
families of dual-containing quantum LDPC error-correcting codes with
nonzero rate, growing minimum distance and good decoding behavior.
This family is derived from Platonic topological tessellations of
2-manifolds. We analyzed their sparsity, proved a logarithmic lower
bound on their distance, showed the no-zero rate of their $X^{vertex}$
and $Z^{face}$ operators, and of their average combined rate, and
simulated their decoding with belief-propagation.

With respect to the distance of the codes, it is a major open problem
in the theory of Riemann surfaces to improve on the logarithmic lower
bound of their systoles \cite{systolessarnak}. The 1-dimensional
systole of a 2-dimensional manifold $M$ is the infimum of all nontrivial
1-dimensional cycles in $M$. 

It seems not likely that there exist families of topological quantum
codes derived from regular algebraic tessellations of 2-manifolds
that have provably better than logarithmic distance properties. Nevertheless
it is possible that irregular or random tessellations might yield
better short noncontractible distance bounds.

Quantum error-correction is foundational to the development of practical
quantum computers. In this paper we have presented a good family of
quantum low-density parity-check error-correcting codes derived from
tessellations of topological surfaces. Physical implementations of
quantum computers using these codes would require few sparse local
physical interactions. Therefore the study of surface quantum LDPC
codes can impact the development of scalable quantum computers.

~ 
\begin{thebibliography}{10}
\bibitem{Biggs-1}N. Biggs. Graphs with large girth. \emph{ArsCombinatorica}.
25C: 73--80. 1988.

\bibitem{spectralgeometry}R. Brooks. Spectral geometry and the cheeger
constant. In \emph{DIMACS Workshop} \emph{Proceedings}. AMS. pp. 5--19,
1993.

\bibitem{QuantumInformationTheory}C. Bennet and P. Shor. Quantum
Information Theory. \emph{IEEE Trans. on Info. Theory. 44: 2724--2742,
1998.}

\bibitem{shorgood}A. Calderbank and P. Shor. Good quantum error-correcting
codes exist. Phys. Rev. A, 54: 1098--1106, 1996.

\bibitem{gallager}R. Gallager. Low-density parity-check codes. \emph{PhD
Thesis. Massachusetts Institute of Technology.} Cambridge, MA. 1963.

\bibitem{kitaevquantum}A. Kitaev. Fault-tolerant quantum computation
by anyons. \emph{Annals of Physics. 303: 2--30, 2003.}

\bibitem{mackaygoodcodes}D. MacKay. Good error correcting codes based
on very sparse matrices. \emph{IEEE Trans. on Info. Theory. 45: 399--431,
1999.}

\bibitem{mackayquantum}D. MacKay, G. Mitchison and P. McFadden. Sparse-graph
codes for quantum error correction. \emph{IEEE Trans. on Info. Theory.
50: 2315--2330, 2004.}

\bibitem{mackaryirregular}D. MacKay, S. Willson and M. Davey. Comparison
of Constructions of Irregular Gallager Codes. \emph{IEEE Trans. on
Communications. 47: 1449--1454, 1999.}

\bibitem{systolessarnak}J. Quine and P. Sarnak. {}``Extremal Riemann
Surfaces,'' presented at the American Mathematical Society special
session. San Francisco, California. January 4-5, 1995.
\end{thebibliography}

\end{document}
