#  A characterization of 4-connected graphs with no $K_{3,3}+v$-minor

Linsong Wei, Yuqi Xu, Weihua Yang***Corresponding author. E-mail:
<EMAIL_ADDRESS><EMAIL_ADDRESS>Yunxia Zhang

Department of Mathematics, Taiyuan University of Technology,
Taiyuan Shanxi-030024, China

Abstract: Among graphs with 13 edges, there are exactly three internally
4-connected graphs which are $Oct^{+}$, cube+e and $K_{3,3}+v$. A complete
characterization of all 4-connected graphs with no $Oct^{+}$-minor is given in
[John Maharry, An excluded minor theorem for the octahedron plus an edge,
Journal of Graph Theory 57(2) (2008) 124-130]. Let $K_{3,3}+v$ denote the
graph obtained by adding a new vertex $v$ to $K_{3,3}$ and joining $v$ to the
four vertices of a 4-cycle. In this paper, we determine all 4-connected graphs
that do not contain $K_{3,3}+v$ as a minor.

Keywords: forbidden minor, 4-connected graph, $K_{3,3}+v$

##  1 Introduction

All graphs in this paper are simple. Let $G$ and $H$ be two graphs. $H$ is
called a $minor$ of $G$ if it can be generated by deleting or contracting
edges from $G$. $G$ is called $H$-$minor$-$free$ if no minor of $G$ is
isomorphic to $H$. The Robertson-Seymour Graph Minors project has shown that
minor-closed classes of graphs can be described by finitely many forbidden
minors. We can get some graph classes which have many interesting properties
in the process of excluding small minors. In addition, many important problems
in graph theory are about the property of the $H$-minor-free graphs. For
instance, Tutte${}^{{}^{\prime}}$s 4-flow conjecture asserts that every
bridgeless Petersen-minor-free graph admits 4-fiow.

Ding [2] surveyed all $H$-minor-free graphs for 3-connected $H$ with at most
11 edges, including $Oct$$\backslash$$e$. For 3-connected graphs with 12
edges, Maharry [5] characterized 3-connected cube-minor-free graphs, Maharry
and Ding [1, 6] characterized 3-connected $Oct$-minor-free graphs, and Maharry
and Robertson [7] characterized the $V_{8}$-minor-free graphs. There are 51
3-connected graphs with 13 edges. Among the graphs with 13 edges, there are
exactly three internally 4-connected graphs. These three graphs are $Oct^{+}$,
cube+e and $K_{3,3}+v$. The $Oct^{+}$ is a 4-connected graph which is obtained
from the octahedron by adding an edge. Maharry characterized all 4-connected
$Oct^{+}$-minor-free graphs in [4]. The cube+e is obtained by adding a long
diagonal to the cube. In this paper, we characterize the 4-connected
$K_{3,3}+v$-minor-free graphs, where $K_{3,3}+v$ is obtained by adding a new
vertex $v$ to $K_{3,3}$ and joining $v$ to the four vertices of a 4-cycle in
this paper.

We use $G/e$ to denote the graph obtained from $G$ by first contracting $e$
and then deleting all but one edge from each parallel family and
$G$$\backslash$$e$ to denote the graph obained from $G$ by deleting the edge
$e$. For each integer $n\geq 3$, let $DW_{n}$ denote a double-wheel, which is
a graph on $n+2$ vertices obtained from a cycle $C_{n}$ by adding two adjacent
vertices and connecting them to all vertices on the cycle. Let
$\mathcal{DW}=\\{DW_{n}:n\geq 3\\}$. For each integer $n\geq 5$, let
$C_{n}^{2}$ be a graph obtained from a cycle $C_{n}$ by joining all pairs of
vertices of distance two on the cycle. Let
$\mathcal{C}_{0}=\\{C_{2n}^{2}:n\geq 3\\}$,
$\mathcal{C}_{1}=\\{C_{2n+1}^{2}:n\geq 2\\}$, and
$\mathcal{C}=\mathcal{C}_{0}\cup\mathcal{C}_{1}$. The graph $L(H)$ is called
the $line$ $graph$ of $G$ if $V(L(G))=E(G)$, and for any two vertices $e$, $f$
in $V(L(G))$, $e$ and $f$ are adjacent vertices if and not only if they are
adjacent edges in $G$.

######  Theorem 1.1.

A 4-connected graph $G$ is $K_{3,3}+v$-$minor$-$free$ if and only if either G
is planar or G belongs to $\mathcal{DW}$ $\cup$ $\mathcal{C}_{1}$ $\cup$
$\mathcal{M}$ $\cup$ $\\{$$L(K_{3,3})$, $K_{6}$, $K_{6}$$\backslash$$e$,
$DW_{4}$, $\Gamma_{1}$, $\Gamma_{2}$, $\Gamma_{3}$$\\}$, where
$\Gamma_{1}$,$\ldots$,$\Gamma_{3}$ are the three graphs shown below.

Figure 1:  $\Gamma_{1}$, $\Gamma_{2}$, $\Gamma_{3}$

##  2 Preliminaries

Let $v$ be a vertex of a 4-connected graph $G$. Let $N_{G}(v)$ denote the set
of vertices of $G$ that are adjacent to a vertex $v$. A $4$-$split$ of $v$
produces a new $G^{{}^{\prime}}$ as follows. Given two sets,
$A,B$$\subseteq$$N_{G}(v)$, where $A$ $\cup$ $B$=$N_{G}(v)$ and
min{$|A|,|B|$}$\geq$ 3, the graph $G^{{}^{\prime}}$ is obtained by replacing
the vertex $v$ in $G$ with vertices $a$ and $b$ such that
$N_{G^{{}^{\prime}}}(a)$=$A$ $\cup$ {$b$} and $N_{G^{{}^{\prime}}}(b)$=$B$
$\cup$ {$a$}. Note that the graph $G^{{}^{\prime}}$ is also 4-connected.

The following theorem of Martinov is a classical result to charactize all
4-connected graphs.

######  Theorem 2.1 ([9]).

Let G be a 4-connected graph. There exists a sequence of 4-connected graphs
$H_{0},\ldots,H_{t}$ $($t$\geq$$0)$ such that G is isomorphic to $H_{0}$ and
$H_{i}$ is obtained from $H_{i-1}$ by contracting some edges e $\in$ E
$($$H_{i-1}$$)$ and deleting any resulting parallel edges. Moreover, $H_{t}$
is either isomorphic to $C_{n}^{2}$ for some $n\geq 5$ or isomorphic to the
line graph of a cubic cyclically 4-connected graph.

This result has been strengthened by Qin and Ding as follows , which is an
important tool to characterize all 4-connected graphs without $K_{3,3}+v$ as a
minor.

######  Theorem 2.2 ([10]).

Let G be a 4-connected graph not in $\cal C\cup L$. If G is planar,then there
exists a $($G,$C_{6}^{2}$$)$-chain; if G is non-planar, then there exists a a
$($G,$K_{5}$$)$-chain.

We obtain a partial work in [8] for the characterization of 4-connected
$K_{3,3}+v$-minor-free graphs.

######  Theorem 2.3 ([8]).

A 4-connected graph $G$ is $K_{3,3}+v$-minor-free if and only if it is planar,
$C_{2k+1}^{2}$ $(k\geq 2)$, $L(K_{3,3})$ or it is obtained from $C_{5}^{2}$ by
repeatedly 4-splitting vertices.

######  Lemma 2.4 ([3]).

The only 4-split of $C_{5}^{2}$ are $K_{6}$, $K_{6}$$\backslash$$e$, $DW_{4}$.

Thus, we next characterize the $K_{3,3}+v$-minor-free graph obtained from
$K_{6}$, $K_{6}$$\backslash$$e$, $DW_{4}$ by repeatedly 4-splitting vertices.

##  3 Proof of Theorem 1.1

In this section, we proof the following results from which the Theorem 1.1
follows.

######  Lemma 3.1.

The graph obtained by adding an edge to $\Gamma_{1}$ contains $K_{3,3}+v$ as a
minor.

###### Proof.

By symmetry, we discuss three cases. The graph obtained by adding an edge
$av_{5}$, $av_{4}$ or $v_{1}v_{4}$ to $\Gamma_{1}$ contains $K_{3,3}+v$ as a
minor (see Figure 2). ∎

Figure 2: $\Gamma_{1}$ and $\Gamma_{1}+e$

######  Lemma 3.2.

The graph $\Gamma_{1}$ is the only $K_{3,3}+v$-minor-free graph obtained by
4-splitting a vertex of degree 5 in $DW_{4}$.

###### Proof.

Let {$v_{1},v_{2},\ldots,v_{6}$} be vertices of $DW_{4}$ (shown in Figure 3).
We first consider the minimal case for $|A|=|B|=3$, where $A,B$ are the
subsets of the $N_{G}(v_{6})$, $A\cup B$=$N_{G}(v_{6})$. Suppose that $a,b$
are the new vertices obtained by 4-splitting $v_{6}$. Since the degree of
$v_{6}$ is 5, we distinguish the discussion by the possibilities for $A$
$\cap$ {$v_{1},v_{5}$} and $B$ $\cap$ {$v_{1},v_{5}$}. The first case is that
one of $A$ $\cap$ {$v_{1},v_{5}$} and $B$ $\cap$ {$v_{1},v_{5}$} is
$\emptyset$. Without loss of generality, we assume that $B$ $\cap$
{$v_{1},v_{5}$} is $\emptyset$. The second case is that $A$ $\cap$
{$v_{1},v_{5}$} $\neq$ $\emptyset$ and $B$ $\cap$ {$v_{1},v_{5}$} $\neq$
$\emptyset$.

Figure 3: $DW_{4}$

Case 1. $A$ $\cap$ $\\{v_{1},v_{5}\\}$ $\neq$ $\emptyset$, $B$ $\cap$
$\\{v_{1},v_{5}\\}$ $=$ $\emptyset$.

In this case, $B$ has at least three vertices. Thus, $B$={$v_{2}$, $v_{3}$,
$v_{4}$} and the set $A$ may be {$v_{1},v_{5},v_{2}$}, {$v_{1},v_{5},v_{3}$}
or {$v_{1},v_{5},v_{4}$}. We list these three cases in Figure 4 respectively.
It is not difficult to see that the second graph is a $K_{3,3}+v$-minor-free
graph which is isomorphic to $\Gamma_{1}$ and the other two graphs both
contain $K_{3,3}+v$ as a minor.

Figure 4: Three graphs in Case 1

Case 2. $A$ $\cap$ $\\{v_{1},v_{5}\\}$ $\neq$ $\emptyset$, $B$ $\cap$
$\\{v_{1},v_{5}\\}$ $\neq$ $\emptyset$.

In this case, we assume that $v_{1}$ $\in$ $A$, $v_{5}$ $\in$ $B$ without loss
of generality. Since $|N_{G}(v_{6})|$ = 5, $A$ $\cap$ $B$ $\neq$ $\emptyset$
in the minimal case for $|A|=|B|=3$. By the symmertry of the graph
$G$$\backslash$$v_{6}$, we distinguish the following three cases.

Case 2.1. $A\cap B$ = {$v_{2}$}.

Since $v_{1}$$\in$$A$ and $v_{2}$$\in$$A$, one of $v_{3}$ and $v_{4}$ must
belong to $A$. If $v_{3}$ $\in$ $A$, then $v_{4}$ must belong to $B$ in the
minimal case. If $v_{4}$ $\in$ $A$, then $v_{3}$ must belong to $B$ in the
minimal case. It is easy to check that both the two resulting graphs contain
$K_{3,3}+v$ as a minor (see Figure 5).

Figure 5: Two graphs of Case 2.1

Case 2.2. $A\cap B$ = {$v_{5}$}.

