# Quantum LDPC Codes Constructed from Point-Line Subsets of the Finite
Projective Plane

Jacob Farinholt Manuscript received Month Day, Year; revised Month Day,
Year.This work was supported by the Naval Surface Warfare Center’s In-house
Laboratory Independent Research (ILIR) and Academic Fellowship (AFP)
programs.J. Farinholt is with the Electromagnetic and Sensor Systems
Department, Naval Surface Warfare Center, Dahlgren Division, Dahlgren, VA
22448<EMAIL_ADDRESS>
###### Abstract

Due to their fast decoding algorithms, quantum generalizations of low-density
parity check, or LDPC, codes have been investigated as a solution to the
problem of decoherence in fragile quantum states. However, the additional
twisted inner product requirements of quantum stabilizer codes force four-
cycles and eliminate the possibility of randomly generated quantum LDPC codes.
Moreover, the classes of quantum LDPC codes discovered thus far generally have
unknown or small minimum distance, or a fixed rate. This paper presents
several new classes of quantum LDPC codes constructed from finite projective
planes. These codes have rates that increase with the block length $n$ and
minimum weights proportional to $n^{1/2}$.

###### Index Terms:

error correction codes, quantum error correction, finite geometry.

##  I Introduction

Classical low-density parity check codes, or LDPC codes, were first discovered
by Gallager [2] in 1960. Later, it was shown that bipartite graphs, called
_Tanner graphs_ , could be used to describe the codes and their actions under
iterative belief propagation decoding algorithms. In 2001, Kou _et al._ [3]
showed that by using finite geometries, many classes of these codes could be
easily generated to have known parameters. Recently, Droms _et al._ [4] and
Castleberry _et al._ [5] showed that LDPC codes constructed from point-line
subsets of finite projective planes could often out-perform those constructed
in [3]. Classical LDPC codes are some of the best known, with rates
asymptotically approaching the Shannon limit [6]. We say a code is an LDPC
code if its parity check matrix is sparse, and its corresponding Tanner graph
has no four-cycles (i.e., any pair of rows in the parity check have no more
than one “1” in common position). In particular, the rows of the parity check
matrix need not all be linearly independent.

The first quantum error correcting codes were discovered by Shor [7],
Calderbank [8], and separately by Steane [9, 10]. Using the stabilizer
formalism introduced by Gottesman [11], it was shown that these corresponding
_stabilizer codes_ could be described using classical parity check matrices
with an added twisted inner product requirement [12]. This twisted inner
product has the unfortunate consequence of forcing four-cycles on a
corresponding Tanner graph. Nevertheless, sparse-graph stabilizer codes with
minimal four-cycles have been suggested as quantum generalizations of
classical LDPC codes. The first such quantum LDPC, or QLDPC, codes were
suggested by Postol in 2001 [13], and many examples were constructed by MacKay
_et al._ [14]. Since then, many other classes of QLDPC codes have been
constructed (see [15, 16] and references therin). However, many of these codes
have unknown or small minimum distance. Tillich and Zemor [15] constructed
fixed-rate QLDPC codes with minimum distances that increase as the square root
of the code length. Aly [16] used finite geometric techniques to create
quantum generalizations of many of the classical LDPC codes constructed in
[3], and suggested that similar codes could be constructed through the use of
projective geometries. In this paper, projective geometries, in particular the
projective plane of order $2^{s}$ and many of its subsets, are used to
construct QLDPC codes with minimum distances proportional to the square root
of the code length, and whose rates also increase with the code length,
providing possibly the best-known rate-increasing QLDPC codes in the current
literature.

This paper is organized as follows. In Section II we introduce quantum
stabilizer codes, classical constructions, and the CSS formalism. In Section
III we introduce finite projective planes and subsets of the plane with
respect to regular hyperovals. Section IV describes methods of constructing
classical self-orthogonal sparse-graph codes from the subsets described in
Section III. Lastly, Section V contains our main results about new classes of
Quantum LDPC codes and their corresponding parameters.

##  II Quantum Stabilizer Codes and CSS Codes

The Pauli operators are given by

$\displaystyle I$ $\displaystyle=\begin{pmatrix}1&0\\\ 0&1\end{pmatrix},\ $
$\displaystyle X=\begin{pmatrix}0&1\\\ 1&0\end{pmatrix},$ $\displaystyle Y$
$\displaystyle=\begin{pmatrix}0&-i\\\ i&0\end{pmatrix},\ $ $\displaystyle
Z=\begin{pmatrix}1&0\\\ 0&-1\end{pmatrix}.$ (1)

These operators, along with the scalars $i^{k}$ for $k\in\mathbb{Z}_{4}$, form
the single-qubit _Pauli group_ $\mathcal{P}$. Observe that
$X^{2}=Y^{2}=Z^{2}=I$, and $Y=iXZ$. A pure state quantum bit, or _qubit_ is a
norm-one element of a two-dimensional complex Hilbert space,
$\mathcal{H}_{2}$. It is well-known [9] that correcting errors induced by the
Pauli operators is sufficient to correct arbitrary errors on single qubits.

