# An approach to the girth problem in cubic graphs

Aya Bernstine School of Computer Science and Engineering, Hebrew University,
Jerusalem 91904, Israel. e-mail<EMAIL_ADDRESS>Nati Linial
School of Computer Science and Engineering, Hebrew University, Jerusalem
91904, Israel. e-mail<EMAIL_ADDRESS>Supported in part by a NSF-BSF
research grant ”Global Geometry of Graphs”.

###### Abstract

We offer a new, gradual approach to the largest girth problem for cubic
graphs. It is easily observed that the largest possible girth of all
$n$-vertex cubic graphs is attained by a $2$-connected graph $G=(V,E)$. By
Petersen’s graph theorem, $E$ is the disjoint union of a $2$-factor and a
perfect matching $M$. We refer to the edges of $M$ as chords and classify the
cycles in $G$ by their number of chords. We define $\gamma_{k}(n)$ to be the
largest integer $g$ such that every cubic $n$-vertex graph with a given
perfect matching $M$ has a cycle of length at most $g$ with at most $k$
chords. Here we determine this function up to small additive constant for
$k=1,2$ and up to a small multiplicative constant for larger $k$.

##  1 Introduction

The girth of a graph $G$ is the shortest length of a cycle in $G$. Our main
concern here is with bounds on $g(n)$, the largest girth of a cubic $n$-vertex
graph. Namely, we seek the best statement of the form ”Every $n$-vertex cubic
graphs must have a short cycle”. An elementary existential argument [5] shows
that $g(n)\geq\log_{2}n$ for infinitely many values of $n$. The best lower
bound that we currently have is $g(n)>\frac{4}{3}\log_{2}n-2$. It is attained
by sextet graphs, an infinite family of explicitly constructed graphs, first
introduced in [2], the girth of which was determined in [12]. On the other
hand, the only upper bound that we have is the more-or-less trivial Moore’s
Bound which says that

$(2+o_{n}(1))\log_{2}n\geq g(n).$

It is our belief that in fact a better upper bound applies

######  Conjecture 1.1.

There is a constant $\epsilon_{0}>0$ such that $(2-\epsilon_{0})\log_{2}n\geq
g(n)$

Concretely, Moore’s lower bound on $n$, the number of vertices in a
$d$-regular graph of girth $g$ is as follows. For odd $g=2k+1$ it is $n\geq
1+d\sum_{i=0}^{k-1}(d-1)^{i}$, for even $g=2k$ it is $n\geq
1+(d-1)^{k-1}+d\sum_{i=0}^{k-2}(d-1)^{i}$.

Moore Graphs which satisfy this with equality were fully characterized about a
half century ago [4], [1]. There is an ongoing research effort to determine,
or at least estimate $g(n)$, and we initiate here a new approach to this
problem. More generally, the search is on for $(d,g)$-cages. These are
$d$-regular graphs of girth $g$ with the smallest possible number of vertices.
The record of the best known bounds in this area is kept in [6].

##  2 Statement of the problem

As the following observation shows, it suffices to consider $2$-connected
graphs. We give the simple proof for completeness sake, but actually more is
known about the connectivity of cubic cages [11].

######  Proposition 2.1.

Among all cubic $n$-vertex graphs that have the largest possible girth $g(n)$,
at least one graph is $2$-connected.

###### Proof.

It is well-known and easy to show that a cubic graph is $2$-connected iff it
is bridgeless. So let the edge $xy\in E$ be a bridge in $G=(V,E)$, a cubic
$n$-vertex graph. Let $x^{\prime}\neq y$ be a neighbors of $x$, and
$y^{\prime}\neq x$ a neighbor of $y$. Let $G^{\prime}$ be obtained from $G$ be
deleting the edges $xx^{\prime}$ and $yy^{\prime}$ and adding the new edges
$xy^{\prime}$ and $yx^{\prime}$. It is easily verified that $G^{\prime}$ has
fewer bridges than $G$, while $\text{girth}(G^{\prime})\geq\text{girth}(G).$ ∎

We next recall Petersen’s theorem [10]: The edge set of every $2$-connected
cubic graph $G$ can be decomposed into a perfect matching $M$ and a $2$-factor
$C$. We call this a Petersen decomposition of $G$, and refer to the edges of
$M$ as chords.

The following is the main focus of this paper:

######  Definition 2.2.

$\gamma_{k}(n)$ is the smallest integer $g$ such every cubic $n$-vertex graph
with any Petersen Decomposition has a cycle of length $\leq g$ with at most
$k$ chords.

We start with some elementary observations concerning $\gamma_{k}(n)$.

  * •

$\gamma_{k}(n)$ is a non-increasing function of $k$.

  * •

In a very loose sense, for fixed $k$, the function $\gamma_{k}(n)$ is non-
decreasing with $n$, although this is not literally correct. For example, the
Tutte-Coxeter Graph, a well-known Moore graph shows that $\gamma(30)=8$. Also,
clearly, $\gamma_{3}(30)\geq\gamma(30)$. On the other hand, extensive computer
searches show that $\gamma_{3}(32)=7$.

  * •

$\gamma_{0}(n)=n$.

  * •

$\gamma_{1}(n)=\lfloor\frac{n}{2}\rfloor+1$. The unique extremal example is a
$(2g-2)$-cycle $C$ and a matching $M$ that matches every antipodal pair of
vertices in $C$.

  * •

A lower bound on $\gamma_{k}(n)$ amounts to a construction of a cubic graph
along with a Petersen Decomposition, where every short cycle has more than $k$
chords.

  * •

Upper bounds on $\gamma_{k}(n)$ are proofs that every cubic graph on $n$
vertices with a given Petersen Decomposition must have a short cycle with few
chords.

  * •

For $k\geq\log_{2}n$ there holds $\gamma_{k}(n)=g(n)$.

###  2.1 Paper Organization

The rest of the paper is organized as follows. In Section 3 we state our upper
and lower bounds on $\gamma_{k}(n)$. In Sections 4 and 5 we prove the upper
resp. lower bounds. In Section 6 we make some connection with the girth
problem in its general form.

##  3 Our results

In this paper we present an upper and lower bounds on cycles with at most $k$
chords

######  Theorem 3.1.

Let $n$ be an even number, then

  1. 1.

$\sqrt{2n}-\frac{5}{2}<\gamma_{2}(n)\leq\sqrt{2n}+2$. In fact,
$\sqrt{2n}+\frac{1}{2}<\gamma_{2}(n)$ holds for infinitely many $n$’s.

  2. 2.

$\frac{1}{2}(2n+\frac{9}{4})^{\frac{1}{2}}+\frac{5}{4}\leq\gamma_{3}(n)\leq(2n)^{\frac{1}{2}}+1$

  3. 3.

$(2n)^{1/3}+O(1)\leq\gamma_{5}(n)\leq\gamma_{4}(n)\leq\frac{3}{2}(2n)^{1/3}$

  4. 4.

$2(\frac{n}{4})^{1/4}+O(1)\leq\gamma_{7}(n)~{}~{}and~{}~{}2(\frac{n}{4})^{1/6}+O(1)\leq\gamma_{11}(n)$

  5. 5.

$\gamma_{2l}(n)\leq 3l+\frac{1}{2}(l+1+\ln 2)(n^{\frac{1}{l+1}})$

for every $l\geq 3$.

  6. 6.

$n^{\frac{4}{3q}}+O(1)\leq\gamma_{q}(n)$

for every prime power $q$.

##  4 Upper bounds - proofs

We prove first the upper bounds in Items 1 and 2, starting with some necessary
preparations. Let $\alpha_{1},\ldots,\alpha_{t}$ be a sequence of $t\geq 2$
distinct positive integers. The corresponding cycle $R$ is comprised of the
sequence $(\alpha_{1},\ldots,\alpha_{t})$ and its cyclic shifts
$(\alpha_{j},\ldots,\alpha_{t},\alpha_{1},\ldots,\alpha_{j-1})$, for every
$j=2,\dots,t$. We say, for $i=1,\ldots,t-1$ that $\alpha_{i},\alpha_{i+1}$ are
adjacent in $R$. Also $\alpha_{t},\alpha_{1}$ are adjacent in $R$. We denote
the set of (unordered) adjacent pairs in $R$ by $A(R)$. Finally we define
$w(R):=\sum_{\alpha,\beta\in A(R)}|\alpha-\beta|$.

######  Proposition 4.1.

Let $\Pi=\\{R_{1}\ldots R_{l}\\}$ be a partition of $[k]$ into cycles for some
even integer $k$. Then $\sum_{i}w(R_{i})\leq\frac{k^{2}}{2}$. The bound is
tight.

###### Proof.

We say that a cycle $R$ covers the interval $[i,i+1]$ if $i,i+1$ lie between
$\alpha$ and $\beta$ for some adjacent pair $\alpha,\beta\in A(R)$ (allowing
$\\{i,i+1\\}$ and $\\{\alpha,\beta\\}$ to have non-empty intersection). Let
$G_{i}$ be the number of cycles in $\Pi$ that cover the interval $[i,i+1]$.
Clearly

$\sum_{j}w(R_{j})=\sum|G_{i}|.$