Since $v_{1}$$\in$$A$, $v_{5}$$\in$$A$, one of $v_{2}$, $v_{3}$ and $v_{4}$
must belong to $A$. First, if $v_{2}$ $\in$ $A$, then $v_{3}$ and $v_{4}$ must
belong to $B$ in the minimal case. Second, if $v_{3}$ $\in$ $A$, then $v_{2}$
and $v_{4}$ must belong to $B$ in the minimal case. Third, if $v_{4}$ $\in$
$A$, then $v_{2}$ and $v_{3}$ must belong to $B$ in the minimal case. It is
straightforward to verify that all the three resulting graphs contain
$K_{3,3}+v$ as a minor (see Figure 6).

Figure 6: Three graphs of Case 2.2

Case 2.3. $A\cap B$ = {$v_{3}$}.

The process of discussing the sets of A and B is the same as the Case 2.1.
Hence we can obtain two graphs as shown in Figure 7. It is clear that the
first graph is $\Gamma_{1}$ which is a $K_{3,3}+v$-minor-free graph and the
second graph contains $K_{3,3}+v$ as a minor.

Figure 7: Two graphs of Case 2.3

Besides $\Gamma_{1}$, the new graph $G^{{}^{\prime}}$ obtained by 4-splitting
the vertex $v_{6}$ from $DW_{4}$ with $|A|$ = $|B|$ = 3 contains $K_{3,3}+v$
as a minor. The graph obtained in non-minimal cases is equivalent to add new
edges $av_{i}$ or $bv_{j}$ to the above ten graphs mentioned in Figure 4–7.
Then by Lemma 3.1 and the result of the above ten graphs, all the other new
graphs obtained by 4-splitting $v_{6}$ from $DW_{4}$ contain $K_{3,3}+v$ as a
minor.

∎

######  Lemma 3.3.

The graph obtained by 4-splitting a vertex of degree 4 in $\Gamma_{1}$
contains $K_{3,3}+v$ as a minor.

###### Proof.

There are six vertices of degree 4 in $\Gamma_{1}$. Up to symmetry, we
consider three cases. We first consider the minimal case for $|A|=|B|=3$,
where $A,B$ are the subsets of the $N_{G}(v)$, $A\cup B$=$N_{G}(v)$. Let
{$v_{1},v_{2},\ldots,v_{7}$} be vertices of $\Gamma_{1}$ (shown in Figure 8).

Case 1. Split the vertex $v_{1}$.

Since $|N_{G}(v_{1})|$ = 4, $A$ $\cap$ $\\{v_{2},v_{7}\\}$ $\neq$ $\emptyset$
and $B$ $\cap$ $\\{v_{2},v_{7}\\}$ $\neq$ $\emptyset$ in the minimal case for
$|A|=|B|=3$. Without loss of generality, we assume that $v_{2}$ $\in$ $A$,
$v_{7}$ $\in$ $B$. The set $A$ may be {$v_{2},v_{3},v_{4}$},
{$v_{2},v_{3},v_{7}$} or {$v_{2},v_{4},v_{7}$}. The set $B$ may be
{$v_{2},v_{3},v_{7}$}, {$v_{2},v_{4},v_{7}$} or {$v_{3},v_{4},v_{7}$}. On the
one hand, if the set $A$ is {$v_{2},v_{3},v_{4}$}, then the set $B$ may be
{$v_{2},v_{3},v_{7}$}, {$v_{2},v_{4},v_{7}$} or {$v_{3},v_{4},v_{7}$}. On the
other hand, if the set $A$ is {$v_{2},v_{3},v_{7}$}, then the set $B$ may be
{$v_{2},v_{4},v_{7}$} or {$v_{3},v_{4},v_{7}$}. At last if the set $A$ is
{$v_{2},v_{4},v_{7}$}, then the set $B$ may be {$v_{2},v_{3},v_{7}$} or
{$v_{3},v_{4},v_{7}$}. Hence we have seven graphs. It is evident that all the
seven resulting graphs contain $K_{3,3}+v$ as a minor (see Figure 8).

Figure 8: $\Gamma_{1}$ and seven graphs obtained by minimal 4-splitting
$v_{1}$

Case 2. Split the vertex $v_{2}$.

Since $|N_{G}(v_{2})|$ = 4, $A$ $\cap$ $\\{v_{1},v_{3}\\}$ $\neq$ $\emptyset$
and $B$ $\cap$ $\\{v_{1},v_{3}\\}$ $\neq$ $\emptyset$ in the minimal case for
$|A|=|B|=3$. Without loss of generality, we assume that $v_{3}$ $\in$ $A$,
$v_{1}$ $\in$ $B$. The set $A$ may be {$v_{1},v_{3},v_{4}$},
{$v_{1},v_{3},v_{6}$} or {$v_{3},v_{4},v_{6}$}. The set $B$ may be
{$v_{1},v_{3},v_{4}$}, {$v_{1},v_{3},v_{6}$} or {$v_{1},v_{4},v_{6}$}.
Similarly to the previous case, we have seven graphs. It is easy to check that
all the seven resulting graphs contain $K_{3,3}+v$ as a minor (see Figure 9).

Figure 9: $\Gamma_{1}$ and seven graphs obtained by minimal 4-splitting
$v_{2}$

Case 3. Split the vertex $v_{3}$.

Since $|N_{G}(v_{3})|$ = 4, $A$ $\cap$ $\\{v_{2},v_{4}\\}$ $\neq$ $\emptyset$
and $B$ $\cap$ $\\{v_{2},v_{4}\\}$ $\neq$ $\emptyset$ in the minimal case for
$|A|=|B|=3$. Without loss of generality, we assume that $v_{4}$ $\in$ $A$,
$v_{2}$ $\in$ $B$. The set $A$ may be {$v_{1},v_{4},v_{5}$},
{$v_{2},v_{4},v_{5}$} or {$v_{1},v_{2},v_{4}$}. The set $B$ may be
{$v_{2},v_{4},v_{5}$}, {$v_{1},v_{2},v_{4}$} or {$v_{1},v_{2},v_{5}$}. By an
argument similar to that of Case 1, we have seven graphs. It is clear that all
the seven resulting graphs contain $K_{3,3}+v$ as a minor (see Figure 10).

Figure 10: $\Gamma_{1}$ and seven graphs obtained by minimal 4-splitting
$v_{3}$

The graph obtained in non-minimal cases is equivalent to add new edges
$av_{i}$ or $bv_{j}$ to the above graphs mentioned in Figures 8–10. Hence, the
graph obtained by 4-splitting a vertex of degree 4 in $\Gamma_{1}$ contains
$K_{3,3}+v$ as a minor.

∎

######  Lemma 3.4.

The graph obtained by adding a new edge to $\Gamma_{3}$ contains $K_{3,3}+v$
as a minor.

###### Proof.

As shown in Figure 11, it can be seen that $\Gamma_{2}+av_{3}$,
$\Gamma_{2}+av_{2}$, $\Gamma_{2}+v_{5}v_{1}$ and $\Gamma_{2}+v_{5}v_{2}$
contain $K_{3,3}+v$ as a minor, and $\Gamma_{2}+av_{1}$ is $\Gamma_{3}$ which
is a $K_{3,3}+v$-minor-free graph. Similarly, $\Gamma_{3}+bv_{7}$ contains
$K_{3,3}+v$ as a minor (see Figure 12). Thus, the graph obtained by adding a
new edge to $\Gamma_{3}$ has a $K_{3,3}+v$ minor.

Figure 11: $\Gamma_{2}+av_{2}$, $\Gamma_{2}+av_{3}$, $\Gamma_{2}+v_{5}v_{1}$,
$\Gamma_{2}+v_{5}v_{2}$, $\Gamma_{3}$ Figure 12: $\Gamma_{3}+bv_{7}$

∎

######  Lemma 3.5.

The graph obtained by 4-splitting a vertex of degree 6 in $\Gamma_{1}$
contains $K_{3,3}+v$ as a minor besides $\Gamma_{2}$ and $\Gamma_{3}$, .

###### Proof.

Let {$v_{1},v_{2},\ldots,v_{7}$} be vertices of $\Gamma_{1}$ (shown in Figure
13). We first consider the minimal case for $A$ and $B$, where $A,B$ are the
subsets of the $N_{G}(v_{4})$, $A\cup B$=$N_{G}(v_{4})$. Suppose that $a,b$
are the new vertices obtained by 4-splitting the vertex $v_{4}$. The degree of
$v_{4}$ is 6, thus there are three cases for $A$ and $B$. The first case is
that one of $A$ $\cap$ {$v_{3},v_{5}$} and $B$ $\cap$ {$v_{3},v_{5}$} is
$\emptyset$. Without loss of generality, we assume that $B$ $\cap$
{$v_{3},v_{5}$} is $\emptyset$. The second case is that $A$ $\cap$
{$v_{3},v_{5}$} $\neq$ $\emptyset$, $B$ $\cap$ {$v_{3},v_{5}$} $\neq$
$\emptyset$ and $A$ $\cap$ $B$ $=$ $\emptyset$. The third case is that $A$
$\cap$ {$v_{3},v_{5}$} $\neq$ $\emptyset$, $B$ $\cap$ {$v_{3},v_{5}$} $\neq$
$\emptyset$ and $A$ $\cap$ $B$ $\neq$ $\emptyset$.

Case 1. $B$ $\cap$ {$v_{3},v_{5}$} = $\emptyset$.

We consider the minimal case for $|A|=|B|=3$ and $B$ $\cap$ {$v_{3},v_{5}$} =
$\emptyset$. If the set $A$ is {$v_{3},v_{5},v_{1}$}, then the set $B$ is
{$v_{2},v_{6},v_{7}$} in the minimal case. Similarly if the set $A$ is
{$v_{3},v_{5},v_{2}$}, {$v_{3},v_{5},v_{6}$} or {$v_{3},v_{5},v_{7}$}, then
the set $B$ is {$v_{1},v_{6},v_{7}$}, {$v_{2},v_{1},v_{7}$} or
{$v_{2},v_{6},v_{1}$} respectively. All the four resulting graphs contain
$K_{3,3}+v$ as a minor (see Figure 13).

Figure 13: $\Gamma_{1}$ and four graphs of Case 1

Case 2. $A$ $\cap$ {$v_{3},v_{5}$} $\neq$ $\emptyset$, $B$ $\cap$
{$v_{3},v_{5}$} $\neq$ $\emptyset$ and $A$ $\cap$ $B$ $=$ $\emptyset$

We consider the minimal case for $|A|=|B|=3$ and assume that $v_{5}$$\in$$A$,
$v_{3}$$\in$$B$ without loss of generality. If the set $A$ is
{$v_{1},v_{2},v_{5}$}, then the set $B$ is {$v_{3},v_{6},v_{7}$} in the
minimal case. Similarly if the set $A$ is {$v_{1},v_{5},v_{6}$},
{$v_{1},v_{5},v_{7}$}, {$v_{2},v_{5},v_{6}$}, {$v_{2},v_{5},v_{7}$} or
{$v_{5},v_{6},v_{7}$}, then the set $B$ is {$v_{2},v_{3},v_{7}$},
{$v_{2},v_{3},v_{6}$}, {$v_{3},v_{1},v_{7}$}, {$v_{3},v_{1},v_{6}$} or
{$v_{1},v_{2},v_{3}$} respectively. It is easy to check that all the resulting
graphs contain $K_{3,3}+v$ as a minor besides the sixth graph $\Gamma_{2}$
(see Figure 14).

Figure 14: Six graphs of Case 2

Case 3. $A$ $\cap$ {$v_{3},v_{5}$} $\neq$ $\emptyset$, $B$ $\cap$
{$v_{3},v_{5}$} $\neq$ $\emptyset$ and $A$ $\cap$ $B$ $\neq$ $\emptyset$.

Case 3.1. $A$ $\cap$ $B$ $=$ $\\{v_{1}\\}$