In the case of multi-qubit states, that is, norm-one elements in
$\mathcal{H}_{2}^{\otimes
n}=\mathcal{H}_{2}\otimes\mathcal{H}_{2}\dots\otimes\mathcal{H}_{2}$, the
$n$-fold tensor product of $\mathcal{H}_{2}$, the corresponding Pauli
operators are $n$-fold tensor products of the operators given in (II), with
corresponding Pauli group $\mathcal{P}_{n}$ on $n$ qubits obtained by
including the scalars $i^{k}$ for $k\in\mathbb{Z}_{4}$.

An arbitrary element $P\in\mathcal{P}_{n}$ is represented as

$P=i^{k}X(a)Z(b),$ (2)

for $k\in\mathbb{Z}_{4}$, and $a=(a_{1},a_{2},\dots,a_{n})$ and
$b=(b_{1},b_{2},\dots,b_{n})$ are both length $n$ binary vectors, with a 1 in
position $i$ of $a$ (resp. $b$) precisely when there is an $X$ (resp. $Z$)
operator acting on qubit $i$. For example, $X(1001)Z(0101)$ should be
interpreted as $X\otimes Z\otimes I\otimes Y$, with the $Y$ at the end since
it is a product of $X$ and $Z$. It has been shown [12] that two elements
$i^{k}X(a)Z(b)$ and $i^{k^{\prime}}X(a^{\prime})Z(b^{\prime})$ of
$\mathcal{P}_{n}$ commute if and only if

$(a|b)*(a^{\prime}|b^{\prime}):=a\cdot b^{\prime}+b\cdot
a^{\prime}=0\pmod{2},$ (3)

where $\cdot$ is the standard inner (dot) product. We call $*$ the _twisted
inner product_.

Observe that the center $C(\mathcal{P}_{n})$ of $\mathcal{P}_{n}$ is given by
$C(\mathcal{P}_{n})=\\{i^{k}I\ |\ k\in\mathbb{Z}_{4}\\}$. Since these elements
are effectively the global phase actions in $\mathcal{P}_{n}$, we can reduce
ourselves to considering the quotient group
$\mathcal{P}_{n}/C(\mathcal{P}_{n})$, the elements of which are equivalence
classes of the form $\\{i^{k}X(a)Z(b)\ |\ k\in\mathbb{Z}_{4}\\}$, for fixed
$a$ and $b$; and we label each equivalence class with its scalar-free element
(e.g. $X(a)Z(b)\equiv\\{i^{k}X(a)Z(b)\ |\ k\in\mathbb{Z}_{4}\\}$). Moreover,
as described in [12], the quotient group $\mathcal{P}_{n}/C(\mathcal{P}_{n})$
is isomorphic to a $2n$-dimensional binary vector space $V_{2n}$ via the map

$X(a)Z(b)\mapsto(a|b),$ (4)

with the commutativity relationship of elements in $\mathcal{P}_{n}$ preserved
by imposing the twisted inner product (3) on the vector space $V_{2n}$.

###  II-A Stabilizer Codes

A _stabilizer group_ $\mathcal{S}\subseteq\mathcal{P}_{n}$ is a commutative
subgroup of $\mathcal{P}_{n}$ that does not contain $-I$. By not containing
$-I$, distinct elements of $\mathcal{S}$ are mapped to distinct equivalence
classes in $\mathcal{P}_{n}/C(\mathcal{P}_{n})$. Thus, without loss of
generality, a stabilizer group can be classically represented as a collection
of vectors in $V_{2n}$ with the property that every pair are orthogonal with
respect to the twisted inner product (3).

A _stabilizer code_ $\mathcal{C}(\mathcal{S})$ for stabilizer group
$\mathcal{S}\subseteq\mathcal{P}_{n}$ is defined as the simultaneous $+1$
eigenspace in $\mathcal{H}_{2}^{\otimes n}$ of each element in $\mathcal{S}$.
An error is detected if it anticommutes with any element of the stabilizer
group, thereby producing a nonzero syndrome. Thus, we can classically define a
stabilizer parity check matrix $H(\mathcal{C})$ for the stabilizer code
$\mathcal{C}(\mathcal{S})$ by letting the rows of $H(\mathcal{C})$ be the
vectors corresponding to the generators of $\mathcal{S}$.

Conversely, a binary length-$2n$ matrix $[A|B]$ is a stabilizer parity check
matrix for some stabilizer code if and only if every pair of rows in $[A|B]$
are orthogonal with respect to (3), or equivalently, if and only if

$AB^{t}+BA^{t}=0\pmod{2}.$ (5)

###  II-B CSS Codes

A large class of stabilizer codes of particular interest are ones that are
constructed from classical error correcting codes. In particular, if $C_{1}$
and $C_{2}\subseteq C_{1}^{\bot}$ are classical codes with parity check
matrices $H(C_{1})$ and $H(C_{2})$, respectively, then

$\textbf{H}(\mathcal{C})=\begin{pmatrix}H(C_{1})&0\\\ 0&H(C_{2})\end{pmatrix}$
(6)

is a stabilizer parity check for a stabilizer code $\mathcal{C}$. Note that
(3) is satisfied by the fact that $H(C_{1})$ is orthogonal to $H(C_{2})$ by
construction. In particular, if $C_{1}$ and $C_{2}$ are classical
$[n,k_{1},d_{1}]$ and $[n,k_{2},d_{2}]$ codes, respectively, then the
stabilizer code $\mathcal{C}$ encodes $K=k_{1}+k_{2}-n$ qubits into $n$
qubits, and corrects $(D-1)/2$ and fewer arbitrary qubit errors, where
$D=\min(d_{1},d_{2})$ [12]. We call such a code an $[[n,K,D]]$ CSS code, where
CSS are the initials of the discoverers of such codes [8, 10]. Note that it is
standard practice to place the parameters of a quantum code inside double
brackets, as opposed to single brackets in the classical case. A particularly
nice scenario is one in which a classical $[n,k,d]$ code $C$, with parity
check matrix $H(C)$, is dual-containing, in which case