We turn to bound $\sum|G_{i}|$. For $i<\frac{k}{2}$, the adjacent pair
$\alpha,\beta$ can cover the interval $[i,i+1]$ only if
$\min(\alpha,\beta)\leq i$. Every index smaller than or equal to $i$ can
contribute a total of $2$ to $|G_{i}|$, once moving left and once moving right
along the cycle. Consequently $|G_{i}|\leq 2i$. By symmetry, the same argument
yields $|G_{i}|\leq 2(k-i)$ when $i>\frac{k}{2}$, and finally
$|G_{\frac{k}{2}}|\leq k$. We sum these inequalities and conclude that

$\sum_{i=1}^{l}|G_{i}|\leq\frac{k(k-2)}{4}+\frac{k(k-2)}{4}+k=\frac{k^{2}}{2}.$

Equality is attained e.g., for the partition $R_{1}\ldots R_{\frac{k}{2}}$
into $\frac{k}{2}$ cycles with $R_{i}=\\{i,i+\frac{k}{2}\\}$. ∎

The following lemma proves the upper bound on $\gamma_{2}(n)$ in Theorem 1.

######  Lemma 4.2.

Let $G=(V,E)$ be an $n$-vertex $2$-connected cubic graph with Petersen
decomposition $E=M\sqcup C$. Then $G$ has a cycle of length $\leq\sqrt{2n}+2$
with at most $2$ chords.

###### Proof.

Let us mention that actually there always exists a cycle of length
$\leq\sqrt{2n}+1$ with at most $2$ chords. We omit the somewhat laborious
details of this stronger argument, and turn to prove the theorem.

If $uv\in M$ is a chord, we write $v^{*}=u$. Let $A$ be an arc of length
$k\leq\sqrt{2n}$ along a cycle $\sigma_{0}$ in $C$, and let
$A^{*}:=\\{v^{*}|v\in A\\}$. If $A^{*}\cap A\neq\emptyset$ this yields a cycle
of length $\leq\sqrt{2n}+1$ with only one chord. So, we may and will assume
that $A^{*}\cap A=\emptyset$.

Let $\sigma\neq\sigma_{0}$ be another cycle of $C$. If
$|A^{*}\cap\sigma|=r\geq 2$, let us denote the vertices of $A^{*}\cap\sigma$
by $u_{1}^{*},\ldots,u_{r}^{*}$ in cyclic order and with indices taken
$\bmod~{}r$. For every $i=1,\ldots,r$ we define the following $2$-chord
cycles: It starts with the chord $u_{i},u_{i}^{*}$; along $\sigma$ to
$u_{i+1}^{*}$; the chord $u_{i+1}^{*},u_{i+1}$; finally along $A$ to $u_{i}$.
When $r=1$ we consider instead the chord-free cycle $\sigma$.
This construction applies as well to $\sigma=\sigma_{0}$, except that the
above $2$-chord cycles are defined only for $i=1,\ldots,r-1$.

We have mentioned in total either $k-1$ or $k$ such $2$-chord cycles depending
on whether or not $A^{*}$ intersects with $\sigma_{0}$.

We turn to bound the total length of those $2$-chord cycles, starting with
their parts that traverse $A$. The collection of $2$-chord cycles that
correspond to any cycle $\sigma$ in $C$ induces a cycle on $A$. As we go over
all $\sigma$ we obtain a partition of $A$ into cycles. By Proposition 4.1 the
sum total of their lengths does not exceed $\frac{k^{2}}{2}$. Other than their
overlaps on $A$, the $2$-chord cycles traverse every chord twice and are
otherwise overlap-free.

Therefore their total length is at most $\leq n+\frac{k^{2}}{2}+{k-1}$.
Consequently, the average length of such cycle does not exceed

$\frac{n+\frac{k^{2}}{2}}{k-1}+1.$

We optimize and take $k=\sqrt{2n+1}+1$ to conclude that at least one of these
$2$-chord cycles with length $\leq\sqrt{2n}+2$.

∎

We prove next the upper bound on $\gamma_{4}(n)$.

######  Lemma 4.3.

Let $E=M\sqcup C$ be a Petersen decomposition of an $n$-vertex $2$-connected
cubic graph $G=(V,E)$. There is a cycle in $G$ of length $\leq L=\lambda
n^{\frac{1}{3}}+3$ with at most four chords, where $\lambda=3\cdot
2^{-\frac{2}{3}}\simeq 1.89$.

###### Proof.

Arguing by contradiction, we assume that all cycles of $C$ are longer than
$L$. We measure distances along $C$. Thus, the $r$-neighborhood of $v\in V$,
is the arc of $2r+1$ vertices centered at $v$ in the cycle of $C$ to which $v$
belongs. The $r$-neighborhood of $S\subset V$ is the union of the
$r$-neighborhoods of all vertices in $S$.

Let $A_{0}$ be an arc of length $k\leq\frac{2L}{3}-2$ along a cycle of $C$. We
may assume that any two vertices in $A_{0}^{*}$ are at distance at least
$\geq\frac{L}{3}-1$, for otherwise we obtain a cycle of length $<L$ with only
two chords. Let $r=\frac{L}{6}-\frac{1}{2}$. It follows that $A_{1}$, the
$r$-neighborhood of $A_{0}^{*}$ has cardinality $|A_{1}|=2kr$. Of course
$|A_{1}^{*}|=|A_{1}|$.

We say that $u,v\in A_{1}^{*}$ are consecutive if the shortest arc of $C$
between them contains no additional vertices of $A_{1}^{*}$. We number the
vertices of $A_{1}^{*}$ from $1$ to $2rk$ cyclically along $C$, proceeding
from a vertex to the consecutive one. If $u\in A_{1}^{*}$ is the $i$-th vertex
in this numbering, we associate with it the following $2$-chords path $P_{i}$
which starts at $u$ and ends in $A_{0}$. This path begins with a hop from $u$
to $u^{*}\in A_{1}$. Then comes a walk along $C$ to the closest vertex in
$A_{0}^{*}$. Call this closest vertex $\beta_{i}$ and the distance traveled
$b_{i}$. The path ends with a hop from $\beta_{i}$ to $\beta_{i}^{*}\in
A_{0}$.

Let $v\in A_{1}^{*}$ be the $(i+1)$-st in this order. Consider the following
$4$-chord cycle:

  1. 1.

from $u$ to $v$ along $C$ a distance of $a_{i}$.

  2. 2.

along $P_{i+1}$ to $\beta_{i+1}^{*}\in A_{0}$ .

  3. 3.

a walk through $A_{0}$ to $\beta_{i}^{*}$ a distance of $c_{i}$.

  4. 4.

from ${\beta_{i}^{*}}$ we traverse $P_{i}$ to $u$, in the direction opposite
to the above description.

The length of this cycle is thus $a_{i}+b_{i}+c_{i}+b_{i+1}+4$. There are
$|A_{1}^{*}|-1=2kr-1$ cycles in this list, since we exclude the case where $u$
is the $2rk$-th vertex of $A_{1}^{*}$ and $v$ is the first. The total length
of these cycles is

$\sum_{i=1}^{2rk-1}(a_{i}+b_{i}+c_{i}+b_{i+1}+4)$

Figure 1: An illustration of the expansion of $A_{0}$. Zigzag edges represent
chords.

We turn to bound the different parts of this sum. The stretches of $a_{i}$
steps are disjoint from $A_{0},A_{1}$, and $A_{0}^{*}$ hence
$\sum_{i=1}^{2rk-1}a_{i}\leq n-|A_{0}|-|A_{0}^{*}|-|A_{1}|=n-2k-2kr$. Consider
next the stretches of walks that go from a vertex in $A_{1}$ to the closest
vertex in $A_{0}^{*}$. For every $\beta_{i}\in A_{0}^{*}$ the sum of the
distances of all vertices in the $r$-neighborhood of $\beta_{i}$ is $r^{2}$.
It follows that $\sum_{i=1}^{2kr-1}b_{i}+\sum_{i=2}^{2kr}b_{i}\leq
2\sum_{i=1}^{2kr}b_{i}=2kr(r+1)$. Finally we turn to bound $\sum c_{i}$. We
argue here in the same way that we did in the proof of Lemma 4.2, except that
here the argument is carried out $2r$ times. Consequently,
$\sum_{i=1}^{2rk-1}c_{i}\leq 2r(\frac{k^{2}}{2})$.

Thus the sum total of the cycles’ lengths is at most $n-2k-2kr+2k\cdot
r(r+1)+rk^{2}+4(2kr)$. This gives the following upper bound on their average
length $\leq\frac{n}{2rk-1}+r+\frac{k}{2}+4$. We get the tightest upper bound
on the length by letting $k=\sqrt{\frac{n}{r}}$ and
$r=\frac{{(2n)}^{1/3}}{2}$. We conclude that there is at least one cycle of
length $\leq 3(\frac{n}{4})^{\frac{1}{3}}+4$. ∎

We finally present an upper bound on $\gamma_{k}(n)$ for every even $k$. This
yields an upper bound also for the case of odd $k$, since $\gamma_{k}(n)$ is a
decreasing function of $k$. The proof is just an adaptation of the upper bound
proof for $\gamma_{4}(n)$.