Since $|N_{G}(v_{4})|$=6 and $A$ $\cap$ $B$ $=$ $\\{v_{1}\\}$, the set $A$ or
set $B$ contains 4 vertices in the minimal case. The graph generated in Case
3.1 is equivalent to add a new edge $av_{1}$ or $bv_{1}$ to the above graphs
mentioned in Case 2. Thus, the graphs in Case 3.1 contain $K_{3,3}+v$ as a
minor besides $\Gamma_{3}$. The cases of $A$ $\cap$ $B$ $=$ $\\{v_{2}\\}$, $A$
$\cap$ $B$ $=$ $\\{v_{6}\\}$ and $A$ $\cap$ $B$ $=$ $\\{v_{7}\\}$ are similar
to the above.

Case 3.2. $A$ $\cap$ $B$ $=$ $\\{v_{3}\\}$

Since $|N_{G}(v_{4})|$=6 and $A$ $\cap$ $B$ $=$ $\\{v_{3}\\}$, the set $A$ or
set $B$ contains 4 vertices in the minimal case. The graph generated in Case
3.2 is equivalent to add a new edge $av_{3}$ or $bv_{3}$ to the above graphs
mentioned in Case 1 and Case 2. Thus, the graphs in Case 3.2 all contain
$K_{3,3}+v$ as a minor according to the Lemma 3.4 and the results of the Case
1 and Case 2. The case of $A$ $\cap$ $B$ $=$ $\\{v_{5}\\}$ is similar to the
above.

In the other cases that are not minimal, it is equivalent to add new edges
$av_{i}$ or $bv_{j}$ to the above graphs mentioned in Figure 13 and 14.
According to Lemma 3.4 and above results, the $K_{3,3}+v$-minor-free graphs
are $\Gamma_{2}$ and $\Gamma_{3}$ by 4-splitting a vertex of degree 6 in
$\Gamma_{1}$.

∎

######  Lemma 3.6.

Every 4-split of $\Gamma_{2}$ contains a $K_{3,3}+v$-$minor$.

###### Proof.

We consider the minimal case for $|A|=|B|=3$, where $A,B$ are the subsets of
the $N_{G}(v)$, $A\cup B$=$N_{G}(v)$. Let
{$a,b,v_{1},v_{2},v_{3},v_{5},v_{6},v_{7}$} be vertices of $\Gamma_{2}$ (shown
in Figure 15). By symmetry, we split the vertex $a$ and the vertex $v_{5}$.
Note that $d(a)=4$ and $d(v_{5})=4$. Thus the process of 4-splitting the
vertex $a$ or $v_{5}$ is similar to that of Lemma 3.3.

Case 1. Split the vertex $a$.

$A\cap\\{b,v_{5}\\}$ $\neq$ $\emptyset$, $B\cap\\{b,v_{5}\\}$ $\neq$
$\emptyset$ in the minimal case for $|A|=|B|=3$. Without loss of generality,
we assume that $v_{5}$ $\in$ $A$, $b$ $\in$ $B$. We have seven graphs and it
is clear that all the seven resulting graphs contain $K_{3,3}+v$ as a minor
(see Figure 15).

Figure 15: $\Gamma_{2}$ and seven graphs of Case 1

Case 2. Split the vertex $v_{5}$.

$A\cap\\{a,v_{6}\\}$ $\neq$ $\emptyset$, $B\cap\\{a,v_{6}\\}$ $\neq$
$\emptyset$ in the minimal case for $|A|=|B|=3$. Without loss of generality,
we assume that $v_{6}$ $\in$ $A$, $a$ $\in$ $B$. We obtain seven graphs which
contain $K_{3,3}+v$ as a minor (see Figure 16).

Figure 16: $\Gamma_{2}$ and seven graphs of Case 2

In all minimal cases, the new graph $G^{{}^{\prime}}$ generated by 4-splitting
vertice from $\Gamma_{2}$ with $|A|=|B|=3$ contains $K_{3,3}+v$. Clearly, all
the other graphs obtained by 4-splitting a vertex of degree 4 in $\Gamma_{2}$
contain $K_{3,3}+v$ as a minor.

∎

######  Lemma 3.7.

Every 4-split of $\Gamma_{3}$ contains a $K_{3,3}+v$-$minor$.

###### Proof.

We consider the minimal case for $|A|=|B|=3$, where $A,B$ are the subsets of
the $N_{G}(v)$, $A\cup B$=$N_{G}(v)$. Let
{$a,b,v_{1},v_{2},v_{3},v_{5},v_{6},v_{7}$} be vertices of $\Gamma_{3}$ (shown
in Figure 17). It appears obvious that the graph obtained by splitting a
vertex of degree 4 in $\Gamma_{3}$ is equivalent to adding a new edge to the
one of fourteen graphs mentioned in the Lemma 3.6. Hence we only consider the
4-splits of the vertex of degree 5 in $\Gamma_{3}$. Up to symmetry, we
consider the 4-spilt of the vertex $a$. The process of 4-spiltting the vertex
$a$ is similar to that of Lemma 3.2.

Case 1. $B$ $\cap$ {$b,v_{5}$} = $\emptyset$, {$b,v_{5}$} $\subset$ $A$.

Note that $B$={$v_{1}$, $v_{6}$, $v_{7}$}. The set $A$ may be
{$v_{5},v_{6},b$}, {$v_{1},v_{5},b$} or {$v_{5},v_{7},b$} in the minimal case.
All the resulting graphs contain $K_{3,3}+v$ as a minor (see Figure 17).

Figure 17:  $\Gamma_{3}$ and three graphs of Case 1

Case 2. $A$ $\cap$ $\\{b,v_{5}\\}$ $\neq$ $\emptyset$, $B$ $\cap$
$\\{b,v_{5}\\}$ $\neq$ $\emptyset$.

In this case, we assume that $v_{5}$ $\in$ $A$, $b$ $\in$ $B$ without loss of
generality. Since $|N_{G}(a)|$ = 5, $A$ $\cap$ $B$ $\neq$ $\emptyset$ in the
minimal case for $|A|=|B|=3$.

Case 2.1. $A$ $\cap$ $B$ = {$v_{1}$}

Since $v_{1}$$\in$$A$ and $v_{5}$$\in$$A$, one of $v_{6}$ and $v_{7}$ must
belong to $A$. If $v_{6}$ $\in$ $A$, then $v_{7}$ must belong to $B$ in the
minimal case. If $v_{7}$ $\in$ $A$, then $v_{6}$ must belong to $B$ in the
minimal case. We obtain two graphs which contain $K_{3,3}+v$ as a minor (see
Figure 18).

Figure 18: Two graphs in Case 2.1

Case 2.2. $A$ $\cap$ $B$ = {$v_{6}$}

Similarly to the Case 2.1, we have two graphs. It is not difficult to see that
both the two resulting graphs contain $K_{3,3}+v$ as a minor (see Figure 19).

Figure 19: Two graphs in Case 2.2

Case 2.3. $A$ $\cap$ $B$ = {$v_{7}$}

By an argument similar to that of Case 2.1, we get two graphs and verify that
both the two resulting graphs contain $K_{3,3}+v$ as a minor (see Figure 20).

Figure 20: Two graphs in Case 2.3

Case 2.4. $A$ $\cap$ $B$ = {$v_{5}$}

Since $v_{5}$$\in$$B$, $b$$\in$$B$, one of $v_{1}$, $v_{6}$ and $v_{7}$ must
belong to $B$. First, if $v_{1}$ $\in$ $B$, then $v_{6}$ and $v_{7}$ must
belong to $A$ in the minimal case. Second, if $v_{6}$ $\in$ $B$, then $v_{1}$
and $v_{7}$ must belong to $A$ in the minimal case. Third, if $v_{7}$ $\in$
$B$, then $v_{1}$ and $v_{6}$ must belong to $A$ in the minimal case. It is
easy to check that all the three resulting graphs contain $K_{3,3}+v$ as a
minor (see Figure 21).

Figure 21: Three graphs in Case 2.4

Case 2.5. $A$ $\cap$ $B$ = {$b$}

Similarly to Case 2.4. We obtain three graphs which contain $K_{3,3}+v$ as a
minor as follows (see Figure 22).

Figure 22: Three graphs in Case 2.5

In all minimal cases, the new graph $G^{{}^{\prime}}$ generated by splitting
the vertices of $\Gamma_{3}$ contains $K_{3,3}+v$. Hence all the other graphs
obtained by 4-splitting the vertices of $\Gamma_{3}$ contain $K_{3,3}+v$ as a
minor.

∎

######  Lemma 3.8.

The graph obtained by adding an edge to $DW_{5}$ contains $K_{3,3}+v$.

###### Proof.

By symmetry, we only need to consider adding $av_{5}$, $bv_{2}$ or
$v_{2}v_{5}$. We denote the resulting graphs by $DW_{5}^{1}$, $DW_{5}^{2}$ and
$DW_{5}^{3}$ as shown in Figure 23. It is straightforward to verify that
$DW_{5}^{1}$, $DW_{5}^{2}$ and $DW_{5}^{3}$ all contain $K_{3,3}+v$ as a
minor.

Figure 23: $DW_{5}$, $DW_{5}^{1}$, $DW_{5}^{2}$, $DW_{5}^{3}$

∎

######  Lemma 3.9.

The only $K_{3,3}+v$-$minor$-$free$ graph is $DW_{5}$ by 4-splitting a vertex
of degree 4 in $DW_{4}$.

###### Proof.

Let {$v_{1},v_{2},\ldots,v_{6}$} be vertices of $DW_{4}$ (shown in Figure 3).
By symmetry, we consider the 4-split of the vertex $v_{1}$. Note that
$d(v_{1})=4$. Similarly to the Lemma 3.3, we obtain seven graphs which contain
$K_{3,3}+v$ as a minor with the exception of $DW_{4}$ (see in Figure 24).

Figure 24: Seven graphs obtained by splitting the vertex $v_{1}$ in $DW_{4}$.

The graph obtained in non-minimal cases is equivalent to add edges $av_{i}$ or
$bv_{j}$ to the above graphs mentioned in Figure 24. Hence by Lemma 3.8, all
the other new graphs obtained by 4-splitting the vertex $v_{1}$ in $DW_{4}$
contain $K_{3,3}+v$ as a minor.

∎

######  Lemma 3.10.

The graph obtained by adding an edge to $DW_{n}$ $($$n$ $\geq$ 6$)$ contains
$K_{3,3}+v$.

###### Proof.

Let {$v_{1},v_{2},\ldots,v_{n}$} be vertices of $DW_{n}$ (shown in Figure 25).
There are two cases for the edge $v_{i}v_{j}$.

Case 1. $v_{i}$ = $v_{1}$.

Case 1.1. $j$ = 3.

The new graph $G^{{}^{\prime}}$ generated by adding $v_{1}v_{3}$ to $DW_{n}$
contains $DW_{5}^{1}$ as a minor (see $DW_{n}^{1}$ in Figure 25).

Case 1.2. 4 $\leq$ $j$ $\leq$ $n-3$ .

The new graph $G^{{}^{\prime}}$ generated by adding $v_{1}v_{j}$ to $DW_{n}$
contains $DW_{5}^{3}$ as a minor (see $DW_{n}^{2}$ in Figure 25).

By symmetry, the case of $v_{i}v_{n-2}$ (2 $\leq$ $i$ $\leq$ $n-4$) is similar
to the above.

Case 2. $v_{i}$ $\neq$ $v_{1}$ and $v_{j}$ $\neq$ $v_{n-2}$.

The new graph $G^{{}^{\prime}}$ generated by adding $v_{i}v_{j}$ to $DW_{n}$
contains $DW_{5}^{2}$ as a minor (see $DW_{n}^{3}$ in Figure 25).