$\textbf{H}(\mathcal{C})=\begin{pmatrix}H(C)&0\\\ 0&H(C)\end{pmatrix}$ (7)

is a stabilizer parity check matrix for an $[[n,2k-n,d]]$ CSS code
$\mathcal{C}$. We call CSS codes constructed in this manner _symmetric_ CSS
codes; otherwise they are called _asymmetric_.

##  III Finite Projective Planes and Regular Hyperovals

|  |  | # of secant lines | # of skew lines
---|---|---|---|---
# of points | # of lines | # of lines | intersecting a non- | intersecting a non-
in $H_{\mathcal{C}}$ | secant to $H_{\mathcal{C}}$ | skew to $H_{\mathcal{C}}$ | hyperoval point | hyperoval point
$q+2$ | $\frac{q^{2}+3q+2}{2}$ | $\frac{q^{2}-q}{2}$ | $\frac{q+2}{2}$ | $\frac{q}{2}$
TABLE I: Number of points and lines with respect to the hyperoval
$H_{\mathcal{C}}$ and non-hyperoval points in $PG(2,q)$.

A _finite projective plane_ $PG(2,q)$ is a finite collection of points, along
with subsets of points (lines) satisfying:

  1. 1.

Any two distinct points determine a unique line.

  2. 2.

Any two distinct lines determine a unique point.

  3. 3.

There exist four points, no three of which are colinear.

Note that the second axiom implies that there are no parallel lines in this
geometry. See Figure 1 for an example of a finite projective plane.

Figure 1: The Fano Plane, $PG(2,2)$, is the simplest example of a finite
projective plane.

The value $q$ is called the _order_ of the projective plane, and the following
properties of $PG(2,q)$ can be determined [17]:

  1. 1.

Every line contains $q+1$ distinct points.

  2. 2.

Every point is incident with $q+1$ distinct lines.

  3. 3.

There are exactly $q^{2}+q+1$ points and $q^{2}+q+1$ lines in the plane.

When $q$ is a prime power, then points and lines of $PG(2,q)$ can be
represented as 1- and 2-dimensional subspaces, respectively, of the
3-dimensional vector space $V_{3}(q)$ over $\mathbb{F}_{q}$. Points are
equivalence classes of the form $[x,y,z]\equiv\\{(cx,cy,cz)\ |\
c\in\mathbb{F}_{q}-\\{0\\}\\}$, for $x$, $y$, and $z$ in $\mathbb{F}_{q}$.
While lines are 2-dimensional subspaces, each can be uniquely represented by
its dual in the 1-dimensional subspace. Thus, to distinguish lines from
points, we label points in brackets, e.g. $[x,y,z]$, and lines in perentheses,
e.g. $(a,b,c)$.

###  III-A Conics, Hyperovals, and Subsets of lines

A _conic_ $\mathcal{C}$ is a set of $q+1$ points in $PG(2,q)$ whose
coordinates satisfy a non-degenerate quadradic equation, that is,

$\mathcal{C}:=\\{[x,y,z]:ax^{2}+by^{2}+cz^{2}+fyz+gzx+hxy=0\\},$ (8)

for some $a,b,c,f,g,h,\in\mathbb{F}_{q}$. Conics have the property that no
three-point subsets are colinear. As such, every line must be either _skew_
(i.e. intersects $\mathcal{C}$ at no points), _tangent_ (i.e. intersects
$\mathcal{C}$ at one point), or _secant_ (i.e. intersects $\mathcal{C}$ at
exactly two points). A well-known result in projective geometry is that when
$q=2^{s}$, all of the tangent lines are concurrent at a point outside the
conic, called the _nucleus_. If the nucleus is added to the conic, we obtain a
_regular hyperoval_ , $H_{\mathcal{C}}$ (hereafter called simply a hyperoval).
Lines tangent to the conic are then secant to the hyperoval, and hence all
lines are either secant or skew to $H_{\mathcal{C}}$. Table I lists the number
of points and lines with respect to a hyperoval.

###  III-B Incidence Stuctures and Parity Checks

The _incidence matrix_ $M_{\pi}$ for $\pi=PG(2,q)$ is constructed by letting
the columns correspond to points, and rows correspond to lines, with
$M_{\pi_{i,j}}=1$ when line $i$ contains point $j$, and $M_{\pi_{i,j}}=0$
otherwise. This matrix is sparse by construction. It was shown in [18] that
the rank of this matrix is $\begin{pmatrix}p+1\\\ 2\end{pmatrix}^{s}+1$, where
$q=p^{s}$. In particular, when $p=2$, this reduces to $3^{s}+1$.

The incidence matrix $M_{\pi}$ is well-suited to act as a parity check matrix
for a classical LDPC code, as it is sparse, and any two rows have exactly one
“1” in common position. However, since this matrix is not self-dual, it must
be adapted by adding a column of all ones, called the _unit vector_ , or
$u$-vector, to it, denoting the new matrix by $M_{\pi}^{\prime}$. Note that
since every row of $M_{\pi}$ has odd weight, adding this vector does not
affect the rank. Since $M_{\pi}^{\prime}$ is self-dual, sparse, and any two
rows have exactly two “1”s in common position, it can be used in the
construction of a parity check matrix for a quantum LDPC code.

