# Quantum Alternating Operator Ansatz (QAOA) beyond
low depth with gradually changing unitaries

Vladimir Kremenetski  Applied and Engineering Physics, Cornell University,
Ithaca, NY 14853  NASA Ames Research Center, Moffett Field, CA 94035, USA
USRA Research Institute for Advanced Computer Science, Mountain View, CA
94043, USA  Anuj Apte  NASA Ames Research Center, Moffett Field, CA 94035, USA
Department of Physics, University of Chicago, Chicago, IL 60637, USA  Tad Hogg
NASA Ames Research Center, Moffett Field, CA 94035, USA  Stuart Hadfield  NASA
Ames Research Center, Moffett Field, CA 94035, USA  USRA Research Institute
for Advanced Computer Science, Mountain View, CA 94043, USA  Norm M. Tubman
<EMAIL_ADDRESS>NASA Ames Research Center, Moffett Field, CA 94035,
USA

(September 3, 2024)

###### Abstract

The Quantum Approximate Optimization Algorithm and its generalization to
Quantum Alternating Operator Ansätze (QAOA) is a promising approach for
applying quantum computers to challenging problems such as combinatorial
optimization and computational chemistry. In this paper, we study the
underlying mechanisms governing the behavior of QAOA circuits beyond shallow
depth in the practically relevant setting of gradually varying unitaries. We
use the discrete adiabatic theorem, which complements and generalizes the
insights obtained from the continuous-time adiabatic theorem primarily
considered in prior work. Our analysis explains some general properties that
are conspicuously depicted in the recently introduced QAOA performance
diagrams. For parameter sequences derived from continuous schedules (e.g.
linear ramps), these diagrams capture the algorithm’s performance over
different parameter sizes and circuit depths. Surprisingly, they have been
observed to be qualitatively similar across different performance metrics and
application domains. Our analysis explains this behavior as well as entails
some unexpected results, such as connections between the eigenstates of the
cost and mixer QAOA Hamiltonians changing based on parameter size and the
possibility of reducing circuit depth without sacrificing performance.

##  1 Introduction

Quantum computing presents numerous promising approaches to challenging
computational problems across a wide variety of applications. Among these
approaches are the Quantum Approximate Optimization Algorithm [1] and Quantum
Alternating Operator Ansatz (QAOA) [2], developed to solve classical
combinatorial optimization problems, and later extended to more general tasks
such as state preparation [3, 4]. In its simplest realization, given a cost
Hamiltonian to optimize, the protocol starts with the ground state of a mixer
Hamiltonian and then proceeds by alternately evolving the state under the two
Hamiltonians $p$ times each. While there are results on QAOA behavior for
small $p$ [5, 6, 7, 8, 9, 10, 11] and in some cases $p\gg 1$ [1, 12, 13],
there remains the challenge of understanding the behavior of QAOA more
broadly. Generally, QAOA is characterized by parameters that represent how
long the Hamiltonians are simulated at each step in the protocol, and
therefore parameter setting is expected to become challenging as $p$ grows
[14, 15, 16, 17, 13].

To better understand the behavior of QAOA, we introduce an approach to
analyzing deep circuits with gradually varying unitaries. This extends beyond
the small-parameter regime of QAOA considered as Trotterized annealing in
prior work [1, 18, 19, 20]. Through our analysis, we show such deep circuits
exhibit surprising phenomena. One is the ground state of the mixer Hamiltonian
directly connecting to a highly excited state of the cost Hamiltonian,
resulting in poor QAOA performance even in an adiabatic limit. Another is
shallower circuits outperforming deeper ones at large parameters due to
_inherently_ non-adiabatic effects (performing comparably to deeper circuits
at smaller parameters). We also show how these phenomena, along with small-
parameter approximations, explain a general qualitative feature [4] in
performance for deep QAOA circuits with slowly varying parameters.

Specifically, we apply the discrete adiabatic theorem [21]. This theorem is a
generalization of the continuous adiabatic theorem, where a state evolving in
time tracks an eigenstate across a product of gradually varying unitaries
rather than the eigenstate of a slowly changing Hamiltonian. Since unitary
eigenvalues can wrap around the complex unit circle and produce avoided
crossings, when QAOA parameters are large, this wrap-around leads to the mixer
ground state becoming connected to a high-lying cost excited state. This
change in connectivity is described by the mathematical theory of holonomy
[22] that generalizes the well-known phenomenon of Berry phase [23, 24].
Consequently, the state resulting from QAOA has high support on the high-lying
excited state in the discrete adiabatic limit (arbitrarily large $p$). Outside
of this limit, we characterize how well the state tracks the changing
eigenstate through small gaps using a discretized Landau-Zener formula.

Figure 1: Schematic QAOA performance diagram. The vertical axis characterizes
the sum of the pairs of angles’ magnitudes in the QAOA schedule. Shading
indicates performance, with lighter shading corresponding to higher
performance, e.g., higher overlap with the target state or lower expected
cost. The blue labels indicate the qualitative behavior regions described in
Section 5.

This new analysis explains the performance features of QAOA seen in a recent
study [4] that applied QAOA with parameters derived from a linear ramp to
electronic structure problems. Qualitatively similar behavior in performance
was observed for intermediate $p$ and in the $p\gg 1$ limit for large angles
across a wide variety of problems, a generality that persisted with nonlinear,
smooth schedules. The general nature of this behavior is sketched in Fig. 1.
The labels in Fig. 1 indicate regions with qualitatively different
performance, though the regions are not entirely disjoint and the boundaries
between them are not sharp. To the left and bottom of the diagram (labeled
Initial State), the performance is low and close to that of the starting
state; while in the lower-right region (High), the performance is high and
approaches continuous adiabatic behavior. The upper-right region (Low) has
very poor performance. At the bottom, QAOA in the Annealing region closely
approximates continuous annealing. Toward the upper left, the Ridge region has
relatively high performance. At large values of $p$, there is a sudden drop in
performance when the angle size exceeds a threshold value: an abrupt change
between High and Low regions. In this paper, we argue that this performance
drop is due to a change in connectivity of eigenstates associated with QAOA
operators, which causes the QAOA state vector to end in an excited state of
the cost Hamiltonian.

The paper is structured as follows. We introduce QAOA in Section 2. Section 3
introduces the discrete adiabatic theorem. Section 4 studies the connections
between eigenstates of the product pairs of unitaries that make up a QAOA
protocol. Section 5 introduces and explains the qualitative generality of QAOA
performance diagrams. Section 6 gives examples with more complex performance
diagram behavior, and Section 7 illustrates how our results apply to schedules
with gradually changing angles beyond those easily captured by performance
diagrams and how these diagrams scale with problem size. Additional technical
derivations are provided as appendices.

##  2 QAOA with gradually changing parameters

For QAOA, a given optimization problem on $n$ variables is encoded as a cost
Hamiltonian $H_{\textnormal{cost}}$ on $n$ qubits. Level-$p$ QAOA uses
$H_{\textnormal{cost}}$ and a suitably chosen mixer Hamiltonian
$H_{\textnormal{mix}}$ to apply $p$ parameterized unitary operators

$U_{\textnormal{{qaoa}}}^{(j)}=e^{-i\beta_{j}H_{\textnormal{mix}}}e^{-i\gamma_{j}H_{\textnormal{cost}}},$
(1)

for $j=1,\ldots,p$, with parameters $\vec{\beta}=(\beta_{1},\ldots,\beta_{p})$
and $\vec{\gamma}=(\gamma_{1},\ldots,\gamma_{p})$, also referred to as
“angles”. We refer to the operators $\exp(-i\beta_{j}H_{\textnormal{mix}})$
and $\exp(-i\gamma_{j}H_{\textnormal{cost}})$ as the mixer and cost unitaries,
respectively. We consider the general setting for QAOA, where the mixer and
the cost Hamiltonians do not commute but are otherwise arbitrary [2], which
includes a wide range of problems from combinatorial optimization as well as
quantum chemistry [4].

QAOA starts with an easily prepared initial state $\ket{\psi_{0}}$, which is
typically the ground state of $H_{\textnormal{mix}}$. For example, for the
originally proposed transverse-field mixer (also known as the $X$-mixer)
$H_{\textnormal{mix}}=-(\sigma^{x}_{1}+\dots+\sigma^{x}_{n})$,
$\ket{\psi_{0}}=\ket{+}^{\otimes n}$, an equally weighted superposition over
the computational basis. QAOA produces the output state

$\ket{\psi_{p}(\vec{\gamma},\vec{\beta})}=U_{\textnormal{{qaoa}}}^{(p)}\ldots
U_{\textnormal{{qaoa}}}^{(1)}\ket{\psi_{0}}.$ (2)

Ideally, this QAOA output state has high overlap with the ground state of
$H_{\textnormal{cost}}$. For combinatorial optimization, it suffices to have
non-negligible support on the ground state in order to solve the problem with
repeated state preparation and measurement, though for challenging problems we
often must settle for an approximate solution i.e., obtaining sufficient
support on a low-lying eigenstate. On the other hand, chemistry applications
such as electronic structure problems often require a much higher overlap with
the true ground state [4].

A common measure of the effectiveness of QAOA is the expected cost (or energy)
$\langle H_{\textnormal{cost}}\rangle$ of the output state
$\ket{\psi_{p}(\vec{\gamma},\vec{\beta})}$. Typically, it may be efficiently
estimated via repeated preparations and measurements. In some cases this
quantity is used as a proxy for the true overlap with the ground state, which
may be as difficult to compute as the underlying problem itself. On the other
hand, for small or moderately sized benchmarking problems we may often compute
the ground state overlap directly [4, 25]. We provide empirical evidence that
both metrics produce similar phenomena, though we primarily use ground state
overlap as the QAOA performance metric.

We consider QAOA parameter schedules with gradually changing parameters, i.e.,
schedules for which $|\gamma_{j}-\gamma_{j+1}|,|\beta_{j}-\beta_{j+1}|$ are
small (relative to the inverse of the norms of $H_{\textnormal{mix}}$ and
$H_{\textnormal{cost}}$). Specifically, we consider a continuous schedule to
be one generated through samples from continuous functions
$\beta(f),\gamma(f)$ on $[0,1]$, so that $\beta_{j}=\beta(f_{j})$,
$\gamma_{j}=\gamma(f_{j})$ where

$f_{j}=\frac{j}{p+1},$ (3)

for $j=1,\ldots,p$, and $p\gg 1$. For simplicity, we focus on linear ramps

$\gamma(f)=\Delta f\quad\mbox{and}\quad\beta(f)=\Delta(1-f),$ (4)

where $\Delta$ is a constant. Section 7 discusses more general schedules.

For the linear schedule of Eqs. (3) and (4), the _QAOA unitary_ of Eq. (1)
becomes

$U_{\textnormal{{qaoa}}}(\Delta,f)=e^{-i\Delta(1-f)H_{\textnormal{mix}}}e^{-i\Delta
fH_{\textnormal{cost}}}$ (5)

for fixed $\Delta$. Similar linear schedules are frequently considered for
QAOA in optimization settings [26, 27, 28, 14, 29, 30, 31]. In particular,
this choice alleviates the parameter setting problem, which generally suffers
from the curse of dimensionality as $p$ becomes large [32], and so enables the
study of much deeper QAOA circuits [4] than is possible for general parameter
choices. Hence, our primary focus in this work will be the effect of
increasing the depth $p$ for fixed problems of given size $n$.

Figure 2: Performance diagram displaying squared overlap of the QAOA output
state with the cost ground state, for the pair of Hamiltonians defined in Eq.
15.

With this choice of schedule the number of free QAOA parameters is
conveniently reduced to just two: $p$ and $\Delta$. Plotting performance vs.
these parameters gives a 2D plot we call a “performance diagram” [4], such as
shown in Fig. 2 and illustrated above in Fig. 1.111In [4] the performance
diagrams are also referred to as “QAOA phase diagrams”.

##  3 The Discrete Adiabatic Regime

For parameters derived from continuous schedules discussed in Section 2, the
QAOA unitary changes very little between each step when $p$ is large. This
section describes QAOA in this regime from the viewpoint of the discrete
adiabatic theorem.

|
---|---
(a) | (b)
Figure 3: Eigenvalues of $H_{\textnormal{{qaoa}}}$ (solid) and
$H_{\textnormal{inst}}$ (dashed) as a function of $f$ for the 2-level example
of Eq. (15) with $\Delta=1.15$. Fig. 6b shows the corresponding eigenvalues of
the unitary $U_{\textnormal{{qaoa}}}$. (a) $H_{\textnormal{{qaoa}}}$ chosen to
be continuous and match $H_{\textnormal{inst}}$ at $f=0$. (b)
$H_{\textnormal{{qaoa}}}$ chosen to match $H_{\textnormal{inst}}$ at both
$f=0$ and $f=1$.

###  3.1 Discrete Adiabatic Evolution

Consider a unitary operator $U(s)$ that is a continuous function of a
parameter $s\in[0,1]$. Starting with an eigenvector $\ket{v_{0}}$ of $U(0)$,
define

$\ket{v_{j}}=U(s_{j})\ket{v_{j-1}}$ (6)

for $j=1,..,L$ where $s_{j}$ uniformly samples the interval, and the unitary
varies only slightly from one iteration to the next when $L$ is large:
$\left||U(s_{j+1})-U(s_{j})|\right|=\mathcal{O}(1/L)$, where $||\cdot||$
denotes the spectral norm.

For sufficiently large $L$, $\ket{v_{j}}$ remains close to an eigenvector of
$U(s_{j})$ for each $j$, assuming these eigenvectors are not degenerate for
any $s_{j}$. In particular, the final vector $\ket{v_{L}}$ will be close to an
eigenvector of $U(s=1)$, within an error of size $\mathcal{O}(1/L)$ [21, 34].

Thus, products of gradually changing unitary matrices lead to the discrete
adiabatic behavior of state vectors that track the evolving eigenvectors [21,
35, 36, 34]. As in the continuous adiabatic case, smaller gaps (Euclidean
distance) between $U(s)$ eigenvalues neighboring that of the eigenvector being
tracked require larger $L$ to maintain the same final overlap [21, 34].

###  3.2 Application to QAOA

The QAOA initial state is typically an eigenvector of the mixer and so also of
$U_{\textnormal{{qaoa}}}(\Delta,0)$. The QAOA circuit of Eq. (2) applies a
product of unitary operators defined by Eq. (5) to the initial state. At each
step the QAOA unitary changes by at most
$\|U_{\textnormal{{qaoa}}}(\Delta,f_{j+1})-U_{\textnormal{{qaoa}}}(\Delta,f_{j})\|=O(\Delta(\|H_{\textnormal{mix}}\|+\|H_{\textnormal{cost}}\|)/p)$.
Consequently, for sufficiently large $p$, the discrete adiabatic theorem
guarantees that, in the absence of degeneracies, the initial state evolves to
_some_ eigenstate of the cost Hamiltonian when $p$ is sufficiently large.
However, unlike the case of slowly evolving Hamiltonians, the changing
unitaries can have different connections between eigenstates at different
values of $\Delta$ as described in Section 4. This can lead to poor QAOA
performance even when $p$ is large enough to be in the adiabatic regime. Thus,
approaching the discrete adiabatic limit is not a sufficient condition for
good QAOA performance.

###  3.3 Contrasting Discrete and Continuous Adiabatic Regimes

The discrete adiabatic theorem is analogous to but distinct from the better-
known continuous-time adiabatic theorem for evolution with slowly changing
Hamiltonians, as considered in quantum annealing. For example, the ramp
schedule of Eq. (4) corresponds to a Hamiltonian

$H_{\textnormal{inst}}(f)=(1-f)H_{\textnormal{mix}}+fH_{\textnormal{cost}}.$
(7)

The evolution of a state over a time $T$ due to a changing Hamiltonian arises
from the Schrödinger equation. With the substitution $t=fT$, this is

$\frac{d}{df}\ket{\psi(f)}=-iTH_{\textnormal{inst}}(f)\ket{\psi(f)}.$ (8)

The (continuous) adiabatic theorem states that if $\ket{\psi(0)}$ is the
$\text{n}^{\text{th}}$ eigenstate of $H_{\textnormal{inst}}(0)$ then, as
$T\rightarrow\infty$, $\ket{\psi(1)}$ is arbitrarily close to the
$\text{n}^{\text{th}}$ eigenstate of $H_{\textnormal{inst}}(1)$, provided the
Hamiltonian changes smoothly and the evolving eigenvector of
$H_{\textnormal{inst}}(f)$ is not degenerate for any $0\leq f\leq 1$ [37, 38].