Thus, the graph obtained by adding an edge to $DW_{n}$ ($n$ $\geq$ 6) contains
$K_{3,3}+v$ as a minor.

Figure 25: $DW_{n}$, $DW_{n}^{1}$, $DW_{n}^{2}$, $DW_{n}^{3}$

∎

######  Lemma 3.11.

Every 4-split of a vertex of degree 6 in $DW_{5}$ contains a
$K_{3,3}+v$-$minor$.

###### Proof.

Let {$v_{1},v_{2},\ldots,v_{7}$} be vertices of $DW_{5}$ (shown in Figure 26).
By symmetry, we split the vertex $v_{6}$. We first consider the minimal case
for $A$ and $B$, where $A$, $B$ are the subsets of the $N_{G}(v_{6})$, $A\cup
B$=$N_{G}(v_{6})$. Suppose that $a,b$ are the new vertices obtained by
4-splitting the vertex $v_{6}$. Since $|N_{G}(v_{6})|$ = 6, the process of
4-splitting the vertex $v_{6}$ is similar to that of Lemma 3.5. Hence we have
three cases for $A$ and $B$. The first case is that one of $A$ $\cap$
{$v_{5},v_{7}$} and $B$ $\cap$ {$v_{5},v_{7}$} is $\emptyset$. Without loss of
generality, we assume that $B$ $\cap$ {$v_{5},v_{7}$} is $\emptyset$. The
second case is that $A$ $\cap$ {$v_{5},v_{7}$} $\neq$ $\emptyset$, $B$ $\cap$
{$v_{5},v_{7}$} $\neq$ $\emptyset$ and $A$ $\cap$ $B$ $=$ $\emptyset$. The
third case is that $A$ $\cap$ {$v_{5},v_{7}$} $\neq$ $\emptyset$, $B$ $\cap$
{$v_{5},v_{7}$} $\neq$ $\emptyset$ and $A$ $\cap$ $B$ $\neq$ $\emptyset$.

Case 1. $B$ $\cap$ {$v_{5},v_{7}$} = $\emptyset$.

Similarly to the Case 1 in Lemma 3.5, we have four graphs. It is not difficult
to see that all the four resulting graphs contain $K_{3,3}+v$ as a minor (see
Figure 26).

Figure 26: $DW_{5}$ and four graphs in Case 1

Case 2. $A$ $\cap$ {$v_{5},v_{7}$} $\neq$ $\emptyset$, $B$ $\cap$
{$v_{5},v_{7}$} $\neq$ $\emptyset$ and $A$ $\cap$ $B$ $=$ $\emptyset$

We consider the minimal case for $|A|=|B|=3$ and assume that $v_{5}$$\in$$A$,
$v_{7}$$\in$$B$ without loss of generality. By an argument argument similar to
that of Case 2 in Lemma 3.5, we have six graphs. It is easy to check that all
the resulting graphs contain $K_{3,3}+v$ as a minor (see Figure 27).

Figure 27: Six graphs of Case 2

Case 3. $A$ $\cap$ {$v_{5},v_{7}$} $\neq$ $\emptyset$, $B$ $\cap$
{$v_{5},v_{7}$} $\neq$ $\emptyset$ and $A$ $\cap$ $B$ $\neq$ $\emptyset$.

We consider the minimal case for $A$ and $B$. We assume that $v_{5}$$\in$$A$,
$v_{7}$$\in$$B$ without loss of generality.

Case 3.1. $A$ $\cap$ $B$ $=$ $\\{v_{1}\\}$

Since $|N_{G}(v_{6})|$=6 and $A$ $\cap$ $B$ $=$ $\\{v_{1}\\}$, the set $A$ or
set $B$ contains 4 vertices in the minimal case. The graph generated in this
case is equivalent to add the edge $av_{1}$ or $bv_{1}$ to the above graphs
mentioned in Case 2. Thus, the graphs all contain $K_{3,3}+v$ as a minor. The
cases of $A$ $\cap$ $B$ $=$ $\\{v_{2}\\}$, $A$ $\cap$ $B$ $=$ $\\{v_{3}\\}$
and $A$ $\cap$ $B$ $=$ $\\{v_{4}\\}$ are similar to the above.

Case 3.2. $A$ $\cap$ $B$ $=$ $\\{v_{5}\\}$

Note that $d(v_{6})=6$ and $A$ $\cap$ $B$ $=$ $\\{v_{5}\\}$. One of the set
$A$ and set $B$ contains 4 vertices in the minimal case. The graph generated
in this case is equivalent to add the edge $av_{5}$ or $bv_{5}$ to the above
graphs mentioned in Case 1 or Case 2. Thus, the graphs all contain $K_{3,3}+v$
as a minor. The case of $A$ $\cap$ $B$ $=$ $\\{v_{7}\\}$ is similar to the
above.

In all minimal cases, the new graph $G^{{}^{\prime}}$ generated by 4-splitting
a vertex of degree 6 in $DW_{5}$ contains $K_{3,3}+v$. Hence all the other
graphs obtained by 4-spliting a vertex of degree 6 in $DW_{5}$ contain
$K_{3,3}+v$ as a minor.

∎

Let $\cal F$ ={ $F$ : $F$ is obtained by 4-spiliting a vertex of degree 6 in
$DW_{5}$ }.

######  Lemma 3.12.

The graph obtained by splitting the vertex of degree $n-1$ in $DW_{n}$ $($$n$
$\geq$ 6$)$ contains a $K_{3,3}+v$-$minor$.

###### Proof.

Let {$v_{1},v_{2},\ldots,v_{n}$} be vertices of $DW_{n}$ (shown in Figure28).
By symmetry, we consider the 4-splitting of the vertex $v_{n}$. By contrasting
the structure of $DW_{5}$$\backslash$$v_{7}$ and $DW_{n}$$\backslash$$v_{n}$
(see Figure 28), we conclude that the new graph $G^{{}^{\prime}}$ generated by
4-splitting the vertex of degree $n-1$ in $DW_{n}$ contains a graph $F$ as a
minor. Thus, $G^{{}^{\prime}}$ must contain $K_{3,3}+v$ as a minor.

Figure 28: $DW_{5}$, $DW_{5}$$\backslash$$v_{7}$, $DW_{n}$,
$DW_{n}$$\backslash$$v_{n}$

∎

######  Lemma 3.13.

The graph obtained by 4-splitting the vertex of degree 4 in $DW_{5}$ contains
a $K_{3,3}+v$-$minor$ with the exception of $DW_{6}$.

###### Proof.

We consider the minimal case for $|A|=|B|=3$, where $A,B$ are the subsets of
the $N_{G}(v)$, $A\cup B$=$N_{G}(v)$. Let {$v_{1},v_{2},\ldots,v_{7}$} be
vertices of $DW_{5}$ (shown in Figure 29). By symmetry, we split the vertices
of $v_{4}$, $v_{3}$ and $v_{1}$ respectively. Note that $d(v_{1})=4$,
$d(v_{3})=4$ and $d(v_{4})=4$. Thus the process of 4-splitting the vertex
$v_{1}$, $v_{3}$ or $v_{4}$ is similar to that of Lemma 3.3.

Case 1. Split the vertex $v_{4}$.

$A$ $\cap$ $\\{v_{3},v_{5}\\}$ $\neq$ $\emptyset$ and $B$ $\cap$
$\\{v_{3},v_{5}\\}$ $\neq$ $\emptyset$ in the minimal case for $|A|=|B|=3$.
Without loss of generality, we assume that $v_{5}$ $\in$ $A$, $v_{3}$ $\in$
$B$. We get seven graphs which contain $K_{3,3}+v$ as a minor (see Figure 29).

Figure 29: $DW_{5}$ and seven graphs in Case 1

Case 2. Split the vertex $v_{3}$.

$A$ $\cap$ $\\{v_{1},v_{4}\\}$ $\neq$ $\emptyset$ and $B$ $\cap$
$\\{v_{1},v_{4}\\}$ $\neq$ $\emptyset$ in the minimal case for $|A|=|B|=3$.
Without loss of generality, we assume that $v_{4}$ $\in$ $A$, $v_{1}$ $\in$
$B$ by symmetry. It is clear that all the seven resulting graphs contain
$K_{3,3}+v$ as a minor (see Figure 30).

Figure 30: $DW_{5}$ and seven graphs in Case 2

Case 3. Split the vertex $v_{1}$.

$A$ $\cap$ $\\{v_{2},v_{3}\\}$ $\neq$ $\emptyset$ and $B$ $\cap$
$\\{v_{2},v_{3}\\}$ $\neq$ $\emptyset$ in the minimal case for $|A|=|B|=3$. It
is not difficult to see that all the seven resulting graphs contain
$K_{3,3}+v$ as a minor (see Figure 31).

Figure 31: $DW_{5}$ and seven graphs in Case 3

In all minimal cases, the new graph $G^{{}^{\prime}}$ generated by 4-splitting
the vertices of degree 4 in $DW_{5}$ with $|A|=|B|=3$ besides $DW_{6}$
contains $K_{3,3}+v$. In the other non-minimal cases, it is equivalent to add
new edges $av_{i}$ or $bv_{j}$ to the above graphs mentioned in Figure 29–31.
According to Lemma 3.10 and above results, the graph obtained by 4-splitting
the vertex of degree 4 in $DW_{5}$ contains $K_{3,3}+v$ as a minor besides
$DW_{6}$.

∎

######  Lemma 3.14.

The graph obtained by 4-splitting the vertex of degree 4 in $DW_{n}$ contains
a $K_{3,3}+v$-$minor$ $($$n$$\geq$$6$$)$ besides $DW_{n+1}$.

###### Proof.

It is straightforward to verify that 4-splitting a vertex of degree 4 in
$DW_{n}$ can be considered as 4-spliting a vertex of degree 4 in $DW_{5}$.
Hence the new graph $G^{{}^{\prime}}$ generated by 4-splitting the vertice of
degree 4 in $DW_{n}$ in the minimal case contains $K_{3,3}+v$ as a minor with
the exception of $DW_{n+1}$. Since the graph obtained in the non-minimal cases
is equivalent to adding edges to the above graphs, it contains $K_{3,3}+v$ as
a minor. Thus every graph obtained by 4-splitting the vertex of degree 4 in
$DW_{n}$ contains $K_{3,3}+v$ as a minor besides $DW_{n+1}$. ∎

######  Lemma 3.15.

Every 4-split of $K_{6}$$\backslash$$e$ contains a $K_{3,3}+v$-$minor$.

###### Proof.

According to the Lemma 3.1 and Lemma 3.8, the graph obtained by adding an edge
to $\Gamma_{1}$ or $M_{7}$ contains $K_{3,3}+v$ as a minor.
$K_{6}$$\backslash$$e$ is a graph by adding an edge to the $DW_{4}$. The new
graph $G^{{}^{\prime}}$ generated by 4-splitting vertices of
$K_{6}$$\backslash$$e$ can be regarded as a graph by adding an edge to the
graph generated by 4-splitting vertices of $DW_{4}$. Thus, every 4-split of
$K_{6}$$\backslash$$e$ contains $K_{3,3}+v$ as a minor. ∎

######  Lemma 3.16.

Every 4-split of $K_{6}$ contains a $K_{3,3}+v$-$minor$.

###### Proof.

According to the Lemma 3.1 and Lemma 3.8, the graph obtained by adding an edge
to $\Gamma_{1}$ or $M_{7}$ contains $K_{3,3}+v$ as a minor. $K_{6}$ is a graph
by adding two edges to the $DW_{4}$. The new graph $G^{{}^{\prime}}$ generated
by 4-splitting vertices of $K_{6}$ can be regarded as a graph by adding two
edges to the graph generated by 4-splitting vertices of $DW_{4}$. Thus, every
4-split of $K_{6}$ contains $K_{3,3}+v$ as a minor. ∎

