# New Qubit Codes from Multidimensional Circulant Graphs 111This material is
based upon work supported by the National Science Foundation under Grant
DMS-2243991.

Padmapani Seneviratne<EMAIL_ADDRESS>Hannah
Cuff22footnotemark: 2<EMAIL_ADDRESS>Alexandra
Koletsos33footnotemark: 3<EMAIL_ADDRESS>Kerry Seekamp44footnotemark: 4
<EMAIL_ADDRESS>Adrian Thananopavarn55footnotemark: 5
<EMAIL_ADDRESS>Department of Mathematics, Texas A&M University-
Commerce,
2600 South Neal Street, Commerce, TX 75428.  Department of Mathematics,
Trinity College, 300 Summit Street Hartford, CT 06106.  Department of
Mathematics, Columbia University, 2990 Broadway New York, NY 10027.
Department of Mathematical Sciences, Smith College, 10 Elm Street Northampton,
MA 01063.  Department of Mathematics, Princeton University, Fine Hall,
Washington Road Princeton, NJ 08544-1000.

###### Abstract

Two new qubit stabilizer codes with parameters $\llbracket
77,0,19\rrbracket_{2}$ and $\llbracket 90,0,22\rrbracket_{2}$ are constructed
for the first time by employing additive symplectic self-dual
${\mathbb{F}}_{4}$ codes from multidimensional circulant (MDC) graphs. We
completely classify MDC graph codes for lengths $4\leq n\leq 40$ and show that
many optimal $\llbracket\ell,0,d\rrbracket$ qubit codes can be obtained from
the MDC construction. Moreover, we prove that adjacency matrices of MDC graphs
have nested block circulant structure and determine isomorphism properties of
MDC graphs.

###### keywords:

Additive codes, Quantum codes, Circulant graphs, Multidimensional circulant
graphs

##  1 Introduction

Errors in quantum computing present a unique challenge in storing and
transmitting data. When designing quantum error-correcting codes (QECCs), one
needs to address both bit flip and phase flip errors which can occur
simultaneosly. The existence of a QECC, which can protect quantum information
against decoherence, was first introduced in 1995 by Shor [13]. In their
seminal work [3], Calderbank, Rains, Shor, and Sloane established a connection
between classical error-correcting codes and binary QECCs (qubit codes).

Unlike their traditional counterparts, zero-dimensional qubit codes play an
important role in quantum computing. They can be used to test the accuracy of
quantum computers. They can also be used to test the storage locations of
qubits that are experiencing greater effects of decoherence than originally
predicted [3]. Zero-dimensional qubit codes corresponds to self-dual additive
codes over the finite field ${\mathbb{F}}_{4}=\\{0,1,\omega,\omega^{2}\\}$,
where $\omega^{2}=\omega+1$. Danielsen and Parker [4] employed Schlingemanns
[11] work to demonstrate that every graph generates a symplectic self-dual
additive code and conversely, any self-dual additive code over
${\mathbb{F}}_{4}$ has a graphical representation.

Highly symmetrical and vertex transitive graphs, such as circulant graphs,
have been extensively studied for their ability to generate optimal self-dual
additive codes [6, 14, 10]. However, other classes of graphs have also
demonstrated success in generating self-dual additive codes. For example, a
recent paper [12], presents five new $\llbracket\ell,0,d\rrbracket$ qubit
codes with parameters $(\ell,d)\in\\{(78,20),(90,21),(91,22),(93,21),(96,22)$
produced by metacirculant graphs, a class of vertex transitive graphs.

We further extend Danielsen and Parkers work by studying multidimensional
circulant graphs (MDCs), a generalization of circulant graphs on multiple
coordinates. We define MDC graphs and study their properties in Section 2.
Enumeration of self-dual codes of length $4\leq n\leq 40$ constructed from MDC
graphs are outlined in Section 3. Finally, we present new and optimal qubit
codes from multi-dimensional construction in Section 4.

##  2 Multidimensional Circulant Graphs

Circulant graphs have been extensively studied for their applications in the
field of code theory. Historically, they have demonstrated success in
generating QECCs via self-dual additive codes. We reference the definition of
circulant graphs presented in [9].

######  Definition 1.

Let $\mathbb{Z}_{n}$ denote the ring of integers modulo $n$. A circulant graph
$C(n,S)$ is a Cayley graph on ${\mathbb{Z}}_{n}$. That is, it is a graph whose
vertices are labeled $\\{0,1,\cdots,n-1\\}$, where two vertices $x$ and $y$
are adjacent if and only if $x-y\,(mod\ n)\in S$, where
$S\subset{\mathbb{Z}}_{n}$ with $S=-S$ and $0\notin S$.

The adjacency matrix of a circulant graph is a circulant matrix. An $n\times
n$ matrix $B$ is circulant if it has the form

$~{}B=\begin{pmatrix}b_{1}&b_{2}&\cdots&b_{n-1}&b_{n}\\\
b_{n}&b_{1}&\cdots&b_{n-2}&b_{n-1}\\\ \vdots&\vdots&\ddots&\vdots&\vdots\\\
b_{3}&b_{4}&\cdots&b_{1}&b_{2}\\\
b_{2}&b_{3}&\cdots&b_{n}&b_{1}\end{pmatrix}.$ (1)

There are numerous generalizations of circulant graphs in literature [1, 9].
Leighton [8] extended the notion of circulant graphs to multiple coordinates,
defining these graphs as multidimensional circulant. Essentially, a MDC graph
is a Cayley graph on ${\mathbb{Z}}_{n_{1}}\times
Z_{n_{2}}\times\cdots\times{\mathbb{Z}}_{n_{k}}$.

######  Definition 2.

Let ${\bf N}=(n_{1},n_{2},\ldots,n_{k})$ and let
$S\subset{\mathbb{Z}}_{n_{1}}\times
Z_{n_{2}}\times\cdots\times{\mathbb{Z}}_{n_{k}}$, with $S=-S$ and ${\bf
0}\notin S$. A MDC graph $\Gamma({\bf N},S)$ has the vertex set
$V(\Gamma)=\\{(v_{1},\ldots,v_{k}):v_{1}\in{\mathbb{Z}}_{n_{1}},\ldots,v_{k}\in{\mathbb{Z}}_{n_{k}}\\}$
and two vertices ${\bf x}=(x_{1},,\cdots,x_{k})$ and ${\bf
y}=(y_{1},,\cdots,y_{k})$ are adjacent if and only if $(x_{1}-y_{1}\ (mod\
n_{1})),\cdots,x_{k}-y_{k}\ (mod\ n_{k}))\in S$,

The following example presents the difference in structure between MDC and
circulant graphs.

######  Example 1.

The hypercube graph $Q_{3}$ is not circulant, but it is MDC, with parameters
$\Gamma((2,4),\\{(0,1),(0,3),(1,0)\\})$. The vertex set is partitioned into

$V_{0}:=\\{(0,0),(0,1),(0,2),(0,3)\\}\mbox{ and
}V_{1}:=\\{(1,0),(1,1),(1,2),(1,3)\\}.$

Figure 1: The $3$-cube graph as a MDC graph

Figure $1$ represents the hypercube graph $Q_{3}$ as a MDC graph with
parameters $N=(2,4)$ and $S=\\{(0,1),(0,3),(1,0)\\})$. The upper layer
contains the vertices in $V_{0}$ as $1,\ldots,4$ and the lower layer presents
the vertices in $V_{1}$ as $5,\ldots,8$.

######  Definition 3.

A nested block-circulant matrix is a $n\times n$ matrix that takes the form