Discretizing the Schrödinger equation over small time steps $\delta t$
produces change from the unitary operator

$U_{\textnormal{inst}}=e^{-i\delta tH_{\textnormal{inst}}}.$ (9)

QAOA evolution of Eq. (2) approximates this continuous evolution in the limit
of

$\Delta\rightarrow 0,\ p\Delta=T.$ (10)

This is because when $\Delta$ is small, the QAOA unitary of Eq. (5) is a
Trotter approximation to Eq. (9) if $\Delta=\delta t$. Thus in this limit, the
discrete and continuous behaviors agree.

The continuous adiabatic limit is obtained if we have

$\Delta\rightarrow 0,\ p\Delta\rightarrow\infty.$ (11)

The discrete adiabatic limit, by contrast, is more general, obtained at:

$p\rightarrow\infty.$ (12)

In the context of QAOA, the continuous adiabatic limit (vanishing “switching
time” $\Delta$ and infinitely fine discretization) is a special case of the
discrete adiabatic limit (infinitely fine discretization) and in general their
behaviors can differ significantly as discussed in Section 4.

One example of this (perhaps surprising) difference is that it is possible to
connect the ground state of a mixer Hamiltonian to an excited state of the
cost Hamiltonian without encountering a degeneracy. This arises because the
eigenvalues of unitary operators exist on the unit circle of the complex
plane, allowing for degeneracy-free connections between, for example, the
mixer ground state and the cost maximal excited state (for a similar reason,
excited-ground connections can emerge between the quasi-energies of Floquet
operators [39, 40]). In the case of non-singular, bounded Hamiltonians, where
eigenvalues lie along the real line, this cannot happen.

To further elucidate the difference between the discrete and continuous cases,
consider a Hamiltonian $H_{\textnormal{{qaoa}}}$ corresponding to the unitary
operator of Eq. (5):

$e^{-i\Delta H_{\textnormal{{qaoa}}}}=U_{\textnormal{{qaoa}}}\equiv
e^{-i\Delta(1-f)H_{\textnormal{mix}}}e^{-i\Delta fH_{\textnormal{cost}}}$ (13)

The eigenvalues of $H_{\textnormal{{qaoa}}}$ are only defined up to arbitrary
integer multiples of $2\pi/\Delta$. By analogy with the behavior of
$H_{\textnormal{inst}}$, one might expect to be able to choose these multiples
such that $H_{\textnormal{{qaoa}}}(f)$ is a continuous function of $f$ and
matches the initial and final Hamiltonians used with annealing, i.e.,
$H_{\textnormal{{qaoa}}}=H_{\textnormal{mix}}$ at $f=0$ and
$H_{\textnormal{{qaoa}}}=H_{\textnormal{cost}}$ at $f=1$. In particular, for
small $\Delta$, the Baker-Campbell-Hausdorff (BCH) formula [37] relates
$H_{\textnormal{{qaoa}}}$ to $H_{\textnormal{inst}}$:

$H_{\textnormal{{qaoa}}}=H_{\textnormal{inst}}-\frac{i\Delta}{2}f(1-f)[H_{\textnormal{mix}},H_{\textnormal{cost}}]+\dots$
(14)

where the omitted terms to the right involve higher-order commutators of
$H_{\textnormal{mix}}$, $H_{\textnormal{cost}}$ and higher powers of $\Delta$
and $f$. Each of these terms is 0 at $f=0$ and $f=1$, so at those values
$H_{\textnormal{{qaoa}}}=H_{\textnormal{inst}}$, thereby matching
$H_{\textnormal{mix}}$ and $H_{\textnormal{cost}}$ at those values of $f$. If
the series converges to a continuous function of $f$, then the BCH formula
provides a choice for $H_{\textnormal{{qaoa}}}$ that is continuous and matches
$H_{\textnormal{mix}}$ at $f=0$ and $H_{\textnormal{cost}}$ at $f=1$.

The behaviors of $H_{\textnormal{{qaoa}}}$ and $H_{\textnormal{inst}}$ become
categorically different for sufficiently large $\Delta$. In that case, the
eigenvalues of $U_{\textnormal{{qaoa}}}$ vary (as a function of $f$ going from
0 to 1) from those corresponding to the ground state energy of the mixer to
eigenvalues corresponding to a cost excited state without encountering a
degeneracy. Therefore, any continuously changing $H_{\textnormal{{qaoa}}}$ no
longer matches $H_{\textnormal{cost}}$ at $f=1$ (if starting at
$H_{\textnormal{mix}}$ at $f=0$) but rather has eigenvalues of
$H_{\textnormal{cost}}$ shifted by an integer multiple of $2\pi/\Delta$. For
such a choice of $H_{\textnormal{{qaoa}}}$, ground states still evolve to
ground states for these shifted energies. Conversely, choosing to define
$H_{\textnormal{{qaoa}}}$ to be the mixer Hamiltonian at $f=0$ and the cost
Hamiltonian at $f=1$ results in at least one discontinuity in the spectrum of
$H_{\textnormal{{qaoa}}}$ at intermediate $f$. Since the BCH formula in Eq.
(14) fixes $H_{\textnormal{{qaoa}}}$ to have such endpoints, this implies that
the formula fails to converge to a continuous function of $f$ at such a value
of $\Delta$.

Fig. 3 is an example of this behavior of $H_{\textnormal{{qaoa}}}$ for the
2-level example discussed in Section 4. This shows that if we choose to make
$H_{\textnormal{{qaoa}}}$ continuous then $H_{\textnormal{{qaoa}}}(1)\neq
H_{\textnormal{inst}}(1)$ due to shifts in the eigenvalues by $2\pi/\Delta$,
as in Fig. 3a. Alternatively, we can define $H_{\textnormal{{qaoa}}}$ to match
$H_{\textnormal{inst}}$ at both $f=0$ and $f=1$, but this requires a
discontinuity in $H_{\textnormal{{qaoa}}}$, as in Fig. 3b.

These observations indicate that focusing on the Hamiltonian corresponding to
the QAOA unitary operator can lead to ambiguity in interpreting its behavior.

##  4 QAOA Eigenvector Behavior

This section describes the behavior of the eigenvalues and eigenvectors of the
QAOA operator defined in Eq. 5. In particular, we discuss conditions under
which the ground state of $H_{\textnormal{mix}}$ at $f=0$ does not connect to
the ground state of $H_{\textnormal{cost}}$ as the QAOA operator evolves.

Specifically, we consider paths through the space of parameters $f$ and
$\Delta$, which determine the QAOA angles in Eq. (4). For the linear ramp
schedule, $\Delta$ is constant while $f$ starts at zero and ends at one. Fig.
4 illustrates two such paths.

Figure 4: Two paths through the parameter space with fixed $\Delta=0.4$
(purple) and $\Delta=1.15$ (orange). The red dot indicates the parameters,
$\Delta=\Delta_{\textnormal{crit}}=2\pi/7$ and $f=1$, at which the 2-level
example of Eq. (15) has a degeneracy due to eigenvalue wrap-around as
discussed in Section 4.2.1.

###  4.1 Eigenstate Connections and Wrap-Around

######  Definition.

For a given path in parameter space starting at $f=0$ and ending at $f=1$, we
say a mixer eigenstate is “connected” to a cost eigenstate if it continuously
changes into the cost eigenstate over the given path.

In the case of degenerate eigenvalues, we can extend the notion of connection
to being between eigenspaces i.e. a state in a mixer eigenspace continuously
changing into a state of a cost eigenspace along the path. We consider the
degenerate case briefly in Section 4.5.

Consider the eigenstates at f=0 and f=1 as two sides of a bipartite graph.
Given the set of mixer eigenstates $\\{\mathcal{U}_{1},...\mathcal{U}_{k}\\}$
and the set of cost eigenstates $\\{\mathcal{V}_{1},...\mathcal{V}_{m}\\}$,
the pair $\\{\mathcal{U}_{i},\mathcal{V}_{j}\\}$ is an edge in the graph for a
particular path through parameter space if eigenstate $\mathcal{U}_{i}$
connects to eigenstate $\mathcal{V}_{j}$. As we shall show, changing $\Delta$
can change these edges.

A key case considered in this paper are the connections for a pair of
eigenstates that are the highest- and lowest-energy eigenstates of
$H_{\textnormal{mix}}$, though our results apply more generally. An important
concept related to changing connections is “wrap-around”, illustrated in Fig.
5

######  Definition.

“Wrap-around” is the phenomenon of a pair of distinct eigenvalues of
$U_{\textnormal{{qaoa}}}(\Delta,f)$ at fixed $f$ wrapping around the unit
circle in the complex plane far enough to intersect and then overtake each
other as $\Delta$ increases from 0.

Figure 5: A sketch of the eigenvalues on the unit circle in the complex plane,
for a three-level $U_{\textnormal{{qaoa}}}$ with increasing values of $\Delta$
and with fixed $0\leq f\leq 1$. For $\Delta$ close to zero, the eigenvalues
are clustered near 1 on the right-most point of the circle as illustrated in
the first circle. As $\Delta$ increases, eigenvalues move around the unit
circle at different speeds. Eventually, the fastest-moving eigenvalue, A,
overtakes and then passes the eigenvalue, C (”wraps around” with it), as shown
in the third circle.

As shown in Section 4.2, wrap-around at $f=0,1$ caused by changing $\Delta$ is
intimately linked to the changing connections between mixer and cost
eigenstates. While wrap-around can happen at either value $f=0$ or $f=1$, we
will, without loss of generality, focus on wrap-around at $f=1$ in the
remaining sections.

Figure 6: Negative argument of the eigenvalues of unitary operators as a
function of $f$ for the 2-level example defined by Eq. (15) for the paths
shown in Fig. 4. (a and b) QAOA unitaries $U_{\textnormal{{qaoa}}}$ of Eq. (5)
for (a) $\Delta=0.4$ and (b) $\Delta=1.15$. A curve is solid (dashed) if its
value at f=0 is that associated with the mixer’s ground (excited) state
energy. (c and d) cost unitaries of Eq. (16) for these values of $\Delta$.
Figure 7: Evolution of the eigenvalues $\lambda$ of the 2-level example QAOA
unitary operator on the unit circle in the complex plane as a function of $f$
for the case of $\Delta=1.15$. The solid and dashed curves correspond to the
ground and excited states of the mixer at $f=0$, respectively. These are the
same eigenvalues whose negative arguments are shown in Fig. 6(b).

###  4.2 QAOA Unitary Degeneracies and Eigenvalue Wrap-around

The eigenvalues of unitary operators are on the unit circle in the complex
plane. We graphically depict them by plotting the negative of the arguments of
these eigenvalues in Fig. 6. Thus for a unitary operator $U=e^{-iH}$ derived
from a Hamiltonian $H$, this plot shows the eigenvalues of $H$ modulo $2\pi$
in the range $-\pi$ to $\pi$ \- note that this means that $U$ can be
degenerate even when $H$ isn’t.

We illustrate the behavior of the QAOA unitary from Eq. 5 with a two-level
example defined by the paths through parameter space shown in Fig. 4 and the
Hamiltonians

$H_{\textnormal{mix}}=\begin{bmatrix}0.5&-0.5\\\
-0.5&0.5\end{bmatrix}\quad\text{and}\quad
H_{\textnormal{cost}}=\begin{bmatrix}0&0\\\ 0&7\end{bmatrix}.$ (15)

####  4.2.1 Eigenvalue Behavior: A Two-level Example

This section describes the behavior of the eigenvalues of the QAOA unitary for
the 2-level example of Eq. (15). The top half of Fig. 6 shows how eigenvalues
change with $f$ along the two paths shown in Fig. 4.

For the smaller $\Delta$ value, the QAOA unitary connects the mixer
Hamiltonian ground state to the cost Hamiltonian ground state. For the larger
$\Delta$ value, Fig. 6(b) shows that the connection changes: the mixer
Hamiltonian ground state connects to the cost Hamiltonian excited state.

This change in connection arises from eigenvalues of the QAOA operator at
$f=0$ and $f=1$ wrapping around the complex unit circle as $\Delta$ is
increased, as illustrated in Fig. 7. In particular, as $\Delta$ changes along
the vertical axes of Fig. 4, with $f=0$ or $f=1$, the set of eigenvectors
doesn’t change and the eigenvalues rotate around the unit circle linearly with
$\Delta$. In Fig. 6, this corresponds to the negative argument of one
eigenvalue increasing through $\pi$, switching to $-\pi$, reaching and then
passing the negative argument of the other eigenvalue.

The first wrap-around is determined by the largest eigenvalue of either
$H_{\textnormal{mix}}$ or $H_{\textnormal{cost}}$. In this example, that
maximum eigenvalue is the excited energy of $H_{\textnormal{cost}}$. Thus to
better understand this wrap-around, we contrast it with that of the cost
unitary on its own,

$U_{\textnormal{cost}}(\Delta,f)=e^{-i\Delta fH_{\textnormal{cost}}}.$ (16)

From Eq. (15), the negative arguments of the eigenvalues of
$U_{\textnormal{cost}}$ are, respectively, $0$ and $7\Delta f\bmod 2\pi$
shifted to the range $-\pi$ to $\pi$. The bottom half of Fig. 6 shows these
expressions for the same $\Delta$ values used in the top half. For the smaller
$\Delta$, the values are $0$ and $7\Delta$ at $f=1$. On the other hand, for
the larger $\Delta$, just above $2\pi/7$, the “excited state” eigenvalue of
$U_{\textnormal{cost}}$ wraps around the unit circle and goes past the “ground
state” eigenvalue at $f=1$. Therefore, the eigenvalues cross each other at
some $f$ between 0 and 1, as seen Fig. 6(d).

Generically, the cost and mixer Hamiltonians do not commute and so the
introduction of mixer unitary to form $U_{\textnormal{{qaoa}}}$ lifts the
degeneracy and turns the level crossing of $U_{\textnormal{cost}}$ into an
avoided crossing for $U_{\textnormal{{qaoa}}}$.

Additional degeneracies occur at values of $f$ other than 0 or 1 for
sufficiently large $\Delta$, as illustrated for the two-level example in Fig.
8.

Figure 8: Magnitude of the difference between the two eigenvalues of the two-
level example as a function of $f$ and $\Delta$. The green points indicate
locations of degenerate eigenvalues. In addition, the entire bottom edge
consists of degenerate eigenvalues, since the QAOA unitary is the identity for
all $f$ when $\Delta=0$ .

####  4.2.2 Eigenvalue Behavior: General Case and Definitions

Figure 9: Negative arguments of the eigenvalues of $U_{\textnormal{{qaoa}}}$
for wrap-around leading to an avoided crossing using
$H_{\textnormal{mix}}=0.5\sum_{i=1}^{8}(I-\sigma_{x}^{i})$ and
$H_{\textnormal{cost}}$ with energies $0,2.5,3,3.5,4.5,5.5,6,7$ in the
computational basis, in order of bitstring value. The $0.0012\times 0.0016$
inset shows the avoided crossing between the wrap-around eigenvalues which
occurs at the location indicated by the arrow.

This section describes the general case of two distinct, initially non-
degenerate eigenvalues which become degenerate due to wrapping around the unit
circle as $\Delta$ increases. The generalization to more than two (possibly
initially degenerate) eigenvalues wrapping around with each other is addressed
in Section 4.5.

Eigenvalue wrap-around at a given $(\Delta,f)$ can lead to avoided crossings
at neighboring parameters. Without loss of generality, we can consider the
pair of cost unitary eigenvalues corresponding to the highest and lowest
energies of the cost Hamiltonian, which determine the eigenvalues of the QAOA
operator at $f=1$. As $\Delta$ increases, these eigenvalues are the first pair
to wrap around the unit circle and cross each other.

Away from $f=1$, the crossing caused by the two cost eigenvalues can become
avoided due to the mixer unitary- in that case, the two eigenvalues of the
QAOA unitary will not cross and will continue to avoid each other even for
significantly larger $\Delta$, just as in Fig. 6(b). In this case, the mixer
ground and highest eigenstates become connected to different cost eigenstates
than they were at smaller values of $\Delta$. This is illustrated for an
eight-level system in Fig. 9, where the intersection of the eigenvalues
leading to the ground and highest excited states results in an avoided
crossing. As $\Delta$ continues to increase, other pairs of eigenvalues wrap-
around at $f=0$ and $f=1$ and can create avoided crossings, which would lead
to more mixer eigenstates becoming connected to different cost eigenstates
than they were at small $\Delta$.