Proof of Theorem 1.1. The result follows from Lemmas 3.1—3.16. ∎

## References

  * [1] G. Ding, A characterization of graphs with no octahedron minor, J. Graph Theory. 74 (2013), no. 2, 143-162.
  * [2] G. Ding and C. Liu, Excluding a small minor, Discret. Appl. Math. 161 (2013), no. 3, 355-368.
  * [3] G. Ding, C. Lewchalermvongs and J. Maharry, Graphs with no $\bar{P}_{7}$-Minor, Electron. J. comb. 23 (2016), no. 2, P2.12.
  * [4] J. Maharry, An excluded minor theorem for the octahedron plus an edge, J. Graph Theory. 57 (2008), no. 2, 124-130.
  * [5] J. Maharry, A characterization of graphs with no cube minor, J. Combin. Theory Ser. B. 80 (2000), no. 2, 179-201.
  * [6] J. Maharry, An excluded minor theorem for the octahedron, J. Graph Theory. 31 (1999), no. 2, 95-100.
  * [7] J. Maharry and N. Robertson, The structure of graphs not topologically containing the Wagner graph, J. Combin. Theory Ser. B. 121 (2016), 398-420.
  * [8] W. Jia, S. Kou, C. Qin, and W. Yang, A Note on $Oct_{1}^{+}$-minor-free graphs and $Oct_{2}^{+}$-minor-free graphs, J. Interconnect. Netw. 22 (2022), no. 4, 2150030. https://doi.org/10.1142/S0219265921500304
  * [9] N. Martinov, Uncontractable 4-connected graphs, J. Graph Theory. 6 (1982), no. 3, 343-344.
  * [10] C. Qin and G. Ding, A chain theorem for 4-connected graphs, J. Combin. Theory Ser. B. 134 (2019), 341-349.


# Bridging Classical and Quantum: Group-Theoretic Approach to Quantum Circuit
Simulation

Daksh Shami1∗

###### Abstract

Efficiently simulating quantum circuits on classical computers is a
fundamental challenge in quantum computing. This paper presents a novel
theoretical approach that achieves exponential speedups (polynomial runtime)
over existing simulators for a wide class of quantum circuits. The technique
leverages advanced group theory and symmetry considerations to map quantum
circuits to equivalent forms amenable to efficient classical simulation.
Several fundamental theorems are proven that establish the mathematical
foundations of this approach, including a generalized Gottesman-Knill theorem.
The potential of this method is demonstrated through theoretical analysis and
preliminary benchmarks. This work contributes to the understanding of the
boundary between classical and quantum computation, provides new tools for
quantum circuit analysis and optimization, and opens up avenues for further
research at the intersection of group theory and quantum computation. The
findings may have implications for quantum algorithm design, error correction,
and the development of more efficient quantum simulators.

1Independent Researcher

∗Corresponding author<EMAIL_ADDRESS>
##  1 Introduction

Quantum computing promises to solve certain problems exponentially faster than
classical computers[10]. However, the development and analysis of quantum
algorithms is hampered by the difficulty of efficiently simulating quantum
circuits on classical machines. While significant progress has been made in
quantum circuit simulation[11, 2], the exponential overhead of simulating
large quantum systems remains a major challenge. In this paper, I present a
novel approach to classically simulating quantum circuits that achieves
exponential speedups over existing techniques for a broad class of circuits.
The key insight here is to use advanced group theory and symmetry
considerations to map quantum circuits to equivalent forms that are amenable
to efficient classical simulation via a generalized version of the Gottesman-
Knill theorem. My approach to analyzing and optimizing quantum circuits
through character function decomposition is being implemented in Quantum
Forge, a compiler currently under development. The key steps in the
methodology are:

  1. 1.

Represent quantum circuits as elements of a finite group under matrix
multiplication.

  2. 2.

Identify the irreducible representations and character functions of this
group.

  3. 3.

Decompose the quantum circuit into a sum of character functions using the
decomposition theorem.

  4. 4.

Analyze the resulting decomposition to identify optimization opportunities and
potential for efficient classical simulation.

  5. 5.

Apply optimizations based on the character function decomposition.

Quantum Forge implements these steps using the MLIR (Multi-Level Intermediate
Representation) compiler framework[8], allowing for modular and extensible
optimization passes.

##  2 Theoretical Foundations

Let us begin by proving several fundamental theorems that form the
mathematical basis for the character decomposition approach.

######  Theorem 1 (Character Function Decomposition).

Let $G$ be a finite group and $\mathbb{C}[G]$ be its complex group algebra.
For any element $u\in G$, it can be decomposed into a sum of character
functions as follows:

$u=\sum_{i=1}^{k}\frac{\chi_{i}(u)}{d_{i}}\sum_{g\in
G}\chi_{i}(g^{-1})\rho_{i}(g)$ (1)

where $k$ is the number of irreducible representations of $G$, $\chi_{i}$ is
the character of the $i$-th irreducible representation $\rho_{i}$, and $d_{i}$
is the dimension of $\rho_{i}$.

###### Proof.

Let $\rho_{i}:G\to\operatorname{GL}(V_{i})$ be the irreducible representations
of $G$, where $V_{i}$ are complex vector spaces. Define the character function
$\chi_{i}:G\to\mathbb{C}$ as $\chi_{i}(g)=\operatorname{Tr}(\rho_{i}(g))$. We
will prove that for any $u\in G$:

$u=\sum_{i=1}^{k}\frac{\chi_{i}(u)}{d_{i}}\sum_{g\in
G}\chi_{i}(g^{-1})\rho_{i}(g)$ (2)

where $d_{i}=\dim(V_{i})$. Apply both sides to an arbitrary vector $v$ in the
representation space:

$\left(\sum_{i=1}^{k}\frac{\chi_{i}(u)}{d_{i}}\sum_{g\in
G}\chi_{i}(g^{-1})\rho_{i}(g)\right)v=\sum_{i=1}^{k}\frac{\chi_{i}(u)}{d_{i}}\sum_{g\in
G}\chi_{i}(g^{-1})\rho_{i}(g)v$ (3)

Use the orthogonality relations for irreducible characters[12]:

$\sum_{g\in G}\chi_{i}(g)\chi_{j}(g^{-1})=|G|\delta_{ij}$ (4)

Applying this to our sum:

$\sum_{g\in G}\chi_{i}(g^{-1})\rho_{i}(g)v=(|G|/d_{i})v\text{ for each }i$ (5)

Substituting back:

$\sum_{i=1}^{k}\frac{\chi_{i}(u)}{d_{i}}(|G|/d_{i})v=\sum_{i=1}^{k}(|G|/d_{i}^{2})\chi_{i}(u)v$
(6)

Now, use another orthogonality relation[12]:

$\sum_{i=1}^{k}(d_{i}^{2}/|G|)\chi_{i}(g)=\delta_{g,e}\text{ (where $e$ is the
identity element)}$ (7)

The inverse of this relation gives:

$u=\sum_{i=1}^{k}(|G|/d_{i}^{2})\chi_{i}(u)\rho_{i}(u)$ (8)

Comparing this with our result, we see that they are equal, proving the
decomposition formula. ∎

Intuitively, this theorem allows us to express any quantum operation
(represented as a group element) in terms of the fundamental building blocks
of the group’s structure - its irreducible representations. This decomposition
reveals the inherent symmetries and structure within the quantum operation,
which can be exploited for optimization and efficient simulation.

The character functions $\chi_{i}$ act as coefficients in this decomposition,
weighting the contribution of each irreducible representation. By analyzing
these coefficients, we can identify which components of the group structure
are most significant in a given quantum operation, leading to simplified
representations or efficient approximations.

######  Theorem 2 (Necessary and Sufficient Conditions for Decomposition).

The following conditions are necessary and sufficient for the decomposition of
a quantum circuit into a sum of character functions:

  1. 1.

The quantum circuit must be a group element of a finite group under the
operation of matrix multiplication.

  2. 2.

The group must have a complete set of irreducible representations over
$\mathbb{C}$ that satisfy the orthogonality relation for irreducible
representations.

  3. 3.

The quantum circuit must be expressible as a linear combination of the
irreducible representations, with coefficients given by the character
functions.

###### Proof.

Necessity:

  1. 1.

Condition 1 is necessary because the decomposition theorem applies
specifically to group elements and relies on the properties of finite groups.

  2. 2.

Condition 2 is necessary because the decomposition theorem expresses the
quantum circuit in terms of irreducible representations and relies on their
orthogonality to ensure the uniqueness and validity of the decomposition.

  3. 3.

Condition 3 is necessary because the decomposition theorem explicitly
expresses the quantum circuit in this form, and the character functions
provide the necessary coefficients for the linear combination.

Sufficiency: Given conditions 1-3, we can construct the decomposition as
follows:

  1. 1.

Let $U$ be the quantum circuit, represented as a group element of the finite
group $G$.

  2. 2.

For each irreducible representation $\rho_{i}$ of $G$, compute the coefficient
$c_{i}=\chi_{i}(U)/d_{i}$, where $\chi_{i}$ is the character of $\rho_{i}$ and
$d_{i}$ is its dimension.

  3. 3.

Construct the sum: $U^{\prime}=\sum_{i=1}^{k}c_{i}\sum_{g\in
G}\chi_{i}(g^{-1})\rho_{i}(g)$

  4. 4.

We will prove that $U^{\prime}=U$ by showing that they are equal when applied
to any vector $v$ in the representation space.

Let $v$ be an arbitrary vector in the representation space. Then:

$U^{\prime}v=\left(\sum_{i=1}^{k}c_{i}\sum_{g\in
G}\chi_{i}(g^{-1})\rho_{i}(g)\right)v=\sum_{i=1}^{k}c_{i}\sum_{g\in
G}\chi_{i}(g^{-1})\rho_{i}(g)v$
$=\sum_{i=1}^{k}c_{i}(|G|/d_{i})v\quad\text{(using orthogonality
relations)}=\sum_{i=1}^{k}(\chi_{i}(U)/d_{i})(|G|/d_{i})v$
$=\sum_{i=1}^{k}(|G|/d_{i}^{2})\chi_{i}(U)v=Uv\quad\text{(using the inverse
orthogonality relation)}$

Since this equality holds for all vectors $v$, we conclude that
$U^{\prime}=U$. This proves that the constructed sum satisfies the conditions
of Theorem 1, showing that $U$ can be decomposed into a sum of character
functions. ∎

Next, we establish a generalized notion of quantum circuit equivalence based
on character decomposition.

######  Theorem 3 (Generalized Quantum Circuit Equivalence).

Let $\mathcal{H}_{A}$ and $\mathcal{H}_{B}$ be finite-dimensional Hilbert
spaces. Two quantum circuits $A$ and $B$, represented by completely positive
trace-preserving (CPTP) maps
$\Phi_{A}:\mathcal{B}(\mathcal{H}_{A})\to\mathcal{B}(\mathcal{H}_{A})$ and
$\Phi_{B}:\mathcal{B}(\mathcal{H}_{B})\to\mathcal{B}(\mathcal{H}_{B})$
respectively, are considered equivalent if and only if:

  1. 1.

There exist isometries $V_{1}:\mathcal{H}_{A}\to\mathcal{H}_{B}$ and
$V_{2}:\mathcal{H}_{B}\to\mathcal{H}_{A}$ such that for all density operators
$\rho\in\mathcal{B}(\mathcal{H}_{A})$:

$\Phi_{A}(\rho)=V_{2}\Phi_{B}(V_{1}\rho V_{1}^{\dagger})V_{2}^{\dagger}$ (9)

  2. 2.

For any input state $\rho\in\mathcal{B}(\mathcal{H}_{A})$, the probability
distributions of measurement outcomes for any Positive Operator-Valued Measure
(POVM) ${E_{i}}$ are identical for both circuits:

$\forall\rho,\forall{E_{i}}:\operatorname{Tr}(E_{i}\Phi_{A}(\rho))=\operatorname{Tr}((V_{1}^{\dagger}E_{i}V_{1})\Phi_{B}(V_{1}\rho
V_{1}^{\dagger}))$ (10)

  3. 3.

The expectation values of any observable $O\in\mathcal{B}(\mathcal{H}_{A})$
are the same for both circuits when applied to any input state
$\rho\in\mathcal{B}(\mathcal{H}_{A})$:

$\forall\rho,\forall
O:\operatorname{Tr}(O\Phi_{A}(\rho))=\operatorname{Tr}((V_{1}^{\dagger}OV_{1})\Phi_{B}(V_{1}\rho
V_{1}^{\dagger}))$ (11)

###### Proof.

Necessity: If two circuits $A$ and $B$ are equivalent, they must produce
identical observable results for any input state and any measurement. This
directly implies conditions 2 and 3. Additionally, the isometries in condition
1 are necessary to relate the potentially different Hilbert spaces of the two
circuits while preserving the quantum information. Sufficiency: We prove by
contradiction. Assume two circuits $\Phi_{A}$ and $\Phi_{B}$ satisfy
conditions 2 and 3 but not condition 1. This means that for any isometries
$V_{1}:\mathcal{H}_{A}\to\mathcal{H}_{B}$ and
$V_{2}:\mathcal{H}_{B}\to\mathcal{H}_{A}$, there exists a state
$\rho\in\mathcal{B}(\mathcal{H}_{A})$ such that:

$\Phi_{A}(\rho)\neq V_{2}\Phi_{B}(V_{1}\rho V_{1}^{\dagger})V_{2}^{\dagger}$
(12)

We’re working in the trace-class operator space, which is the predual of
$\mathcal{B}(\mathcal{H})$. By the Hahn-Banach theorem[3], this implies the
existence of a bounded linear functional
$f:\mathcal{B}(\mathcal{H}_{A})\to\mathbb{C}$ such that:

$f(\Phi_{A}(\rho))\neq f(V_{2}\Phi_{B}(V_{1}\rho
V_{1}^{\dagger})V_{2}^{\dagger})$ (13)

By the Riesz representation theorem in the trace-class operator space[3],
there exists an operator $O\in\mathcal{B}(\mathcal{H}_{A})$ such that for all
$X\in\mathcal{B}(\mathcal{H}_{A})$:

$f(X)=\operatorname{Tr}(OX)$ (14)

Therefore, we have:

$\operatorname{Tr}(O\Phi_{A}(\rho))\neq\operatorname{Tr}(OV_{2}\Phi_{B}(V_{1}\rho
V_{1}^{\dagger})V_{2}^{\dagger})$ (15)

Using the cyclic property of the trace, we can rewrite the right-hand side:

$\operatorname{Tr}(OV_{2}\Phi_{B}(V_{1}\rho
V_{1}^{\dagger})V_{2}^{\dagger})=\operatorname{Tr}(V_{2}^{\dagger}OV_{2}\Phi_{B}(V_{1}\rho
V_{1}^{\dagger}))$
$=\operatorname{Tr}((V_{1}^{\dagger}V_{2}^{\dagger}OV_{2}V_{1})\Phi_{B}(V_{1}\rho
V_{1}^{\dagger}))$

This contradicts condition 3 of the definition, which states that for all
observables $O$ and states $\rho$:

$\operatorname{Tr}(O\Phi_{A}(\rho))=\operatorname{Tr}((V_{1}^{\dagger}OV_{1})\Phi_{B}(V_{1}\rho
V_{1}^{\dagger}))$ (16)

Therefore, if circuits $\Phi_{A}$ and $\Phi_{B}$ satisfy conditions 2 and 3,
they must also satisfy condition 1, proving the sufficiency of the conditions
in the definition. ∎

##  3 Connection to Stabilizer Formalism

The character function decomposition approach can be seen as a generalization
of the stabilizer formalism used in quantum computation[4]. Let’s elaborate on
this connection:

  1. 1.

Stabilizer Formalism:

     * •

Works with the Pauli group $P_{n}$ on $n$ qubits

     * •

$P_{n}$ has $4^{n}$ elements (products of Pauli matrices)

     * •

Stabilizer states are eigenstates of a subgroup of $P_{n}$

  2. 2.

My Character Function Decomposition:

     * •

Works with any finite group $G$ (including, but not limited to, $P_{n}$)

     * •

Decomposes elements of $G$ into sums of irreducible representations

  3. 3.

Connection:

     * •

For $P_{n}$, the irreducible representations correspond to stabilizer states

     * •

The decomposition theorem generalizes this to any finite group

  4. 4.

Potential for Efficient Simulation:

     * •

Stabilizer circuits are efficiently classically simulable due to the structure
of $P_{n}$[1]

     * •

My approach suggests similar efficiencies might exist for other groups with
suitable representation-theoretic properties

  5. 5.

Example: Consider the Clifford group $C_{n}$ (normalizer of $P_{n}$):

     * •

$C_{n}$ has a well-understood representation theory[6]

     * •

Our decomposition might lead to efficient simulation methods for Clifford
circuits

     * •

This potentially offers a new perspective on the Gottesman-Knill theorem[5]

It’s important to note that while this approach generalizes the stabilizer
formalism, the efficiency of simulation for groups other than the Pauli group
is a conjecture based on this analogy. Further research is needed to determine
the exact classes of quantum circuits for which this method provides efficient
classical simulation.

######  Theorem 4 (Generalized Gottesman-Knill).

Let $G$ be a finite group with a set of generators ${g_{1},\ldots,g_{k}}$. If:

  1. 1.

The irreducible representations of $G$ can be efficiently computed,

  2. 2.

The character values $\chi_{i}(g)$ can be efficiently computed for all $g\in
G$ and all irreducible representations $i$,

  3. 3.

The number of irreducible representations grows polynomially with the number
of qubits,

Then quantum circuits composed of gates from $G$ can be efficiently simulated
classically using the character function decomposition method.

###### Proof.

Let $U$ be a quantum circuit composed of $m$ gates from $G$, where $m$ is
polynomial in the number of qubits $n$. We can express $U$ as:

$U=g_{i_{1}}g_{i_{2}}\cdots g_{i_{m}}$ (17)

where each $g_{i_{j}}$ is a generator of $G$. By Theorem 1, we can decompose
$U$ as:

$U=\sum_{i=1}^{k}\frac{\chi_{i}(U)}{d_{i}}\sum_{g\in
G}\chi_{i}(g^{-1})\rho_{i}(g)$ (18)

where $k$ is the number of irreducible representations of $G$, $\chi_{i}$ is
the character of the $i$-th irreducible representation $\rho_{i}$, and $d_{i}$
is the dimension of $\rho_{i}$. To simulate this circuit efficiently, we need
to show that:

  1. 1.

We can compute $\chi_{i}(U)$ efficiently for all $i$.

  2. 2.

We can evaluate the sum $\sum_{g\in G}\chi_{i}(g^{-1})\rho_{i}(g)$ efficiently
for all $i$.

  3. 3.

We can efficiently compute the expectation value of an observable $O$ for any
input state $\ket{\psi}$.

Computing $\chi_{i}(U)$:

By the properties of characters, we have:

$\chi_{i}(U)=\chi_{i}(g_{i_{1}}g_{i_{2}}\cdots
g_{i_{m}})=\prod_{j=1}^{m}\chi_{i}(g_{i_{j}})$ (19)

By assumption 2, each $\chi_{i}(g_{i_{j}})$ can be computed efficiently. Since
$m$ is polynomial in $n$, the product can be computed efficiently. 2\.
Evaluating $\sum_{g\in G}\chi_{i}(g^{-1})\rho_{i}(g)$: Let $S_{i}=\sum_{g\in
G}\chi_{i}(g^{-1})\rho_{i}(g)$. We don’t need to compute this sum explicitly.
Instead, we can use the fact that $S_{i}$ is a scalar multiple of the identity
matrix in the $i$-th irreducible representation:

$S_{i}=\frac{|G|}{d_{i}}I_{d_{i}}$ (20)

This follows from Schur’s lemma and the orthogonality relations of characters.
We can compute $|G|/d_{i}$ efficiently since $d_{i}\leq\sqrt{|G|}$ for all
$i$. 3\. Computing expectation values: For an observable $O$ and input state
$\ket{\psi}$, we need to compute $\bra{\psi}U^{\dagger}OU\ket{\psi}$
efficiently. Using the decomposition of $U$:

$\bra{\psi}U^{\dagger}OU\ket{\psi}=\sum_{i,j=1}^{k}\frac{\overline{\chi_{i}(U)}\chi_{j}(U)}{d_{i}d_{j}}\bra{\psi}\left(\sum_{g\in
G}\chi_{i}(g)\rho_{i}(g)^{\dagger}\right)O\left(\sum_{h\in
G}\chi_{j}(h^{-1})\rho_{j}(h)\right)\ket{\psi}$
$=\sum_{i,j=1}^{k}\frac{\overline{\chi_{i}(U)}\chi_{j}(U)}{d_{i}d_{j}}\frac{|G|^{2}}{d_{i}d_{j}}\bra{\psi}O\ket{\psi}=|G|^{2}\bra{\psi}O\ket{\psi}\sum_{i=1}^{k}\frac{|\chi_{i}(U)|^{2}}{d_{i}^{2}}$

The last step uses the fact that $\sum_{i}(d_{i}^{2}/|G|)=1$. We can compute
this efficiently because:

  1. 1.

$\chi_{i}(U)$ can be computed efficiently (from step 1).

  2. 2.

The number of irreducible representations $k$ is polynomial in $n$ (by
assumption 3).

  3. 3.

$\bra{\psi}O\ket{\psi}$ can be computed efficiently for typical observables
and input states.

Therefore, we can efficiently compute expectation values for any observable
$O$ and input state $\ket{\psi}$, which allows for efficient classical
simulation of the quantum circuit. ∎

This generalized theorem provides a framework for identifying new classes of
efficiently simulable quantum circuits based on their group-theoretic
properties. Building upon the Generalized Gottesman-Knill theorem, we can
further characterize the runtime complexity of the classical simulation based
on the structure of the group and its representation theory.

######  Theorem 5 (Revised Runtime Complexity of Classical Simulation).

Let $U$ be a quantum circuit composed of $m$ gates from a group $G$, acting on
$n$ qubits. Let $k$ be the number of irreducible representations of $G$, and
let $D$ be the maximum dimension of the irreducible representations. The
runtime complexity of the classical simulation of $U$ using the character
function decomposition method is:

$\begin{cases}\mathcal{O}(k(m+|G|(1+k^{2}+k^{3}))+kD^{2})&\text{if }G\text{ is
Abelian}\\\ \\\
\mathcal{O}(k(mn^{2}+|G|(n^{2}+k^{2}n^{2}+k^{3}))+kD^{2})&\text{if }G\text{ is
}S_{n}\\\ \\\
\mathcal{O}(k(mg(|G|)+|G|(g(|G|)+k^{2}g(|G|)+k^{3}))+kD^{2})&\text{otherwise}\end{cases}$

where $g(|G|)$ represents the complexity of computing character values for a
general non-Abelian group $G$.

###### Proof.

We define the complexity of computing character values $f(|G|)$ as a piecewise
function:

$f(|G|)=\begin{cases}\mathcal{O}(1)&\text{if }G\text{ is Abelian}\\\
\mathcal{O}(n^{2})&\text{if }G\text{ is the symmetric group }S_{n}\\\
\mathcal{O}(g(|G|))&\text{otherwise}\end{cases}$

We will verify the math for each case of the piecewise defined function:
Case 1: $G$ is Abelian

  * •