$A=\begin{pmatrix}B_{1}&B_{2}&\ldots&B_{{l_{0}}-1}&B_{l_{0}}\\\
B_{l_{0}}&B_{1}&\ldots&B_{{l_{0}}-2}&B_{{l_{0}}-1}\\\
\vdots&\vdots&\ddots&\vdots&\vdots\\\ B_{3}&B_{4}&\ldots&B_{1}&B_{2}\\\
B_{2}&B_{3}&\ldots&B_{{l_{0}}}&B_{1}\end{pmatrix}$

where each block $B_{1},B_{2},\ldots,B_{l_{0}}$ can be recursively partitioned
into blocks $B^{i}_{1},B^{i}_{2},\ldots,B^{i}_{l_{1}}$, where $1\leq i\leq r$
for some $r$ and the smallest form of each block is a circulant matrix, as
given in equation 1.

######  Theorem 1.

Consider a multidimensional circulant graph $\Gamma(\mathbf{N},S)$ with
$\mathbf{N}=(n_{1},n_{2},\ldots,n_{k})$, where $n_{1}\leq n_{2}\leq\ldots\leq
n_{k}$. First, let us define $N_{1}=\frac{(n_{2}\cdot n_{3}\cdots
n_{k})}{n_{1}}$, $N_{2}=\frac{N_{1}}{n_{2}}$, $N_{3}=\frac{N_{2}}{n_{3}}$,
$\ldots$ , $N_{k}=\frac{N_{k-1}}{n_{k}}$. The adjacency matrix $A(\Gamma)$ of
$\Gamma({\bf N},S)$ is nested block circulant and has the form:

$A(\Gamma)=\begin{pmatrix}A_{1,1}&A_{1,2}&\ldots&A_{1,{l-1}}&A_{1,l}\\\
A_{1,l}&A_{1,1}&\ldots&A_{1,{l-2}}&A_{1,{l-1}}\\\
\vdots&\vdots&\ddots&\vdots&\vdots\\\
A_{1,3}&A_{1,4}&\ldots&A_{1,1}&A_{1,2}\\\
A_{1,2}&A_{1,3}&\ldots&A_{1,l}&A_{1,1}\end{pmatrix}$

where each block $A_{1,j}$ is a $N_{1}\times N_{1}$ submatrix of $A(\Gamma)$
for $1\leq j\leq n_{1}$.

###### Proof.

Let $\Gamma(\mathbf{N},S)$ be a multidimensional circulant graph where
$\mathbf{N}=(n_{1},n_{2},\cdots,n_{k})$ and the vertices are ordered
lexicographically. Let $N_{1}=\frac{(n_{2}\cdot n_{3}\cdots n_{k})}{n_{1}}$,
$N_{2}=\frac{N_{1}}{n_{2}}$, $N_{3}=\frac{N_{2}}{n_{3}}$, $\ldots$ ,
$N_{k}=\frac{N_{k-1}}{n_{k}}$.

First, let us show that the adjacency matrix $A$ of $\Gamma(\mathbf{N},S)$ is
block-circulant. To do so, let us partition the vertex set as $V=V^{1}_{0}\cup
V^{1}_{1}\cup\cdots\cup V^{1}_{n_{1}-1}$, where

$V^{1}_{i}=\\{(i,x_{2},\ldots,x_{k})\ |\ 0\leq x_{j}\leq n_{j}-1,\ 2\leq j\leq
k\\}\;\mbox{and}\;0\leq i\leq n_{1}-1.$ (2)

Accordingly, each $V^{1}_{i}$ will form $n_{1}$ submatrices, each of which we
will call $A^{1}_{i,l}$, where $|A^{1}_{i,l}|=N_{1}$, $0\leq l\leq n_{1}-1$.
Now, let vertex ${\bf x}=(i,x_{2},\ldots,x_{k})\in V_{i}^{1}$ and vertex ${\bf
y}=(l,y_{2},\ldots,y_{k})\in V_{l}^{1}$. We know ${\bf x}\sim{\bf y}$ iff
${\bf x}-{\bf y}\in S$, or rather, $(i-l,x_{2}-y_{2},\ldots,x_{k}-y_{k})\in
S$. With this in mind, consider vertex ${\bf
x}^{\prime}=(i+1,x_{2},\ldots,x_{k})\in V_{i+1}^{1}$ and vertex ${\bf
y}^{\prime}=(l+1,y_{2},\ldots,y_{k})\in V_{l+1}^{1}$. We can see that ${\bf
x}^{\prime}\sim{\bf y}^{\prime}$ iff $(i-l,x_{2}-y_{2},\ldots,x_{k}-y_{k})\in
S$. Therefore, the adjacency relation between $V^{1}_{i}$ and $V^{1}_{l}$ is
the same as the adjacency relation between $V^{1}_{i+1}$ and $V^{1}_{l+1}$.
Thus, we can establish the equality $A^{1}_{i,l}=A^{1}_{{i+1},{l+1}}$, showing
that each row of submatrices in $A(\Gamma)$ is a cyclic shift of one block to
the right of the previous row of submatrices.

Next, let us show that each submatrix $A^{1}_{i,l}$ is also block-circulant.
Let us partition $V^{1}_{i}=V^{2}_{i,0}\cup V^{2}_{i,1}\cup\ldots\cup
V^{2}_{i,n_{2}-1}$, where

$V^{2}_{i,p}=\\{(i,p,x_{3},\ldots,x_{k})\ |\ 0\leq x_{j}\leq n_{j}-1,\ 3\leq
j\leq k\\}$ and $0\leq p\leq n_{2}-1$.

Accordingly, each $V^{2}_{i,p}$ will form $n_{2}$ submatrices, each of which
we will call $A^{2}_{p,q}$, where $|A^{2}_{p,q}|=N_{2}$, $0\leq q\leq
n_{2}-1$. Now, let vertex ${\bf x}=(i,p,x_{3},\ldots,x_{k})\in V^{2}_{i,p}$
and vertex ${\bf y}=(l,q,y_{3},\ldots,y_{k})\in V^{2}_{l,q}$. We know ${\bf
x}\sim{\bf y}$ iff ${\bf x}-{\bf y}\in S$, or rather,
$(i-l,p-q,x_{3}-y_{3},\ldots,x_{k}-y_{k})\in S$. With this in mind, consider
vertex ${\bf x}^{\prime}=(i,p+1,x_{3},\ldots,x_{k})\in V^{2}_{i,p+1}$ and
vertex ${\bf y}^{\prime}=(l,q+1,y_{3},\ldots,y_{k})\in V^{2}_{l,q+1}$. We can
see that ${\bf x}^{\prime}\sim{\bf y}^{\prime}$ iff
$(i-l,p-q,x_{3}-y_{3},\ldots,x_{k}-y_{k})\in S$. Thus, we can establish the
equality $A^{2}_{p,q}=A^{2}_{p+1,q+1}$, showing that each row of submatrices
in $A^{1}_{i,l}$ is a cyclic shift of one block to the right of the previous
row of submatrices in $A^{1}_{i,l}$.

Thus, using this argument, there will be $|N|$ layers $l$ of nested blocks
that compose $A$, and layers $1\leq l\leq N-1$ will be block-circulant with
${n_{l}}^{2}$ submatrices $A^{l}_{i,j}$, where $0\leq i,j\leq n_{l}-1$ and
$|A^{l}_{i,j}|=N_{l}$. The $|N|^{th}$ layer will be circulant since
$|A^{l}_{i,j}|=N_{k}=1$ where $l=|N|$, showing that it will be composed of
blocks with dimension $1\times 1$ circulating around the matrix, which are
really just singular elements. ∎