This motivates defining some common terms for wrap-around and avoided
crossings.

######  Definition.

We call a degeneracy between two eigenvalues isolated if the point in
$(f,\Delta)$-space where the degeneracy takes place has no other parameter
points within some neighborhood where the two eigenvalues are equal.

An example of this is the degeneracy in our two-level example at
$(f=1,\Delta=2\pi/7)$ leading to an avoided crossing as $\Delta$ increases, as
seen from comparing Fig. 6(b) and Fig. 6(d).

######  Definition.

We call a degeneracy between two eigenvalues continuous if the set of points
in $(f,\Delta)$-space where the two eigenvalues are equal forms a continuous
curve.

As an example, Fig. 6(d) shows a continuous degeneracy, where the eigenvalues
of the cost unitary continue to cross after initially touching at $f=1$ and
the resulting degeneracy moves inward to $0<f<1$ as $\Delta$ increases.

######  Definition.

$\Delta_{\textnormal{crit}}$ is the smallest value of $\Delta>0$ at which the
ground state eigenvalue (of the mixer or cost) wraps around with another of
its eigenvalues and this leads to an isolated degeneracy at $f=0$ or 1,
respectively.

In the case of our two-level example, $\Delta_{\textnormal{crit}}=2\pi/7$ due
to an isolated degeneracy at $f=1$ and none below that value of $\Delta$. For
the same reason $\Delta_{\textnormal{crit}}$ is also $2\pi/7$ for the eight
level example in Fig. 9.

In summary, two conditions are jointly sufficient for two fixed-$\Delta$ paths
(with $\Delta$ values $\Delta_{1}<\Delta_{2}$) to have different connections
between the mixer and cost eigenstates. Firstly, that some eigenvalues wrap
around at some $\Delta_{1}<\Delta<\Delta_{2}$ at $f=0$ or $f=1$, and secondly
that there is an isolated degeneracy at the $\Delta$ of wrap-around and value
of $f$.

Some significant differences exist between two-level and larger systems.
Multiple consecutive wrap-arounds with several different eigenvalues, both by
those of $H_{\textnormal{cost}}$ and $H_{\textnormal{mix}}$, means that once
connection between the two ground eigenstates is severed, it might not be re-
established by further increases in $\Delta$. Further, since the mixer can
have off-diagonal elements that couple two wrapping cost eigenstates
indirectly (and vice versa for the cost), continuous degeneracies emerge in
nontrivial cases where the mixer and cost don’t commute. These include the
cases where $\Delta_{\textnormal{crit}}$ is larger than the value of $\Delta$
at which the highest excited eigenvalue first wraps around to meet the ground
state eigenvalue because this first wrap-around produces a continuous
degeneracy rather than an isolated one.

###  4.3 Eigenvector Swap

Section 3 states that in the discrete adiabatic limit, the QAOA state vector
tracks the eigenvectors of the QAOA unitary as we go from $f=0$ to $f=1$ if
starting from an eigenvector of the mixer Hamiltonian. Thus, it is important
to identify how the wrap-around behavior described in the previous section
affects the eigenvectors.

####  4.3.1 Two-Level Example

Figure 10: Paths of the QAOA eigenvector on the Bloch sphere starting from the
uniform superposition as parameters change along the small and large delta
paths of Fig. 4, purple and orange curves, respectively.

We first consider our two-level example and the two paths through parameter
space defined in Fig. 4.

For these paths, the evolution of the QAOA eigenvector starting at $\ket{+}$
is shown in Fig. 10. The eigenvector trajectory for the purple, small-$\Delta$
path goes from the ground state of the mixer Hamiltonian to the ground state
of the cost Hamiltonian. On the other hand, the eigenvector trajectory for the
orange, large-$\Delta$ path goes from the ground state of the mixer to the
excited state of the cost. Thus eigenvalue wrap-around is associated with a
change in connection between initial and final eigenvectors along these paths.

####  4.3.2 Eigenvector Swap from Wrap-Around at Isolated Degeneracies

The 2-level example shows the change in eigenstate connections when $\Delta$
is large enough for the first wrap around to occur. We generalize this
observation to $n$-level systems, showing that wrap around leads to the
eigenvectors involved in the change in eigenvector connections directly
swapping places (i.e., changing into one another along the path) without
contribution from any other eigenvectors.

We do this by constructing a closed path through the $f,\Delta$ parameter
space to show the swap near an isolated degeneracy from wrap-around implies
the same swap occurs during QAOA when $\Delta$ is above the value at which
that wrap-around takes place, but small enough to be below any other wrap
arounds.

Figure 11: Example path near an isolated degeneracy (red point) at $f=1$. The
path starts at point A, below the degeneracy, and ends at point B, above the
degeneracy and remains within a small distance $\epsilon$ of the degeneracy.

To evaluate the behavior of eigenvectors near an isolated degeneracy
corresponding to a wrap-around at $(f=1,\Delta=\Delta_{\textnormal{crit}})$,
consider a path within a small distance $\epsilon$ of the degeneracy that
starts at $f=1$ just below the degeneracy and ends at $f=1$ above it, as
illustrated by points A and B in Fig. 11. Such paths can pass arbitrarily
close to the degeneracy without encountering other degeneracies, so the
swapping $U_{\textnormal{{qaoa}}}$ eigenvectors of $U_{\textnormal{{qaoa}}}$
change continuously along the path. The wrap-around associated with this
degeneracy means the eigenvalues of $U_{\textnormal{{qaoa}}}$ associated with
the degeneracy switch their ordering between points A and B of the path.

The entire path is near the degeneracy, so $H_{\textnormal{mix}}$ is a small
perturbation to $H_{\textnormal{cost}}$, allowing us to describe the
eigenvalues and eigenvectors of $U_{\textnormal{{qaoa}}}$ along the path with
degenerate perturbation theory [41]. In the limit of $\epsilon\rightarrow 0$,
this theory shows that the evolving eigenvector of $U_{\textnormal{{qaoa}}}$
is a linear combination of the eigenvectors involved in the isolated
degeneracy. This linear combination starts with the ground state of
$H_{\textnormal{cost}}$ at point A of the path and ends with the excited state
at point B. Moreover, the exchange takes place over a smaller path interval
when the eigenvalue gap along the path is small. This generalizes to multiple
degenerate states [41], i.e. the evolution of eigenvectors involved in the
degeneracy remains in the subspace defined by those vectors for small paths
around the degeneracy.

####  4.3.3 Behavior near a degeneracy: an eight-level example

Figure 12: Negative arguments of the eigenvalues of $U_{\textnormal{{qaoa}}}$
near the wrap-around degeneracy at $\Delta=2\pi/7$ for the 8-level example in
Fig. 9. The values are shown as a function of $t$, ranging from 0 to 1 along
the semicircle path of Fig. 11 with $\epsilon=0.01$, starting from point A and
using a symmetric logarithmic scale to emphasize the two states involved in
the degeneracy. The inset shows the avoided crossing between these two
eigenvalues, which occurs at the location indicated by the arrow. The inset’s
range is $10^{-6}$ horizontally and $0.4\times 10^{-6}$ vertically.

To illustrate the behavior near the degeneracy, we use the 8-level example
shown in Fig. 9. Along this small path, Fig. 12 shows eigenvalues change only
a small amount, with wrap-around of the two eigenvalues involved in the
degeneracy.

In this example, the ground state of $H_{\textnormal{cost}}$ wraps around with
the highest excited state. The mixer does not directly couple these two
states, thereby illustrating a higher-order application of degenerate
perturbation theory [41].

Figure 13: Eigenvector swapping in the 8-level example as a function of path
parameter $t$ near the location of the avoided crossing on the semicircular
path from Fig. 11. The curves show the squared overlap of the
$U_{\textnormal{{qaoa}}}$ eigenvector with the eigenvectors of
$H_{\textnormal{cost}}$.

Fig. 13 shows how the $U_{\textnormal{{qaoa}}}$ eigenvector changes along the
semicircular path, expressed as a linear combination of the eigenvectors of
$H_{\textnormal{cost}}$. At $t=0$, i.e., point A on the path of Fig. 11, the
eigenvector is the ground state of $H_{\textnormal{cost}}$. At $t=1$, i.e.,
point B on the path, it is the highest excited state of
$H_{\textnormal{cost}}$. The figure shows that the change in eigenvector
occurs mainly near the avoided crossing in eigenvalues along the path, and
remains almost entirely in the subspace of the two eigenvectors involved in
the degeneracy. The other six eigenvectors contribute only slightly to the
$U_{\textnormal{{qaoa}}}$ eigenvector as it evolves from the ground to
highest-excited state of $H_{\textnormal{cost}}$. Perturbation theory shows
those slight contributions vanish in the limit $\epsilon\rightarrow 0$. Thus,
the behavior of the 8-level system near the degeneracy is well-approximated by
a swap within the 2-level subspace involved in the isolated degeneracy.

####  4.3.4 Eigenvector Swap for QAOA with Wrap-Around

Figure 14: A closed path relating QAOA eigenvector evolution to the swap at a
degeneracy at $f=1$ (indicated by the red point). The path consists of
vertical segments at $f=0$ and $f=1$, and horizontal segments with values of
$\Delta$ below and above the degeneracy:
$\Delta_{1}<\Delta_{\textnormal{crit}}<\Delta_{2}$. The dashed line indicates
a QAOA path with wrap-around and eigenvector swap. The labels indicate the
eigenvectors on various parts of the path, as described in the text.

A QAOA path through parameter space, i.e., from $f=0$ to $f=1$, does not,
typically, pass through a degeneracy. Thus the argument establishing the
eigenvector swap based on degenerate perturbation theory does not apply.
Nevertheless, when $\Delta$ is increased from below
$\Delta_{\textnormal{crit}}$ to above it, a swap occurs along the QAOA path.
To see this, we construct a closed path as illustrated in Fig. 14 to connect
behavior along the QAOA path to the swap at the degeneracy. Along the vertical
edge at the right, with $f=1$, the eigenvector changes from
$H_{\textnormal{cost}}$ ground to excited state at the degeneracy. However,
other than at the degeneracy, the eigenvector does not change. Along the left
vertical edge, with $f=0$, there is no change in the eigenvector, which is the
ground state of $H_{\textnormal{mix}}$. Along the horizontal path with
$\Delta=\Delta_{1}<\Delta_{\textnormal{crit}}$, the eigenvector of
$U_{\textnormal{{qaoa}}}$ continuously changes from the ground state of
$H_{\textnormal{cost}}$ to that of $H_{\textnormal{mix}}$ (there can be no
interactions with high-lying excited states yet as argued in Sec. 4.4). Thus,
on the horizontal portion of the path along
$\Delta=\Delta_{2}>\Delta_{\textnormal{crit}}$ (dashed line in Fig. 14) the
eigenvector continuously changes from the ground state of
$H_{\textnormal{mix}}$ to the excited state of $H_{\textnormal{cost}}$. That
is, the eigenvector swaps along this path.

Figure 15: Evolution of the eigenvector of the QAOA operator corresponding to
$\ket{+}$ at $f=0$ (i.e., the ground state of the mixer) along a closed path
in $f$ and $\Delta$ for the 2-level example. At each point along the path,
shown as the black rectangle, the plot indicates the location on the Bloch
sphere of the eigenvector relative to that location. The purple and orange
portions of the path correspond to the small and large $\Delta$ paths of Fig.
4, respectively. The Bloch axes are aligned so that the $\ket{+}$ state points
in the direction of increasing $f$ and the $\ket{+i}$ state points in the
direction of increasing $\Delta$.

We illustrate the relation between swap at the degeneracy and along the QAOA
path in Fig. 15 for the 2-level example. Section 4.5 discusses the case of
more than two states wrapping around at the degeneracy.

This argument shows the swap occurs on any path starting from the mixer ground
state and ending with $\Delta$ above $\Delta_{\textnormal{crit}}$ at $f=1$
provided it does not go through other degeneracies. In particular, the path
need not be linear so eigenvector swaps are not specific to linear ramp of Eq.
(4).

####  4.3.5 Topological Perspective on Eigenvector Connections

The eigenvectors of the QAOA operator (5) change continuously along paths
through parameter space. As a result, where an eigenvector connects as we move
through parameter space is determined entirely by where the path begins and
ends, and whether the path goes through any degeneracies. As illustrated in
Fig. 14 and Fig. 15, going around the closed path that starts and ends at the
degeneracy takes us to an eigenvector that differs from the initial
eigenvector.

In the familiar case of Berry phase [23], a closed loop in the parameter space
leads to a geometrical phase but does not lead to a change in the eigenvector
under consideration. The Berry (geometric) phase acquired along a closed path
depends on the area of the loop in parameter space, but the eigenvector swap
only depends on whether or not the path _goes through_ an isolated degeneracy
(rather than just containing one, which also distinguishes isolated
degeneracies from exceptional points in topological physics [42]).

The analysis of eigenvector behavior can be generalized since it only relies
on a closed path in the $(f,\Delta)$ space passing through a single isolated
degeneracy. For the more general case, the eigenvector that becomes degenerate
along the path will evolve into an orthogonal eigenvector at the end of path.
When the starting point of the closed path is degenerate, then isolated
degeneracy leads to an evolution into an orthogonal eigenspace.

Given a family of parameterized Hamiltonians, cyclic evolution along a closed
path can also induce interchanges of eigenvalues, with the initial and final
states having different eigenvalues. This permutation of eigenstates while
traversing a closed path in parameter space through a degeneracy, as described
in this section, corresponds to nontrivial holonomy of the path [22, 43]. For
discussion of holonomy in related applications see [36, 39, 44, 45, 46, 47].

A topological perspective on QAOA may provide insight into its generic
behaviors. For example, variation of the closed path does not change the
eigenvector swap behavior, provided the distorted path continues to pass
through the degeneracy. The portion of the path relevant for QAOA is the
connection between f=0 and f=1, whereas the vertical portions are
constructions that do not correspond to QAOA steps. Therefore, changes in the
path due to variation in schedules or implementation noise do not alter the
eigenvector swap behavior described here, provided the changes don’t result
the path in crossing additional degeneracies.

Another insight from topology is that as $\Delta$ increases the increasing
number of wrap arounds of the eigenvalues may lead to, in effect, a connection
between the mixer ground state at $f=0$ and a random cost state at $f=1$. If
this occurs, the large-$p$ performance of QAOA for large $\Delta$ will be
close to random guessing, in contrast to the performance for $\Delta$ just
above $\Delta_{\textnormal{crit}}$, where QAOA connects to the highest-energy
cost eigenstate, giving the worst possible expected cost. The topology of how
eigenstates connect when $\Delta$ is large may be a useful guide as to how to
adjust the step size (corresponding to a nonuniform schedule) to either track
or avoid tracking eigenvector swaps over narrow parameter intervals, in order
to increase the chances of QAOA reaching low cost eigenstates.

###  4.4 Eigenvalue Gaps Associated with Wrap-Around

As argued in Section 4.2, connections cost and mixer eigenstates can be
reorganized if wrap-around by the eigenvalues of the cost (or mixer) unitary
results in an avoided crossing. This section describes some properties of the
gaps associated with these avoided crossings, with the discussion applying
symmetrically to wrap-around caused by both cost and mixer eigenvalues.
Derivations for these properties are in Appendix B, with their precise
statements in the gap formula of Eq. 28 and Theorem 1.

Perturbation theory indicates that isolated degeneracies from wrap-arounds at
$f=0,1$ occur generically for most choices of cost and mixer. Since the size
of the encountered eigenvalue gaps affects how well a discrete evolution
tracks an eigenvector [34], we characterize the scaling of the gap from the
avoided crossing due to wrap-around. We show in Eq. 28 that for the specific
case of wrap-around between two non-degenerate cost eigenstates $\ket{x}$ and
$\ket{y}$, the gap size $|g|$ due to the avoided crossing from wrap-around at
$\Delta^{*},f=1$ _generically_ goes as

$|g|=2c_{\textnormal{eff}}^{\textnormal{x,y}}\delta^{k}+O(\delta^{k+1}),$ (17)