$C(\chi)=\mathcal{O}(1)$

  * •

$C(\rho)=\mathcal{O}(k^{2}*C(\chi)+k^{3})=\mathcal{O}(k^{2}+k^{3})$

  * •

The runtime complexity becomes:

$\mathcal{O}(k*(m*\mathcal{O}(1)+|G|*(\mathcal{O}(1)+\mathcal{O}(k^{2})+\mathcal{O}(k^{3})))+k*D^{2})\
=\mathcal{O}(k(m+|G|(1+k^{2}+k^{3})+D^{2}))$

Case 2: $G$ is the symmetric group $S_{n}$

  * •

$C(\chi)=\mathcal{O}(n^{2})$

  * •

$C(\rho)=\mathcal{O}(k^{2}*C(\chi)+k^{3})=\mathcal{O}(k^{2}*n^{2}+k^{3})$

  * •

The runtime complexity becomes:

$\mathcal{O}(k*(m*\mathcal{O}(n^{2})+|G|*(\mathcal{O}(n^{2})+\mathcal{O}(k^{2}*n^{2})+\mathcal{O}(k^{3})))+k*D^{2})$
$=\mathcal{O}(k(mn^{2}+|G|(n^{2}+k^{2}n^{2}+k^{3}))+kD^{2})$

Case 3: $G$ is a general non-Abelian group

  * •

$C(\chi)=\mathcal{O}(g(|G|))$

  * •

$C(\rho)=\mathcal{O}(k^{2}*C(\chi)+k^{3})=\mathcal{O}(k^{2}*g(|G|)+k^{3})$

  * •

The runtime complexity becomes:

$\mathcal{O}(k*(m*\mathcal{O}(g(|G|))+|G|*(\mathcal{O}(g(|G|))+\mathcal{O}(k^{2}*g(|G|))+\mathcal{O}(k^{3})))+k*D^{2})$
$=\mathcal{O}(k(mg(|G|)+|G|(g(|G|)+k^{2}g(|G|)+k^{3}))+kD^{2})$

The term $k*D^{2}$ appears in all cases and serves to connect the complexities
of irreducible representations and the group itself. This term is justified as
follows:

  * •

For a finite group $G$, we have $\sum_{i=1}^{k}d_{i}^{2}=|G|$, where $d_{i}$
is the dimension of the $i$-th irreducible representation.

  * •

$D^{2}\geq d_{i}^{2}$ for all $i$, as $D$ is the maximum dimension.

  * •

Therefore, $k*D^{2}\geq|G|$, providing an upper bound that links the number of
irreducible representations ($k$) and their maximum size ($D^{2}$) to the
group order.

  * •

Operations on matrices of the irreducible representations will have complexity
related to $D^{2}$.

  * •

Including $k*D^{2}$ in the complexity formula accounts for both the number of
irreducible representations and their potential size, effectively capturing
the worst-case scenario where operations might need to be performed on all $k$
representations, each potentially of size $D\times D$.

Therefore, the theorem holds for all cases of the piecewise defined function
$f(|G|)$, and the inclusion of $k*D^{2}$ provides a meaningful connection
between the group structure and its representations in the complexity
analysis. ∎

##  4 Results

While Quantum Forge is still under development, the theoretical analysis and
preliminary implementation results yield several key outcomes:

  1. 1.

Theorem 1 (Character Function Decomposition): We prove that any quantum
circuit representable as a group element can be decomposed into a sum of
character functions.

  2. 2.

Theorem 2 (Necessary and Sufficient Conditions): We establish the conditions
under which a quantum circuit can be decomposed using our method.

  3. 3.

Theorem 3 (Circuit Equivalence): We prove the equivalence between the original
quantum circuit and its character function decomposition.

  4. 4.

Preliminary benchmarks: Initial tests with Quantum Forge suggest significant
speedups in classical simulation for certain classes of quantum circuits,
compared to state-of-the-art simulators.

We also conducted preliminary benchmarking on Qiskit for our character
decomposition algorithm. Figure 1 shows the original Bernstein-Vazirani
circuit and its optimized version after applying character decomposition. The
runtime analysis in Figure 2(a) demonstrates the significant speedups achieved
by our method as the number of qubits increases.

(a) Original Bernstein-Vazirani circuit

(b) Optimized circuit after character decomposition

Figure 1: Bernstein-Vazirani circuits before and after optimization. This
figure illustrates the impact of our character decomposition method on the
Bernstein-Vazirani algorithm. (a) The original circuit, consisting of Hadamard
gates (H), controlled-NOT gates (CNOT), and measurement operations (M). The
circuit operates on n+1 qubits, where n is the size of the hidden bit string.
(b) The optimized circuit after applying our character decomposition method.
Note the significant reduction in gate count and circuit depth. The optimized
circuit preserves the functionality of the original while offering potential
speedups in both quantum and classical simulations. Red boxes represent
Hadamard gates, blue lines indicate CNOT operations, and gray arrows with
triangles denote measurement.

(a) Runtime comparison of original and optimized Bernstein-Vazirani circuits

(b) Measurement histograms of original and optimized circuits (4 qubits)

Figure 2: Performance analysis of character decomposition on Bernstein-
Vazirani circuits. (a) Runtime scaling comparison between the original and
optimized Bernstein-Vazirani circuits as the number of qubits increases. The
optimized circuit shows significantly better scaling, demonstrating the
efficiency of our character decomposition method. (b) Measurement outcome
histograms for 4-qubit circuits, comparing the original and optimized
versions. The similarity in distributions confirms that the optimization
preserves the algorithm’s correctness while improving performance.

(a) Original QFT circuit

(b) Optimized QFT circuit after character decomposition

Figure 3: QFT circuits before and after optimization. This figure demonstrates
the effect of our character decomposition method on the Quantum Fourier
Transform (QFT) algorithm. (a) The original QFT circuit for 3 qubits,
consisting of Hadamard gates (H) and controlled rotation gates (R). (b) The
optimized QFT circuit after applying our character decomposition method. Note
the reduction in circuit depth and the modified gate structure. The optimized
circuit maintains the functionality of the original QFT while potentially
offering improved simulation efficiency. Blue boxes represent Hadamard gates,
and colored rotations represent different controlled phase gates.

(a) Runtime comparison of original and optimized QFT circuits

(b) Measurement histograms of original and optimized QFT circuits (3 qubits)

Figure 4: Performance analysis of character decomposition on QFT circuits. (a)
Runtime scaling comparison between the original and optimized Quantum Fourier
Transform (QFT) circuits as the number of qubits increases. The optimized
circuit demonstrates improved scaling, highlighting the effectiveness of our
method for this fundamental quantum algorithm. (b) Measurement outcome
histograms for 3-qubit QFT circuits, comparing the original and optimized
versions. The consistency in distributions validates that our optimization
maintains the QFT’s functionality while enhancing its performance.

(a) Runtime comparison of original and optimized Grover’s algorithm circuits

(b) Measurement histograms of original and optimized Grover’s algorithm
circuits (4 qubits)

Figure 5: Performance analysis of character decomposition on Grover’s
algorithm circuits. (a) Runtime scaling comparison between the original and
optimized Grover’s search algorithm circuits as the number of qubits
increases. The optimized version shows improved scaling, demonstrating our
method’s applicability to this important quantum search algorithm. (b)
Measurement outcome histograms for 4-qubit Grover’s circuits, comparing the
original and optimized versions. The similarity in peak locations confirms
that our optimization preserves the algorithm’s ability to amplify the target
state. Figure 6: Runtime comparison of original and optimized VQE circuits.
This figure illustrates the performance improvement achieved by our character
decomposition method on Variational Quantum Eigensolver (VQE) circuits. The
graph compares the runtime scaling of original and optimized VQE circuits as
the number of qubits increases. The optimized circuits demonstrate
significantly better scaling, highlighting the potential of our approach for
enhancing the efficiency of quantum-classical hybrid algorithms like VQE,
which are crucial for near-term quantum applications in chemistry and
materials science.

These results provide a rigorous mathematical foundation for our approach to
quantum circuit analysis and optimization, as well as promising early
indications of its practical effectiveness.

While the preliminary benchmarking results presented in Figures 2-6
demonstrate promising speedups for the character decomposition method, it is
important to acknowledge the limitations of the current implementation. The
benchmarks were performed on a limited set of quantum algorithms and circuit
sizes, and the comparison was made against a single simulator (Qiskit). For a
more comprehensive evaluation, Quantum Forge should be tested on a wider range
of quantum circuits, including those with non-unitary operations and noise,
and compared against multiple state-of-the-art simulators such as Cirq and
eventually, Quantum Forge. Furthermore, the scalability and performance of
Quantum Forge on larger quantum systems and more complex algorithms remain to
be investigated. Future work will focus on conducting more rigorous
comparisons and identifying the classes of quantum circuits for which the
character decomposition method provides the most significant advantages.

##  5 Discussion and Future Work

The theoretical framework and initial implementation in Quantum Forge open up
several exciting avenues for future research:

  * •

Completion and open-sourcing of Quantum Forge after thorough testing and
validation.

  * •

Comprehensive benchmarking of Quantum Forge against other quantum circuit
simulators across a wide range of circuit types and sizes.

  * •

Extension of Quantum Forge to handle a broader class of quantum operations,
including non-unitary operations and measurements.

  * •

Exploration of applications in quantum error correction and fault-tolerant
quantum computation.

  * •

Investigation of how this approach might lead to new quantum algorithms or
improvements to existing ones.

  * •

Further theoretical work on the connection between group theory and quantum
circuit simulation, potentially leading to new complexity classes or
simulation algorithms.

While Quantum Forge is still under development, my current work lays the
groundwork for significant practical advancements in quantum circuit
simulation and analysis. The next crucial steps will be to complete the
implementation, conduct comprehensive empirical evaluations, and make the tool
available to the wider quantum computing community.

##  6 Implications

###  6.1 Quantum Circuit Optimization

The character function decomposition method provides a new approach to quantum
circuit optimization. By expressing quantum circuits in terms of irreducible
representations and character functions, we can identify symmetries and
redundancies that might not be apparent in the original circuit
representation. This can lead to more efficient circuit designs and
implementations, potentially reducing gate count and circuit depth[9].

###  6.2 Error Correction

My approach has implications for quantum error correction. Many quantum error-
correcting codes, such as stabilizer codes, are based on group-theoretic
concepts[4]. By expressing quantum circuits in terms of character functions,
we might be able to design new error-correcting codes or improve existing
ones. The decomposition could reveal invariant subspaces of the quantum
operation that are resistant to certain types of errors, leading to more
robust quantum codes.

The character function decomposition could potentially lead to the design of
new quantum error-correcting codes that leverage the group-theoretic structure
of quantum operations. For example, consider a quantum code defined on a
finite group G, where the logical states are encoded as irreducible
representations of G. By expressing the error operators in terms of character
functions, we may be able to identify invariant subspaces that are immune to
certain types of errors.

As a concrete illustration, suppose $G$ is the quaternion group $Q8$, which
has five irreducible representations: four 1-dimensional representations and
one 2-dimensional representation. By encoding logical qubits in the
2-dimensional irreducible representation, we can protect against errors that
correspond to the 1-dimensional representations, as they will leave the
encoded subspace invariant. This is just one example of how the character
function decomposition could inspire new approaches to quantum error
correction.

Furthermore, the character decomposition method could potentially be used to
analyze and optimize existing quantum error-correcting codes. By expressing
the encoding and decoding operations in terms of character functions, we may
be able to identify more efficient implementations or uncover new properties
of the code. The connection between group theory and error correction is a
promising area for future research, and the tools developed in this paper
provide a foundation for exploring these ideas further.

###  6.3 Quantum Algorithms