######  Lemma 4.4.

Let $E=M\sqcup C$ be a Petersen decomposition of an $n$-vertex $2$-connected
cubic graph $G=(V,E)$. There is a cycle in $G$ of length $\leq
3l+(l-1)(2^{-\frac{l}{l+1}}n^{\frac{1}{l+1}})+n^{\frac{1}{l+1}}2^{\frac{1}{l+1}}$
with at most $2l$ chords.

###### Proof.

We only sketch the proof, since it is similar to the proof of lemma 4.3. Let
$A_{0}$ be an arc of length $k<\frac{1}{2}(l+1)(n^{\frac{1}{l+1}})$. For every
$0<i\leq l-1$, we let $A_{i}$ be the $r$-neighborhood of $A_{i-1}^{*}$. It
follows that $A_{i}$ has cardinality $|A_{i}|=(2r)^{i}k$. We number the
vertices of $A_{l-1}^{*}$ from $1$ to $(2r)^{l-1}k$ cyclically along $C$. Let
$u\in A_{l-1}^{*}$ be the $i$-th vertex in this numbering. We associate with
it the following $l$-chords path $P_{i}$ which starts at $u$ and ends in
$A_{0}$. It begins with a hop from $u$ to $u^{*}\in A_{l-1}$ then a walk along
$C$ to the closest vertex in $A_{l-2}^{*}$ call it $\beta_{l-2}$ a distance of
$b^{i}_{l-2}$ then a hop to $\beta_{l-2}^{*}$ and in general from vertex
$\beta_{j}^{*}\in A_{j-1}$ a walk along $C$ to the closest a distance
$b_{i}^{j}$ to a vertex $\beta_{j-1}\in A^{*}_{j-2}$. Let $v\in A_{l-1}^{*}$
be the ($i+1$)-st in this order and consider the following $2l$-chord cycle:

  1. 1.

from $u$ to $v$ along $C$ a distance $a_{i}$.

  2. 2.

along $P_{i+1}$ to $\beta^{i+1*}\in A_{0}$.

  3. 3.

a walk along $A_{0}$ to $\beta^{i*}_{0}$ distance $c_{i}$.

  4. 4.

from $\beta^{i*}_{0}$ we traverse $P_{i}$ to $u$ in the opposite direction of
the path.

The length of this cycle is thus
$a_{i}+\sum_{j=1}^{l-1}b^{j}_{i}+b^{j}_{i+1}+c_{i}+2l$. There are
$|A_{l-1}|^{*}-1=(2r)^{l-1}k-1$ cycles to consider. The total length is
$\sum^{(2r)^{l-1}k-1}_{i=1}(a_{i}+c_{i}+\sum_{j=1}^{l-1}b^{j}_{i}+b^{j}_{i+1}+2l)$,
we bound all the steps as we did in proving Lemma 4.3. This yields that
$\frac{n}{(2r)^{l-1}k-1}+(l-1)r+\frac{k}{2}+3l-2$ is an upper bound on their
average length, and this for any two integers $r,k\geq 1$. The optimal choice
is $k=\sqrt{\frac{2n}{(2r)^{l-1}}}$ and $r=\frac{(2n)^{\frac{1}{l+1}}}{2}$.
With this choice we conclude that there is at least one cycle of length $\leq
3l+(l-1)(2^{-\frac{l}{l+1}}n^{\frac{1}{l+1}})+n^{\frac{1}{l+1}}2^{\frac{1}{l+1}}$
∎

##  5 Lower bounds

We prove the lower bound on $\gamma_{2}(n)$ by providing an explicit
construction. In the Petersen Decomposition of our graph, $C$ is a Hamilton
cycle.

######  Lemma 5.1.

$\gamma_{2}(n)\geq\sqrt{(2n+\frac{9}{4})}+\frac{1}{2}$ whenever $n=8l^{2}+6l$
with $l$ a positive integer. Namely, we construct a cubic $n$-vertex graph
$G=(V,E)$ with a Petersen Partition $E=M\sqcup C$, where $C$ is a Hamilton
cycle and where the shortest cycle with $2$ chords or less has length $4l+2$.

###### Proof.

All the indices mentioned below are taken $\bmod~{}n$. The vertices of $C$ are
numbered $0,\ldots,n-1$ in this order. Note that $n$ is divisible by $2l$. We
divide $C$ into $n/2l$ equal-length blocks and construct a graph that is
invariant under rotation by $2l$. The first block is comprised of vertices
$0,\ldots,2l-1$. Let $A=(a_{0},a_{1}...a_{l-1})$ be a sequence of $l$ odd
integers. For every $l>j\geq 0$, we introduce the chord $(2j,2j+a_{j})$, and,
as mentioned, we rotate these chords with steps of $2l$. Stated differently,
we (uniquely) express every even integer $x$ in the range $0,\ldots,n-1$ as
$x=2lk+2j$, where $0\leq k<\frac{n}{2l}$, $0\leq j<l$ and connect vertex $x$
by a chord to $x+a_{j}$. Since the integers $a_{i}$ are all odd, every chord
connects a vertex of even index to one of odd index. Also, every even vertex
is incident with exactly one chord. In order for $G$ to be cubic, also every
odd vertex must be incident with a single chord. Namely, we need to choose the
$a_{i}$ so that

$2lk+2j+a_{j}=2lr+2s+a_{s}\Rightarrow k=r,j=s\text{~{}for every~{}}0\leq
k,r<\frac{n}{2l},~{}0\leq j,s<l.$ (1)

In order that every cycle with exactly one chord has length $\geq g=4l+2$ we
must satisfy

$n-g+1\geq a_{j}\geq g-1\text{~{}for every~{}}0\leq j\leq l-1$ (2)

We choose the parameters so that $a_{i}\equiv a_{j}\bmod 2l$ for all
$i,j=0,\ldots,l-1$. This yields Condition (1) by considering the equations
$\bmod~{}2l$. Concretely, we let $A$ be the arithmetic progression
$a_{j}=4l(j+1)+1$. Condition (2) is easily seen to hold.

Consider the shortest $2$-chord cycle with chords

$(2kl+2j,2kl+2j+a_{j})\text{~{}and~{}}(2rl+2s,2rl+2s+a_{s}).$

We need to show that its length is $\geq g$. There are two cases to consider,
as the arc of this cycle which starts at $2kl+2j$ can end at either $2rl+2s$
or $2rl+2s+a_{s}$. Let us introduce the notation $\|x\|:=\min\\{x,n-x\\}$ for
an integer $n-1\geq x\geq 0$. We extend the definition to all integers $x$ by
first taking the residue of $x\bmod n$. Using this terminology, we need to
show that if $(k,j)\neq(r,s)$, then

$\|2kl+2j-(2rl+2s)\|+\|2kl+2j+a_{j}-(2rl+2s+a_{s})\|\geq g-2$

and

$\|2kl+2j-(2rl+2s+a_{s})\|+\|2kl+2j+a_{j}-(2rl+2s)\|\geq g-2.$

Due to the cyclic symmetry of our construction no generality is lost if we
assume that $r=0$ and $0\leq k<2l+2$. We also spell out the values of
$a_{j},a_{s}$ and $g$ and now we have to show that if $k\neq 0$ or $j\neq s$,
then

$\|2kl+2(j-s)\|+\|2kl+(4l-2)(j-s)\|\geq 4l$ (3)

and

$\|2l(k-2s-2)+2(j-s)-1\|+\|2l(k+2j+2)+2(j-s)+1\|\geq 4l.$ (4)

The inequality $\|x\|\geq y$ for an integer $n>x\geq 0$ and a positive integer
$y$ is equivalent to the conjunction of the inequalities $x\geq y$ and
$n-x\geq y$. For negative arguments we use the fact that $\|-x\|=\|x\|$, then
apply the above. Let us refer to the left hand side of Equation (3) as
$\|A_{1}\|+\|A_{2}\|$ and to Equation (4) as $\|B_{1}\|+\|B_{2}\|$. Note that
$n-B_{1}\geq n-A_{1}\geq 4l$. It suffices therefore to prove that
$|A_{1}|+\|A_{2}\|\geq 4l$ and $|B_{1}|+\|B_{2}\|\geq 4l$.

We start with the case $k=0$, which implies $j\neq s$. In Equation (3) this
yields $|A_{1}|\geq 2$ and $n-4l>4l^{2}-6l+2\geq|A_{2}|\geq 4l-2$ hence
$|A_{1}|+\|A_{2}\|\geq 4l$. In Equation (4) when $k=0$ either $j\geq 1$ and
then $n-4l>4l^{2}+2l-1>|B_{2}|\geq 4l$ or $s\geq 1$ and then $|B_{1}|\geq 4l$
hence $|B_{1}|+\|B_{2}\|\geq 4l$.

We turn our attention to Equation (3) with $k\geq 1$. It is easy to see that
$A_{1}>4l$ when $k\geq 3$. On the other hand, $A_{2}>n-4l$ when $k\leq 2$. It
remains to show that $|A_{1}|+|A_{2}|\geq 4l$ when $k\in\\{1,2\\}$. This is
done in the following case analysis.

  * •