######  Example 2.

Let $\Gamma(\mathbf{N},S)$ be a MDC graph with $\mathbf{N}=(3,2,2)$ and
$S=\\{(0,1,0),(2,0,1),(2,0,0)\\}$. This yields the adjacency matrix

$A$ = $\begin{pmatrix}\begin{array}[]{|c c:c c|}\hline\cr 0&0&1&0\\\
0&0&0&1\\\ \hdashline 1&0&0&0\\\ 0&1&0&0\\\
\hline\cr\end{array}&\begin{array}[]{c c c c}1&1&0&0\\\ 1&1&0&0\\\ 0&0&1&1\\\
0&0&1&1\end{array}&\begin{array}[]{c c c c}1&1&0&0\\\ 1&1&0&0\\\ 0&0&1&1\\\
0&0&1&1\end{array}\\\ \\\ \begin{array}[]{c c c c}1&1&0&0\\\ 1&1&0&0\\\
0&0&1&1\\\ 0&0&1&1\end{array}&\begin{array}[]{c c c c}0&0&1&0\\\ 0&0&0&1\\\
1&0&0&0\\\ 0&1&0&0\end{array}&\begin{array}[]{c c c c}1&1&0&0\\\ 1&1&0&0\\\
0&0&1&1\\\ 0&0&1&1\end{array}\\\ \\\ \begin{array}[]{c c c c}1&1&0&0\\\
1&1&0&0\\\ 0&0&1&1\\\ 0&0&1&1\end{array}&\begin{array}[]{c c c c}1&1&0&0\\\
1&1&0&0\\\ 0&0&1&1\\\ 0&0&1&1\end{array}&\begin{array}[]{c c c c}0&0&1&0\\\
0&0&0&1\\\ 1&0&0&0\\\ 0&1&0&0\end{array}\end{pmatrix}$

Note that $A(\Gamma)$ is composed of $9$ blocks that are $4\times 4$ sub-
matrices, where the first row of blocks circulates to the right to produce the
second and third rows of blocks. Each of these larger blocks is composed of
four $2\times 2$ smaller blocks, in accordance with Theorem 1.

######  Remark 1.

The adjacency matrix of a MDC graph can be completely determined by the first
row of each of the $n_{1}$ first row block matrices. In example 2, supports of
the first row of each of the first three block matrices are
$\\{3\\},\\{1,2\\},$ and $\\{1,2\\}$. We could write
$\Gamma((3,2,2),[\\{3\\},\\{1,2\\},\\{1,2\\}])$ rather than listing all
elements of the defining set $S$. Henceforth, $S$ denotes the supports of the
first row of the first $n_{1}$ blocks.

The complement $G^{\prime}$ of a graph $G$ is the graph on the same vertex set
as $G$ such that two distinct vertices in $G^{\prime}$ are adjacent if and
only if they are not adjacent in $G$. It is a well known fact that the
complement graph of a circulant graph is again a circulant graph. We will show
that the same is true for MDC graphs as well.

######  Lemma 2.

The complement graph of a MDC graph is also MDC.

###### Proof.

Let $\Gamma({\bf N},S)$ be a MDC graph with the vertex set $V$ and let
$V^{*}=V\setminus{\bf 0}$. Clearly, $S\subset V^{*}$. Let us define
$S^{\prime}=V^{*}\setminus S$ and claim $\Gamma^{\prime}({\bf
N},S)=\Gamma({\bf N},S^{\prime})$. Let ${\bf x}$ and ${\bf y}$ be two adjacent
vertices in $\Gamma({\bf N},S)$ . By the definition, ${\bf x}-{\bf y}\in S$
and ${\bf x}-{\bf y}\notin V^{*}\setminus S=S^{\prime}$. Hence, if ${\bf x}$
is adjacent to ${\bf y}$ in $\Gamma({\bf N},S)$ then they are not adjacent in
$\Gamma({\bf N},S^{\prime})$ and vice versa. Therefore, we have
$\Gamma^{\prime}({\bf N},S)=\Gamma({\bf N},S^{\prime})$

∎

An $m$-multipartite graphs is a graph in which vertices can be partitioned
into $m$ distinct independent sets.

######  Theorem 3.

Let $\Gamma({\bf N},S)$ be a MDC graph and define
$S_{j}=\bigcup\limits_{(x_{1},\ldots,x_{k})\in S}\\{x_{j}\\}$, the set
consisting of all $j^{th}$ coordinates of elements of $S$. Then $\Gamma({\bf
N},S)$ is a multipartite graph whenever $0\notin S_{1}$.

###### Proof.

Arrange the vertices in lexicographical order as in equation 2.

$V_{i}=\\{(i,x_{2},\ldots,x_{k})\ |\ 0\leq x_{j}\leq n_{j}-1,\ 2\leq j\leq
k\\}\;\mbox{and}\;0\leq i\leq n_{1}-1.$

Then $V(\Gamma)=V_{0}\cup V_{1}\cup\cdots\cup V_{n_{j}-1}$ is a partition of
the vertex set. Assume $0\notin S_{1}$ and let ${\bf
v}=(i,v_{2},\ldots,v_{k})$ and ${\bf u}=(i,u_{2},\ldots,u_{k})$ be arbitrary
vertices in the same partition $V_{i}$. Note that ${\bf v}-{\bf
u}=(0,v_{2}-u_{2},\ldots,v_{k}-u_{k})$ and ${\bf v}-{\bf u}\notin S$ as
$0\notin S_{1}$. Therefore, none of the vertices in same partition $V_{i}$ are
connected to each other and $\Gamma({\bf N},S)$ is a $n_{1}$ partite graph.

∎

Next, we establish a relationship between MDC graphs and another class of
vertex transitive graphs, namely metacirculant graphs, introduced by Alspach
and Parsons [1]. First, we recall the definition of metacirculant graphs.

######  Definition 4.

[1] Let $m,n$ be two fixed positive integers and $\alpha\in\mathbb{Z}_{n}$ be
a unit. Let $S_{0},S_{1},\ldots,S_{\lfloor m/2\rfloor}\\\
\subset\mathbb{Z}_{n}$ satisfy the four properties $S_{0}=-S_{0}$, $0\notin
S_{0}$, $\alpha^{m}S_{k}=S_{k}$ for $1\leq k\leq\lfloor m/2\rfloor$, and If
$m$ is even then $\alpha^{m/2}S_{m/2}=-S_{m/2}$. The meta-circulant graph
$\Gamma:=\Gamma\left(m,n,\alpha,S_{0},S_{1},\ldots,S_{\lfloor
m/2\rfloor}\right)$ has the vertex set
$V(\Gamma)=\mathbb{Z}_{m}\times\mathbb{Z}_{n}$. Let
$V_{0},V_{1},\ldots,V_{m-1}$, where $V_{i}:=\\{(i,j):0\leq j\leq n-1\\}$, be a
partition of $V(\Gamma)$. Let $1\leq k\leq\lfloor m/2\rfloor$. Vertices
$(i,j)$ and $(i+k,h)$ are adjacent if and only if $(h-j)\in\alpha^{i}\,S_{k}$.

The following result shows that any two dimensional MDC graph can be
represented as a metacirculant graph. But, the converse of the theorem is not
true in general.

######  Theorem 4.

Any two-dimensional MDC graph can be represented as a metacirculant graph with
$\alpha=1$.

###### Proof.