We can likewise consider classical LDPC parity check matrices constructed by
the incidence structures of subsets of points and lines in $PG(2,q)$. Such
classical codes have been recently studied [4, 5], but again, these incidence
matrices must be adapted to make them self-orthogonal in order to use them to
construct parity checks for QLDPC codes.

##  IV Classical Self-Orthogonal LDPC Codes

Here we construct self-orthogonal parity check matrices for classical LDPC
codes constructed from the incidence matrices from point-line subsets of
$PG(2,q)$. In particular, we assume that $q=2^{s}$ so that we can use the
subset structure based on hyperovals. We then study the properties of the
corresponding classical codes. The results of this section are summarized in
Table II.

###  IV-A All Points and All Lines, $M_{\pi}^{\prime}$

We again let $M_{\pi}$ be the incidence matrix for $\pi=PG(2,q)$ for
$q=2^{s}$, and let $M_{\pi}^{\prime}$ be the concatenation of $M_{\pi}$ with
the $u$-vector, i.e. $M_{\pi}^{\prime}=[M_{\pi}|\mathbf{1}]$. This matrix has
$4^{s}+2^{s}+2$ columns and $4^{s}+2^{s}+1$ rows. As discussed in Section
III-B, the rank of this matrix is $3^{s}+1$.

###### Proposition IV.1

The matrix $M_{\pi}^{\prime}$ is a parity check for a classical
$[4^{s}+2^{s}+2,\ 4^{s}-3^{s}+2^{s}+1,\ 2^{s}+2]$ LDPC code.

###### Proof:

The length and dimension are obvious. To prove minimum distance, we have two
cases:

  * $A)$:

The last bit of a minimum weight codeword is a 0. In this case, the codeword
will have the same weight as a minimum weight codeword for a code with
classical parity check matrix given by $M_{\pi}$, which is known to be
$2^{s}+2$ [3].

  * $B)$:

The last bit $c_{n}$ of a minimum weight codeword $c$ is a 1. Each additional
1-bit in $c$ will cause $c$ to be orthogonal to $2^{s}+1$ rows of
$M_{\pi}^{\prime}$. Thus, in addition to $c_{n}$, the codeword $c$ needs at
least $m$ additional 1-bits, where $m$ is the smallest integer such that
$m(2^{s}+1)\geq 4^{s}+2^{s}+1$, which is determined to be $2^{s}+1$. Thus, if
$c_{n}=1$, then the weight of $c$ is lower bounded by $2^{s}+2$, completing
the proof.

∎

Note that, we can alternatively prove results on minimum weight from a graph-
theoretic approach. In particular, $M_{\pi}^{\prime}$ can be graphically
viewed as the incidence matrix for a projective plane $\pi=PG(2,q)$ with an
additional point $u$ through which every line intersects. Then a codeword is
graphically viewed as a collection of points in this “extended projective
plane” $\pi^{\prime}$, through which every line intersects an even number of
times, since this would correspond to a vector having an even number of 1-bits
in common position with each row of the parity check, and hence orthogonal to
each row. In particular, if the codeword has a 0 at the $u$-column, then we
reduce ourselves to studying a collection of points $\mathcal{S}$ in $\pi$
satisfying this. However, if the codeword has a 1 at the $u$-column, then the
collection of points contains the point $u$ through which every line
intersects. Then the remaining points $\mathcal{S}$ are all in $\pi$ such that
every line intersects $\mathcal{S}$ an odd number of times. The weight of the
codeword is given by $|\mathcal{S}|$ or $|\mathcal{S}|+1$ depending on whether
the codeword has a 0 or a 1 at the end, respectively. Thus, we can determine
the minimum weight of a code by finding a minimal set of points $\mathcal{S}$
in $PG(2,q)$ in each case. Such an approach will be used for many of the
proofs in the following constructions.

###  IV-B Skew Lines and Non-Hyperoval Points, $H(C_{sk})$

| $n$ | $k$ | $d$
---|---|---|---
$C_{\pi}^{\prime}$ | $4^{s}+2^{s}+2$ | $4^{s}-3^{s}+2^{s}+1$ | $2^{s}+2$
|  | $4^{s}-3^{s}-1\leq k$ | $2^{s-1}+1$
$C_{sk}$ | $4^{s}$ | $\leq 4^{s}-3^{s}+2^{s}$ | $\leq d\leq 2^{s}$
|  |  | $2^{s-1}+2$
$C_{seA}$ | $4^{s}+2^{s}+2$ | $4^{s}-3^{s}+2^{s}+1$ | $\leq d\leq 2^{s}+2$
$C_{se}$ | $4^{s}$ | $4^{s}-3^{s}+2^{s}+1$ | $2^{s-1}+2\leq d\leq 2^{s}+2$
TABLE II: Summary of classical LDPC codes constructed from $PG(2,2^{s})$ and
subsets with respect to a hyperoval.