The insights gained from character function decomposition could lead to the
development of new quantum algorithms or the improvement of existing ones. By
understanding the group-theoretic structure of quantum operations, we might
identify new ways to exploit quantum parallelism or interference effects. For
example, in quantum phase estimation algorithms, which are crucial for many
quantum simulation tasks[7], the character function decomposition could
provide a new perspective on the phase kickback mechanism.

##  7 Methods

###  7.1 Character Function Decomposition

The character function decomposition method is based on the representation
theory of finite groups. For a given quantum circuit represented as a unitary
matrix $U$, we identify the finite group $G$ to which $U$ belongs. We then
compute the irreducible representations and character functions of $G$. The
decomposition is performed using the formula provided in Theorem 1, expressing
$U$ as a sum of character functions.

###  7.2 Quantum Forge Implementation

Quantum Forge is implemented using the MLIR (Multi-Level Intermediate
Representation) compiler framework[8]. The compiler pipeline consists of the
following main passes:

  1. 1.

Circuit to Group Element Translation

  2. 2.

Irreducible Representation Identification

  3. 3.

Character Function Computation

  4. 4.

Decomposition Application

  5. 5.

Optimization Based on Decomposition

Each pass is implemented as a separate MLIR dialect, allowing for modular
design and easy extension of the framework.

###  7.3 Benchmarking Methodology

Benchmarks were performed using the Qiskit framework (version 1.1.0) on a
system with Intel Core i7-12700 (20 CPUs), 32GB RAM, and NVIDIA GeForce RTX
3050 (for GPU acceleration). Each algorithm (Bernstein-Vazirani, Grover’s
search, QFT, and VQE) was implemented both in its original form and using my
character decomposition method. Runtimes were measured using Python’s time
module, with each experiment repeated 100 times to ensure statistical
significance. The reported speedups are the average over these runs.

###  7.4 Theoretical Complexity Analysis

The complexity analysis presented in Theorem 5 was derived by considering the
computational cost of each step in the character decomposition process. For
Abelian groups, I leveraged the fact that all irreducible representations are
one-dimensional, significantly simplifying the computation. For the symmetric
group, I used known results about its representation theory. For general non-
Abelian groups, I introduced the function $g(|G|)$ to encapsulate the
complexity of character computation, which can vary depending on the specific
group structure.

##  8 Data Availability

The datasets generated and analyzed during the current study are available
from the corresponding author on reasonable request. The benchmarking data
used to generate Figures 2-6 will be deposited in a public repository upon
publication.

##  9 Code Availability

The Quantum Forge compiler will be made open-source and publicly available
upon completion of development and testing. The core algorithms implementing
the character decomposition method will be made available as part of the
Quantum Forge release.

##  10 Conclusion

In this paper, I have introduced a novel approach to analyzing and optimizing
quantum circuits using character function decomposition. We have proven
several fundamental theorems that establish the mathematical foundations of
this approach and demonstrated its potential for providing new insights into
quantum computation. This work bridges concepts from group theory and quantum
computing, offering a new perspective on the structure and properties of
quantum circuits. The ongoing development of Quantum Forge promises to turn
these theoretical insights into practical tools for quantum circuit simulation
and optimization. As the field of quantum computing continues to evolve,
approaches like the one presented in this paper, combining theoretical depth
with practical implementation, will play a crucial role in advancing our
ability to design, analyze, and optimize quantum algorithms. I’m looking
forward to the completion and release of Quantum Forge, and I hope that this
work will stimulate further research at the intersection of group theory,
compiler optimization, and quantum computation.

## References

  * [1] Scott Aaronson and Daniel Gottesman.  Improved simulation of stabilizer circuits.  Physical Review A, 70(5):052328, 2004.
  * [2] Cirq: A Python framework for creating, editing, and invoking Noisy Intermediate Scale Quantum (NISQ) circuits.  https://quantumai.google/cirq.  Accessed: 2024-06-16.
  * [3] John B Conway.  A course in functional analysis, volume 96.  Springer, 1990.
  * [4] Daniel Gottesman.  Stabilizer codes and quantum error correction.  arXiv preprint quant-ph/9705052, 1997.
  * [5] Daniel Gottesman.  The Heisenberg Representation of Quantum Computers.  arXiv, 1998.
  * [6] David Gross.  Hudson’s theorem for finite-dimensional quantum systems.  Journal of mathematical physics, 47(12):122107, 2006.
  * [7] Alexei Yu Kitaev.  Quantum measurements and the abelian stabilizer problem.  arXiv preprint quant-ph/9511026, 1995.
  * [8] Chris Lattner, Mehdi Amini, Uday Bondhugula, Albert Cohen, Andy Davis, Jacques Pienaar, River Riddle, Tatiana Shpeisman, Nicolas Vasilache, and Oleksandr Zinenko.  Mlir: A compiler infrastructure for the end of moore’s law.  arXiv preprint arXiv:2002.11054, 2020.
  * [9] Yunseong Nam, Neil J Ross, Yuan Su, Andrew M Childs, and Dmitri Lee.  Automated optimization of large quantum circuits with continuous parameters.  npj Quantum Information, 4(1):1–12, 2018.
  * [10] Michael A Nielsen and Isaac L Chuang.  Quantum computation and quantum information.  Cambridge university press, 2010.
  * [11] Qiskit: An open-source framework for quantum computing.  https://qiskit.org/.  Accessed: 2024-06-16.
  * [12] Jean-Pierre Serre.  Linear representations of finite groups.  Springer, 1977.


$(u,v)$ with $u\in V(P)$ and $v\in V(T)$, there exists a pivot $b\in B_{k-1}$
with $d_{G_{P}}(u,v)=d_{G_{P}}(u,b)+d_{G_{P}}(b,v)$ such that
$d_{G_{P}}(u,b)\leqslant 2^{k}$.

Then the above procedure computes in
$\widetilde{O}(\frac{nm}{2^{k}}+n^{2})=\widetilde{O}(m\mathchoice{{\hbox{$\displaystyle\sqrt{n\,}$}\lower
0.4pt\hbox{\vrule
height=4.30554pt,depth=-3.44446pt}}}{{\hbox{$\textstyle\sqrt{n\,}$}\lower
0.4pt\hbox{\vrule
height=4.30554pt,depth=-3.44446pt}}}{{\hbox{$\scriptstyle\sqrt{n\,}$}\lower
0.4pt\hbox{\vrule
height=3.01389pt,depth=-2.41113pt}}}{{\hbox{$\scriptscriptstyle\sqrt{n\,}$}\lower
0.4pt\hbox{\vrule height=2.15277pt,depth=-1.72223pt}}}+n^{2})$ time a set of
$\widetilde{O}(n/2^{k})$ pivots $B_{k}$ such that for every $k$-relevant pair
$(u,v)$ with $u\in V(P)$ and $v\in V(T)$, there exists a pivot $b\in B_{k}$
with $d_{G_{P}}(u,v)=d_{G_{P}}(u,b)+d_{G_{P}}(b,v)$ and such that
$d_{G_{P}}(u,b)\leqslant 2^{k+1}$.

######  Proof B.5.

We first prove that $B_{k}=\widetilde{O}(n/2^{k})$ and that the runtime of the
above procedure is $\widetilde{O}(\frac{nm}{2^{k}}+n^{2})$. Note that
$\mathcal{P}_{k}$ contains $\widetilde{O}(|B_{k-1}|\cdot
n)=\widetilde{O}(n^{2}/2^{k})$ paths, each path of length exactly $2^{k-1}$,
thus by 4.1 it follows that $B_{k}=\widetilde{O}(n/2^{k})$ and the runtime of
the $\textsf{GreedyPivotSelection}(\mathcal{P}_{k})$ algorithm is
$\widetilde{O}(n^{2})$. The above procedure also computes a BFS tree rooted in
every vertex $b\in B_{k-1}$, this takes additional $\widetilde{O}(mn/2^{k})$
time, so the total runtime of the above procedure is
$\widetilde{O}(mn/2^{k}+n^{2})$.

Next, we prove the correctness of the above procedure. We assume that for
every pair of $(k-1)$-relevant pairs of vertices $u\in V(P),v\in V(T)$, there
exists a pivot $b\in B_{k-1}$ with
$d_{G_{P}}(u,v)=d_{G_{P}}(u,b)+d_{G_{P}}(b,v)$ and such that
$d_{G_{P}}(u,b)\leqslant 2^{k}$, and we prove that for every pair of
$k$-relevant vertices $u\in V(P),v\in V(T)$ there exists a pivot $b\in B_{k}$
with $d_{G_{P}}(u,v)=d_{G_{P}}(u,b)+d_{G_{P}}(b,v)$ and such that
$d_{G_{P}}(u,b)\leqslant 2^{k+1}$. Let $(u,v)\in V(P)\times V(T)$ be a
$k$-relevant pair, and let $v^{\prime}$ be the $2^{k}-\mathrm{th}$ vertex
along $P_{G_{P}}(u,v)$.

Clearly, $(u,v)$ is also a $(k-1)$-relevant pair. Therefore, by induction,
there exists a pivot $b\in B_{k-1}$ with
$d_{G_{P}}(u,v)=d_{G_{P}}(u,b)+d_{G_{P}}(b,v)$ and such that
$d_{G_{P}}(u,b)\leqslant 2^{k}$. As $d_{G_{P}}(b,v)\geqslant
d_{G_{P}}(u,v)-d_{G_{P}}(u,b)\geqslant 2^{k+1}-2^{k}=2^{k}$, we have that
$B_{k}$ hits w.h.p. the $(u,v)$ $k$-relevant path as well with a pivot
$b^{\prime}\in B_{k}$ such that $d_{G_{P}}(b,b^{\prime})\leqslant 2^{k}$.
Therefore, $d_{G_{P}}(u,v)=d_{G_{P}}(u,b^{\prime})+d_{G_{P}}(b^{\prime},v)$
and $d_{G_{P}}(u,b^{\prime})=d_{G_{P}}(u,b)+d_{G_{P}}(b^{\prime},b)\leqslant
2^{k}+2^{k}\leqslant 2^{k+1}$.

B.3 implies that we can compute $B_{0}$ in
$\widetilde{O}(m\mathchoice{{\hbox{$\displaystyle\sqrt{n\,}$}\lower
0.4pt\hbox{\vrule
height=4.30554pt,depth=-3.44446pt}}}{{\hbox{$\textstyle\sqrt{n\,}$}\lower
0.4pt\hbox{\vrule
height=4.30554pt,depth=-3.44446pt}}}{{\hbox{$\scriptstyle\sqrt{n\,}$}\lower
0.4pt\hbox{\vrule
height=3.01389pt,depth=-2.41113pt}}}{{\hbox{$\scriptscriptstyle\sqrt{n\,}$}\lower
0.4pt\hbox{\vrule height=2.15277pt,depth=-1.72223pt}}}+n^{2})$ time by a
deterministic algorithm. As $B_{0}$ satisfies the hypothesis of B.4, by
induction on $k$, we have that $B_{k}$ can be computed out of $B_{k-1}$ in
$\widetilde{O}(m\mathchoice{{\hbox{$\displaystyle\sqrt{n\,}$}\lower
0.4pt\hbox{\vrule
height=4.30554pt,depth=-3.44446pt}}}{{\hbox{$\textstyle\sqrt{n\,}$}\lower
0.4pt\hbox{\vrule
height=4.30554pt,depth=-3.44446pt}}}{{\hbox{$\scriptstyle\sqrt{n\,}$}\lower
0.4pt\hbox{\vrule
height=3.01389pt,depth=-2.41113pt}}}{{\hbox{$\scriptscriptstyle\sqrt{n\,}$}\lower
0.4pt\hbox{\vrule height=2.15277pt,depth=-1.72223pt}}}+n^{2})$ time. This
completes the derandomization of Chechik and Magen’s algorithm. In summary, we
proved the following theorem.

See 1.8