We consider two-dimensional MDC graphs $\Gamma((m,n),S)$ and metacirculant
graphs
$\Gamma(m,n,1,S_{0},S_{1},\cdots S_{k})$. By definition, both vertex sets are
$\mathbb{Z}_{m}\times\mathbb{Z}_{n}$, so they have a trivial bijective
mapping. We wish to show that this bijective mapping results in a homomorphism
between edges.

Given any two-dimensional circulant graph $G_{1}=\Gamma((m,n),S)$, let
$S_{i}=\\{s|(i,s)\in S\\}$ for $0\leq i\leq\lfloor m/2\rfloor$, and $G_{2}$ be
the corresponding metacirculant graph with $\alpha=1$. We first verify that
$G_{2}$ satisfies the criteria for metacirculant graphs:

$S=-S\implies S_{0}=-S_{0}$ $0\notin S\implies 0\notin S_{0}$
$\alpha^{m}S_{k}=1^{m}S_{k}=S_{k}$ $S=-S\implies S_{m/2}=-S_{m/2}\text{ for
even }m$

Now, for any two vertices
$(a_{1},b_{1}),(a_{2},b_{2})\in\mathbb{Z}_{m}\times\mathbb{Z}_{n}$, we have

$\displaystyle(a_{1},b_{1})\sim(a_{2},b_{2})\text{ in }G_{1}$
$\displaystyle\iff(a_{2}-a_{1},b_{2}-b_{1})\in S$ $\displaystyle\iff
b_{2}-b_{1}\in S_{a_{2}-a_{1}}\text{ or }b_{1}-b_{2}\in S_{a_{1}-a_{2}}$
$\displaystyle\iff b_{2}-b_{1}\in\alpha^{a_{1}}S_{a_{2}-a_{1}}\text{ or
}b_{1}-b_{2}\in\alpha^{a_{2}}S_{a_{1}-a_{2}}$
$\displaystyle\iff(a_{1},b_{1})\sim(a_{2},b_{2})\text{ in }G_{2},$

thus demonstrating that adjacency is the same and $G_{1}$ and $G_{2}$ are
isomorphic. ∎

Now that we have established fundamental properties of MDC graphs, we explore
some isomorphism properties of these graphs. Understanding isomorphism
properties within the class of MDC graphs and between the classes of MDC
graphs and other vertex transitive graphs allows us to improve the search
process for self-dual additive codes from MDC graphs, effectively reducing the
number of MDC graphs in the search process for a given length. We now present
these isomorphism properties.

Certain MDC graphs happen to be, in fact, one dimensional circulant graphs.
Leighton [8] proved the following characterization of MDC graphs.

######  Proposition 5.

[8] The MDC graph $\Gamma({\bf N},S)$ is isomorphic to a circulant graph on
$n$ vertices whenever $n=\prod_{1}^{k}n_{i}$ with ${\bf
N}=(n_{1},n_{2},\ldots,n_{k})$ and $n_{i},1\leq i\leq k$ are distinct primes.

Using theorem 5 as a framework, we establish a more stronger result valid for
all distinct relatively prime numbers.

######  Theorem 6.

The MDC graph $\Gamma({\bf N},S)$ is isomorphic to a circulant graph on $n$
vertices whenever $n=\prod_{1}^{k}n_{i}$ with ${\bf
N}=(n_{1},n_{2},\ldots,n_{k})$ and $n_{i},1\leq i\leq k$ are distinct
relatively prime integers.

###### Proof.

We will prove the result for $k=2$. Let $m$ and $n$ be relatively prime
integers. Define the function $\phi$ such that

$\displaystyle\phi:{\mathbb{Z}}_{m}\times{\mathbb{Z}}_{n}\rightarrow{\mathbb{Z}}_{mn}$
$\displaystyle\phi(x,y)=nx+my$