with relative error from the higher-order contribution vanishing as
$\delta\rightarrow 0$. In Eq. 17, $\delta=\Delta-\Delta^{*}$, $k$ is the
length of the shortest coupling path between the two wrapping cost eigenstates
through the mixer (referred to in this paper as the “coupling distance”),
$c_{\textnormal{eff}}^{\textnormal{x,y}}$ is an effective coupling computed
through the weighted sum of products of mixer off-diagonal couplings as given
in Eq. 31, and we have simplified it from Eq. 28 by assuming the mixer has
zero diagonals. While this paper only provides a method for computing
$c_{\textnormal{eff}}^{\textnormal{x,y}}$ for the wrap-around of non-
degenerate cost eigenvalues, the degenerate case also exhibits scaling
$O(\delta^{k})$ in the $\delta\rightarrow 0$ limit for mixer couplings between
degenerate cost eigenstates- similar to the gap scaling with low-lying excited
states found for NP-Complete problem instances in the continuous adiabatic
case [48]. While this scaling holds for most Hamiltonians, the special case of
the mixer and cost Hamiltonians being very sparse and local is discussed in
Appendix E.1, where the exponent can be significantly greater than the
coupling distance.

As a clarifying example, with the $X$ mixer and a cost Hamiltonian diagonal in
the computational basis, $k$ equals the Hamming distance between the states
and the coupling strength between states is 1. Another example is the
diffusion mixer, used in unstructured search, where all non-diagonal entries
are equal (and exponentially small). In that case, $k=1$, but due to the
exponentially small non-diagonal entries,
$c_{\textnormal{eff}}^{\textnormal{x,y}}$ and the gap are exponentially small.

Our derivation for the gap size is based on the lowest-order term of a sum of
contributions from different coupling paths. Thus it applies in the limit of
small $\delta$. For larger $\delta$, other paths could contribute, especially
those with much stronger couplings than the lowest-order term. For example,
consider a slight modification to the $X$ mixer: adding a small coupling, say,
$2^{-10}$, between the states $\ket{000}$ and $\ket{111}$ that are not coupled
by the $X$ mixer. Near the wrap around of these two states, specifically for
$\delta\ll 2^{-(10/3)}$, this coupling would dominate in its (small)
contribution to the gap over that of a 3-coupling path of the $X$ mixer
between the states with $c_{\textnormal{eff}}^{\textnormal{x,y}}=1$. However,
for larger $\delta$ the $k=3$ path would dominate.

In the case where the gap size is small compared to the gaps with neighboring
cost eigenvalues of the wrapping eigenvalues, the formula is quite accurate.
For example, in Fig. 12, Eq. 28 predicts a gap size of $4.761\times 10^{-8}$
compared to the numerically computed gap size of $4.766\times 10^{-8}$.
Further, if $k\geq 2$, then the gap from wrap-around at $f=1$ occurs at
$1-(\delta/\Delta_{\textnormal{crit}})+O(\delta^{2})$ with the $X$-mixer and a
cost Hamiltonian diagonal in the computational basis. We also show in Appendix
B.1.2 that, for $k\geq 2$, the exchange of eigenvectors occurs approximately
symmetrically about the avoided crossing from wrap-around.

Isolated degeneracies from eigenvalues wrapping around the complex unit circle
can also occur for $0<f<1$, as illustrated in Fig. 8, though these do not
change connections between eigenstates at $f=0$ and $f=1$, save for paths that
go directly through them. We prove through Theorem 1 that such “intermediate”
isolated degeneracies do not occur at $\Delta$ smaller than the value for
which the first pair of eigenvalues wraps around at $f=0,1$. Therefore,
generically, the first isolated degeneracies from wrap-around due to
increasing $\Delta$ are the ones at the endpoints $f=0,1$. Unlike most of the
previous results in this section, this result holds regardless of the
degeneracy of the states experiencing wrap-around. In fact, a consequence of
the Theorem’s proof is that the highest excited eigenvalue is closest to the
ground eigenvalue at $f=0,1$ rather than in the middle, meaning no
interactions between the two eigenstates can take place before wrap-around at
$f=0,1$.

###  4.5 Wrap-around of Degenerate Eigenvalues

In Section 4.4 most of our quantitative results apply to two initially non-
degenerate eigenvalues wrapping around, and this is the main focus of this
paper’s quantitative analysis. When the two eigenvalues are degenerate, more
complicated dynamics emerge. This section describes this complexity for the
wrap-around at $\Delta_{\textnormal{crit}}$.

The multiplicities of the cost eigenvalues are independent of $\Delta$ so
there are always the same number of linearly independent eigenvectors
continuously evolving into the eigenvectors of each cost eigenspace. Consider
the generic case where $\Delta_{\textnormal{crit}}$ occurs when the highest
eigenvalue wraps around with the ground eigenvalue and, without loss of
generality, suppose this occurs at $f=1$. Let $\mathcal{U}_{0}$ be the ground
eigenspace of the mixer and let $\mathcal{V}_{0}$ be the ground eigenspace of
the cost, with $D^{U}_{0}$ and $D^{V}_{0}$ their respective dimensions. If the
total multiplicity of eigenvalues wrapping around at $f=1$ ($f=0$) with
$\mathcal{V}_{0}$ ($\mathcal{U}_{0}$) is greater than $D^{V}_{0}$
($D^{U}_{0}$), then all the states that were going to the cost ground state
originally will go to some cost excited state - the cost (mixer) excited
eigenspaces “push out” all of the original states. However, if the total
multiplicity of wrapping cost excited states doesn’t exceed the dimension of
the cost ground eigenspace (nor mixer excited states for mixer ground
eigenspace), then some of the eigenvectors that continuously evolved to the
cost ground eigenspace at lower $\Delta$ continue to do so. Therefore, for
degenerate ground eigenvalues, the $\Delta$ at which connection between mixer
and cost ground eigenspaces is completely severed is determined not
necessarily by wrap-around with the maximal excited energy, but by the
smallest $\Delta$ at which the multiplicity of wrapping excited eigenvalues
exceeds the multiplicity of the ground eigenvalue at $f=0$ or $f=1$ (whichever
comes first).

##  5 Understanding QAOA performance diagrams

As described in the Introduction, QAOA performance diagrams exhibit similar
qualitative behaviors for a variety of schedules, mixers and problems,
including those of classical optimization and quantum chemistry [4]. This
section explains these behaviors and their generality using the
$U_{\textnormal{{qaoa}}}$ eigenstate connection changes discussed in Section
4, conditions on when the QAOA state vector tracks the changing eigenvectors,
and QAOA behavior for small angles [49].

Figure 16: Schematic of our explanations of the QAOA performance diagram.
Shading indicates performance, with lighter shading corresponding to higher
performance. The labels indicate the rough locations on the diagram where each
explanation applies. Figure 17: QAOA performance diagrams showing squared
overlap with the cost ground state for (A) the two-level example given in Eq.
15 and (B) the Hamiltonian pair from Fig. 9. For orders of magnitude of $p$
larger than the ones on the graph, the Ridge region eventually decreases to
$\Delta_{\textnormal{crit}}$ marked by the red line in (B).

These explanations arise from several distinct aspects of QAOA with gradually
changing parameters, as summarized in Section 5.1. First, Section 5.2 explains
the Low and High regions i.e. the regions at large $p$, as due to the discrete
adiabatic theorem and changes in eigenstate connections. Second, Section 5.3
explains the bottom portion of the diagram and the lower boundary of the Ridge
region through a perturbative expansion in small angles. Third, Section 5.4
explains that the upper boundary of the Ridge arises due to the QAOA step
becoming small enough for the QAOA state vector to track the evolving
$U_{\textnormal{{qaoa}}}$ eigenvector. Finally, Section 5.5 describes how
these separate explanations combine to describe the full diagram. Fig. 16
schematically illustrates the portions of the diagram to which each of these
explanations applies. Fig. 17 shows examples of the applicability of these
explanations to two actual diagrams.

###  5.1 QAOA Performance Regions

This subsection gives an overview our explanations of the features of QAOA
performance diagrams. Subsequent subsections provide details of these
explanations.

I. Discrete adiabatic region:  From the discrete adiabatic theorem, for very
large $p$ (far right of diagram), the output state has high support on
whatever cost eigenstate the mixer ground eigenstate is connected to. Below
$\Delta_{\textnormal{crit}}$ this is the cost ground eigenstate, and above
$\Delta_{\textnormal{crit}}$ this is some cost excited eigenstate.

II. Small angle approximation:  In the bottom part of the diagram, the
performance is described using a small-angle expansion of
$U_{\textnormal{{qaoa}}}$ operator. For these small angles, the QAOA schedule
approximates a continuous anneal, with increasing $\Delta$ and $p$ associated
with a longer anneal time and hence better performance.

III. Tracking eigenvector swap across eigenvalue gaps: Above
$\Delta_{\textnormal{crit}}$, changing eigenstate connections due to wrap-
around produce avoided crossings. The gap size of these avoided crossings
shrinks exponentially in how indirectly the mixer (or cost) couples the
eigenstates whose eigenvalues have wrapped around. The changing eigenvectors
continuously exchange places over a narrow interval (or “swap”) at the gap,
with the swap taking place over smaller intervals for smaller gaps.
Consequently, in order for performance to deteriorate with increasing $p$, the
discretization must be fine enough for QAOA to sample the interval over which
this swap happens. For finer discretization, the interaction at the gap may be
modeled with a discrete version of the Landau-Zener formula. Finally, the
value of $p$ at which performance deteriorates is determined by the $p$ at
which reduced diabatic transitions to the ground state at the gap outweigh
improvements in tracking the changing eigenvectors up to the gap.

IV. Initial State dominated region:  Along the left edge of the performance
diagram, $p$ is so small that the squared overlap of the QAOA output state
only slightly improves on the initial overlap of the mixer ground state with
the cost ground eigenspace. Thus the choice of initial mixer ground state is
the dominant determiner of performance. This follows from previous
observations that QAOA exhibits limited performance unless $p$ is at least of
order $\log(n)$ for $n$ qubits [14, 50, 51].

###  5.2 Discrete Adiabatic Region

The behavior near the right edge of the QAOA performance diagram arises from
the discrete adiabatic theorem and connections between
$U_{\textnormal{{qaoa}}}$ eigenstates. Below $\Delta_{\textnormal{crit}}$, in
the generic case where there are no degeneracies with low-lying excited states
in the middle, the QAOA output state has squared overlap with the cost ground
eigenspace near one. This is because the mixer ground eigenstate is connected
to the cost ground eigenstate, so by the discrete adiabatic theorem [21, 34],
the state vector tracks the continuously changing eigenvectors from mixer
ground state to cost ground state.

As discussed in Section 4, above $\Delta_{\textnormal{crit}}$ the ground
eigenstate of $H_{\textnormal{mix}}$ is connected to the maximal excited
eigenstate of $H_{\textnormal{cost}}$, and so the discrete adiabatic theorem
implies that the QAOA output state has squared overlap near one with the
maximal cost excited state and consequently a high expected energy. As
$\Delta$ continues to increase, the mixer ground eigenstate forms new
connections to other excited eigenstates of $H_{\textnormal{cost}}$, including
some low-lying ones, as eigenvalues at both $f=0$ and $f=1$ continue to go
around the complex unit circle. Depending on the spacing of the cost and mixer
energies, for all but very small systems (as in Fig. 17(A)) the connection
between mixer ground and cost ground eigenstates might never be established
again, or re-established only for very small intervals of $\Delta$.

The situation is more complicated when the mixer or cost ground eigenvalue is
degenerate. In this case, different sub-spaces of the mixer ground eigenspace
can connect to different excited cost eigenspaces, and a degenerate cost
eigenvalue can mean that wrap-around with a few eigenvalues (multiplicity
equal to the ground space dimension) must happen at $f=1$ or $f=0$ to fully
sever connection with the mixer ground eigenspace, as discussed in Section
4.5. While most of the quantitative analysis in this paper concerns the case
when the unitary eigenvalues wrapping around are non-degenerate, the same
framework can qualitatively describe performance diagrams for the degenerate
case.

###  5.3 Small Angle Region

We explain the lower-left region of the QAOA performance diagram through an
application of small-angle approximations for QAOA. Exact expressions as power
series in the algorithm parameters for QAOA probabilities and expectation
values are derived in [49] using the Heisenberg representation of quantum
mechanics. Keeping only the leading-order terms results in easily computable
approximations valid when all parameters have relatively small magnitudes [49,
Sec. 4], as is the case for the lower portion of the QAOA performance diagram.

As described in Appendix A, the small-angle approximation relates QAOA
performance to sums over combinations of QAOA parameters and expectations of
cost operators.

The form of these sums indicates why the performance diagram behavior is
general with respect to problems, mixers and schedules: because behavior as a
function of $p$ and $\Delta$ enters only through the angle sums, so as long as
coefficients – from cost and mixer operators – do not change sign, the
framework predicts the same qualitative behavior at the bottom of the
performance diagram.

The small-angle expansion of [49] converges to the exact value in the regime
$\Delta\ll 1/p$ (generalizing the case $\Delta\ll 1$ in [49], which applies
for fixed $p$). The theory describes the qualitative behavior of QAOA for
somewhat larger parameters [49, Fig. 4], including the qualitative behavior of
the lower portion of the QAOA performance diagram even for $\Delta$ comparable
to $1/p$. See Section 6.1 for an example.

On a more conceptual level, for small enough $\Delta$, we can interpret QAOA
as the implementation of a Trotterized, continuous adiabatic evolution between
two interpolated Hamiltonians. As such, performance improves as $p$ increases,
i.e., corresponding to a slower anneal, while increasing $\Delta$ at fixed $p$
corresponds roughly to increased evolution time.

###  5.4 Eigenvector Tracking and Performance Near the Ridge

This subsection explains that the Ridge region for
$\Delta>\Delta_{\textnormal{crit}}$ arises from the QAOA state vector stepping
over the gap in eigenvalues of the $U_{\textnormal{{qaoa}}}$ operator when $p$
is not too large. This region ends when $p$ is sufficiently large that QAOA
tracks the swapping eigenvector at the gap, leading to the adiabatic limit.

####  5.4.1 Tracking the swapping eigenvector

As discussed in Section 3, the step size in parameter space (here given by
$1/p$) required to track the changing eigenvectors of
$U_{\textnormal{{qaoa}}}$ depends on the eigenvalue gaps encountered along the
path through parameter space, with smaller gaps requiring smaller step sizes
(here, larger $p$). When $p$ is too small, the eigenvector swap taking place
at the avoided crossing from wrap-around above $\Delta_{\textnormal{crit}}$ is
missed entirely, causing the state vector to track the “wrong” eigenvector to
the ground state. Once $p$ is large enough, the discretization is fine enough
to track an eigenvector up to and through the swap, causing the overlap of the
state vector with the maximal excited state to increase.

While we leave a precise estimate of this size of $p$ for future work, we show
in Appendix C.1 the width of the interval over which the eigenvector exchange
(or “swap”) occurs shrinks exponentially with how indirectly the two swapping
cost eigenstates are coupled by the mixer.

Overall, larger steps through parameter space (i.e., smaller $p$) can allow
QAOA to step over the small interval over which the eigenvectors continuously
swap. For a reader familiar with the continuous adiabatic regime and
annealing, this situation should be surprising; picking QAOA angles large
enough that the adiabatic limit performs poorly (by going to the wrong
eigenvector) can nevertheless improve QAOA performance by allowing QAOA to
deviate from the adiabatic limit with larger parameter steps.

####  5.4.2 Landau-Zener Formula explains declining ridge slope on the right

Figure 18: QAOA performance diagrams showing squared overlap with the cost
ground state for the Hamiltonian pair from Fig. 9. The gray region covers the
set of parameters for which the squared overlap of the output QAOA state with
the cost ground state is at least 0.95. (A) The horizontal lines denote the
values of $\Delta$ at which wrap-arounds occur (i.e. $\Delta^{*}$) between the
cost ground state and the seventh (7E), sixth (6E), fifth (5E), and fourth
(4E) excited states, in order of increasing $\Delta^{*}$, as well as their
coupling distance to the cost ground state ($k$). The curves plot the values
of $p$ for which Eq. 18 predicts a 95$\%$ rate of diabatic transition for each
wrap-around. At each $\Delta$, the curve with the smallest $p$ determines the
overall shape of the contour. (B) The curve shows the predicted value of $p$
where an overall 95$\%$ transition to the cost ground state is predicted from
diabatic transitions across _all_ the gaps. (C) Same as (B) but numerically
correcting for imperfect QAOA tracking of the eigenvectors up to the swaps at
the gaps. Calculations to generate the curves are in Appendix D.

Performance deterioration with $p$ (the slope of the ridge after the decline
starts) can be approximated with a discrete version of the Landau-Zener
formula, due to interactions at the gap.