Suppose we restrict ourselves to the incidence structure formed by only the
lines skew to a hyperoval, along with the $u$-vector. In such a case, we can
find a weight one codeword by letting the last bit be 0, and letting
$\mathcal{S}$ consist of only a hyperoval point. Since skew lines intersect
the hyperoval nowhere, $\mathcal{S}$ corresponds to a codeword. A code of
minimum weight 1 is useless, so we will instead delete the columns
corresponding to hyperoval points. Thus, we let $H(C_{sk})$ be the incidence
matrix whose rows correspond to skew lines and whose columns correspond to
non-hyperoval points in$PG(2,q)$, concatenated with the $u$-vector. This
matrix will have $\frac{q^{2}-q}{2}$ rows and $q^{2}$ columns.

###### Proposition IV.2

The matrix $H(C_{sk})$ is a parity check matrix for a classical
$[4^{s},k_{sk},d_{sk}]$ LDPC code $C_{sk}$, where $4^{s}-3^{s}-1\leq
k_{sk}\leq 4^{s}-3^{s}+2^{s}$ and $2^{s-1}+1\leq d_{sk}\leq 2^{s}$.

###### Proof:

We know that $\dim(M_{\pi}^{\prime})=3^{s}+1$. Since skew lines never
intersect hyperoval points, removal of the columns corresponding to hyperoval
points does not change the dimension. In [5] it was shown that removing rows
corresponding to lines secant to the conic will not affect the dimension.
Removing the lines tangent to the conic (i.e. the remaining lines secant to
the hyperoval) gives us the matrix $H(C_{sk})$, but may possibly decrease the
dimension. Thus $3^{s}-2^{s}\leq\dim(H(C_{sk}))\leq 3^{s}+1$, from which we
determine the bounds on the code dimension.

To prove minimum distance, we again consider two cases, namely, if the last
bit of a codeword is a 0 or a 1.

  * $A)$:

Suppose the codeword has a 0 at the $u$-column. Then we view the codeword as a
collection of non-hyperoval points $\mathcal{S}$ in $PG(2,q)$ such that any
skew line intersects $\mathcal{S}$ in an even number of places. Let $p$ be a
point in $\mathcal{S}$. Then it must be intersected by $q/2$ skew lines. Then
for each of these skew lines, $\mathcal{S}$ must have an additional point
through which the line intersects. Thus, $|\mathcal{S}|\geq\frac{q}{2}+1$.

  * $B)$:

Suppose the codeword has a 1 at the $u$-column. Then we view the codeword as a
collection of non-hyperoval points $\mathcal{S}$ in $PG(2,q)$ such that any
skew line intersects $\mathcal{S}$ in an odd number of places, namely, at
least once. Since any two lines in $PG(2,q)$ intersect at exactly one point,
we obtain a minimum when we choose $\mathcal{S}$ to be a line. Since hyperoval
points are removed, secant lines have the fewest number of non-hyperoval
points in $PG(2,q)$, namely $q-1$. Thus, if the codeword has a 1 in the
$u$-column, then it must have weight at least $|\mathcal{S}|+1=q$. Since
$\mathcal{S}$ was found constructively, codewords of such weight do exist, and
hence this acts as our upper bound on the minimum weight.

∎

###  IV-C Secant Lines and All Points, $H(C_{seA})$

We now consider classical LDPC codes whose incidence matrices are constructed
by removing the rows in $M_{\pi}^{\prime}$ corresponding to lines skew to a
given hyperoval, leaving only the rows corresponding to the lines secant to
the hyperoval. This matrix, denoted $H(C_{seA})$, will have $q^{2}+q+2$
columns and $(q^{2}+3q+2)/2$ rows.

###### Proposition IV.3

The matrix $H(C_{seA})$ is a parity check matrix for a classical
$[4^{s}+2^{s}+2,\ 4^{s}-3^{s}+2^{s}+1,\ d_{seA}]$ LDPC code $C_{seA}$, where
$2^{s-1}+2\leq d_{seA}\leq 2^{s}+2$.

###### Proof:

We know $\dim(M_{\pi}^{\prime})=3^{s}+1$. It is also known [5] that removing
the rows corresponding to skew lines (thereby giving us $H(C_{seA})$) does not
change the rank of this matrix. Thus $\dim(H(C_{seA}))=3^{s}+1$. Since the
length $n$ is $4^{s}+2^{s}+2$, we solve for $\dim(C_{seA})=n-\dim(H(C_{seA}))$
to obtain our result.

To prove the bounds on the minimum distance, we again have the following two
cases:

  * $A)$:

Suppose the codeword has a 0 at the $u$-column. Then we view the codeword as a
collection of points $\mathcal{S}$ in $PG(2,q)$ such that any secant line
intersects $\mathcal{S}$ in an even number of places. Let $p$ be a point in
$\mathcal{S}$. Then it must be intersected by $(q+2)/2$ secant lines. Then for
each of these secant lines, $\mathcal{S}$ must have an additional point
through which the line intersects. Thus,
$|\mathcal{S}|\geq\frac{q+2}{2}+1=\frac{q}{2}+2=2^{s-1}+2$.

  * $B)$:

Suppose the codeword has a 1 at the $u$-column. Then it corresponds to a
collection of points $\mathcal{S}$ in $PG(2,q)$ such that every line secant to
the hyperoval intersects it an odd number of times, namely, at least once.
Since each line in $PG(2,q)$ intersects all other lines exactly once, we
obtain a minimum when we choose the points in $\mathcal{S}$ to be a collection
of $q+1$ points that make up a line. Thus, if a codeword has a 1 at the
$u$-column, then it must have weight at least $|\mathcal{S}|+1=q+2=2^{s}+2$.
Since $\mathcal{S}$ was found constructively, codewords of such weight do
exist, and hence this acts as the upper bound on the minimum weight.