Clearly, $\phi$ is a bijection from ${\mathbb{Z}}_{m}\times{\mathbb{Z}}_{n}$
to ${\mathbb{Z}}_{mn}$. Let $\Gamma=\Gamma((m,n),S)$ be a MDC graph indexed by
the vertex set ${\mathbb{Z}}_{m}\times{\mathbb{Z}}_{n}$. We will show that
there exists a corresponding isomorphic circulant graph $C(mn,\phi(S))$.
Given $S$ is a defining set for the MDC graph $\Gamma((m,n),S)$, we first need
to show that $\phi(S)$ is a defining set for the circulant graph
$C(mn,\phi(S))$. Let $(s_{1},s_{2}),(t_{1},t_{2})\in S$ such that
$(s_{1},s_{2})+(t_{1},t_{2})=(0,0)$. Then
$\phi((s_{1},s_{2}))+\phi((t_{1},t_{2}))=(ns_{1}+ms_{2})+(nt_{1}+mt_{2})=n(s_{1}+t_{1})+m(s_{2}+t_{2})=0$.
Consequently, if $(t_{1},t_{2})$ is the additive inverse of $(s_{1},s_{2})\in
S$ then $\phi((t_{1},t_{2}))$ is the additive inverse of
$\phi((s_{1},s_{2}))\in\phi(S)$, and $\phi(S)$ is a defining set for
$C(mn,\phi(S))$.
Let ${\bf x}=(x_{1},x_{2})$ and ${\bf y}=(y_{1},y_{2})$ be two adjacent
vertices in $\Gamma$. Then ${\bf x}-{\bf
y}=(x_{1}-y_{1},x_{2}-y_{2})=(s_{1},s_{2})\in S$. Now
$\phi(s_{1},s_{2})=ns_{1}+ms_{2}\in\phi(S)$. Further,
$\phi(x_{1},x_{2})=nx_{1}+mx_{2}$, $\phi(y_{1},y_{2})=ny_{1}+my_{2}$, and
$\phi(x_{1},x_{2})-\phi(y_{1},y_{2})=(nx_{1}+mx_{2})-(ny_{1}+my_{2})=n(x_{1}-y_{1})+m(x_{2}-y_{2})=ns_{1}+ms_{2}\in\phi(S)$.
Therefore, we have shown that if two vertices are adjacent in the MDC graph
$\Gamma$ then their images under $\phi$ are adjacent in the circulant graph
$C(mn,\phi(S))$ implying $\Gamma((m,n,S)\equiv C(mn,\phi(S))$. , ∎

This allows us to establish a pattern that determines the total number of
distinct sets $\mathbf{N}$ for a multidimensional circulant graph with a
particular number of vertices.

######  Corollary 7.

The number of non-isomorphic sets $\mathbf{N}$ for a MDC graph $\Gamma(N,S)$
with a particular number of vertices $n$ is equivalent to the number of ways
to represent $n$ as a product of prime powers.

######  Example 3.

Consider $n=36$: The prime factorization of $n=2^{2}\cdot 3^{2}$. Then there
are $4$ distinct sets that generate non-isomorphic MDC graphs.

$n=3^{2}*2^{2}\rightarrow N=(9,4)\leftrightarrow N=(36)$

$n=3^{1}*3^{1}*2^{1}*2^{1}\rightarrow
N=(3,3,2,2)\leftrightarrow(6,3,2)\leftrightarrow(6,6)$

$n=3^{2}*2^{1}*2^{1}\rightarrow N=(9,2,2)\leftrightarrow(18,2)$

$n=3^{1}*3^{1}*2^{2}\rightarrow(3,3,4)\leftrightarrow(3,12)$

We also can observe isomorphisms among graphs with the same vertex set. One
such family of isomorphic graphs is given by the following theorem.

######  Theorem 8.

The multidimensional circulant graphs $\Gamma({\bf N},S)$ and $\Gamma({\bf
N},\sigma(S))$ are isomorphic, where

$\displaystyle\sigma\colon{\mathbb{Z}}_{n_{1}}\times{\mathbb{Z}}_{n_{2}}\times\cdots{\mathbb{Z}}_{n_{k}}$
$\displaystyle\longrightarrow\mathbf{{\mathbb{Z}}}_{n_{1}}\times{\mathbb{Z}}_{n_{2}}\times\cdots{\mathbb{Z}}_{n_{k}}$
$\displaystyle(a_{1},a_{2},\ldots,a_{k})$
$\displaystyle\longmapsto(\alpha_{1}a_{1},\alpha_{2}a_{2},\ldots,\alpha_{k}a_{k}).$

and
$\alpha_{1}\in{\mathbb{Z}}_{n_{1}},\alpha_{2}\in{\mathbb{Z}}_{n_{2}},\ldots\alpha_{k}\in{\mathbb{Z}}_{n_{k}}$
are units.

###### Proof.

Because all $\alpha$’s are units, $\sigma$ has a well-defined inverse,
$\sigma^{-1}((a_{1},\ldots,a_{k}))=(\alpha_{1}^{-1}a_{1},\ldots,\alpha_{k}^{-1}a_{k})$
and is bijective. Let ${\bf a}=(a_{1},\ldots,a_{k})$ and ${\bf
b}=(b_{1},\ldots,b_{k})$ be two vertices of $\Gamma({\bf N},S)$ . We know
${\bf a}\sim{\bf b}$ if and only if ${\bf a}-{\bf b}\in S$ and ${\bf a}-{\bf
b}=(a_{1}-b_{1},\ldots,a_{k}-b_{k})\in S$. Observe that $\sigma({\bf
a})-\sigma({\bf
b})=(\alpha_{1}a_{1}-\alpha_{1}b_{1},\ldots,\alpha_{k}a_{k}-\alpha_{k}b_{k})=(\alpha_{1}(a_{1}-b_{1}),\ldots,\alpha_{k}(a_{k}-b_{k}))\in\sigma(S)$,
implying $\sigma({\bf a})\sim\sigma({\bf b})$ in $\Gamma({\bf N},\sigma(S))$.
∎

In some special cases, there may be an isomorphism between different
$\mathbf{N}$’s even though the elements of $\mathbf{N}$ are not coprime. One
example is the cube graph:

######  Example 4.

The $3$-cube graph can be represented in two different ways:
$\Gamma((4,2),\\{(0,1),(1,0),(3,0)\\})$ and
$\Gamma((2,2,2),\\{(0,0,1),(0,1,0),(1,0,0)\\})$.

This isomorphism may be generalized to more dimensions, according to the
following theorem:

######  Theorem 9.

Every $k$-dimensional circulant graph with $\mathbf{N}=(4,2,2,\dotsc,2)$ is
isomorphic to a $(k+1)$-dimensional circulant graph with
$\mathbf{N}=(2,2,2,2,\dotsc,2)$.

###### Proof.

Let $\Gamma((4,2,2,\dotsc,2),S)$ be a multidimensional circulant graph. Now,
we define a transformation
$\phi(s):\mathbb{Z}_{4}\times\mathbb{Z}_{2}^{k-1}\rightarrow\mathbb{Z}_{2}^{k+1}$
as follows: If $s=(s_{1},s_{2},\cdots,s_{k})$, then let

$\phi(s)=\begin{cases}(0,0,s_{2},\cdots,s_{k})&s_{1}=0\\\
(1,0,s_{2},\cdots,s_{k})&s_{1}=1\\\ (1,1,s_{2},\cdots,s_{k})&s_{1}=2\\\
(0,1,s_{2},\cdots,s_{k})&s_{1}=3.\end{cases}$

As $\phi$ forms a bijective mapping on the first two coordinates and leaves
the rest the same, $\phi$ is bijective on the vertex sets from
$\mathbf{N}=(4,2,2,\dotsc,2)$ to $\mathbf{N}=(2,2,2,2,\dotsc,2)$.

Now, using this mapping, we will show that applying $\phi$ to the elements of
$S$ results in a homomorphism. Suppose two vertices $v_{1}$ and $v_{2}$ are
adjacent in $\Gamma((4,2,2,\dotsc,2),S)$. Then, in
$\Gamma((2,2,2,2,\dotsc,2),\phi(S))$, we have 3 cases.

  1. 1.

If the first coordinates of $v_{1}$ and $v_{2}$ are the same, the first two
coordinates of $\phi(v_{1})$ and $\phi(v_{2})$ are the same, so
$(0,0,s_{2},\cdots,s_{k})\in S$ connects the two in
$\Gamma((2,2,2,2,\dotsc,2),\phi(S))$.

  2. 2.

If the first coordinates of $v_{1}$ and $v_{2}$ differ by one, exactly one of
the first two coordinates of $\phi(v_{1})$ and $\phi(v_{2})$ will differ, so
either $(1,0,s_{2},\cdots,s_{k})\in S$ or $(0,1,s_{2},\cdots,s_{k})\in S$
connects the two in $\Gamma((2,2,2,2,\dotsc,2),\phi(S))$.

  3. 3.

If the first coordinates of $v_{1}$ and $v_{2}$ differ by two, both of the
first two coordinates of $\phi(v_{1})$ and $\phi(v_{2})$ will differ, so
$(1,1,s_{2},\cdots,s_{k})\in S$ connects the two in
$\Gamma((2,2,2,2,\dotsc,2),\phi(S))$.

In any case, $\phi(v_{1})$ and $\phi(v_{2})$ are adjacent, and as the cases
exactly cover the coordinates of $\phi(v_{1})$ and $\phi(v_{2})$, if
$\phi(v_{1})$ and $\phi(v_{2})$ are adjacent, then $v_{1}$ and $v_{2}$ will be
as well. Therefore, $\Gamma((4,2,2,\dotsc,2),S)$ is isomorphic to
$((2,2,2,2,\dotsc,2),\phi(S))$. ∎

##  3 Self-dual additive codes from MDC graphs

In this section, we use our own unique construction of multidimensional
circulant graphs to generate zero-dimensional quantum error correcting codes,
which we represent as self-dual additive codes over ${\mathbb{F}}_{4}$. Most
of the qubit codes of length $n=1$ through $n=30$ found on
http://www.codetables.de are extremal, meaning these codes meet their
appropriate bound. However, we attempt to improve the minimum distance of non-
extremal codes using MDC construction. We find two new $0$-dimensional qubit
codes of lengths $77$ and $90$ with respective minimum distances $19$ and
$22$, improving upon previous best-known minimum distances by $1$.

An additive code $C$ of length $n$ over ${\mathbb{F}}_{4}$ is an additive
subgroup of ${\mathbb{F}}_{4}^{n}$. An element ${\bf c}$ of $C$ is called a
codeword of $C$. The weight of a vector ${\bf u}\in{\mathbb{F}}_{4}^{n}$ is
the number of nonzero entries of ${\bf u}$. The least nonzero weight of all
codewords in $C$ is called the minimum distance of $C$. If $C$ is an additive
code of length $n$ over ${\mathbb{F}}_{4}$ with minimum distance $d$ and size
$2^{k}$, then $C$ is denoted by $(n,2^{k},d)_{4}$. The weight distribution of
$C$ is the set $\\{W_{0},W_{1},\ldots,W_{r}\\}$, where $0\leq r\leq n$ and
$W_{j}=W_{j}(C)$ is the number of codewords of weight $j$ in $C$.

Given two vectors ${\bf u}=(u_{1},u_{2},\ldots,u_{n})$ and ${\bf
v}=(v_{1},v_{2},\ldots,v_{n})$ in ${\mathbb{F}}_{4}^{n}$, the Hermitian trace
inner product of ${\bf u}$ and ${\bf v}$ is defined by

$\displaystyle{\bf u}*{\bf v}=\sum_{i=1}^{n}u_{i}v_{i}^{2}+u_{i}^{2}v_{i}.$

The symplectic dual $C^{*}$ of an additive code $C$ is given by $C^{*}=\\{{\bf
u}\in{\mathbb{F}}_{4}^{n}\mid{\bf u}*{\bf c}=0\;\mbox{for all}\;{\bf c}\in
C\\}$. An additive code $C$ is called symplectic self-dual if $C=C^{*}$.

Schlingemann [11] and later Danielsen [4] showed that every self-dual additive
code over ${\mathbb{F}}_{4}$ can be represented by a graph. In particular, if
$C(\Gamma)$ denotes the additive code generated by the row span of the matrix
$A(\Gamma)+\omega\cdot I$, where $A(\Gamma)$ is the adjacency matrix of a
graph $\Gamma$ and $I$ is the identity matrix, then $C(\Gamma)$ is symplectic
self-dual.

There were several studies involving classification of additive self-dual
codes over ${\mathbb{F}}_{4}$. First, Danielsen and Parker [4] did a complete
classification for lengths $n\leq 12$. Later, Gulliver and Kim [7], Grassl and
Harada [6], and Saito [10] contributed to the classification of lengths up to
$n\leq 50$. These studies centered on additive codes from one-dimensional
circulant graphs with circulant adjacency and bordered matrices. In this work,
we consider multidimensional circulant graphs and expand the search space for
new qubit codes.

An additive self-dual code $C$ over ${\mathbb{F}}_{4}$ is called Type $II$ if
the weights of all the codewords in $C$ is even. A code which is not Type $II$
is called Type $I$. Any Type $II$ code must have even length. We classify Type
$I$ and Type $II$ additive self-dual codes from MDC graphs by the following
result.

######  Lemma 10.

Let $\Gamma=$ $\Gamma({\bf N},S)$ be a MDC graph that produces the additive
self-dual code $C_{\Gamma}$. Then $C_{\Gamma}$ is Type $II$ if and only if
$\mid S\mid$ is odd.

###### Proof.

It was shown in [4] that self-dual additive code $C$ generated by a regular
graph $\Gamma$ is Type $II$ if and only if all vertices of $\Gamma$ have odd
degrees. MDC graphs are regular with valency $|S|$ and the result follows. ∎

We ran an exhaustive search to generate every possible self-dual additive code
that could be generated with MDC graphs when $n$ ranges from $4$ to $40$. To
conclude this section, we present a table that provide a comparative study
between the qubit codes generated with MDC graphs, and qubit codes generated
with circulant graphs.

In the table $1$, $n$ denotes the number of vertices (length of the additive
code), $N$ signifies distinct sets, $d_{\textit{max}}^{mdc}(n)$ indicates the
maximum minimum distance among self-dual additive codes generated by MDC
graphs, $d_{\textit{max}}^{c}(n)$ denotes the maximum known minimum distance
generated using circulant graphs [10], and $d_{max}(n,0)$ means the maximum
known minimum distance among all qubit codes with distance $n$ and dimension
$0$ [5].

$n$ | $N$ | $d_{max}^{mdc}(n)$ | $d_{\textit{max}}^{c}(n)$ | $d_{max}(n,0)$ | $n$ | $N$ | $d_{\textit{max}}^{mdc}(n)$ | $d_{\textit{max}}^{c}(n)$ | $d_{max}(n,0)$
---|---|---|---|---|---|---|---|---|---
4 | [2, 2] | 2 | 2 | 2 | 24 | [3, 8],[2, 12],[2,2, 6] | 8 | 8 | 8-10
6 | [2, 3] | 4 | 4 | 4 | 26 | [2, 13] | 8 | 8 | 8-10
8 | [2, 4],[2, 2, 2] | 4 | 4 | 4 | 27 | [3, 9] | 8 | 8 | 9-10
|  |  |  |  |  | [3, 3, 3] | 6 |  |
9 | [3, 3] | 4, 3 | 4 | 4 | 28 | [4, 7],[2, 14] | 10, 8 | 10 | 10
10 | [2, 5] | 4 | 4 | 4 | 30 | [3, 10] | 12 | 12 | 12
12 | [3, 4],[2, 6] | 6,4 | 6 | 6 | 32 | [2, 16] | 10 | 10 | 10-12
|  |  |  |  |  | [8,4],[2, 2, 8][2, 2, 2, 4] | 8 |  |
|  |  |  |  |  | [2, 4, 4] | 6 |  |
|  |  |  |  |  | [2, 2, 2, 2, 2] | 8 |  |
14 | [2, 7] | 6 | 6 | 6 | 33 | [3, 11] | 10 | 10 | 10-12
15 | [3, 5] | 6 | 6 | 6 | 34 | [2, 17] | 10 | 10 | 10-12
16 | [2, 8] | 6 | 6 | 6 | 35 | [5, 7] | 10 | 10 | 11-13
| [4, 4],[2, 2, 4] | 4 |  |  |  |  |  |  |
| [2, 2, 2, 2] | 4 |  |  |  |  |  |  |
18 | [2, 9], [3, 6] | 6 | 6 | 8 | 36 | [2, 18] | 12 | 11 | 12-14
|  |  |  |  |  | [4, 9] | 11 |  |
|  |  |  |  |  | [3, 12],[6, 6] | 10 |  |
20 | [4, 5], [2, 10] | 8 | 8 | 8 | 38 | [2, 19] | 12 | 12 | 12-14
21 | [3, 7] | 7 | 7 | 8 | 39 | [3, 13] | 11 | 11 | 11-14
22 | [2, 11] | 8 | 8 | 8 | 40 | [5, 8],[2, 20],[2,2, 10] | 12 | 12 | 12-14
Table 1: Minimum distances of MDC graph codes.

##  4 New and optimal qubit codes

This section presents new and optimal symplectic self-dual additive codes
generated from the MDC construction. We refer to a code $C$ as new if the
minimum distance of $C$ is higher than the best known minimum distance
available in the literature for the same length and the dimension. A code $C$
is called optimal if $C$ has the best known minimum distance among known codes
with the same parameters.

A central point of focus of our work involves comparing the quantum codes
generated by multidimensional circulant graphs with the quantum codes
generated by circulant graphs. We have thus far shown that MDC graphs have the
potential to produce codes with better minimum distances than codes produced
by circulant graphs. For example, the best minimum distance of codes generated
by circulant graphs for $n=36$ is $11$, while the best minimum distance of
codes generated by MDC graphs for $n=36$ is $12$. In the following
proposition, we establish two non-isomorphic families of MDC graphs that yield
$\llbracket 36,0,12\rrbracket$ qubit codes, adapting Proposition 2 in [12].

######  Proposition 11.

The non-isomorphic MDC graphs

$\begin{split}\Gamma_{36,1}&=\Gamma((2,18),[\\{4,5,6,7,13,14,15,16\\},\\{1,3,7,13,17\\}]\\\
\Gamma_{36,2}&=\Gamma((2,18),[\\{3,7,13,17\\},\\{1,5,6,8,9,11,12,14,15\\}]\end{split}$

generates two inequivalent $(36,2^{36},12)$, Type II additive self-dual codes
$C_{36,1}$ and $C_{36,2}$ yielding two inequivalent $\llbracket
36,0,12\rrbracket$ qubit codes.

###### Proof.

The MDC graphs $\Gamma_{36,1}$ and $\Gamma_{36,2}$ have valency $|S|=13$ and
by Lemma 10, the self-dual additive codes $C_{36,1}$ and $C_{36,2}$ are Type
$II$. The weights $W_{12}(C_{36,1})=28764$ and $W_{12}(C_{36,2})=20844$
implying the two codes $C_{36,1}$ and $C_{36,2}$ are inequivalent. By Theorem
4, the MDC graphs $\Gamma_{36,1}$ and $\Gamma_{36,2}$ are isomorphic to
metacirculant graphs $G_{36,1}$ and $G_{36,2}$ respectively, obtained in [12],
Proposition 2. ∎

i.

(a) *

ii.

(b) * Figure 2:  i). MDC graph $\Gamma_{36,1}$, ii). MDC graph
$\Gamma_{36,2}$.

[.45] [.45]

There is no circulant or cyclic construction for the optimal qubit code with
parameters $\llbracket 72,0,18\rrbracket$. In Grassl’s table [5], the optimal
qubit code is listed by a stored generator matrix. We were able to obtain $16$
non-equivalent $\llbracket 72,0,18\rrbracket$ codes with the MDC construction.

######  Proposition 12.

There exists at least $16$ non-equivalent MDC based optimal qubit codes with
parameters $\llbracket 72,0,18\rrbracket$. The corresponding non-isomorphic
MDC graphs have parameters $\Gamma_{72,i}=\Gamma({\bf N},S_{i}),\;1\leq i\leq
16$, where

${\scriptsize\begin{split}S_{1}&=[\\{2,3,5,7,8,9,10,11,12,13,15,17,18\\},\\{1,4,8,10,11,12,13,15,18\\},\\{1,3,17\\},\\{1,2,5,7,8,9,10,12,16\\}],\\\
S_{2}&=[\\{3,4,6,8,12,14,16,17\\},\\{4,5,7,13,14,16,17\\},\\{1,6,14\\},\\{3,4,6,7,13,15,16\\}],\\\
S_{3}&=[\\{2,4,5,6,7,13,14,15,16,18\\},\\{1,3,4,6,7,9,10,14,15,16,17,18\\},\\{3,5,9,10,11,15,17\\},\\{1,2,3,4,5,6,10,11,13,14,16,17\\}]\\\
S_{4}&=[\\{5,7,8,12,13,15\\},\\{1,2,4,5,7,8,9,12,16,18\\},\\{2,4,5,6,8,9,10,11,12,14,15,16,18\\},\\{1,2,4,8,11,12,13,15,16,18\\}]\\\
S_{5}&=[\\{4,5,6,8,9,11,12,14,15,16\\},\\{3,5,6,7,8,11,12,13,14,15,16,17\\},\\{2,3,6,9,10,11,14,17,18\\},\\{3,4,5,6,7,8,9,12,13,14,15,17\\}]\\\
S_{6}&=[\\{2,4,6,7,9,10,11,13,14,16,18\\},\\{2,4,7,9,11,12,16,17\\},\\{2,5,6,8,12,14,15,18\\},\\{3,4,8,9,11,13,16,18\\}]\\\
S_{7}&=[\\{5,6,7,9,11,13,14,15\\},\\{3,6,9,11,13,16,18\\},\\{1,2,3,4,6,7,10,13,14,16,17,18\\},\\{2,4,7,9,11,14,17\\}]\\\
S_{8}&=[\\{2,5,6,14,15,18\\},\\{2,3,6,11,15,16,18\\},\\{1,6,8,12,14\\},\\{2,4,5,9,14,17,18\\}]\\\
S_{9}&=[\\{3,4,6,7,8,9,10,11,12,13,14,16,17\\},\\{1,4,6,7,8,10,11,12,13,14,15,17\\},\\{7,9,11,13\\},\\{1,3,5,6,7,8,9,10,12,13,14,16\\}]\\\
S_{10}&=[\\{3,4,7,8,9,11,12,13,16,17\\},\\{2,3,4,5,8,9,13,14,15,16,17,18\\},\\{1,4,6,7,8,9,11,12,13,14,16\\},\\{2,3,4,5,6,7,11,12,15,16,17,18\\}]\\\
S_{11}&=[\\{4,8,12,16\\},\\{1,2,3,4,6,9,10,14,17\\},\\{2,6,7,8,9,10,11,12,13,14,18\\},\\{1,3,6,10,11,14,16,17,18\\}]\\\
S_{12}&=[\\{3,4,5,6,7,10,13,14,15,16,17\\},\\{1,2,3,4,5,12,13,16,17\\},\\{3,4,5,15,16,17\\},\\{1,3,4,7,8,15,16,17,18\\}]\\\
S_{13}&=[\\{2,4,6,7,8,9,11,12,13,14,16,18\\},\\{1,2,4,6,7,8,11,16,18\\},\\{1,2,3,4,7,8,9,11,12,13,16,17,18\\},\\{1,2,4,9,12,13,14,16,18\\}]\\\
S_{14}&=[\\{2,3,4,5,7,8,9,11,12,13,15,16,17,18\\},\\{2,3,4,5,8,10,11,12,13,14,15,16,17,18\\},\\{2,3,4,8,9,10,11,12,16,17,18\\},\\{2,3,4,5,6,7,8,9,10,12,15,16,17,18\\}]\\\
S_{15}&=[\\{5,6,7,9,11,13,14,15\\},\\{5,6,7,8,9,11,12,18\\},\\{3,10,17\\},\\{2,8,9,11,12,13,14,15\\}]\\\
S_{16}&=[\\{5,6,7,9,11,13,14,15\\},\\{1,2,4,5,6,7,9,10,11,13,14,16,18\\},\\{3,5,7,10,13,15,17\\},\\{1,2,4,6,7,9,10,11,13,14,15,16,18\\}]\end{split}}$

###### Proof.

The graphs $\Gamma_{72,i}$ have valencies
$[34,25,41,39,43,35,34,25,41,45,33,35,43,53,27,41]$ for $1\leq i\leq 16$
respectively. Therefore, graphs
$\Gamma_{1},\Gamma_{2},\Gamma_{3},\Gamma_{4},\Gamma_{5},\Gamma_{6},\Gamma_{10},\Gamma_{11},\Gamma_{14}$,
and $\Gamma_{15}$ are non-isomorphic. Let $C_{72,i}$ denote the corresponding
additive self-dual codes from $\Gamma_{72,i}$ $1\leq i\leq 16$. Then
$W_{18}(C_{72,i})=[5760,9108,10404,9768,9244,9684,5028,8940,9252,9792,9012,8844,7776,\\\
9336,8256,8064]$ implying codes $C_{72,i}$ are inequivalent for $1\leq i\leq
16$. ∎

Further, there is no known circulant construction of the $\llbracket
76,0,18\rrbracket$ code. We were able to find $3$ inequivalent codes from the
MDC construction.

######  Proposition 13.

There are at least $3$ MDC based optimal non-equivalent qubit codes with
parameters $\llbracket 76,0,18\rrbracket$. The corresponding MDC graphs are
given by $\Gamma_{76,i}=\Gamma((2,38),S_{i}),\;1\leq i\leq 3$, where

${\scriptsize\begin{split}S_{1}=&[\\{6,8,9,10,11,29,30,31,32,34\\},\\{3,6,9,11,13,14,16,17,20,23,24,26,27,29,31,34,37\\}]\\\
S_{2}=&[\\{2,3,4,5,7,8,10,11,12,13,14,15,18,22,25,26,27,28,29,30,32,33,35,36,37,38\\},\\\
&\\{1,2,3,4,5,6,7,8,9,11,12,13,14,15,16,17,18,22,23,24,25,26,27,28,29,31,32,33,34,35,36,37,38\\}]\\\
S_{3}=&[\\{2,3,5,7,8,11,12,13,15,16,17,18,19,21,22,23,24,25,27,28,29,32,33,35,37,38\\},\\\
&\\{1,2,4,5,6,8,11,12,13,14,15,16,17,18,22,23,24,25,26,27,28,29,32,34,35,36,38\\}]\end{split}}$

###### Proof.

The valence of the MDC graphs $\Gamma_{76,i}$ are $27,29$, and $53$
respectively for $1\leq i\leq 3$. Hence, the graphs are non-isomorphic and the
generated additive codes are non-equivalent. ∎

Next, we introduce the two new qubit codes with lengths $77$ and $90$ obtained
from the MDC construction.

######  Proposition 14.

The MDC graph $\Gamma_{77}$:=$\Gamma({\bf N},S)$ , where ${\bf N}=(7,11)$ with
the defining set $S=[s_{1},s_{2},\ldots,s_{7}]$, where
$s_{1}=\\{3,4,5,6,7,8,9,10\\}$, $s_{2}=\\{1,2,4,6,10,11\\}$,
$s_{3}=\\{1,2,3,4,5,6,9,11\\}$, $s_{4}=\\{1,2,4,5,6,7,9,10,11\\}$,
$s_{5}=\\{1,2,3,4,6,7,8,9,11\\}$, $s_{6}=\\{1,2,4,7,8,9,10,11\\}$, and
$s_{7}=\\{1,2,3,7,9,11\\}$ generates a new $(77,2^{77},19)_{4}$ additive self-
dual code $C_{77}$. The corresponding qubit code $Q_{77}$ has parameters
$\llbracket 77,0,19\rrbracket$ and exceeds the minimum distance of the best
known qubit code listed on the Grassl’s table [5] by $1$.

###### Proof.

The MDC graph $\Gamma_{77}$ and consequently, the additive code $C_{77}$ was
found by a randomized search and the minimum distance of $C_{77}$ was verified
using MAGMA. ∎

######  Proposition 15.

The MDC graph $\Gamma_{90}:=$ $\Gamma({\bf N},S)$ , where ${\bf N}=(9,10)$
with the defining set $S=[s_{1},s_{2},\ldots,s_{9}]$ of vectors, where
$s_{1}=\\{2,3,4,5,6,7,8,9,10\\}$, $s_{2}=\\{1,3,4,7,9,10\\}$,
$s_{3}=\\{1,2,4,6,7,8,9\\}$, $s_{4}=\\{1,3,6,8,9,10\\}$,
$s_{5}=\\{1,3,5,8,9,10\\}$, $s_{6}=\\{1,2,3,4,7,9\\}$,
$s_{7}=\\{1,2,3,4,6,9\\}$, $s_{8}=\\{1,3,4,5,6,8,10\\}$, and
$s_{9}=\\{1,2,3,5,8,9\\}$ produces a new $(90,2^{90},22)_{4}$ Type $II$
additive self-dual code $C_{90}$. The new $\llbracket 90,0,22\rrbracket$ qubit
code $Q_{90}$ has better minimum distance than the best known qubit code with
parameters $\llbracket 90,0,21\rrbracket$ given in [12].

###### Proof.

A randomized search among all symbol sets ${\bf
N}=(2,45),(3,30),(5,18),(6,15)$ and $(9,10)$ yielded the desired graph
$\Gamma_{90}$ with the additive code $C_{90}$. MAGMA was used to verify the
minimum distance of $C_{90}$. The code is Type $II$, since $|S|=59$. ∎

##  5 Concluding remarks

We have shown that MDC graphs have similar properties to circulant graphs and
are as effective as circulant graphs with regard to obtaining optimal self-
dual additive codes. Computationally, we observed that two-dimensional MDC
graphs produced codes with higher minimum distances than that of higher
dimensional MDC graphs. This drawback may be due to the fact that adjacency
matrices of MDC graphs have nested block circulant structures.

## Supplementary material

  1. 1.

MDC graphs $\Gamma_{77}$ and $\Gamma_{90}$, and their corresponding additive
codes can be explicitly constructed by running MDB77Test.m and MDB90Test.m.

  2. 2.

The certificates of minimum distance computations for $\llbracket
77,0,19\rrbracket$ and $\llbracket 90,0,22\rrbracket$ are labeled
New77output.txt  and New90output.txt.

## References

  * [1] B. Alspach and T. D. Parsons, “A construction for vertex-transitive graphs,” _Canad. J. Math._ , vol. 34, no. 2, pp. 307–318, Apr 1982.
  * [2] W. Bosma, J. Cannon, and C. Playoust, “The MAGMA algebra system I: The user language,” _J. Symb. Comput._ , vol. 24, no. 3-4, pp. 235–265, Sep 1997.
  * [3] A. R. Calderbank, E. M. Rains, P. M. Shor, and N. J. A. Sloane, “Quantum error correction via codes over $GF(4)$,” _IEEE Trans. Inform. Theory_ , vol. 44, no. 4, pp. 1369–1387, Jul 1998.
  * [4] L. E. Danielsen and M. G. Parker, “On the classification of all self-dual additive codes over ${GF}(4)$ of length up to $12$,” _J. Combin. Theory, Ser. A_ , vol. 113, no. 7, pp. 1351–1367, Oct 2006.
  * [5] M. Grassl, “Bounds on the minimum distance of linear codes and quantum codes,” Online available at http://www.codetables.de, 2007, accessed on 2020-11-27.
  * [6] M. Grassl and M. Harada, “New self-dual additive $\mathbb{F}_{4}$-codes constructed from circulant graphs,” _Discrete Math._ , vol. 340, no. 3, pp. 399–403, Mar 2017.
  * [7] T. A. Gulliver and J-L. Kim, “Circulant based extremal additive self-dual codes over $GF(4)$”, IEEE Trans. Inform. Theory, 50 (2004), 359–366.
  * [8] F. T. Leighton, “Circulants and the Characterization of Vertex-Transitive Graphs,” _Journal of Research of the National Bureau of Standards_ , vol. 88, no. 6, November-December 1983.
  * [9] E. A. Monakhova, “A survey on undirected circulant graphs,” _Discrete Math. Algorithms Appl._ , vol. 04, no. 01, p. 1250002, Mar 2012.
  * [10] K. Saito, “Self-dual additive $\mathbb{F}_{4}$-codes of lengths up to $40$ represented by circulant graphs,” _Adv. Math. Commun._ , vol. 13, no. 2, pp. 213–220, 2019.
  * [11] D. Schlingemann, “Stabilizer codes can be realized as graph codes”, Quantum Info. Comput., vol. 2 (2002), 307–-323.
  * [12] P. Seneviratne and M. F. Ezerman, “Improved quantum codes from metacirculant graphs via self-dual additive $\mathbb{F}_{4}$-codes”, in submission.
  * [13] P. W. Shor, “Scheme for reducing decoherence in quatum memory”, Phys. Rev. A. vol 52, (1995), 2493.
  * [14] Z. Varbanov, “Additive circulant graph codes over $GF(4)$”, _Math. Maced._ , vol. 6, (2008), pp.73–79.