For $p$ sufficiently large, the discretization is fine enough to track the
changing eigenvectors up to the avoided crossing, and the dynamics in the
neighbourhood of the avoided crossing can be well-estimated by an off-diagonal
perturbation in the “effective” two-level Hamiltonian [52]. In Appendix C.2,
we use this approximation to derive the probability of a diabatic transition
to the cost ground state

$P\approx\exp(-\frac{B_{0}}{1+\delta/\Delta^{*}}\delta^{2k}p)\leavevmode\nobreak\
,$ (18)

where $\delta=\Delta-\Delta^{*}$ with $\Delta^{*}$ being the value at which
wrap-around occurs at $f=1$, and $B_{0}$ is a positive constant given by Eq.
64, independent of $\delta$ but dependent on
$c_{\textnormal{eff}}^{\textnormal{x,y}}$, which, along with the coupling
distance $k$, is defined in Section 4.4 and explicitly provided in Eq. 31.
While the general Discrete Landau-Zener approach is useful for avoided
crossings emerging anywhere in the parameter space, the above formula is
specifically derived for wrap-around at $f=1$ (or a lightly modified version
at $f=0$, with $H_{\textnormal{cost}}$ and $H_{\textnormal{mix}}$ dependencies
exchanged).

Section 4.4 notes that wrap-around at $f=0,1$ is the source of the first
isolated degeneracies as $\Delta$ increases from zero. Isolated degeneracies
can occur for intermediate values $f$ for larger $\Delta$. However, as these
do not change the overall eigenstate connections, they are only relevant for
narrow ranges of $\Delta$. Thus the dominant source of performance
deterioration arises from wrap-around at $f=0,1$.

For $\Delta$ above the smallest value of $\Delta^{*}$ (i.e.,
$\Delta_{\textnormal{crit}}$), QAOA leads to the ground state of
$H_{\textnormal{cost}}$ only if the state vector undergoes a diabatic
transition at the avoided crossing due to wrap-around. As $\Delta$ increases
and other wrap-arounds take place, QAOA leads to the ground state only if
multiple diabatic transitions occur across the gaps. If one gap has a diabatic
transition rate far lower than the others, it is the dominant source of
performance deterioration. Therefore, for constant step size, the right
boundary of the RIDGE region is determined by the largest gap.

Section 4.4 explains that as $\Delta$ increases above the value $\Delta^{*}$
at which the wrap-around takes place, each respective gap grows as
$\delta^{k}$. Eq. 18 suggests that the rate of diabatic transition decreases
at each gap, pushing the right boundary of the performance ridge to the left
and performance deteriorates faster with increasing $p$. This means that
distantly-coupled states (higher $k$) not only require exponentially larger
$p$ for QAOA to notice the swap, but the effect from this swap is very small
and grows very slowly with increasing $p$. For instance in Fig. 17(A) where
the wrapping states are directly coupled, performance deteriorates rapidly
just above $\Delta_{\textnormal{crit}}$. By contrast, in Fig. 17(B), the
third-order coupled states have a slow performance decay even after
discretization is fine enough to track an eigenvector up to the first swap.

Fig. 18 shows the predictions of Eq. 18 for the performance diagram of Fig.
17(B). Eq. 18 gives upper bounds for the values of $p$ at which a specified
success probability $P$ can be obtained (excepting edge cases where the ground
state eigenstates become accidentally reconnected). This is because these
curves indicate the value of $p$ where a fraction $P$ of the QAOA state at the
respective avoided crossing goes on to the ground state. Any deviations from
this happen because there were even more deviations prior to the avoided
crossing. For example. this could be caused by small gaps with low-energy
excited states, other avoided crossings due to wrap-around, $p$ too small to
closely track the changing eigenvector up to the avoided crossing, etc. This
is why all curves in Fig. 18(A) overestimate the $p$ at which the $P_{0}=0.95$
success contour occurs, due to poor tracking at small $p$ and due to other
wrap-around avoided crossings at large $p$. Fig. 18(B) corrects for the latter
cause by taking all wrap-around gaps into account, but still overshoots the
$P_{0}=0.95$ contour at small $p$ due to $p$ being too small to track the
changing eigenvectors. We numerically correct for this in Fig. 18(C), giving a
more accurate contour prediction. From this, we can see that if $\Delta$ is
large enough, the $p$ required to achieve any high diabatic transition to the
ground state is so small that the state vector is unable to closely follow any
eigenvector of the QAOA operator and consequently the performance degrades.

We can approximate the value of $p$ required to achieve a squared overlap with
the ground state close to unity $P=1-\varepsilon$ by inverting Eq. 18 and
doing a Taylor expansion to obtain

$p_{\varepsilon}\approx\frac{\varepsilon}{B_{0}}\frac{(1+\delta/\Delta^{*})}{\delta^{2k}}=-\frac{\varepsilon\leavevmode\nobreak\
p_{0}}{\log{P_{0}}}\leavevmode\nobreak\ \leavevmode\nobreak\ .$ (19)

where $P_{0}$ is the probability of obtaining the ground state at a specific
value $p_{0}$.

###  5.5 Summary

In the adiabatic performance region, for $p$ exponentially large in system
size, the performance is determined by changing eigenstate connections as
$\Delta$ varies. In the small-angle region, an expansion approximation
explains the increasing performance with fixed $p$ and increasing $\Delta$.
Above $\Delta_{\textnormal{crit}}$, performance on the ridge is explained by
whether $p$ is large enough to detect swaps with high-lying excited states,
with the size of $p$ required exponential in how indirectly coupled the states
are.

Our discussion explains why QAOA performance diagrams have the same
qualitative behavior for the metric of expected cost of the output state,
e.g., as seen in Section 6.1. For sufficiently large $p$ and above
$\Delta_{\textnormal{crit}}$, the output state gains support on high-lying
excited states and thus a high expected energy. While these are intermixed
with connections to low-lying excited states at narrow ranges of $\Delta$,
there still are accumulated avoided crossings with eigenvalues that lead to
those of high-lying cost excited states. Thus the same qualitative features of
QAOA diagrams occur for several performance metrics.

##  6 Examples

###  6.1 Expected Cost Performance Diagram for an Ising Problem

As described in Section 2, overlap with the ground state and expected cost are
two metrics of QAOA performance. Previous examples of QAOA performance
diagrams focused on ground state overlap [4]. In this section, we show
expected cost gives similar behaviors by using a spin Ising problem as an
illustrative example. The Ising spin problem is to find the ground state of
$n$ spins $s_{i}$, $i=1,\ldots,n$ each of which is $\pm 1$. The fully-
connected version illustrated here has Hamiltonian

$H=\sum_{i}h_{i}s_{i}+\sum_{i<j}J_{i,j}s_{i}s_{j}$ (20)

A random instance has the $h_{i}$ and $J_{i,j}$ selected independently and
uniformly at random in the range $-1$ to $1$.

Figure 19: Expected cost after completing QAOA as a function of QAOA
parameters $\Delta$ and $p$, for a 6-variable fully-connected Ising spin
system instance taken from [4, Fig. 2]. The ground state has expected cost
$-6.13$. The initial uniform superposition has expected cost
$\left<C\right>=0$.

Fig. 19 is the QAOA performance diagram of the Ising instance shown in [4,
Fig. 2], but showing the expected cost instead of the squared overlap with the
ground state. The diagram extends to $p\approx 1000$ to show the drop in
performance above a critical value of $\Delta$, as seen in the upper-right
portion of the figure.

Fig. 20 compares the expected cost of QAOA with the Pade rational function
approximation based on the two-term expansion for the expected cost [49, Thm
4.2.1].

The range of $\Delta$ in this figure corresponds to the lower portion of Fig.
19. Hence the the small-angle expansion of [49] matches the qualitative
behavior of the lower portion of the performance diagram, namely high
performance (i.e., small expected cost) occurs at smaller $p$ as $\Delta$
increases. This two-term expansion somewhat underestimates the expected cost.
Appendix A provides additional details of these results.

Figure 20: Actual (top) and predicted (bottom) expected cost for the Ising
spin system shown in Fig. 19.

###  6.2 QAOA Performance Diagram for H2

This section applies our analysis of QAOA to identifying the ground state of a
hydrogen molecule. In this case, $H_{\textnormal{cost}}$ is the full
Hamiltonian prepared in the basis of Slater determinants using the full cc-
pVTZ basis generated using Psi4 [53], while the mixer is simply the diagonal
part of the cost Hamiltonian, as in [4]. Thus both the mixer and the initial
state differ significantly from the common case of the $X$ mixer and uniform
initial state. Fig. 21 shows the resulting QAOA performance diagram.

Figure 21: $-\ln|1-(\text{final squared overlap})|$ as a function of $\Delta$
and $p$.

In this case, $\Delta_{\textnormal{crit}}=2\pi/13.9077\approx 0.4518$ (where
13.9077 is the spectral range of this problem) due to wrap around of the
eigenvalues of the cost ground and highest excited states. Below
$\Delta_{\textnormal{crit}}$ is the behavior predicted in Section 5.3, with
performance at fixed $p$ improving as $\Delta$ increases. The performance
improvement is quite drastic in some cases; for instance, achieving $99.9\%$
squared overlap at $\Delta=0.05$ requires $p=70$, while at $\Delta=0.4$ it is
only $p=10$.

The wrapping cost ground and maximal excited states are directly coupled by
the mixer, so the redirection of the ground state to the excited state is
noticeable at small $p$. Since the expected energies of the cost wrapping
states are similar for $H_{\textnormal{mix}}$, Eq. 18 does not directly apply.
However, we expect an exponential dependence on $p$ and verify this by using
Eq. 19 to predict the value of $p$ at which the performance hits $99\%$
squared overlap, given an overlap of $0.1581$ at $p=5000$. This estimates a
$99\%$ overlap at $p\approx 27$, which is close to the true value of $p=25$.

Slightly increasing $\Delta$ restores the connection between the two
Hamiltonians’ ground eigenstates - this is because the spectrum of the two
Hamiltonians is so similar that the ground/maximal excited states of
$H_{\textnormal{mix}}$ wrap around at $\Delta=2\pi/13.8561\approx 0.4534$
before any more cost eigenvalues wrap past each other, “undoing” the altered
connection between the ground eigenstates of the two Hamiltonians. The cost
Hamiltonian directly couples the highest/lowest eigenstates of the mixer, so
this transition is clearly visible at low $p$, just as the first. Thus our
topological perspective offers a more intuitive explanation for why
performance deteriorates on such a narrow band of $\Delta$ than the usual
angle size divergence analysis.

Above this value of $\Delta$, due to the weak connections between the cost
eigenstates produced by the mixer (and vice versa), eigenvalues of indirectly-
connected states wrapping around do not result in gaps that are noticeable at
this scale. Eventually, above $\Delta\approx 1$, enough significant gaps from
avoided crossings due to wrap-around have emerged that performance completely
deteriorates.

##  7 General Schedules and Problem Size Scaling

This section shows how the explanations of Section 5 apply to additional cases
of performance diagrams.

###  7.1 General schedules with gradually changing angles

The previous two sections illustrated how the small-angle approximation,
eigenstate connections for $p$ in the adiabatic limit and small eigenvalue
gaps explain performance diagrams for QAOA using the linear ramp of Eq. (4).
This section generalizes these explanations to other schedules with gradually
changing angles. This is of general interest as there is strong numerical
evidence that optimized QAOA protocols approach an asymptotic continuous limit
with large $p$ [14, 54, 55].

One set of results applies to schedules in the discrete adiabatic limit.
Schedules with gradually changing $\beta_{j},\gamma_{j}$ as defined in Section
2 correspond to discrete samplings of continuous paths in parameter space.
Section 4.3.5 describes how the mixer and cost eigenstates connected by
continuous paths through $f,\Delta$ parameter space are determined entirely by
the initial and final parameter values along that path (assuming the path does
not pass through degeneracies). Applying the discrete adiabatic theorem,
Section 5.2 showed which cost eigenstate the QAOA state approaches for $p\gg
1$, based only on $(\beta(0),\gamma(0))$ and $(\beta(1),\gamma(1))$.
Specifically, the initial eigenstate determines the cost eigenstate that QAOA
produces. For small angles, QAOA can be regarded as a first-order Trotter
approximation to annealing [18]. One application of this generality of our
approach is to analyze convergence of this approximation. In particular, fixed
time-step, first-order Trotterizations of a continuous anneal correspond to
fixed-$\Delta$ paths in our parameter space. Therefore, for a fixed choice of
gapped, bounded Hamiltonians and continuous schedule sampled from to produce
gradually changing angles, there exists a time step corresponding to
$\Delta_{\textnormal{crit}}$ above which the product sequence of unitaries is
guaranteed to fail to approximate continuous annealing.

Our results also apply to schedules with gradually changing angles where the
difference between consecutive angles is not small enough to produce behavior
close to that of the discrete adiabatic limit. Section 5.4 explains whether
QAOA along a continuous path through parameter space follows a particular
eigenvector swap, based on the gaps encountered along the path. In particular,
to find the effects of gaps from wrap-arounds on nonlinear paths, it is enough
to alter the calculus relative to $\Delta,f$ in Appendices C.1 and C.2 to
$\beta(s),\gamma(s)$, allowing an application of our analysis to nonlinear
paths (since the location and emergence of gaps can be easily translated from
the $\Delta,f$ parameterization in this paper). The discrete Landau-Zener
approach is helpful in analyzing diabatic transitions at avoided crossings
near isolated degeneracies in parameter space, not just the ones at the edges.
For avoided crossings in this setting, the formula is easier to use than the
general formula of the Discrete Adiabatic Theorem in [34, Theorem 3].

Unlike the discrete adiabatic theorem and Landau-Zener formula, the small-
angle framework applied in Section 5.3 does not depend on the continuity of
the parameter schedule and in some cases can be applied to small $p$. Thus the
small-angle analysis, which applies to the lower portion of performance
diagrams, generalizes beyond schedules with gradually changing angles.

###  7.2 Sparse Local Constraint Satisfaction Problems: Performance Diagram
and Problem Size

The performance diagrams and discussion of their properties summarized in
Section 5.5 focus on QAOA performance as a function of $p$ and $\Delta$ for a
fixed problem. This section discusses how the behaviors scale with problem
size for the $X$-mixer and typical cases of sparse local-constraint
satisfaction problems, i.e., problems where each constraint deals with at most
some constant number of variables and each variable appears in at most a
constant number of constraints.

Figure 22: Schematic scaling of the QAOA performance diagram with problem size
$n$. Curve (A) indicates the fuzzy, left boundary of the performance ridge
from small angle analysis. Curves (B) and (C) mark the values of $p$ at which
a fixed diabatic transition to the ground state is predicted solely due wrap-
arounds at $\Delta_{\textnormal{crit}}$ and $\Delta^{*}$ respectively. Here,
$\Delta_{\textnormal{crit}}\propto 1/n$, $\bar{\Delta}\propto 1/\log(n)$ and
$\Delta^{*}\propto\log(\log(n))/\log(n)$. These curves, along with those from
all the wrap-arounds not shown in this range of $\Delta$, define an envelope
contour (dashed) that forms the right, fuzzy boundary of the Ridge region.
Curve (C) indicates where this boundary exists for $p$ polynomial (here,
quadratic) in $n$.

Consider applying the $X$ mixer to a problem with size $n$ whose range of
costs is $\Theta(n)$, e.g., as is typical of random hard problems such as
$k$-SAT where the number of clauses, and hence maximum possible cost, is
proportional to $n$ [56]. The largest eigenvalue of the $X$ mixer is also of
this order in $n$. Thus the first wrap around occurs at $\Delta\propto 1/n$.
Without loss of generality, for this discussion we suppose that the cost
Hamiltonian has a larger range of eigenvalues than the mixer, so this first
wrap around is due to that of the highest cost.

For such problems, Fig. 22 illustrates a possible scaling for the Ridge
region. For large $p$, Appendix A.3 shows that $\Delta\propto 1/p$ has
constant QAOA performance, corresponding to the downward-sloping behavior of
the bottom part of the Ridge region in the performance diagrams. These scaling
arguments suggest the left-side of the ridge crosses
$\Delta_{\textnormal{crit}}\propto 1/n$ with $p\propto n$, which arises from
minimizing the expected cost from the first two terms of [49, Theorem 4.2.1]
applied to random Ising problems as a function of $n$. $\bar{\Delta}$
indicates where this estimated lower bound intersects with the vertical axis
at $p\propto\log(n)$.

Above $\Delta_{\textnormal{crit}}$, for sufficiently large $p$ one reaches the
adiabatic regime which has poor performance due to going to the wrong
eigenstate, and so is outside the Ridge region.