∎

###  IV-D Secant Lines and Non-Hyperoval Points, $H(C_{se})$

While removing hyperoval points was not necessary to obtain good classical
codes constructed from secant lines, we nevertheless remove them here for
reasons that will become apparent later. Let $H(C_{se})$ be the matrix formed
by removing from $M_{\pi}^{\prime}$ the columns corresponding to hyperoval
points and the rows corresponding to lines skew to the hyperoval. This matrix
will have $(q^{2}+3q+2)/2$ rows and $q^{2}$ columns.

###### Proposition IV.4

The matrix $H(C_{se})$ is a parity check matrix for a classical $[4^{s},\
4^{s}-3^{s}+2^{s}+1,\ d_{se}]$ LDPC code $C_{se}$, where $2^{s-1}+2\leq
d_{se}\leq 2^{s}+2$.

###### Proof:

We know $\dim(M_{\pi})=3^{s}+1$. In [5] it was shown that columns
corresponding to hyperoval points and rows corresponding to skew lines can be
removed without affecting the dimension. Since the weight of each row of the
resulting matrix is odd, we can add the $u$-vector, to obtain the matrix
$H(C_{se})$, without affecting the rank. Thus, $\dim(H(C_{se}))=3^{s}+1$, from
which we determine the dimension of $C_{se}$.

To prove the minimum distance, we have the following two cases:

  * $A)$:

Suppose a codeword has a 0 at the $u$-column. Then it corresponds to a
collection of non-hyperoval points $\mathcal{S}$ in $PG(2,q)$ such that every
secant line intersects $\mathcal{S}$ in an even number of points. Let
$p\in\mathcal{S}$. Since it is intersected by $(q+2)/2$ secant lines, we must
have at least one additional point in $\mathcal{S}$ for each line to
intersect. Thus $|\mathcal{S}|\geq\frac{q}{2}+2=2^{s-1}+2$.

  * $B)$:

Suppose a codeword has a 1 at the $u$-column. The proof continues in a similar
fashion to that of Proposition IV.3. A set of points $\mathcal{S}$ in
$PG(2,q)$ corresponding to a codeword with a $1$ at the $u$-column will be
minimal when it intersects every secant line exactly once in non-hyperoval
points, which occurs when $\mathcal{S}$ is a collection of $q+1$ points
corresponding to a skew line. Thus, $|\mathcal{S}|+1=2^{s}+2$. Again, since
such codewords do exist, this weight acts as an upper bound on the minimum
weight of the code.

∎

##  V Quantum LDPC Codes

Using the results from Section IV, we construct parity check matrices for
QLDPC codes using the asymmetric and symmetric CSS constructions (6) and (7).

###  V-A Symmectric QLDPC Codes from All Points and All Lines

The symmetric QLDPC codes $\mathcal{C}_{\pi}$ constructed here have as a
parity check matrix $H(\mathcal{C}_{\pi})$ of the form

$H(\mathcal{C}_{\pi})=\begin{bmatrix}M_{\pi}^{\prime}&0\\\
0&M_{\pi}^{\prime}\end{bmatrix},$ (9)

where $M_{\pi}^{\prime}$ is as defined in Section IV-A. Recall that
$M_{\pi}^{\prime}$ is self-orthogonal by construction, and is a parity check
matrix for a classical LDPC code, and hence $H(\mathcal{C}_{\pi})$ is well-
defined.

###### Theorem V.1

Given a finite projective plane $\pi=PG(2,2^{s})$ for some positive integer
$s$, the matrix $H(\mathcal{C}_{\pi})$ in (9) is a parity check matrix for an
$[[n,\ 2k-n,\ D]]$ QLDPC code $\mathcal{C}_{\pi}$, where $n=4^{s}+2^{s}+2$,
$k=4^{s}-3^{s}+2^{s}+1$, and $D=2^{s}+2$.

###### Proof:

This follows immediately from Proposition IV.1 and the properties of symmetric
CSS codes. ∎

Observe that this code has a rate $\frac{2k-n}{n}$ that rapidly increases with
the length, and a minimum distance that increases on the order $\sqrt{n}$. The
number of stabilizers used for error correction, given by the number of rows
in the parity check, is almost $2n$.

###  V-B Asymmetric QLDPC Codes

The asymmetric QLDPC codes $\mathcal{C}_{asym}$ constructed here have as a
parity check matrix $H(\mathcal{C}_{asym})$ of the form

$H(\mathcal{C}_{asym})=\begin{bmatrix}H(C_{sk})&0\\\
0&H(C_{se})\end{bmatrix},$ (10)

where $H(C_{sk})$ and $H(C_{se})$ are as defined in Sections IV-B and IV-D,
respectively. Note that $H(C_{sk})$ and $H(C_{se})$ are orthogonal by
construction, and both have the same block length. Moreover, each is a parity
check for a classical LDPC code, making $H(\mathcal{C}_{asym})$ a well-defined
parity check for a QLDPC code.

###### Theorem V.2