There holds $A_{1}<0$ exactly when $s>kl+j$. But then $A_{2}<0$ as well and we
get $|A_{1}|+|A_{2}|=-A_{1}-A_{2}=4l(s-k-j)$. Clearly $s>kl+j\geq k+j$ so that
$|A_{1}|+|A_{2}|\geq 4l$ as claimed.

  * •

When $A_{1}>0>A_{2}$, there holds $|A_{1}|+|A_{2}|=A_{1}-A_{2}=(4l-4)(s-j)$.
We are in this range exactly when when $\frac{kl}{2l-1}<s-j<kl$, in this case
we would compute and $A_{1}-A_{2}\geq 4l$, because $j+1<s$, and $k\geq 1$.

  * •

In the last remaining case $A_{1},A_{2}>0$. Here $s<\frac{kl}{2l-1}+j$ and
$A_{1}+A_{2}=4l(k+j-s)>4l$.

Inequality (3) follows.

We proceed to Equation (4). Note that $B_{2}>0$. Also, $B_{2}\leq 4l$ only
when $k=j=0$ in this case $|B_{1}|=|-4ls-4l-2s-1|>4l$. Hence we are left to
consider the case where $\|B_{2}\|=n-B_{2}$, the only case when $n-B_{2}<4l$
is when $k=2l+1$ and $j=l-1$ but then $|B_{1}|>4l$. Inequality (4) follows.
With this we can conclude that the construction is valid.

∎

######  Remark 5.2.

For $l=1$, this construction yields the Heawood graph which is a Moore graph.

We proceed to bound $\gamma_{3}(n)$ by giving an appropriate explicit
construction.

The main idea of the construction is to transform the graph from Lemma 5.1
into a ”bipartite” version. This relies on the fact that in the original
construction $n$ is even and every chord connects a vertex of even index to
one with an odd index. In this construction no cycle has exactly $3$ chords,
while the length of every $2$-chord cycle in the original graph is only cut in
half at worst.

######  Lemma 5.3.

$\gamma_{3}(n)\geq\frac{1}{2}\sqrt{(2n+\frac{9}{4})}+\frac{5}{4}$ for every
$n=8l^{2}+6l$ with $l$ a positive integer. Namely, we construct a cubic
$n$-vertex graph $G=(V,E)$ with a Petersen Partition, where the shortest cycle
with $3$ chords or less has length $2l+2$.

###### Proof.

The graph that we construct has the same vertex set $V$ and the same set of
chords $M$ as in the graph $G$ of Lemma 5.1. What changes is the $2$-factor
$C$ of the Petersen Partition. In the original construction $C$ was a Hamilton
Cycle that traverses the vertices in order. In the present construction $C$ is
the disjoint union of two cycles, $C_{even}$ and $C_{odd}$ that traverse all
the even-indexed resp. odd vertices in order.

It is clear that $H$ is cubic, since every vertex is incident to exactly one
chord and has two neighbors in the $2$-factor in which it resides. As shown in
Lemma 5.1, every chord connects an even-indexed vertex to an odd one. It
follows that every cycle in $H$ has an even number of chords. Therefore we
only need to consider cycles with $2$ chords. Also, the only chordless cycles
are $C_{odd},C_{even}$ whose length is $\frac{n}{2}\gg 2l+2$.

Finally we come to cycles $\cal{C}$ with exactly $2$ chords in $H$. Such a
cycle is composed of an arc from $v_{1}$ to $v_{2}$ in $C_{odd}$, a chord
$v_{2}v_{3}$ to $v_{3}\in C_{even}$, an arc from $v_{3}$ to $v_{4}$ in
$C_{even}$ and a chord $v_{4}v_{1}$ back to $C_{odd}$. We can consider the
cycle $\tilde{\cal{C}}$ in $G$ that traverses $C$ from $v_{1}$ to $v_{2}$,
takes the chord $v_{2}v_{3}$, then traverses $C$ from $v_{3}$ to $v_{4}$ and
finally the chord $v_{4}v_{1}$. This is a $2$-chord cycle in $G$. and
$\text{length}(\tilde{\cal{C}})=2\cdot\text{length}(\cal{C})\rm-2$. As Lemma
5.1 shows $\text{length}(\tilde{\cal{C}})\geq 4l-2$. The conclusion follows. ∎

The lower bounds on $\gamma_{4},\gamma_{5},\gamma_{7},\gamma_{11}$ are proved
by an explicit construction as well. We start with a general construction
method from which these claims easily follow

######  Lemma 5.4.

Given an $n$-vertex $d$-regular graph $H=(V^{\prime},E^{\prime})$ with girth
$m$, there is an explicit $2nd$-vertex cubic graph $G=(V,E)$ with Petersen
Partition $M\sqcup C$, where the shortest length of a cycle in $G$ with at
most $m-1$ chords is $2d$.

###### Proof.

To construct $G$, associate with every vertex v in H a $2d$-cycle $C^{(v)}$.
The $2$-factor $C$ of $G$’s Petersen’s decomposition is the union of $C^{(v)}$
over all $v\in V^{\prime}$. For every edge $v_{1}v_{2}\in E^{\prime}$ we
introduce two edges: One between a vertex $v\in C^{(v_{1})}$ and a vertex
$u\in C^{(v_{2})}$. The second edge is $u^{\prime}v^{\prime}$, where
$v^{\prime}$ the antipode of $v$ in $C^{(v_{1})}$ and $u^{\prime}$ is the
antipode of $u$ in $C^{(v_{2})}$. Since girth$(H)=m$, a cycle in $G$ with
fewer than $m$ chords can be either one of the $2d$-cycles $C^{(v)}$ or it
must include some pairs of antipodal vertices, as described above. However, in
the latter case it must include both chords $uv$ and $u^{\prime}v^{\prime}$,
and hence its length must be at least $2d+2$. ∎

######  Corollary 5.5.

$\gamma_{4}(n)\geq\gamma_{5}(n)\geq 2(\frac{n}{4})^{1/3}+O(1),$
$\gamma_{7}(n)\geq 2(\frac{n}{4})^{1/4}+O(1)$

and

$\gamma_{11}(n)\geq 2(\frac{n}{4})^{1/6}+O(1).$

###### Proof.

Let $q$ be a prime power, these statements follows from three infinite
families of Moore Graphs where $d=q+1$, and $g=6,8,12$. All these
constructions come from projective planes. For the case where $g=6,d=q+1$ we
recall the construction of $H$, the points vs. lines graph over the finite
field of order $q$. This is a bipartite $(q+1)$-regular graph, whose two sides
are called $P$ and $L$ for ”points” and ”lines”, with $|P|=|L|=q^{2}+q+1$. The
girth of $H$ is $6$. As for the cases where $g=8,12$, and $d=q+1$ these graphs
are similarly incidence graphs of generalized Quadrangles and generalized
Hexagons [3].

∎

######  Corollary 5.6.

Let $q$ be a prime power then

$\gamma_{q}(n)\geq(n)^{\frac{4}{3q}}$

###### Proof.

This is based on a family of graphs due to Lazebnik, Ustimenko and Woldar [7].
For $q$ a prime power, they construct a $q$-regular graph $G(V,E)$ of order
$2q^{k-t+1}$ and girth $g\geq k+5$. Here $k\geq 1$ is an odd integer, and
$t=\lfloor\frac{k+2}{4}\rfloor$. Namely, $G$ is a $q$-regular graph with $n$
vertices and $g\geq\frac{4}{3}\log_{q}(q-1)\log_{q-1}(n)$ . ∎

##  6 Something on the general girth problem

Some of our results have a bearing on the girth problem for $d$-regular graphs
also for $d>3$. As shown in [11] and [8], every $(d,g)$-cage is $d$-edge-
connected, whence there is no loss in generality in considering only
$(d-1)$-edge-connected $d$-regular graphs $G=(V,E)$. As shown in [9], every
such graph has a $2$-factor $C$. In this view, we ask again about short cycles
with few chords in $G$, where a chord is an edge in $M:=E\setminus C$.

######  Definition 6.1.

$\gamma^{d}_{k}(n)$ is the smallest integer $g$ such every $d$-regular
$n$-vertex graph with a given $2$-factor $C$ has a cycle of length $\leq g$
with at most $k$ chords.

We illustrate the connection by proving the following lemma.

######  Lemma 6.2.

$\gamma^{d}_{2}(n)\leq\sqrt{\frac{2n}{d-2}}$.

###### Proof.

Again, for any set of vertices $S\subseteq V$, we denote

$S^{*}:=\\{v\in V|\text{~{}there is some~{}}u\in S\text{~{}such that~{}}uv\in
M\text{~{}is a chord}\\}.$