For local constraint satisfaction problems, $b$ bit flips correspond to an
$O(b)$ change in cost. In particular, the highest cost state, of order $n$,
has $\Theta(n)$ bit flips compared to the ground state. Thus the coupling
distance, defined in Section 4.4, between the highest cost and ground states
is $k=\Theta(n)$. Consequently, when the highest cost states wrap around, from
Section 5.4, the $p$ at which significant deterioration occurs scales as
$(1/\delta)^{\Theta(n)}$, and thus will not be noticeable save for
exponentially large $p$ even at fixed values of $\Delta$ significantly smaller
than 1.

In Appendix E.2, using the discrete Landau-Zener approximation from Section
5.4.2 and the lowest-order approximation of the gaps from Section 4.4, we
estimate that when $p$ is some fixed polynomial function of $n$, the gaps that
produce some fixed squared overlap $<1$ with the cost ground state first occur
for $\Delta$ just above $\Delta^{*}\propto 1/w(n)$, where

$w(n):=\frac{\log(n)}{\log(\log(n))}.$ (21)

In particular, for large $n$, we estimate that the wrap-around of states
differing in $\propto w(n)$ bits from the ground state produces the gaps that
predominantly contribute to an upper boundary to the right edge of the Ridge
region, compared to all other wrap-arounds at $f=0,1$, for $p$ polynomial in
$n$. Since even one such wrap-around is enough to produce this effect at $f=0$
or $f=1$ (see Appendix E.2), it does not matter that many excited states
differing by $\propto w(n)$ bit flips might have a slower-scaling energy
difference.

According to this analysis, the left and right boundaries of the Ridge region
do not intersect when $n$ is large. The wrap-around with low-lying excited
states with $O(1)$ difference in cost from the ground state does not
contribute to the right boundary, as they occur at higher values of $\Delta$.
As we estimate in Appendix E.2, the wrap-around between cost or mixer states
with $\sim w(n)$ coupling distance dominates in size over gaps occurring at
smaller $\Delta$ with greater coupling distance.

This analysis suggests the general scaling of the lower-left and upper-right
fuzzy boundaries of the Ridge region. In particular, it suggests that for the
class of problems used for this example, scaling the performance diagram axes
by $n$ horizontally and $\propto w(n)$ vertically will result in similar
diagrams for different $n$, similar to overlapping behaviors seen with finite-
size scaling in the context of phase transitions in combinatorial search such
as satisfiability [56]. Importantly, the estimation from our analysis
approximates an _upper boundary_ to the Ridge region from just one effect
(wrap-around at $f=0,1$) - other effects might need to be taken into account
to predict the scaling of its actual location.

##  8 Discussion

The deterioration of QAOA performance at large angles was observed in [57] and
attributed to a large Trotter error in comparison to the (continuous)
adiabatic limit. We identify a more complex phenomenon: the poor performance
is not necessarily due to adiabaticity breaking down, but rather due to the
change in connectivity between initial and final eigenstates. Our application
of the discrete adiabatic theorem to schedules with gradually changing angles
shows QAOA convergence [58] and supplements analysis of digitized continuous
drives [18, 59].

Our discussion indicates the _location_ , i.e., ranges of $p$ and $\Delta$, of
the Ridge region. An open question is the _absolute performance_ of QAOA on
the ridge. Numerical observations of the performance diagrams indicate
performance on the ridge just above $\Delta_{\textnormal{crit}}$ is comparable
to that for small $\Delta$ and much larger $p$, but it remains to be seen how
this behavior scales with larger problem sizes.

Figure 23: (A) Negative arguments of $U_{\textnormal{{qaoa}}}$ eigenvalues,
with the $X$-mixer and cost energies (in order of bitstring value) 10, 5.4,
7.18, 0.6, 0, 7, 7, 3.35 at $\Delta=0.66>\Delta_{\textnormal{crit}}=2\pi/10$
which has a small gap with a low-lying energy state circled in blue. (B)
Performance diagram for choice of mixer and cost in (A) displayed as squared
overlap with cost ground state.

In particular, there may be small gaps among low-energy states that occur at
values of $f$ other than the location of the gap in the highest-energy wrap
around just above $\Delta_{\textnormal{crit}}$. Then, the absolute performance
in the Ridge region might be low, as the state vector fails to go to the
ground state eigenvector at small $p$ due to these other small gaps. Fig. 23
illustrates this behavior with a three-qubit example. Here, $\Delta$ is
slightly above $\Delta_{\textnormal{crit}}$ and so there is a small eigenvalue
gap near $f=0.95$ from wrap-around which is comparable in size to the
eigenvalue gap between the ground and low-lying energies. Consequently,
absolute performance on the QAOA ridge is limited by the gap from wrap-around
for problems whose overall minimum gap is at $f=1$ (prior numerical
investigation has found this to commonly be the case for chemistry problems
[60] as seen in Section 6.2) and for problems where the gap with low-lying
eigenstates is not as small as the gap formed from wrap-around (generically,
this is true for $\Delta$ sufficiently close to $\Delta_{\textnormal{crit}}$).
Therefore, another important follow-up is determining the typical performance
on the ridge for different classes of problems. Further, the qualitative
argument used to identify the location of the left Ridge region in the
performance diagram is based on the an extrapolation of [49, Theorem 4.2.1] to
angle sizes where higher-order terms are not necessarily small. A direction
for future work here is to numerically test the applicability of this analysis
to various classes of problems.

Another promising direction for future work is utilizing our approach to aid
the design of schedules for low-depth circuits, which is of interest because
noise in the implementation of QAOA on hardware can significantly degrade
performance as the depth of the circuit grows [61, 62]. One could use the
topological perspective to construct nonlinear schedules that exploit the
structure of multiple wrap-arounds, i.e., large steps to avoid tracking
swapping eigenvectors through gaps and small steps to follow eigenvectors
through gaps, while using the discrete Landau-Zener approach (potentially
applying discretized versions of current multi-state models [63, 64]) to
estimate parameter regions that have low or high diabatic transitions to the
ground state at a particular depth. This could potentially allow for shortcuts
to adiabatic behavior [65, 66, 67]. Even simpler design improvements are
possible - as argued and observed numerically in our work, it is often
possible to reduce the circuit depth $p$, while increasing the angle size
$\Delta$, with only marginal sacrifice in QAOA performance.

Another observation from our work is that judiciously picking the start and
endpoints in parameter space provides an alternative means of state
preparation. Starting with one cost eigenstate above an isolated degeneracy at
$f=1$, then taking an open half-tour around the degeneracy leads to a
different eigenstate. In the cases where the highest cost excited state is
easy to identify and prepare (as is the case for many Ising instances [68]),
this leads to a version of QAOA where the mixer is not required to have an
easy-to-prepare ground state and can be optimized to reflect structure of the
cost problem. Exploiting such structure might lead to advancements [69], but
whether such a protocol can improve on traditional approaches requires further
investigation.

##### Conclusion.

In this work we have presented a new lens of analysis for QAOA circuits with
gradually varying unitaries. Using the discrete adiabatic theorem, we recover
the usual expected behavior at sufficiently small angles corresponding to
Trotterized annealing, as well as capture the fundamentally different behavior
leading to novel phenomena due to the wrap-around of unitary eigenvalues for
larger angles. The latter results in changing connections between cost and
mixer Hamiltonian eigenstates and diabatic transitions at small gaps due to
these wrap-arounds. We have used this and other techniques such as
perturbation theory to explain a surprising qualitative generality in QAOA
performance diagrams from optimization to chemistry problems. Our findings
represent a hitherto unexplored perspective on QAOA which carries implications
for parameter schedule design, limitations of the annealing perspective on
QAOA, and performance characterization.

## Acknowledgments

We are grateful for support from NASA Ames Research Center. We acknowledge
funding from the NASA ARMD Transformational Tools and Technology (TTT)
Project. VK, TH, and SH were supported by the NASA Academic Mission Services,
Contract No. NNA16BD14C. AA is supported by Yoichiro Nambu Graduate Fellowship
courtesy of Department of Physics, University of Chicago. Calculations were
performed as part of the XSEDE computational Project No. TG-MCA93S030 on
Bridges-2 at the Pittsburgh supercomputer center. We also would like to thank
Lucas Brady, Carlos Mejuto Zaera, Ruslan Shaydulin, Thomas Watts, Haoran Lu,
Alexander Avdoshkin, and Andrew Yates for providing feedback on earlier drafts
of this paper.