Given a finite projective plane $PG(2,2^{s})$ for some positive integer $s$,
the matrix $H(\mathcal{C}_{asym})$ in (10) is a parity check matrix for a
$[[4^{s},K,D]]$ QLDPC code $\mathcal{C}_{asym}$, where $4^{s}-2\cdot
3^{s}+2\leq K\leq 4^{s}-2\cdot 3^{s}+2^{s}-1$, and $D\geq 2^{s-1}+1$.

###### Proof:

The length is determined by observing that $H(C_{sk})$ and $H(C_{se})$ are
parity checks for classical codes of length $4^{s}$. We obtain the dimension
$K$ and minimum distance $D$ from Propositions IV.2 and IV.4, and the fact
that $K=\dim(\mathcal{C}_{asym})=k_{sk}+k_{se}-n$, and minimum distance $D$ is
bounded below by $\min(d_{sk},d_{se})$, where $k_{sk}$, $k_{se}$, $d_{sk}$ and
$d_{se}$ are respectively the dimensions and minimum distances of the
classical codes $C_{sk}$ and $C_{se}$, respectively. ∎

While the bound on the dimension may be coarse, it is important to observe
that the rate of these codes nevertheless increases rapidly with the code
length $n$. The code will have only $n+\sqrt{n}+1$ parity checks, and very few
four-cycles.

###  V-C Symmectric QLDPC Codes from Skew Lines

The parity check matrix $H(\mathcal{C}_{symSK})$ for the symmetric QLDPC codes
$\mathcal{C}_{symSK}$ constructed here have the form

$H(\mathcal{C}_{symSK})=\begin{bmatrix}H(C_{sk})&0\\\
0&H(C_{sk})\end{bmatrix},$ (11)

where $H(C_{sk})$ is the self-orthogonal classical LDPC parity check matrix
defined in Section IV-B.

###### Theorem V.3

Given a finite projective plane $PG(2,2^{s})$ for some positive integer $s$,
the matrix $H(\mathcal{C}_{symSK})$ defined in (11) is a parity check matrix
for a $[[4^{s},\ 2k_{sk}-4^{s},\ D]]$ QLDPC code $\mathcal{C}_{symSK}$, where
$4^{s}-3^{s}-1\leq k_{sk}\leq 4^{s}-3^{s}+2^{s}$, and $D\geq 2^{s-1}+1$.

###### Proof:

This follows immediately from Proposition IV.2 and the properties of symmetric
CSS codes. ∎

Although the bound on the dimension of these codes is not as tight as that of
the asymmetric codes described in Section V-B, these codes nevertheless have a
fast rate that increases with the length $n$. The bound on the minimum
distance is the same as for the asymmetric codes, showing that these, too,
describe fast-rate QLDPC codes with good minimum distance. The codes will have
$n-\sqrt{n}$ parity checks and few four-cycles.

Code | CSS Type | Length | Dimension | Minimum | Number of
---|---|---|---|---|---
|  |  |  | Distance | Stabilizers
|  |  |  | (Lower Bound) |
$C_{\pi}$ | Symmetric | $4^{s}+2^{s}+2$ | $4^{s}-2\cdot 3^{s}+2^{s}$ | $2^{s}+2$ | $2^{2s+1}+2^{s+1}+2$
$C_{asym}$ | Asymmetric | $4^{s}$ | $4^{s}-2\cdot 3^{s}+2\leq K$ | $2^{s-1}+1$ | $4^{s}+2^{s}+1$
|  |  | $\leq 4^{s}-2\cdot 3^{s}+2^{s}-1$ |  |
$C_{symSK}$ | Symmetric | $4^{s}$ | $4^{s}-2\cdot 3^{s}-2\leq K$ | $2^{s-1}+1$ | $4^{s}-2^{s}$
|  |  | $\leq 4^{s}-2\cdot 3^{s}+2^{s+1}$ |  |
$C_{symSE}$ | Symmetric | $4^{s}+2^{s}+2$ | $4^{s}-2\cdot 3^{s}+2^{s}$ | $2^{s-1}+2$ | $4^{s}+3\cdot 2^{s}+2$
TABLE III: QLDPC Code Parameters for Parity Checks Constructed from
$PG(2,2^{s})$

###  V-D Symmetric QLDPC Codes from Secant Lines

Two different classical LDPC codes constructed from secant lines were
discussed in Section IV, namely those whose parity checks $H(C_{seA})$ were
constructed from all points, and those whose parity checks $H(C_{se})$ had the
columns corresponding to hyperoval points removed. Although $H(C_{se})$ is
orthogonal to $H(C_{sk})$, it is not self-orthogonal, while $H(C_{seA})$ is.
Thus, the parity check matrix $H(\mathcal{C}_{symSE})$ for the symmetric QLDPC
codes $\mathcal{C}_{symSE}$ constructed here have the form

$H(\mathcal{C}_{symSE})=\begin{bmatrix}H(C_{seA})&0\\\
0&H(C_{seA})\end{bmatrix}.$ (12)

###### Theorem V.4

Given a finite projective plane $PG(2,2^{s})$, for some positive integer $s$,
the matrix $H(\mathcal{C}_{symSE})$ in (12) is a parity check matrix for an
$[[n,2k_{seA}-n,D]]$ QLDPC code $\mathcal{C}_{symSE}$, where
$n=4^{s}+2^{s}+2$, $k_{seA}=4^{s}-3^{s}+2^{s}+1$, and $D\geq 2^{s-1}+2$.