Let $A$ be an arc of length $k\leq\frac{2n}{d-2}$ then $|A^{*}|=(d-2)k$. Let
$u_{1},\dots,u_{k(d-2)}$ be the vertices of $A^{*}$ in cyclic order. For every
$i=1,\dots,k(d-2)$ we define the following $2$-chord cycle. It starts with the
chord $u_{i},u_{i}^{*}$, then proceeds along $C$ to $u_{i+1}^{*}$, traverses
the chord $u_{i+1},u_{i+1}^{*}$ and continues along $C$ to $u_{i}$. There are
$k(d-2)$ such cycles in total and as in the proof of Lemma 4.2, their total
length does not exceed $\leq n+\frac{k^{2}}{2}\cdot(d-2)$. Consequently the
average length of such cycle is bounded from above by

$\frac{n}{k(d-2)}+\frac{k}{2}.$

We take $k=\sqrt{\frac{2n}{d-2}}$ and conclude that at least one cycle has
length $\leq\sqrt{\frac{2n}{d-2}}$.

∎

## References

  * [1] Eiichi Bannai and Tatsuro Ito  “On finite Moore graphs”  In _Journal of the Faculty of Science, the University of Tokyo. Sect. 1 A, Mathematics_ 20, 1973, pp. 191–208
  * [2] N. Biggs and M. Hoare  “The sextet construction of cubic graphs”  In _Combinatorica_ 3, 1983, pp. 153–165
  * [3] Norman Biggs  “Algebraic Graph Theory”, Cambridge Mathematical Library, 1974
  * [4] R.. Damerell  “On Moore graphs”  In _Mathematical Proceedings of the Cambridge Philosophical Society_ 74.2 Cambridge University Press, 1973, pp. 227–236
  * [5] Paul Erdös and Horst Sachs  “Reguläre Graphen gegebener Taillenweite mit minimaler Knotenzahl”  In _Mathematics_ , 1963
  * [6] Geoffrey Exoo and Robert Jajcay  “Dynamic Cage Survey”  In _the electronic journal of combinatorics_ , 2013
  * [7] Felix Lazebnik, Vasiliy A. Ustimenko and Andrew J. Woldar  “A new series of dense graphs of high girth”  In _Bulletin of the American Mathematical Society_ 32, 1995, pp. 73–79
  * [8] Yuqing Lin, Mirka Miller and Christopher A. Rodger  “All (k;g)-cages are k-edge-connected”  In _Journal of Graph Theory_ 48, 2005, pp. 219–227
  * [9] Nathan Linial  “On Petersen’s graph theorem”  In _Discrete Mathematics_ 33, 1981, pp. 53–56
  * [10] Julius Petersen  “The theory of regular graphs”  In _Acta Mathematics_ 15, 1891, pp. 193–220
  * [11] Ping Wang, Xu Baoguang and Jianfang Wang  “A Note on the Edge-Connectivity of Cages”  In _Electron J Combin_ 10, 2003
  * [12] Alfred Weiss  “Girths of bipartite sextet graph”  In _Combinatorica_ , 1984, pp. 241–245


# Low-Depth Unitary Coupled Cluster Theory for Quantum Computation

Jia Chen  [<EMAIL_ADDRESS>Hai-Ping Cheng  [<EMAIL_ADDRESS>J. K. Freericks
[<EMAIL_ADDRESS>
###### Abstract

The unitary coupled cluster (UCC) approximation is one of the more promising
wave-function ansätze for electronic structure calculations on quantum
computers via the variational quantum eigensolver algorithm. However, for
large systems with many orbitals, the required number of UCC factors still
leads to very deep quantum circuits, which can be challenging to implement.
Based on the observation that most UCC amplitudes are small for weakly
correlated molecules, we devise an algorithm that employs a Taylor expansion
in the small amplitudes, trading off circuit depth for extra measurements.
Strong correlations can be taken into account by performing the expansion
about a small set of UCC factors, which are treated exactly. Near equilibrium,
the Taylor series expansion often works well without the need to include any
exact factors; as the molecule is stretched and correlations increase, we find
only a small number of factors need to be treated exactly.

UFL_Physics]Department of Physics, University of Florida, Gainesville, FL
32611, USA [QTP]Quantum Theory Project, University of Florida, Gainesville, FL
32611, USA UFL_Physics]Department of Physics, University of Florida,
Gainesville, FL 32611, USA [QTP]Quantum Theory Project, University of Florida,
Gainesville, FL 32611, USA Georgetown_Physics]Department of Physics,
Georgetown University, 37th St. and O St., NW, Washington, DC 20057, USA

##  1 Introduction

Quantum computing provides a new paradigm for manipulating information
according to the laws of quantum mechanics; it is expected to provide an
advantage over classical computation for some scientific problems.1 As
envisioned by Richard Feynman, one of those problems is simulating quantum
mechanical systems.2 Focusing on molecular quantum systems, quantum chemistry
is poised to be among the fields of study that could benefit from the
developments of quantum computation. An example for how this can be achieved
is given by the phase estimation algorithm 3, 4 for computing energy
eigenvalues and preparing energy eigenstates. This algorithm has been
simulated and shown to work5; it will provide opportunities for solving
problems that cannot be solved on classical computers. Unfortunately, phase
estimation is quite challenging to implement, because it requires controlled
time evolution of the system. Hence, it has extremely deep circuits if the
time evolution of the molecule is treated exactly in a conventional basis for
the Hamiltonian.

Current quantum hardware is limited due to noise and decoherence. This near-
term hardware is called noisy intermediate-scale quantum (NISQ)6. They can
only work with low-depth circuits on a modest number of qubits. This precludes
direct application of many quantum algorithms, such as the phase-estimation
algorithm. To be specific, we have to work with two constraints in the near
term: (i) the number of qubits will remain relatively small and (ii) the
allowed circuit depth will remain low due to gate fidelity and decoherence
errors. To take advantage of existing and near-term quantum computers, the
variational quantum eigensolver (VQE) has been proposed as a low-depth
alternative to quantum phase estimation. 7 It is a hybrid quantum-classical
method, and it shows great promise.8 VQE needs to be carried out both on
quantum and classical computers: on the quantum computer, quantum states
depending on a set of variational parameters are prepared, and the expectation
value of the Hamiltonian is then measured. Next, that set of parameters is
optimized on classical computers and the loop is repeated until converged.
But, this approach suffers from the need for higher-depth circuits as the
ansatz wavefunction becomes more complex and from the appearance of barren
plateaus in the optimization space (which is exacerbated by the noise and
decoherence of NISQ machines). Our approach attempts to resolve both of these
issues by using a quadratic expansion of the energy in terms of the
variational amplitudes, which allows for significantly lower depth in the
required circuits and an optimization that is performed entirely on the
classical computer. But, it does so at the expense of requiring significantly
more measurements.

Originally proposed as a wave-function ansatz for quantum chemistry about four
decades ago,9, 10, 11 unitary coupled cluster theory (UCC) has gained renewed
attention because, in its factorized form, it can serve as an efficient state
preparation method for the VQE. Usually, the UCC ansatz starts from the
Hartree-Fock (HF) reference state in the occupation number representation;
then the different UCC factors are applied to the HF states in sequence; this
excites the HF state by including terms from unoccupied orbitals, but it also
includes de-excitation terms when the prepared state includes terms that can
be de-excited by the next UCC factor. General speaking, the circuit depth for
UCC state preparation is proportional to the number of excitations applied,
especially if they are the same rank excitation. For example, a molecule with
$N$ orbitals, has $N^{4}$ doubles excitations, which are usually the most
important excitations to include in the ansatz. As a result, including all (or
just a fraction of) all possible singles and doubles excitations already
requires a circuit depth that is prohibitively high for large molecules,
especially so on NISQ hardware.

In this contribution, we show how to improve this situation, by requiring only
a small subset of UCC factors to be applied to the reference state on the
quantum computer. The insight behind this comes from the fact that most
amplitudes $\theta$ have small absolute values. This suggests that they can be
expanded in a Taylor series about $\theta=0$, truncated at quadratic order and
then optimized. Doing this from the reference HF state is only viable when the
molecule is weakly correlated, which holds predominantly near the equilibrium
configuration bond distances and angles. But, how many UCC factors need to be
treated exactly when carrying out this approach as the correlations are
increased (due to stretching)? This is the question we address in this work.
We find the number remains relatively small, implying that such an approach
can enable more complex molecules to be treated on currently available NISQ
machines. Similar ideas have been used in other contexts as well. A quadratic
expansion about a density-matrix-renormalization group calculation was
performed successfully for a carbon dimer12 and the approach was also
investigated for a quantum-inspired algorithm using an ansatz that can be
constructed solely from Clifford circuits, which can be easily simulated on a
classical computer 13. Our approach is similar to both of these earlier works,
but has a number of differences as well.

##  2 Theory and Method

###  2.1 Unitary Coupled Cluster Theory (UCC) in Factorized Form and Operator
Identity for UCC Factors

In unitary coupled cluster (UCC) theory, the trial wave-function is expressed
in an exponential form, given by

$\displaystyle|\Psi_{\textrm{UCC}}\rangle=\exp(\hat{\sigma})|\Psi_{0}\rangle,$
(1)

where $|\Psi_{0}\rangle$ is the reference state and the operator
$\hat{\sigma}$ is an anti-Hermitian combination of particle-hole excitation
and de-excitation:

$\displaystyle\hat{\sigma}$ $\displaystyle=\hat{T}-\hat{T}^{\dagger};$ (2)
$\displaystyle\hat{T}$
$\displaystyle=\sum_{i}^{occ}\sum_{a}^{vir}\theta_{i}^{a}\hat{a}_{a}^{\dagger}\hat{a}_{i}+\sum_{ij}^{occ}\sum_{ab}^{vir}\theta_{ij}^{ab}\hat{a}_{a}^{\dagger}\hat{a}_{b}^{\dagger}\hat{a}_{j}\hat{a}_{i}+\cdots~{}.$
(3)

Here, the rotation angles $\theta$ are the variational parameters. We use
letters from the start of the alphabet $a$, $b$, $c,\ldots$ to denote the
virtual orbitals, with respect to the reference state, and letters from the
middle of the alphabet $i$, $j$, $k,\ldots$ to denote the occupied orbitals in
the reference state. To simplify the notation, we express a general $n$-fold
excitation operator as
$\hat{a}^{ab\dots}_{ij\dots}=\hat{a}^{\dagger}_{a}\hat{a}^{\dagger}_{b}\dots\hat{a}_{j}\hat{a}_{i}$
(with the corresponding de-excitation operator being its Hermitian conjugate).
We work with a factorized form for the UCC, which is given by

$\displaystyle|\Psi_{\textrm{UCC}}\rangle=U_{\textrm{UCC}}|\Psi_{0}\rangle=\prod_{k}e^{\theta_{k}\sigma_{k}}=\prod_{ij\cdots}^{occ}\prod_{ab\cdots}^{vir}\exp[\theta_{ij\cdots}^{ab\cdots}(\hat{a}_{ij\cdots}^{ab\cdots}-\hat{a}_{ab\cdots}^{ij\cdots})]|\Psi_{0}\rangle.$
(4)

The factorized form is generally different from an ansatz that puts all
operators in one exponential. But, because we are doing a variational
calculation and there is flexibility given by the needed chemical accuracy,
this factorized form is usually sufficient to achieve chemical accuracy, if
enough factors are included. Indeed, if factors are repeated, it can be used
to approximate the original UCC ansatz via the Trotter product formula.

For a general UCC factor, we derived a general operator identity based on a
hidden SU(2) algebra.14, 15, 16 It is

$\displaystyle\begin{split}&U^{a_{1}\dots a_{n}}_{i_{1}\dots
i_{n}}=\exp[\theta(\hat{a}^{a_{1}\dots a_{n}}_{i_{1}\dots
i_{n}}-\hat{a}^{i_{1}\dots i_{n}}_{a_{1}\dots
a_{n}})]=1+\sin\theta(\hat{a}^{a_{1}\dots a_{n}}_{i_{1}\dots
i_{n}}-\hat{a}^{i_{1}\dots i_{n}}_{a_{1}\dots a_{n}})\\\
&+(\cos\theta-1)[\hat{n}_{a_{1}}\dots\hat{n}_{a_{n}}(1-\hat{n}_{i_{1}})\dots(1-\hat{n}_{i_{n}})+(1-\hat{n}_{a_{1}})\dots(1-\hat{n}_{a_{n}})\hat{n}_{i_{1}}\dots\hat{n}_{i_{n}}].\end{split}$
(5)

Here the number operators are of the form $\hat{n}=\hat{a}^{\dagger}\hat{a}$.
If rotation angle $\theta=0$, the UCC factor becomes the identity:
$U(0)=\mathbb{I}$.

We can take the derivative of Eq. (5):

$\displaystyle\begin{split}&\frac{d\hat{U}^{a_{1}\dots a_{n}}_{i_{1}\dots
i_{n}}(\theta)}{d\theta}=\cos\theta(\hat{a}^{a_{1}\dots a_{n}}_{i_{1}\dots
i_{n}}-\hat{a}^{i_{1}\dots i_{n}}_{a_{1}\dots a_{n}})\\\
&-\sin\theta[\hat{n}_{a_{1}}\dots\hat{n}_{a_{n}}(1-\hat{n}_{i_{1}})\dots(1-\hat{n}_{i_{n}})+(1-\hat{n}_{a_{1}})\dots(1-\hat{n}_{a_{n}})\hat{n}_{i_{1}}\dots\hat{n}_{i_{n}}].\end{split}$
(6)

When we evaluate the derivative at $\theta=0$, it becomes the operator term in
the exponent, namely

$\displaystyle\frac{d\hat{U}^{a_{1}\dots a_{n}}_{i_{1}\dots
i_{n}}(\theta)}{d\theta}|_{\theta=0}=\hat{a}^{a_{1}\dots a_{n}}_{i_{1}\dots
i_{n}}-\hat{a}^{i_{1}\dots i_{n}}_{a_{1}\dots a_{n}}=\hat{\sigma}^{a_{1}\ldots
a_{n}}_{i_{1}\ldots i_{n}}.$ (7)

The derivative of the wavefunction with respect to one rotation angle
immediately follows as

$\displaystyle\frac{dU_{\textrm{UCC}}}{d\theta_{k}}=\hat{U}_{n}\cdots\hat{U}_{k+1}\frac{d\hat{U}_{k}}{d\theta_{k}}\hat{U}_{k-1}\cdots\hat{U}_{2}\hat{U}_{1}.$
(8)

Evaluated at $\theta_{k}=0$, a simple result is obtained:

$\displaystyle\frac{dU_{\textrm{UCC}}}{d\theta_{k}}\Big{|}_{\vec{\theta}=0}=\frac{d\hat{U}_{k}}{d\theta_{k}}\Big{|}_{\theta_{k}=0}=\hat{\sigma}_{k}.$
(9)

###  2.2 Quadratic Angle Expansion

A Taylor expansion of the expectation value of the energy around the point
where all angles vanish ($\vec{\theta}=0$) becomes

$\displaystyle\langle\hat{H}(\vec{\theta})\rangle=\langle\hat{H}(0)\rangle+\sum_{k}b_{k}\theta_{k}+\frac{1}{2}\sum_{k,m}A_{km}\theta_{k}\theta_{m}+\mathcal{O}(\theta^{3})$
(10)

where,

$\displaystyle b_{k}$
$\displaystyle=\frac{d\langle\hat{H}(\vec{\theta})\rangle}{d\theta_{k}}\Big{|}_{\vec{\theta}=0}=\langle\Psi_{0}|\hat{U}^{\dagger}(0)\hat{H}\frac{d\hat{U}(0)}{d\theta_{k}}|\Psi_{0}\rangle+\langle\Psi_{0}|\frac{d\hat{U}^{\dagger}(0)}{d\theta_{k}}\hat{H}\hat{U}(0)|\Psi_{0}\rangle$
$\displaystyle=\langle\Psi_{0}|\hat{H}\hat{\sigma}_{k}|\Psi_{0}\rangle+\langle\Psi_{0}|\hat{\sigma}_{k}^{\dagger}\hat{H}\hat{|}\Psi_{0}\rangle=2\text{Re}\langle\Psi_{0}|\hat{H}\hat{\sigma}_{k}|\Psi_{0}\rangle,$
(11)

and

$\displaystyle
A_{km}=\frac{d^{2}\langle\hat{H}(\vec{\theta})\rangle}{d\theta_{k}d\theta_{m}}\Big{|}_{\vec{\theta}=0}$
$\displaystyle=\langle\Psi_{0}|\hat{U}^{\dagger}(0)\hat{H}\frac{d^{2}\hat{U}(0)}{d\theta_{k}d\theta_{m}}|\Psi_{0}\rangle+2\langle\Psi_{0}|\frac{\hat{U}^{\dagger}(0)}{d\theta_{k}}\hat{H}\frac{d\hat{U}(0)}{d\theta_{m}}|\Psi_{0}\rangle$
$\displaystyle+\langle\Psi_{0}|\frac{d^{2}\hat{U}^{\dagger}(0)}{d\theta_{k}d\theta_{m}}\hat{H}\hat{U}(0)|\Psi_{0}\rangle$
$\displaystyle=2\langle\Psi_{0}|\hat{\sigma}^{\dagger}_{k}\hat{H}\hat{\sigma}_{m}|\Psi_{0}\rangle+2\text{Re}\langle\Psi_{0}|\hat{H}(\hat{\sigma}_{k}\hat{\sigma}_{m})|\Psi_{0}\rangle.$
(12)

Note that the real part is not necessary in most calculations, since the
wavefunction is usually expanded in terms of real coefficients; this can
change in the presence of a magnetic field or with spin-orbit coupling. The
ordering of the operators, however, is important. Note that in Eq. (2.2), we
have used the following notation:

$\displaystyle(\hat{\sigma}_{k}\hat{\sigma}_{m})=\begin{cases}\hat{\sigma}_{k}\hat{\sigma}_{m},&\text{if
}m\geq k\\\ \hat{\sigma}_{m}\hat{\sigma}_{k}&\text{otherwise}\end{cases}.$
(13)