## References

  * Farhi  _et al._ [2014] E. Farhi, J. Goldstone, and S. Gutmann, A Quantum Approximate Optimization Algorithm, arXiv e-prints (2014), arXiv:1411.4028 [quant-ph] .
  * Hadfield  _et al._ [2019] S. Hadfield, Z. Wang, B. O’gorman, E. G. Rieffel, D. Venturelli, and R. Biswas, From the quantum approximate optimization algorithm to a quantum alternating operator ansatz, Algorithms 12, 34 (2019).
  * Ho and Hsieh [2019] W. W. Ho and T. H. Hsieh, Efficient variational simulation of non-trivial quantum states, SciPost Physics 6, 029 (2019).
  * Kremenetski  _et al._ [2021a] V. Kremenetski _et al._ , Quantum alternating operator ansatz (QAOA) performance diagrams and applications for quantum chemistry, arXiv preprint arXiv:2108.13056 (2021a).
  * Farhi and Harrow [2016] E. Farhi and A. W. Harrow, Quantum supremacy through the quantum approximate optimization algorithm, arXiv preprint arXiv:1602.07674 (2016).
  * Wang  _et al._ [2018] Z. Wang, S. Hadfield, Z. Jiang, and E. G. Rieffel, Quantum approximate optimization algorithm for maxcut: A fermionic view, Physical Review A 97, 022304 (2018).
  * Wurtz and Love [2021] J. Wurtz and P. Love, Maxcut quantum approximate optimization algorithm performance guarantees for $p>1$, Phys. Rev. A 103, 042612 (2021).
  * Vikstål  _et al._ [2020] P. Vikstål, M. Grönkvist, M. Svensson, M. Andersson, G. Johansson, and G. Ferrini, Applying the quantum approximate optimization algorithm to the tail-assignment problem, Phys. Rev. Applied 14, 034009 (2020).
  * Díez-Valle  _et al._ [2022] P. Díez-Valle, D. Porras, and J. José García-Ripoll, QAOA pseudo-Boltzmann states, arXiv e-prints (2022), arXiv:2201.03358 [quant-ph] .
  * Akshay  _et al._ [2022] V. Akshay, H. Philathong, E. Campos, D. Rabinovich, I. Zacharov, X.-M. Zhang, and J. D. Biamonte, Circuit depth scaling for quantum approximate optimization, Phys. Rev. A 106, 042438 (2022).
  * Streif and Leib [2019] M. Streif and M. Leib, Comparison of QAOA with Quantum and Simulated Annealing, arXiv e-prints (2019), arXiv:1901.01903 [quant-ph] .
  * Jiang  _et al._ [2017] Z. Jiang, E. G. Rieffel, and Z. Wang, Near-optimal quantum circuit for Grover’s unstructured search using a transverse field, Phys. Rev. A 95, 062317 (2017).
  * Koßmann  _et al._ [2022] G. Koßmann, L. Binkowski, L. van Luijk, T. Ziegler, and R. Schwonnek, Deep-Circuit QAOA, arXiv e-prints (2022), arXiv:2210.12406 [quant-ph] .
  * Zhou  _et al._ [2020] L. Zhou, S.-T. Wang, S. Choi, H. Pichler, and M. D. Lukin, Quantum approximate optimization algorithm: Performance, mechanism, and implementation on near-term devices, Phys. Rev. X 10, 021067 (2020).
  * Leng  _et al._ [2022] J. Leng, Y. Peng, Y.-L. Qiao, M. Lin, and X. Wu, Differentiable Analog Quantum Computing for Optimization and Control, arXiv e-prints (2022), arXiv:2210.15812 [quant-ph] .
  * Wurtz and Lykov [2021] J. Wurtz and D. Lykov, The fixed angle conjecture for qaoa on regular maxcut graphs, arXiv preprint arXiv:2107.00677 (2021).
  * Brady  _et al._ [2021] L. T. Brady, C. L. Baldwin, A. Bapat, Y. Kharkov, and A. V. Gorshkov, Optimal protocols in quantum annealing and quantum approximate optimization algorithm problems, Phys. Rev. Lett. 126, 070505 (2021).
  * Kocia  _et al._ [2022] L. Kocia, F. A. Calderon-Vargas, M. D. Grace, A. B. Magann, J. B. Larsen, A. D. Baczewski, and M. Sarovar, Digital adiabatic state preparation error scales better than you might expect, arXiv e-prints (2022), arXiv:2209.06242 [quant-ph] .
  * Sack and Serbyn [2021a] S. H. Sack and M. Serbyn, Quantum annealing initialization of the quantum approximate optimization algorithm, Quantum 5, 491 (2021a).
  * Pelofske  _et al._ [2023] E. Pelofske, A. Bärtschi, and S. Eidenbenz, Quantum Annealing vs. QAOA: 127 Qubit Higher-Order Ising Problems on NISQ Computers, arXiv e-prints (2023), arXiv:2301.00520 [quant-ph] .
  * Dranov  _et al._ [1998] A. Dranov, J. Kellendonk, and R. Seiler, Discrete time adiabatic theorems for quantum mechanical systems, J. of Mathematical Physics 39, 1340 (1998).
  * Cheon  _et al._ [2009] T. Cheon, A. Tanaka, and S. W. Kim, Exotic quantum holonomy in hamiltonian systems, Physics Letters A 374, 144 (2009), arXiv:0909.2033 .
  * Berry [1984] M. V. Berry, Quantal phase factors accompanying adiabatic changes, Proceedings of the Royal Society of London. A. Mathematical and Physical Sciences 392, 45 (1984).
  * Wilczek and Zee [1984] F. Wilczek and A. Zee, Appearance of gauge structure in simple dynamical systems, Physical Review Letters 52, 2111 (1984).
  * Willsch  _et al._ [2020] M. Willsch, D. Willsch, F. Jin, H. De Raedt, and K. Michielsen, Benchmarking the quantum approximate optimization algorithm, Quantum Inf. Process. 19, 197 (2020).
  * Hogg [2000] T. Hogg, Quantum search heuristics, Physical Review A 61, 052311 (2000).
  * Crooks [2018] G. E. Crooks, Performance of the Quantum Approximate Optimization Algorithm on the Maximum Cut Problem, arXiv e-prints (2018), arXiv:1811.08419 [quant-ph] .
  * Bigan Mbeng  _et al._ [2019] G. Bigan Mbeng, R. Fazio, and G. Santoro, Quantum Annealing: a journey through Digitalization, Control, and hybrid Quantum Variational schemes, arXiv e-prints (2019), arXiv:1906.08948 [quant-ph] .
  * Shaydulin  _et al._ [2021] R. Shaydulin, S. Hadfield, T. Hogg, and I. Safro, Classical symmetries and the Quantum Approximate Optimization Algorithm, Quantum Information Processing 20, 359 (2021).
  * Sack and Serbyn [2021b] S. H. Sack and M. Serbyn, Quantum annealing initialization of the quantum approximate optimization algorithm, Quantum 5, 491 (2021b).
  * Streif and Leib [2020] M. Streif and M. Leib, Training the quantum approximate optimization algorithm without access to a quantum processing unit, Quantum Science and Technology 5, 034008 (2020).
  * McClean  _et al._ [2018] J. R. McClean, S. Boixo, V. N. Smelyanskiy, R. Babbush, and H. Neven, Barren plateaus in quantum neural network training landscapes, Nature Communications 9, 4812 (2018).
  * Note [1] In [4] the performance diagrams are also referred to as “QAOA phase diagrams”.
  * Costa  _et al._ [2021] P. C. S. Costa, D. An, Y. R. Sanders, Y. Su, R. Babbush, and D. W. Berry, Optimal scaling quantum linear systems solver via discrete adiabatic theorem, arXiv e-prints (2021), arXiv:2111.08152 [quant-ph] .
  * Hogg [2003] T. Hogg, Adiabatic quantum computing for random satisfiability problems, Physical Review A 67, 022314 (2003), arXiv:quant-ph/0206059 .
  * Tanaka [2011] A. Tanaka, Adiabatic theorem for discrete time evolution, J. of the Physical Society of Japan 80, 125002 (2011), arXiv:1107.2989 .
  * Sakurai and Napolitano [2017] J. J. Sakurai and J. Napolitano,  _Modern Quantum Mechanics_, 2nd ed. (Cambridge University Press, 2017).
  * Albash and Lidar [2018] T. Albash and D. A. Lidar, Adiabatic quantum computation, Reviews of Modern Physics 90, 015002 (2018), arXiv:1611.04471 [quant-ph] .
  * Tanaka and Miyamoto [2007] A. Tanaka and M. Miyamoto, Quasienergy anholonomy and its application to adiabatic quantum state manipulation, Phys. Rev. Lett. 98, 160407 (2007).
  * Miyamoto and Tanaka [2007] M. Miyamoto and A. Tanaka, Cheon’s anholonomies in floquet operators, Phys. Rev. A 76, 042115 (2007).
  * Shiff [1968] L. Shiff,  _Quantum Mechanics_ , 3rd ed. (McGraw-Hill, New York, 1968).
  * Ding  _et al._ [2022] K. Ding, C. Fang, and G. Ma, Non-Hermitian topology and exceptional-point geometries, Nature Reviews Physics 4, 745 (2022).
  * Tanaka  _et al._ [2014] A. Tanaka, S. W. Kim, and T. Cheon, Exotic quantum holonomy and higher-order exceptional points in quantum kicked tops, Phys. Rev. E 89, 042904 (2014).
  * Cheon [1998] T. Cheon, Double spiral energy surface in one-dimensional quantum mechanics of generalized pointlike potentials, Physics Letters A 248, 285 (1998).
  * Ergoktas  _et al._ [2022] M. S. Ergoktas _et al._ , Topological engineering of terahertz light using electrically tunable exceptional point singularities, Science 376, 184 (2022).
  * Schumer  _et al._ [2022] A. Schumer _et al._ , Topological modes in a laser cavity through exceptional state transfer, Science 375, 884 (2022).
  * Patil  _et al._ [2021] Y. S. S. Patil, J. Höller, P. A. Henry, C. Guria, Y. Zhang, L. Jiang, N. Kralj, N. Read, and J. G. E. Harris, Measuring the knot of degeneracies and the eigenvalue braids near a third-order exceptional point, arXiv e-prints (2021), arXiv:2112.00157 [physics.optics] .
  * Altshuler  _et al._ [2009] B. Altshuler, H. Krovi, and J. Roland, Adiabatic quantum optimization fails for random instances of NP-complete problems, arXiv e-prints , arXiv:0908.2782 (2009).
  * Hadfield  _et al._ [2022] S. Hadfield, T. Hogg, and E. G. Rieffel, Analytical framework for quantum alternating operator ansätze, Quantum Science and Technology 8, 015017 (2022).
  * Bravyi  _et al._ [2020] S. Bravyi, A. Kliesch, R. Koenig, and E. Tang, Obstacles to variational quantum optimization from symmetry protection, Phys. Rev. Lett. 125, 260505 (2020).
  * Hastings [2019] M. B. Hastings, Classical and Quantum Bounded Depth Approximation Algorithms, arXiv e-prints (2019), arXiv:1905.07047 [quant-ph] .
  * Cohen-Tannoudji  _et al._ [2020] C. Cohen-Tannoudji, B. Diu, and F. Laloë,  _Quantum mechanics. Volume 1: Basic concepts, tools, and applications_ , 2nd ed., edited by S. Reid Hemley, N. Ostrowsky, and D. Ostrowsky (Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim, 2020).
  * et. al. [2017] R. P. et. al., Psi4 1.1: An open-source electronic structure program emphasizing automation, advanced libraries, and interoperability (2017), http://cccbdb.nist.gov/ .
  * Pagano  _et al._ [2020] G. Pagano, A. Bapat, P. Becker, K. S. Collins, A. De, P. W. Hess, H. B. Kaplan, A. Kyprianidis, W. L. Tan, C. Baldwin, L. T. Brady, A. Deshpande, F. Liu, S. Jordan, A. V. Gorshkov, and C. Monroe, Quantum approximate optimization of the long-range Ising model with a trapped-ion quantum simulator, Proceedings of the National Academy of Science 117, 25396 (2020).
  * Brady  _et al._ [2021] L. T. Brady, L. Kocia, P. Bienias, A. Bapat, Y. Kharkov, and A. V. Gorshkov, Behavior of Analog Quantum Algorithms, arXiv e-prints (2021), arXiv:2107.01218 [quant-ph] .
  * Kirkpatrick and Selman [1994] S. Kirkpatrick and B. Selman, Critical behavior in the satisfiability of random boolean expressions, Science 264, 1297 (1994).
  * Wurtz and Love [2022] J. Wurtz and P. J. Love, Counterdiabaticity and the quantum approximate optimization algorithm, Quantum 6, 635 (2022).
  * Binkowski  _et al._ [2023] L. Binkowski, G. Koßmann, T. Ziegler, and R. Schwonnek, Elementary Proof of QAOA Convergence, arXiv e-prints , arXiv:2302.04968 (2023).
  * Hatomura [2023] T. Hatomura, Scaling of errors in digitized counterdiabatic driving, arXiv e-prints (2023), arXiv:2303.04235 [quant-ph] .
  * Kremenetski  _et al._ [2021b] V. Kremenetski, C. Mejuto-Zaera, S. J. Cotton, and N. M. Tubman, Simulation of adiabatic quantum computing for molecular ground states, The Journal of Chemical Physics 155, 234106 (2021b), https://doi.org/10.1063/5.0060124 .
  * Marshall  _et al._ [2020] J. Marshall, F. Wudarski, S. Hadfield, and T. Hogg, Characterizing local noise in QAOA circuits, IOP SciNotes 1, 025208 (2020), arXiv:2002.11682 [quant-ph] .
  * Xue  _et al._ [2019] C. Xue, Z.-Y. Chen, Y.-C. Wu, and G.-P. Guo, Effects of Quantum Noise on Quantum Approximate Optimization Algorithm, arXiv e-prints (2019), arXiv:1909.02196 [quant-ph] .
  * Sinitsyn [2013] N. A. Sinitsyn, Nonadiabatic transitions in exactly solvable quantum mechanical multichannel model: Role of level curvature and counterintuitive behavior, Phys. Rev. Lett. 110, 150603 (2013).
  * Lin and Sinitsyn [2014] J. Lin and N. A. Sinitsyn, Exact transition probabilities in the three-state Landau-Zener-Coulomb model, Journal of Physics A Mathematical General 47, 015301 (2014).
  * Campbell and Deffner [2017] S. Campbell and S. Deffner, Trade-off between speed and cost in shortcuts to adiabaticity, Phys. Rev. Lett. 118, 100601 (2017).
  * Guéry-Odelin  _et al._ [2019] D. Guéry-Odelin, A. Ruschhaupt, A. Kiely, E. Torrontegui, S. Martínez-Garaot, and J. G. Muga, Shortcuts to adiabaticity: Concepts, methods, and applications, Rev. Mod. Phys. 91, 045001 (2019).
  * Hegade  _et al._ [2021] N. N. Hegade, K. Paul, Y. Ding, M. Sanz, F. Albarrán-Arriagada, E. Solano, and X. Chen, Shortcuts to Adiabaticity in Digitized Adiabatic Quantum Computing, Physical Review Applied 15, 024038 (2021), arXiv:2009.03539 [quant-ph] .
  * Lucas [2014] A. Lucas, Ising formulations of many NP problems, Frontiers in Physics 2, 10.3389/fphy.2014.00005 (2014).
  * Bennett  _et al._ [1997] C. H. Bennett, E. Bernstein, G. Brassard, and U. Vazirani, Strengths and weaknesses of quantum computing, SIAM Journal on Computing 26, 1510 (1997), https://doi.org/10.1137/S0097539796300933 .
  * Kato [1976] T. Kato,  _Perturbation theory for linear operators; 2nd ed._, Grundlehren der mathematischen Wissenschaften : a series of comprehensive studies in mathematics (Springer, Berlin, 1976).
  * Feynman [1939] R. P. Feynman, Forces in molecules, Phys. Rev. 56, 340 (1939).
  * Wittig [2005] C. Wittig, The Landau-Zener formula, The Journal of Physical Chemistry B 109, 8428 (2005), pMID: 16851989, https://doi.org/10.1021/jp040627u .
  * Erdos and Renyi [1960] P. Erdos and A. Renyi, On the evolution of random graphs, Publ. Math. Inst. Hungary. Acad. Sci. 5, 17 (1960).
  * [74] DLMF, NIST Digital Library of Mathematical Functions, http://dlmf.nist.gov/, Release 1.1.8 of 2022-12-15, f. W. J. Olver, A. B. Olde Daalhuis, D. W. Lozier, B. I. Schneider, R. F. Boisvert, C. W. Clark, B. R. Miller, B. V. Saunders, H. S. Cohl, and M. A. McClain, eds.
  * Bollobás [2001] B. Bollobás,  _Random graphs_ , 2nd ed., Cambridge studies in advanced mathematics No. 73 (Cambridge University Press, 2001).
  * Bogdanowicz [2009] Z. R. Bogdanowicz, Undirected simple connected graphs with minimum number of spanning trees, Discrete Mathematics 309, 3074 (2009).

Appendix

##  Appendix A Application of QAOA small-angle analysis

The results for QAOA in the small-parameter regime of [49, Theorem 4.2.1]
describe behavior at the bottom of the performance diagram. This theorem
expresses the expected cost of the final QAOA state as a series in polynomials
of the QAOA angles, with coefficients determined by initial state expectation
values of operators derived from the cost function via commutators [49]. For
level-$p$ QAOA, to leading-order

$\langle H_{\textnormal{cost}}\rangle_{p}=\langle
H_{\textnormal{cost}}\rangle_{0}\,-\,(\sum_{i,j\geq
i}\gamma_{i}\beta_{j})\,\langle\,[H_{\textnormal{cost}},[H_{\textnormal{mix}},H_{\textnormal{cost}}]]\,\rangle_{0}+\dots$
(22)

where the terms not shown to the right are proportional to increasingly higher
order products of the $\gamma_{i},\beta_{j}$, with the next nonzero
contribution proportional to a quartic polynomial of the QAOA angles.

###  A.1 QAOA schedules

For the ramp schedules of Eq. (4), the parameter polynomials of [49, Theorem
4.2.1] are functions of $p$ and $\Delta$. The angle sum appearing in the
leading order term is

$\sum_{i,j\geq i}\gamma_{i}\beta_{j}=\frac{p(6+5p+p^{2})}{24(1+p)}\Delta^{2}$
(23)

The small-angle analysis applies to arbitrary parameter schedules. In
particular, [49, Remark 4.2.1] indicates the angle sum terms scale as powers
of $\Delta p$ in the same way as the ramp when $\Delta$ is interpreted as a
characteristic magnitude of the angles. Thus the dependence on $p$ and
$\Delta$ in the theorem does not depend on specific details of the QAOA
schedule, thereby indicating why the observed QAOA performance diagram
behavior is generic in the regimes of validity of [49, Theorem 4.2.1], in
particular when $p\Delta\ll 1$ (for fixed problem size).

###  A.2 Ising problem

Finding the ground state of a Hamiltonian is a minimization problem, so we use
$-X$ as the mixer, so the initial uniform superposition is the ground state of
the mixer. This contrasts with the use of the $+X$ mixer in [49]. This change
of sign of mixer is equivalent to changing the sign of $\beta$ instead. In
applying this theorem to finding the ground state of the Ising problem, we
make this sign change in the angle sums.

For the Ising Hamiltonian of Eq. (20), the leading-order correction to
$\langle H_{\textnormal{cost}}\rangle_{p}-\langle
H_{\textnormal{cost}}\rangle_{0}$ of [49, Theorem 4.2.1] is

$-\frac{p(6+5p+p^{2})}{6(1+p)}\Delta^{2}\left(\sum_{i}h_{i}^{2}+2\sum_{i<j}J_{i,j}^{2}\right)$
(24)

The random Ising problems considered here have
$\left<h_{i}^{2}\right>=\left<J_{i,j}^{2}\right>=1/3$, so averaging over this
problem class gives

$-\frac{\Delta^{2}n^{2}p\left(p^{2}+5p+6\right)}{18(p+1)}$ (25)

which, for large $p$, is $-n^{2}(\Delta p)^{2}/18$. A similar evaluation of
the angle sums and costs involved in the second term of [49, Theorem 4.2.1]
for large $p$ gives $n^{3}(\Delta p)^{4}/504$.

These expressions allow generalizing the range of validity of this series
expansion beyond $\Delta\ll 1$ for fixed $p$ and a given problem (hence fixed
$n$) discussed in [49]. Specifically, the second term is small compared to the
first when $\Delta\ll 1/(p\sqrt{n})$.

The first term is negative, indicating $\left<C\right>$ decreases, i.e., QAOA
performance improves, when moving from the lower left toward the upper right
of the diagram, until the second, and higher, terms become important for
$\Delta\sim 1/(p\sqrt{n})$ and lead to increasing $\left<C\right>$. This
suggests the Ridge region in the performance diagram occurs for $\Delta\sim
1/(p\sqrt{n})$ or larger. On the other hand, $\Delta p\rightarrow\infty$ gives
the adiabatic limit, which gives low performance above
$\Delta_{\textnormal{crit}}$.

A similar analysis applies to sparsely connected Ising problems that
correspond to local CSPs discussed in Section 7.2. One such class of problems
is when each pair of spins is independently connected with probability
$q=m/(n-1)$ with $m$ a fixed constant, independent of $n$. Thus, on average, a
spin is connected to $(n-1)q=m$ other spins. The couplings $J_{i,j}$ for
connected spins are randomly selected in the same way as for the fully
connected case described in Section 6.1.

For the small-angle analysis, the sparse Ising problem only changes the
expectation values of the coupling appearing in the cost operators, e.g., in
Eq. (24). In particular, $\left<J_{i,j}^{2}\right>=q/3$ and, for large $p$,
the leading-order term is $-n(m+1)(\Delta p)^{2}/18$. Similarly, the second
term of [49, Theorem 4.2.1] is $n(5m^{2}+28m+8)(\Delta p)^{4}/2520$. Both
these terms are linear in $n$, and the second term is small compared to the
first when $\Delta\ll 1/p$. This indicates a lower bound for the ridge region
of these sparsely connected problems occurs with $\Delta\sim 1/p$.

###  A.3 Scaling from small-angle analysis

Any problem whose cost operator expectations and maximum energy depending on
$n$ in the same way as the Ising example will have the same scaling for the
location of the Ridge region in terms of $n$ as the Ising example. This
includes any QUBO whose cost coefficients are independent of $n$ [49, Lemma
B.0.2].

Moreover, the angle sums in the series expansion of [49, Theorem 4.2.1] are
proportional to powers of $\Delta p$ for large $p$ (e.g., the angle sum given
in Appendix A.1). For higher order terms to be small requires $\Delta p\ll 1$,
rather than just $\Delta\ll 1$ used in [49] in the context of fixed $p$. Thus,
for large $p$, $\Delta\propto 1/p$ has constant QAOA performance,
corresponding to the downward-sloping behavior of the Ridge region for small-
to-intermediate $p$ in the performance diagrams.

The schematic scaling shown in Fig. 22 is given by combining these
observations for sparsely connected problems, and extrapolating the small-
angle series from $\Delta$ so small that QAOA operators are close to the
identity so the QAOA output state is close to the initial state. This
emphasizes the qualitative behavior for moderately large $p$.

For such problems, as discussed in Section 7.2, $\Delta_{\textnormal{crit}}$
is of order $1/n$. This suggests the Ridge region occurs when $1/n$ is at
least of order $1/p$, i.e., $p$ is at least of order $n$.

A consequence of this discussion of the size of the terms in [49, Theorem
4.2.1] is that $p=O(\log n)$ is not large enough for QAOA to reach the Ridge
region since we have $\Delta$ at most $O(1/n)$ to avoid wrap-around so $\Delta
p$ is then at most of order $\log(n)/n$, which is small compared to 1. Thus
the first term dominates, indicating performance increases with increasing $p$
beyond $\log n$ so these parameters are below the Ridge region.

For problems whose costs scale with $n$ differently than the Ising example, a
similar analysis can use the corresponding scaling of expectations of cost
operators appearing in [49, Theorem 4.2.1], and the $n$ dependence of the
maximum energy to determine scaling of $\Delta_{\textnormal{crit}}$. Using
these scaling behaviors will give corresponding estimates for the location of
the Ridge region.