###### Proof:

Here $k_{seA}=\dim(C_{seA})$. The rest follows from Proposition IV.3 and the
properties of symmetric CSS codes. ∎

Note that the length and dimension (and therefore the rate) of this code is
the same as that of $\mathcal{C}_{\pi}$, while the minimum distance and number
of stabilizers is roughly half that of $\mathcal{C}_{\pi}$.

##  VI Conclusion

Table III gives a summary of the results for each of the QLDPC codes discussed
in this report.

While many of the parameters are not exact for many of these codes, the bounds
nevertheless indicate that each of these codes are at least comparable to most
quantum LDPC codes in the literature. In fact, as previously mentioned, many
of these parameters are completely unknown for the other quantum LDPC codes.

While further research is necessary to determine exact values of minimum
distance and dimension of most of these codes, it is nevertheless established
that the projective plane is a very useful tool in the construction of quantum
low-density parity check codes. Similar techniques can also be used to
construct QLDPC codes from $PG(m,p^{s})$ for $m>2$ and/or $p$ an odd prime.
Note that in the case of $PG(2,p^{s})$ where $p$ is an odd prime, the
$u$-column is not necessarily linearly dependent on the columns of the
corresponding incidence matrix, making it much more difficult to determine
dimensions of corresponding QLDPC codes. However, this is resolved if in
addition to concatenating the $u$-column to the incidence matrix of the
projective plane, you also concatenate an identity matrix to it. This would
change the parameters in a known manner. Additionally, if $p$ is odd, then the
point-line subsets should be taken with respect to a conic, as we lose the
regular hyperoval structure present when $p$ is even.

## Acknowledgment

The author would like to thank James Troupe, Keye Martin, Keith Mellinger, and
Geir Agnarsson for useful discussions.

## References

  * [1] J. M. Farinholt, “Classes of high-performance quantum ldpc codes from finite projective geometries,” Master’s Thesis, George Mason University, 2012.
  * [2] R. G. Gallager, “Low density parity check codes,” _Transactions of the IRE Professional Group on Information Theory_ , vol. IT-8, pp. 21–28, January 1962\.
  * [3] Y. Kou, S. Lin, and M. P. C. Fossorier, “Low density parity check codes based on finite geometries: A rediscovery and new results,” _IEEE Trans. Inform. Theory_ , vol. 47, pp. 2711–2736, 2001.
  * [4] Droms, Meyer, and K. E. Mellinger, “Ldpc codes generated by conics in the classical projective plane,” _Designs, Codes, and Cryptography_ , vol. 40, no. 3, 2006.
  * [5] Castleberry, K. Hunsberger, and K. E. Mellinger, “Ldpc codes arising from hyperovals,” _Bull. Inst. Combin. Appl._ , vol. 58, pp. 59 – 72, 2010.
  * [6] C. E. Shannon, “A mathematical theory of communication,” _Bell System Technical Journal_ , vol. 27, pp. 379 – 423, 623 – 656, 1948.
  * [7] P. W. Shor, “Scheme for reducing decoherence in quantum computer memory,” _Phys. Rev. A_ , vol. 52, pp. 2493–2496, 1995.
  * [8] A. R. Calderbank and P. W. Shor, “Good quantum error-correcting codes exist,” _arXiv:quant-ph/9512032_ , 1996.
  * [9] A. M. Steane, “Multiple particle interference and quantum error correction,” _Proc. R. Soc. Lond. A_ , vol. 452, no. 2551, 1996.
  * [10] ——, “Error correcting codes in quantum theory,” _Phys. Rev. Lett._ , vol. 77, pp. 793 – 797, 1996.
  * [11] D. Gottesman, “Class of quantum error-correcting codes saturating the quantum hamming bound,” _Phys. Rev. A_ , vol. 54, pp. 1862–1868, 1996.
  * [12] A. R. Calderbank, E. M. Rains, P. W. Shor, and N. J. A. Sloane, “Quantum error correction and orthogonal geometry,” _Phys. Rev. Lett._ , vol. 78, no. 3, 1997.
  * [13] Postol, “A proposed quantum low density parity check code,” _arXiv:quant-ph/0108131_ , 2001.
  * [14] MacKay, Mitchison, and McFadden, “Sparse-graph codes for quantum error correction,” _IEEE Transactions on Information Theory_ , vol. 50, no. 10, 2004.
  * [15] J.-P. Tillich and G. Zémor, “Quantum ldpc codes with positive rate and minimum distance proportional to n 1/2,” in _Proceedings of the 2009 IEEE international conference on Symposium on Information Theory - Volume 2_ , ser. ISIT’09. Piscataway, NJ, USA: IEEE Press, 2009, pp. 799–803. [Online]. Available: http://dl.acm.org/citation.cfm?id=1701275.1701299
  * [16] S. Aly, “A class of quantum ldpc codes constructed from finite geometries,” in _Proc. 2008 IEEE Global Communication_ , ser. Globecom ’08, New Orleans, LA, USA, 2008.
  * [17] P. J. Cameron, _Combinatorics: Topics, Techniques, Algorithms_. Cambridge University Press, 1994.
  * [18] K. J. C. Smith, “On the $p$-rank if the incidence matrix of points and hyperplanes in a finite projective geometry,” _J. Comb. Theory_ , vol. 7, pp. 122 – 129, 1969.