The ordering of the UCC factors matters in the second derivative matrix
because of second term in Eq. (2.2). The de-excitation operator may also apply
when the first operator can be de-excited. Since
$\hat{\sigma}_{k}|\textrm{HF}\rangle$ and
$\hat{\sigma}_{k}\hat{\sigma}_{m}|\textrm{HF}\rangle$ are both single
determinants, the above expressions for $A$ and $b$ are just many-body
Hamiltonian matrix elements in the Hartree-Fock basis and with respect to
many-body product states (determinants). This means one can perform an initial
minimization, about the point where all angles are zero, from the Hamiltonian,
expressed in the Hartree-Fock basis and extended to include matrix elements
for all states that are required in the $b_{k}$ vector and the $A_{km}$
matrix.

To minimize the energy with respect to the angles, we take the derivative of
Eq. (10) about the point where each $\theta_{i}=0$ and set the derivative to
zero in order to find the minimum energy. We have

$\displaystyle\frac{d\langle\hat{H}(\vec{\theta})\rangle}{d\theta_{i}}\Big{|}_{\vec{\theta}=0}=b_{i}+\sum_{j}A_{ij}\theta_{j}=0$
(14)

In matrix form, the angles that minimize the energy are the solution of the
following system of linear equations:

$\displaystyle\mathbf{A}\cdot\vec{\theta}=-\vec{b}.$ (15)

Angles that minimize the energy can be obtained either by inversion of the
matrix $\mathbf{A}$, or by solving linear system Eq. (15) by row-reduction (or
by using sparse-matrix iterative techniques).

The correlation energy, which is the difference between the total energy and
the Hartree-Fock energy becomes

$\displaystyle
E_{corr}=\langle\hat{H}(\vec{\theta})\rangle-\langle\hat{H}(0)\rangle=\vec{b}\cdot\vec{\theta}_{min}+\frac{1}{2}\vec{\theta}^{T}_{min}\cdot\mathbf{A}\cdot\vec{\theta}_{min}.$
(16)

Note how this calculation is quite straightforward and simple to carry out, it
just requires generating Hartree-Fock matrix elements and solving the linear
matrix equation.

###  2.3 Exact UCC Reference

For this quadratic expansion to be accurate, it is necessary for the angles to
be small. This is not the case for strongly correlated systems. To extend this
scheme to correlated systems, we can treat factors with large angles more
carefully. After separating factors with large angles $\\{\hat{\sigma_{l}}\\}$
and small angles $\\{\hat{\sigma_{s}}\\}$ into two groups, UCC factors with
large angles are used to construct an exact UCC reference wave-function and
angles are optimized:

$\displaystyle|\Psi^{\textrm{UCC}}_{0}\rangle=\prod_{l}e^{\theta_{l}\hat{\sigma_{l}}}|\textrm{HF}\rangle.$
(17)

This reference state naturally contains more than one determinant, and its
contribution to the correlation energy can be calculated as

$\displaystyle
E_{0}^{corr}=\langle\Psi^{\textrm{UCC}}_{0}|\hat{H}|\Psi^{\textrm{UCC}}_{0}\rangle-
E_{\textrm{HF}}.$ (18)

In the second step, angles for all UCC factors are expanded to second order,
as described in last section. The difference is that, for factors used in the
UCC reference, their angles are expanded with respect to their optimized
values, instead of around zero. The presence of these nonzero angles in the
reference state affects the computation of the $b$ vector and the $A$ matrix
for all of their elements. The total energy after the quadratic expansion
becomes, in this case,

$\displaystyle\langle\hat{H}(\vec{\theta})\rangle=\langle\Psi^{\textrm{UCC}}_{0}|\hat{H}|\Psi^{\textrm{UCC}}_{0}\rangle+\sum_{k}b_{k}\theta_{k}+\frac{1}{2}\sum_{k,m}A_{km}\theta_{k}\theta_{m}+\mathcal{O}(\theta^{3})$
(19)

Again, $b_{k}$ and $A_{km}$ can be obtained by taking the corresponding
derivatives. But, the two groups of UCC factors, corresponding to large and
small angles, have different expressions for the derivatives. For the vector
$b_{k}$, if $k$ is within the group of small angles, elements can be
calculated simply by replacing the reference state $|\Psi_{0}\rangle$ in Eq.
(2.2) by $|\Psi_{0}^{\textrm{UCC}}\rangle$ as defined in Eq. (17); otherwise,
$b_{k}$ can be calculated as a derivative of UCC wave-function, by inserting
Eq. (6) into Eq. (8). We have an exact expression for the derivative of each
UCC factor. Furthermore, we know exactly where to place the derivative
operator within the calculation. The matrix $A_{km}$ can be obtained in a
similar way—if two factors $k,m$ are both small angle factors, then Eq. (2.2)
can be employed with $|\Psi_{0}^{\textrm{UCC}}\rangle$ replacing
$|\Psi_{0}\rangle$ . If one or two of $k,m$ are large angle factors,
derivatives with respect to $|\Psi_{0}^{\textrm{UCC}}\rangle$ need to be
taken, just like the case for $b_{k}$, already discussed. It is a simple
exercise to work out the exact formulas (we do not write them out here).

The energy minimization is again carried out to find $\theta_{min}$ for both
large and small angles. Then the large angles used to construct the UCC
reference wave-function are updated by
$\theta^{\prime}_{l}=\theta_{l}+\theta_{l}^{min}$. These $\theta^{\prime}_{l}$
values are then used to construct the new UCC reference wavefunction, which is
used for the new quadratic angle expansion. This procedure is iterated until
the calculation has converged to a fixed point for both the large and the
small angles. The total correlation energy now has three contributions:

$\displaystyle
E_{corr}=E_{0}^{corr}+\vec{b}\cdot\vec{\theta}_{min}+\frac{1}{2}\vec{\theta}^{T}_{min}\cdot\mathbf{A}\cdot\vec{\theta}_{min}.$
(20)

The computational procedure described above can be carried out as a hybrid
quantum-classical algorithm. The preparation of the UCC reference state needs
to be performed on a quantum computer. Then the quantities $b_{k}$ and
$A_{km}$ are measured with respect to the prepared UCC reference state. As we
will show later, only a small number of factors are required in the UCC
reference state, which greatly reduces the circuit depth on a quantum
computer. As a trade off, the $b_{k}$ and $A_{km}$ require many more
measurements. But of course, even a standard VQE procedure will require
calculating at least something like the $b_{k}$ for a gradient-based
minimizer, or to choose the best operator to pick from an operator pool. If
this tradeoff is worthwhile requires a more detailed analysis. But, note that
there are likely some measurements that can be replaced by cubic expansion
about $\vec{\theta}=0$, because they might not depend strongly on the large
angles. This analysis can be performed on a classical computer prior to the
quantum computation and can greatly reduce the required measurements.

One potential issue in this procedure is the appearance of an instability in
the minimization step for strongly correlated cases. The origin of this
instability is that the inverse of $\mathbf{A}$ may be ill-defined (due to
zero or near zero eigenvalues). To overcome this, we use a pseudo-inverse of
$\mathbf{A}$, which is constructed as follows. First, $\mathbf{A}$ is
diagonalized via a similarity transformation with the matrix $Q$:
$\mathbf{A}=\mathbf{Q}\mathbf{\Lambda}\mathbf{Q}^{-1}$. Then, a cutoff
$\epsilon$ is applied to the eigenvalues included in $\Lambda$. If an
eigenvalue is smaller than $\epsilon$, the corresponding diagonal element of
$\Lambda^{\prime}$ is set to zero. The reduced set of eigenvalues is placed in
the diagonal matrix $\Lambda^{\prime}$, and the pesudoinverse of $\mathbf{A}$
is calculated as
$\mathbf{A}^{-1}\approx\mathbf{Q}\mathbf{\Lambda^{\prime}}^{-1}\mathbf{Q}^{-1}$,
where the terms in $\bf{\Lambda}^{\prime}$ that were set equal to zero are not
inverted in computing the pseudoinverse—they remain set equal to zero.
Thisapproach is the same as a singular-value decomposition of a matrix,
relative to a cutoff $\epsilon$. Then, the angles that minimize the energy are
found from $\theta_{min}=-\mathbf{A}^{-1}\cdot\vec{b}$.

##  3 Results and Discussion

###  3.1 Near equilibrium

We implemented this quadratic UCC (qUCC) method using integrals generated by
PySCF. We performed calculations on a set of small molecules with the ccpvdz
basis set. To benchmark the calculations, we use almost exact energies from
the semistochastic heat-bath configuration interaction calculation as a
reference.17 The results are summarized in Fig. 1.

While an exact UCC calculation is always variational, the qUCCSD approximation
need not have its energy bounded by the full configuration interaction (FCI)
from below, because of the potential error from the truncated Taylor
expansion. This means it need not be strictly variational. For several
molecules in Fig. 1, the errors are indeed negative. However, if we compare
the absolute error, qUCCSD is more accurate than CCSD, which has similar
computational scaling. Comparing to CCSD(T), qUCCSD is not as accurate, but is
not expected to be either. What is surprising is that qUCCSD is consistently
not that far away from CCSD(T).

Figure 1:  Error, (E-EFCI), from CCSD, CCSD(T) and qUCCSD calculations on a
subset of Gaussian-2 molecules. The basis set is ccpvdz. O2 and S2 are spin
triplets, and NO is a spin doublet. All others are spin singlets.