Specifically, the small-angle analysis can indicate the scaling of cost
Hamiltonians that have different connectivity among the problem variables than
the fully and sparsely-connected cases discussed here. For instance, a local
Hamiltonian, where each variable only interacts with $O(1)$ other variables
instead of fully connected interactions, will have substantially fewer terms
in the cost expectations leading to slower growth with $n$. For problems with
pairwise interactions among variables, [49, Lemma B.0.2] gives the cost
expectations in terms of sums over the interaction strengths. Similarly, [49,
Lemma 2.5.3] includes the generalization to interactions among triples of
variables, which is relevant for the scaling of performance diagrams for 3-SAT
which have qualitatively similar features to those seen with pairwise
interactions [4]. The number of nonzero terms in these sums determine their
scaling with respect to problem size $n$.

###  A.4 Molecular ground state problems

Our QAOA construction for the electronic structure problem [4] is also
considered in [49, Sec. 5.3]. As indicated there, it is relatively
straightforward to extend the result and proof of [49, Theorem 4.2.1] to the
quantum chemistry setting, which results in a similar term at leading order to
the Ising case.

##  Appendix B Results for isolated degeneracies

Here we provide supporting results for the claims regarding isolated
degeneracies of Section 4.

###  B.1 Formula for gap from wrap-around of two non-degenerate eigenstates

We derive a perturbative formula for the size of the gap resulting from wrap-
around of two non-degenerate cost eigenstates at $f=1$ based on $\Delta$ and
the couplings of cost eigenstates by the mixer. It may be trivially modified
to account for wrap-around at $f=0$.

####  B.1.1 Formula for gap size

We first introduce some helpful definitions.

######  Definition.

Two cost eigenstates $\ket{x},\ket{y}$ are said to be _“coupled”_ by the mixer
if there exists an ordered tuple of cost eigenstates
$S=\\{\ket{s_{0}=x},\ket{s_{1}},...,\ket{s_{n}}\\}$ such that

$P(S)=\left(\prod_{j=0}^{n-1}\bra{s_{j}}H_{\textnormal{mix}}\ket{s_{j+1}}\right)\bra{s_{n}}H_{\textnormal{mix}}\ket{y}\neq
0$ (26)

We call such this set a _“coupling path”_ , and the cardinality of this set
the _“length”_ of the path.

For example, with the $X$-mixer, states $\ket{000}$ and $\ket{111}$ have a
coupling path $S=\\{\ket{000},\ket{001},\ket{011}\\}$ of length three. This is
not the only coupling path between the two states, others exist of the same
length (e.g., $\\{\ket{000},\ket{100},\ket{101}\\}$) or different length
(e.g., $\\{\ket{000},\ket{001},\ket{101},\ket{100},\ket{110}\\}$).

######  Definition.

Two cost eigenstates $\ket{x},\ket{y}$ are said to be _“k-coupled”_ by the
mixer if the shortest coupling path between them is of length $k$.

For the $X$-mixer example, the states $\ket{000}$ and $\ket{111}$ are
3-coupled, because the X-mixer directly couples two bitstrings with a Hamming
distance of one, so all the shortest coupling paths between these two
bitstrings have a length of 3. In general, for the case of the $X$-mixer and
computational ($Z$) basis, states whose bitstrings have a Hamming distance of
$k$ are $k$-coupled. We now recursively define a multivariate polynomial:

$Q^{n}(b_{1},...b_{n})=\frac{1}{(n+1)!}-\sum_{m=1}^{n}\frac{1+ib_{m}}{2m!}Q^{n-m}(b_{m+1},...,b_{n}),\
\ \ Q^{0}=1,\ \ \ \ b_{i}\in\mathbb{R}$ (27)

The first few orders of this polynomial are shown in Table 1.

Gap Formula: Let $\Delta=\Delta^{*}$ such that
$e^{-i\Delta^{*}E_{x}}=e^{-i\Delta^{*}E_{y}}$ for exactly two distinct, non-
degenerate energies of $H_{\textnormal{cost}}$ $E_{x},E_{y}$ and suppose the
corresponding $H_{\textnormal{cost}}$ eigenstates are $k$-coupled by the
mixer. Then, for a path at $\Delta=\Delta^{*}+\delta$, $k\geq 2$ and using Eq.
29, the gap magnitude $|g|$ from the avoided crossing due to wrap-around is

$|g|=2|c_{\textnormal{eff}}^{\textnormal{x,y}}|\left|\frac{\delta}{\Gamma-1}\right|^{k}+O(\delta^{k+1})$
(28)

if $D_{x}-D_{y}\neq E_{x}-E_{y}$

We introduce notation:

$D_{s_{j}}=\bra{s_{j}}H_{\textnormal{mix}}\ket{s_{j}},\ \ \
E_{s_{j}}=\bra{s_{j}}H_{\textnormal{cost}}\ket{s_{j}},\ \ \ \
\Gamma=\frac{D_{x}-D_{y}}{E_{x}-E_{y}}$ (29)

where $\ket{s_{j}}$ are cost eigenstates. In practice, $\Gamma=0$ for many
common mixers (zero diagonals), which simplifies our formulas. Next, we define
$a_{j}$ for the $j$-th term in some fixed coupling path $S$

$a^{S}_{j}=\cot\left(\frac{\Delta^{*}}{2}(E_{s_{j}}-E_{x})\right)$ (30)

Finally, we define an “effective” coupling between states $\ket{x},\ket{y}$
as:

$c_{\textnormal{eff}}^{\textnormal{x,y}}=\sum_{S}P(S)Q^{k-1}(a_{1}^{S},...,a_{k-1}^{S})$
(31)

where the sum is over all $k-$coupling paths between the states.

If $c_{\textnormal{eff}}^{\textnormal{x,y}}\neq 0$, the degeneracy at
$f=1,\Delta=\Delta^{*}$ is guaranteed to be isolated. As this is generically
the case (though see examples of exceptions in Appendix E.1), it follows that
the degeneracy is generically isolated and the resulting gap from wrap-around
goes as $\theta(\delta^{k})$ as $\delta\rightarrow 0$. That is, the gap size
shrinks exponentially with coupling distance. Further, the size of the
resulting gap depends to lowest order only on the energies of the intermediate
coupling states, so if $c_{x,y}^{\text{eff}}=0$, the resulting gap goes as
$O(\delta^{k+1})$ as $\delta\rightarrow 0$, and it is not a guarantee that the
degeneracy at $(1,\Delta^{*})$ is continuous (not isolated). Finally, while
$c_{\textnormal{eff}}^{\textnormal{x,y}}$ is difficult to compute in general,
it depends only on $H_{\textnormal{mix}}$ and $H_{\textnormal{cost}}$,
allowing a characterization of how quickly the gap grows as $\Delta$ increases
above $\Delta^{*}$. Also, given the simple recursive formula in Eq.27 which we
use to determine $c_{\textnormal{eff}}^{\textnormal{x,y}}$, this formula is
simpler than conventional perturbation theory [37, 70] when $k$ becomes large.
An area of future work is to compute “average” values of
$c_{\textnormal{eff}}^{\textnormal{x,y}}$ and its scaling with $k$ for
different families of mixer/cost Hamiltonians, as is done in Appendix E. In
deriving the formula, we also get a first-order estimate for the gap location
$f=1+\epsilon$ in a fixed-$\Delta$ path, satisfying
$\delta/(\Delta^{*}\epsilon)=-1+(D_{x}-D_{y})/(E_{x}-E_{y})+O(\delta)$.

k=1 | $1$
---|---
k=2 | $-\frac{i}{2}b_{1}$
k=3 | $-(\frac{1}{4}b_{1}b_{2}+\frac{1}{12})$
k=4 | $i(\frac{1}{8}b_{1}b_{2}b_{3}+\frac{1}{24}(b_{1}+b_{3}))$
k=5 | $\frac{1}{16}b_{1}b_{2}b_{3}b_{4}+\frac{1}{48}(b_{1}b_{2}+b_{1}b_{4}+b_{3}b_{4})+\frac{1}{120}$
Table 1: Simplified versions of $Q^{k-1}(b_{1},...,b_{k-1})$ from Eq. 27 for
some fixed coupling path for $k=1,...,5$.

####  B.1.2 Deriving Gap Formula

To derive the gap formula, Eq. 28, consider wrap-around that takes place at
$(f=1,\Delta=\Delta^{*})$ such that
$e^{-i\Delta^{*}E_{x}}=e^{-i\Delta^{*}E_{y}}$ for non-degenerate cost
eigenstates $\ket{x},\ket{y}$. Suppose that at $\Delta=\Delta^{*}+\delta$ the
gap $g$ from avoided crossing due to wrap-around occurs at $f=1+\epsilon$,
then without loss of generality the $N\times N$ QAOA unitary (as defined in
Eq. 5) may be expressed as:

$U_{\textnormal{{qaoa}}}(1+\epsilon,\Delta^{*}+\delta)=\lambda_{1}\ket{v_{1}}\bra{v_{1}}+(\lambda_{1}+g)\ket{v_{2}}\bra{v_{2}}+\sum_{j=3}^{N}\lambda_{j}\ket{v_{j}}\bra{v_{j}}$

Where $\lambda_{j}$ and $\ket{v_{j}}$ are the eigenvalues and eigenvectors
respectively of the QAOA unitary, and $\ket{v_{1}},\ket{v_{2}}$ are the
eigenvectors involved in the eigenvector swap. These eigenvectors and the gap
$g$ depend on $\epsilon,\delta$. We define distance
$r=\sqrt{\epsilon^{2}+\delta^{2}}$ in parameter space from the point of
degeneracy at $(f=1,\Delta=\Delta^{*})$. The difference between
$U_{\textnormal{{qaoa}}}(1+\epsilon,\Delta^{*}+\delta)$ and

$\mathcal{U}:=U_{\textnormal{{qaoa}}}(1,\Delta^{*})$ (32)

goes as $O(r)$, $r\rightarrow 0$. From perturbation theory [70], the
difference between $\ket{v_{j}}$ and the nearest eigenvector of $\mathcal{U}$
goes as $O(r)$, as does the difference between the eigenvalues of
$U_{\textnormal{{qaoa}}}(1+\epsilon,\Delta^{*}+\delta)$ and the nearest
eigenvalues of $\mathcal{U}$. As discussed in Section 4.3, $\ket{v_{1}}$ and
$\ket{v_{2}}$ lie predominantly within the subspace spanned by $\ket{x}$ and
$\ket{y}$, though $\ket{x}$ and $\ket{y}$ can have $O(r)$ magnitude of overlap
with other $\ket{v_{j}}$. Since $g=O(r)$, we cannot simply compute the
submatrix of $U_{\textnormal{{qaoa}}}$ on $\ket{x}$ and $\ket{y}$, as the
order of the gap size could be of the same order as overlap with the other
eigenvectors of $U_{\textnormal{{qaoa}}}$. To resolve this, we introduce the
“residual matrix” of a unitary $U$, $R^{\vec{l}}(U)$:

$R^{\vec{l}}(U)=\prod_{j=1}^{|\vec{l}|}(U-l_{j}I)$ (33)

By choosing $\vec{l}=\\{\lambda_{1},\lambda_{3},...,\lambda_{N}\\}$, we have:

$R_{\textnormal{{qaoa}}}=R^{\vec{l}}(U_{\textnormal{{qaoa}}}(1+\epsilon,\Delta^{*}+\delta))=g\prod_{j=3}^{N}(\lambda_{1}+g-\lambda_{j})\ket{v_{2}}\bra{v_{2}}=g\prod_{j=3}^{N}(\lambda_{1}-\lambda_{j})\ket{v_{2}}\bra{v_{2}}+O(g^{2})$
(34)

The remaining term $O(g^{2})$ is negligible provided that
$|g|\ll|\lambda_{1}-\lambda_{j}|,\ \forall j\neq 1,2$. As each $\lambda_{j}$
is perturbatively within $O(r)$ of some eigenvalue $e^{-i\Delta^{*}E_{cost}}$
of $e^{-i\Delta^{*}H_{\textnormal{cost}}}$, it is from here that the
requirement of $\ket{x},\ket{y}$ being non-degenerate with other eigenstates
of $H_{\textnormal{cost}}$ originates, and that we expect our gap formula from
Eq. 28 to break down when the predicted eigenvalue is of the same order as
separation of $e^{-i\Delta^{*}E_{x}}=e^{-i\Delta^{*}E_{y}}$ of other
eigenvalues of $e^{-i\Delta^{*}H_{\textnormal{cost}}}$.

Now, $\ket{v_{2}}=c_{x}\ket{x}+c_{y}\ket{y}+\gamma\ket{v^{\perp}}$ where
$\ket{v^{\perp}}$ is orthogonal to $\ket{x},\ket{y}$ and $|\gamma|=O(r)$.
Consequently, we have:

$\sqrt{|\bra{x}R_{\textnormal{{qaoa}}}\ket{x}|^{2}+|\bra{y}R_{\textnormal{{qaoa}}}\ket{y}|^{2}+|\bra{x}R_{\textnormal{{qaoa}}}\ket{y}|^{2}+|\bra{y}R_{\textnormal{{qaoa}}}\ket{x}|^{2}}=\left|\left(\prod_{j=3}^{N}(\lambda_{1}-\lambda_{j})+O(r)\right)g\right|=|Kg|$
(35)

$\frac{\sqrt{|\bra{x}R_{\textnormal{{qaoa}}}\ket{x}|^{2}+|\bra{y}R_{\textnormal{{qaoa}}}\ket{y}|^{2}+|\bra{x}R_{\textnormal{{qaoa}}}\ket{y}|^{2}+|\bra{y}R_{\textnormal{{qaoa}}}\ket{x}|^{2}}}{\left|\prod_{j=3}^{N}(\lambda_{1}-\lambda_{j})\right|}=|g|(1+O(r))$
(36)

and

$\frac{|\bra{x}R_{\textnormal{{qaoa}}}\ket{x}|^{2}}{|K|^{2}|c_{x}|^{4}}=\
\frac{|\bra{y}R_{\textnormal{{qaoa}}}\ket{y}|^{2}}{|K|^{2}|c_{y}|^{4}}=\
\frac{|\bra{y}R_{\textnormal{{qaoa}}}\ket{x}|^{2}}{|K|^{2}|c_{x}|^{2}|c_{y}|^{2}}=\frac{|\bra{x}R_{\textnormal{{qaoa}}}\ket{y}|^{2}}{|K|^{2}|c_{x}|^{2}|c_{y}|^{2}}=|g|^{2}$
(37)

Perturbation theory implies that the leading order change comes from the
diagonal terms. Therefore, for $k\geq 2$ for fixed $r$, the choice of gap is
minimized when we choose $\epsilon,\delta$ such that the first-order-in-$r$
components of $\bra{x}R_{\textnormal{{qaoa}}}\ket{x}$ and
$\bra{y}R_{\textnormal{{qaoa}}}\ket{y}$ vanish. Computing these values will
yield a first-order approximation of the gap location. First, we enforce that
both terms cancel out their first order in $r$ contributions:

$\bra{x}R_{\textnormal{{qaoa}}}\ket{x}=(\bra{x}i\left(\Delta^{*}\epsilon
H_{\textnormal{mix}}-(\Delta^{*}\epsilon+\delta)H_{\textnormal{cost}}\right)\mathcal{U}\ket{x}+e^{-i\Delta^{*}E_{x}}-\lambda_{1})\prod_{j\neq
x,y}(e^{-i\Delta^{*}E_{x}}-e^{-i\Delta^{*}E_{j}})+O(r^{2})$

with an analogous equation holding for $\ket{y}$. Thus, by solving the
following equation

$\Delta^{*}\epsilon
D_{x}-(\Delta^{*}\epsilon+\delta)E_{x}=O(r^{2})=\Delta^{*}\epsilon
D_{y}-(\Delta^{*}\epsilon+\delta)E_{y}\leavevmode\nobreak\ ;$

we obtain a relation between $\delta$ and $\epsilon$

$\frac{\delta}{\Delta^{*}\epsilon}=\frac{D_{x}-D_{y}}{E_{x}-E_{y}}-1+O(r)=\Gamma-1+O(r)\leavevmode\nobreak\
.$ (38)

Here, $E_{j},D_{j},\Gamma$ are given by Eq. 29. This provides us with a first-
order estimate of the gap location from the avoided crossing. As an aside, if
we regard the “unperturbed” energies in the computational basis near $f=1$ as
being given by $\Delta(1-f)D_{x,y}+\Delta fE_{x,y}$ a slightly more accurate
approximation would replace $\Delta^{*}$ with $\Delta$ in Eq. 38. However, we
will proceed with this first-order estimate as we are interested in the