###  3.2 Chemical Bond Stretching

Thje quadratic expansion of the unitary coupled cluster theory using HF ground
state as reference, as described earlier, shows many similar characteristics
with the older XCC approaches 18, and other linearized coupled-cluster methods
19 developed by Rodney Bartlett and his colleagues. But even at second order,
the derivatives from a factorized form of the UCC depend on the ordering,
while for a conventional UCC, they do not. The common weakness of the XCC
methods is that they diverge when near-degeneracy is present in the HF states,
so they cannot treat level crossings or near level crossings in the potential
energy surface. This often occurs for bond stretching and breaking situations.
One way to overcome this difficulty for the quadratic expansion of the
factorized form of the unitary coupled cluster theory is to use multi-
determinant reference states, as detailed in Section. 2.3.

To demonstrate this method, we performed calculations for the bond stretching
of a H2O molecule with the 6-31G basis set. In total, this system has 74
single and 2240 double excitations. We first did a geometry optimization, and
then optimized the H-O bond length. It becomes 0.96Å and the optimized H-O-H
angle is 104.5∘. To study the situations of bond stretching, we gradually
increase the bond from its equilibrium length to 2.74Å, while keeping the
H-O-H angle fixed. Standard quantum chemistry methods inclduing full
configuration interaction (FCI) and coupled-cluster singles and doubles (CCSD)
were carried to test against the qUCCSD with exact UCC reference states. Here
all the qUCCSD calculations were performed with 28 factors of large angles and
$\epsilon=0.1$ for pseudo-inverse procedure. Those 28 large angles factors are
determined from initial MP2 amplitudes. Results can be found in Fig. 2.

As expected, CCSD correlation energies are close to the exact FCI results when
the molecular geometries are close to equilibrium. But, CCSD has difficulties
when away from equilibrium; CCSD violates the variational principle and gives
lower energies then FCI when O-H bond length is larger then 2.2 Å. We also
find that qUCCSD with UCC reference usually gives better results than CCSD.
Close to equilibrium, qUCCSD gives similar results as CCSD, and when far
equilibrium, qUCCSD with UCC reference states has better behaviour then CCSD,
since it never violates variational principle.

Figure 2:  Panel (a) and panel (b): total correlation energies for the water
molecule as function of the H-O bond length. Here, we plot results for FCI
(black circles), CCSD (red squares) and qUCCSD (blue diamonds) with a UCC
reference state (that contains 28 exact UCC factors). Note that the ranges of
the plots differ in the two panels. Panel (c) error of the CCSD (red squares)
and qUCCSD (blue diamonds) results relative to the FCI as a function of the
H-O bond length. Note how the CCSD calculation becomes nonvariational at
strong coupling.

##  4 Conclusion

One of the main issues slowing down the ability for quantum computers to show
an advantage over classical computers is that current hardware can only run
codes that are quite short in circuit depth. In this situation, the only
advantage will occur due to the larger memory that a quantum computer has in
storing quantum states. The algorithm discussed here, denoted qUCC, is a
methodology that will allow quantum computers to aid in determining the
electronic structure of complex molecules much sooner, because it trades off
circuit depth for additional measurements. If those additional measurements
can be carried out, then we might see a quantum advantage sooner than later.

To illustrate how this methodology works, we showed that the number of exact
UCC factors needed in an electronic structure calculation on a quantum
computer can be greatly reduced from that of a standard approach. Our test
case (bond stretching of water molecule) shows better results can be achieved
with only a small fraction of factors (28 versus 2314) when constructing the
wavefunction. Our result compares the qUCC approach to a CC approach, but
results would be similar for a comparison to a standard UCC approach as well.
Our algorithm is one way to utilize low-depth quantum circuits to treat
molecules with large basis sets, which has been a major obstacle for applying
quantum computing to quantum chemistry.

JC and HPC are supported by the Department of Energy, Basic Energy Sciences as
part of the Center for Molecular Magnetic Quantum Materials, an Energy
Frontier Research Center under Award No. DE-SC0019330. JKF is supported from
the National Science Foundation under grant number CHE-1836497. JKF is also
funded by the McDevitt bequest at Georgetown University. This research used
resources of the National Energy Research Scientific Computing Center (NERSC),
a U.S. Department of Energy Office of Science User Facility operated under
Contract No. DE-AC02-05CH11231, and University of Florida Research Computing
systems. We also acknowledge useful discussions with Rodney Bartlett, Garnet
Chan, Joseph Lee, John Staunton, Cyrus Umrigar, Luogen Xu and Dominika Zgid.

## References

  * Nielsen and Chuang 2011 Nielsen, M. A.; Chuang, I. L. _Quantum Computation and Quantum Information_ ; Cambridge University Press, 2011
  * Feynman 1982 Feynman, R. P. Simulating physics with computers. _International Journal of Theoretical Physics_ 1982, _21_ , 467–488
  * Abrams and Lloyd 1997 Abrams, D. S.; Lloyd, S. Simulation of Many-Body Fermi Systems on a Universal Quantum Computer. _Phys. Rev. Lett._ 1997, _79_ , 2586–2589
  * Abrams and Lloyd 1999 Abrams, D. S.; Lloyd, S. Quantum Algorithm Providing Exponential Speed Increase for Finding Eigenvalues and Eigenvectors. _Phys. Rev. Lett._ 1999, _83_ , 5162–5165
  * Aspuru-Guzik et al. 2005 Aspuru-Guzik, A.; Dutoi, A. D.; Love, P. J.; Head-Gordon, M. Simulated Quantum Computation of Molecular Energies. _Science_ 2005, _309_ , 1704–1707
  * Preskill 2018 Preskill, J. Quantum Computing in the NISQ era and beyond. _Quantum_ 2018, _2_ , 79
  * Peruzzo et al. 2014 Peruzzo, A.; McClean, J.; Shadbolt, P.; Yung, M.-H.; Zhou, X.-Q.; Love, P. J.; Aspuru-Guzik, A.; O’Brien, J. L. A variational eigenvalue solver on a photonic quantum processor. _Nat. Commun._ 2014, _5_ , 4213
  * Cao et al. 2019 Cao, Y.; Romero, J.; Olson, J. P.; Degroote, M.; Johnson, P. D.; Kieferová, M.; Kivlichan, I. D.; Menke, T.; Peropadre, B.; Sawaya, N. P. D.; Sim, S.; Veis, L.; Aspuru-Guzik, A. Quantum Chemistry in the Age of Quantum Computing. _Chemical Reviews_ 2019, _119_ , 10856–10915
  * Kutzelnigg 1977 Kutzelnigg, W. In _Methods of Electronic Structure Theory_ ; Schaefer, H. F., Ed.; Springer US: New York, NY, USA, 1977; Chapter 5, pp 129–188
  * Koch and Kutzelnigg 1981 Koch, S.; Kutzelnigg, W. Comparison of CEPA and CP-MET methods. _Theor. Chim. Acta_ 1981, _59_ , 387–411
  * Kutzelnigg and Koch 1983 Kutzelnigg, W.; Koch, S. Quantum chemistry in Fock space. II. Effective Hamiltonians in Fock space. _J. Chem. Phys._ 1983, _79_ , 4315–4335
  * Sharma and Alavi 2015 Sharma, S.; Alavi, A. Multireference linearized coupled cluster theory for strongly correlated systems using matrix product states. _J. Chem. Phys._ 2015, _143_ , 102815
  * Mitarai et al. 2020 Mitarai, K.; Suzuki, Y.; Mizukami, W.; Nakagawa, Y. O.; Fujii, K. Preprint, arXiv:2011.09927
  * Evangelista et al. 2019 Evangelista, F. A.; Chan, G. K.-L.; Scuseria, G. E. Exact parameterization of fermionic wave functions via unitary coupled cluster theory. _J. Chem. Phys._ 2019, _151_ , 244112
  * Xu et al. 2020 Xu, L.; Lee, J. T.; Freericks, J. K. Test of the unitary coupled-cluster variational quantum eigensolver for a simple strongly correlated condensed-matter system. _Mod. Phys. Lett. B_ 2020, _34_ , 2040049
  * Chen et al. 2021 Chen, J.; Cheng, H.-P.; Freericks, J. K. Quantum-Inspired Algorithm for the Factorized Form of Unitary Coupled Cluster Theory. _J. Chem. Theory Comput._ 2021, _17_ , 841–847
  * Yao et al. 2020 Yao, Y.; Giner, E.; Li, J.; Toulouse, J.; Umrigar, C. J. Almost exact energies for the Gaussian-2 set with the semistochastic heat-bath configuration interaction method. _J. Chem. Phys._ 2020, _153_ , 124117
  * Bartlett et al. 1989 Bartlett, R. J.; Kucharski, S. A.; Noga, J.; Watts, J. D.; Trucks, G. W. Some Consideration of Alternative Ansätz in Coupled-Cluster Theory. 1989, 125–149
  * Bartlett and Musiał 2007 Bartlett, R. J.; Musiał, M. Coupled-cluster theory in quantum chemistry. _Rev. Mod. Phys._ 2007, _79_ , 291–352