# The QAOA gets stuck starting from a good classical string

Madelyn Cain1, Edward Farhi2,3, Sam Gutmann, Daniel Ranard3, Eugene Tang3
1Department of Physics, Harvard University, Cambridge, MA 02138
2Google Quantum AI, Venice, CA 90291
3Center for Theoretical Physics, Massachusetts Institute of Technology,
Cambridge, MA 02139

###### Abstract

The Quantum Approximate Optimization Algorithm (QAOA) is designed to maximize
a cost function over bit strings. While the initial state is traditionally a
uniform superposition over all strings, it is natural to try expediting the
QAOA: first use a classical algorithm to produce some good string, and then
run the standard QAOA starting in the computational basis state associated
with that string. Here we report numerical experiments that show this method
of initializing the QAOA fails dramatically, exhibiting little to no
improvement of the cost function. We provide multiple analytical arguments for
this lack of improvement, each of which can be made rigorous under different
regimes or assumptions, including at nearly linear depths. We emphasize that
our negative results only apply to our simple incarnation of the warm-start
QAOA and may not apply to other approaches in the literature. We hope that our
theoretical analysis will inform future algorithm design.

##  1 Introduction

The Quantum Approximate Optimization Algorithm (QAOA) [FGG14] is designed to
find good approximate solutions to the problem of maximizing a cost function
defined on bit strings. The standard QAOA starts in the uniform superposition
of all classical bit string and applies cost function-dependent unitaries,
with the goal of improving the cost function beyond its expected value in the
initial state. It is natural to imagine running a classical algorithm to
produce a good string then initializing the QAOA in the associated
computational basis state and looking for improvement. Variations of this idea
have been explored in existing literature under the name of _warm-start QAOA_.

Here we seek to theoretically understand a counter-intuitive phenomenon: in
extensive numerical experiments involving small and large instances at low and
high depths, the QAOA makes effectively zero progress when starting from a
single warm start string. That is, nearly every good classical string appears
to be a local maximum that cannot be improved by any QAOA circuit at any
numerically accessible depth. The consistency of our numerics suggests there
is an underlying theoretical reason why the QAOA with a warm start gets stuck.
In this work, we provide several analytic arguments to explain this
phenomenon. Each argument has a different flavor and can be made rigorous in
different regimes or under different assumptions. Section 5 presents an
argument for small angles and low depths, Section 6 presents an argument for
constant depths that rests on a thermality assumption, and Section 7 presents
an argument for sub-linear depths that rests on an assumption about how the
number of strings decreases at higher cost.

We emphasize that our results apply to the case where the QAOA is initialized
in a single classical string and the unitary operators comprising the QAOA do
not depend explicitly on the initial string; they do not necessarily apply to
possibly more viable approaches to the warm-start QAOA in the literature
[Tat+20, EMW21].

##  2 Standard and single-string warm-start QAOA

###  2.1 A quick review of the standard QAOA

The standard QAOA starts in the uniform superposition of all $n$-bit strings
$\ket{s}=\frac{1}{2^{n/2}}\sum_{z}\ket{z}$, and applies a sequence of $2p$
unitaries depending on the $2p$ parameters $\boldsymbol{\gamma}$ and
$\boldsymbol{\beta}$, producing

$\ket{\boldsymbol{\gamma},\boldsymbol{\beta}}=e^{-i\beta_{p}B}e^{-i\gamma_{p}C}\dots
e^{-i\beta_{1}B}e^{-i\gamma_{1}C}\ket{s},$ (1)

where $B=\sum_{i}X_{i}$ is the sum of the single-qubit $X$ operators, and $C$
is the diagonal cost function operator. The goal is then to find the
parameters $\boldsymbol{\gamma},\boldsymbol{\beta}$ to make
$\bra{\boldsymbol{\gamma},\boldsymbol{\beta}}C\ket{\boldsymbol{\gamma},\boldsymbol{\beta}}$
as large as possible. We focus on graph-based problems such as MaxCut, where
the cost function can be written as

$C(z)=\sum_{\langle i,j\rangle\in E}C_{\langle i,j\rangle}(z_{i},z_{j}),$ (2)

where $\langle i,j\rangle$ ranges over all edges of a graph $G=(V,E)$. For
example, the MaxCut cost function is

$\displaystyle C_{\mathrm{MC}}=\frac{1}{2}\sum_{\langle i,j\rangle\in
E}(1-Z_{i}Z_{j}),$ (3)

which counts the number of cut edges. The cut fraction is defined as the
number of cut edges divided by the total number of edges. It will often be
convenient to consider the simpler MaxCut cost function operator,

$\displaystyle C_{Z}=-\sum_{\langle i,j\rangle\in E}Z_{i}Z_{j}.$ (4)

###  2.2 The QAOA starting from a good classical string

In this paper, we focus on the QAOA starting at a computational basis state
$\ket{w}$, where $w$ is a good string, with operators in the same form as the
previous section. Note that when we start in $\ket{w}$, the first unitary
$e^{-i\gamma_{1}C}$ in equation (1) only introduces a phase, so effectively
the state becomes

$\ket{\boldsymbol{\gamma},\boldsymbol{\beta},w}=U(\boldsymbol{\gamma},\boldsymbol{\beta})|w\rangle=e^{-i\beta_{k}B}e^{-i\gamma_{k-1}C}\dots
e^{-i\gamma_{1}C}e^{-i\beta_{1}B}\ket{w},$ (5)

which depend on the $2k-1$ parameters $\beta_{1},\dots,\beta_{k}$ and
$\gamma_{1},\dots,\gamma_{k-1}$. In keeping with the convention of the
standard QAOA, where there are $2p$ parameters, we define the QAOA starting on
a classical string with a fractional value of $p$ so that $2p=2k-1$.

Given $w$, the goal is to maximize
$\bra{\boldsymbol{\gamma},\boldsymbol{\beta},w}C\ket{\boldsymbol{\gamma},\boldsymbol{\beta},w}$
by finding the optimal parameters

$\displaystyle(\boldsymbol{\gamma}_{w},\boldsymbol{\beta}_{w})=\operatorname*{arg\,max}_{(\boldsymbol{\gamma},\boldsymbol{\beta})}\,\langle
w|U^{\dagger}(\boldsymbol{\gamma},\boldsymbol{\beta})CU(\boldsymbol{\gamma},\boldsymbol{\beta})|w\rangle.$
(6)

We then define the optimal QAOA unitary for the string $w$,

$\displaystyle U_{w}=U(\boldsymbol{\gamma}_{w},\boldsymbol{\beta}_{w}),$ (7)

which depends on $w$ only through the optimal parameters
$(\boldsymbol{\gamma}_{w},\boldsymbol{\beta}_{w})$.

###  2.3 Cost function as a sum over neighborhoods

We now review how the expected cost function may be organized as a sum over
subgraphs, as in [FGG14]. This is instructive for analyzing large graphs at
constant $p$ in Sections 3.2 and 6. We consider the warm-start QAOA with
initial classical string $w$ and expected cost $\bra{w}U^{\dagger}CU\ket{w}$,
where $U=U(\boldsymbol{\gamma},\boldsymbol{\beta})$ is the QAOA unitary. In
this regime, the operator $U^{\dagger}C_{\langle i,j\rangle}U$ only acts non-
trivially on the “edge neighborhood” of $\langle i,j\rangle$: vertices within
graph distance $r$ of $\langle i,j\rangle$, where the radius $r=p-\frac{1}{2}$
is the number of applications of $e^{-i\gamma C}$ in the QAOA circuit. Because
$U^{\dagger}C_{\langle i,j\rangle}U$ only acts non-trivially on the edge
neighborhood of $\langle i,j\rangle$, we can write

$\displaystyle\langle w|U^{\dagger}CU|w\rangle$ $\displaystyle=\sum_{\langle
i,j\rangle\in E}\langle w|U^{\dagger}C_{\langle i,j\rangle}U|w\rangle.$ (8)
$\displaystyle=\sum_{\langle i,j\rangle\in E}\langle w_{\langle
i,j\rangle}|U^{\dagger}C_{\langle i,j\rangle}U|w_{\langle i,j\rangle}\rangle.$
(9)

where $w_{\langle i,j\rangle}$ refer to the subset of bits in the
corresponding edge neighborhood. For constant $p$ on a bounded-degree graph,
this sum can be handled with low computational cost: each term can be computed
using only the Hilbert space of the qubits in the edge neighborhood and the
values $w_{\langle i,j\rangle}$.

##  3 Numerical experiments

We first present numerical experiments for MaxCut that consistently show that
running the standard QAOA starting from a good string does not lead to
improvement, both for small graphs at high depth and also for larger graphs
where we can only explore at lower depth. The results we present are typical;
we did numerical experiments for various graphs of different sizes and at many
QAOA depths, and never saw appreciable improvements. We replicate the small
system size results in Appendix B for the Maximum Independent Set problem at
$16$ vertices. In Appendix C we also look at the Sherrington-Kirkpatrick (SK)
model, which is fully connected and has random couplings, and obtain similar
results at $14$ vertices, albeit with rare exceptions discussed in Appendix
C.1.

###  3.1 Small system sizes and high depth

In Table 2 we present data for MaxCut on a 12 vertex, 3-regular graph at
depths up to $p=9/2$, where each edge neighborhood wraps around the graph many
times. For this instance, the largest cut value is 16 and the mean cut value
is 9. For each warm start we optimize the QAOA using a random initial guess
for parameters, and repeat the maximization for 40 random initial guesses. We
first optimize all strings with a cut value of 11, and find that most strings
do not improve at all, and the rest have small improvement. We then look at
all classical strings with a better cut value of 13. Here even fewer strings
show improvement, and again the improvements are small. We find that the QAOA
never improves when initialized in near-optimal strings with a cut value of
15. We expect that the failure to find improvement at very low bit number will
continue at high bit number, which we verify next. In Table 2 we show how the
usual QAOA which starts in the uniform superpositon makes steady progress to
the optimal value as the depth increases.

Warm start at $C_{\text{MC}}(w)=11$ with 516 classical strings $w$
---
$p$ | $3/2$ | $5/2$ | $7/2$ | $9/2$
Number of strings improved | 56 | 72 | 112 | 164
Mean cost of improved strings | 11.03 | 11.05 | 11.09 | 11.10
Largest cost of improved strings | 11.04 | 11.18 | 11.29 | 11.42
Warm start at $C_{\text{MC}}(w)=13$ with 126 classical strings $w$
$p$ | $3/2$ | $5/2$ | $7/2$ | $9/2$
Number of strings improved | 2 | 2 | 2 | 6
Mean cost of improved strings | 13.05 | 13.12 | 13.14 | 13.06
Largest cost of improved strings | 13.05 | 13.12 | 13.14 | 13.15
Warm start at $C_{\text{MC}}(w)=15$ with 10 classical strings $w$
$p$ | $3/2$ | $5/2$ | $7/2$ | $9/2$
Number of strings improved | 0 | 0 | 0 | 0

Table 1: MaxCut. QAOA improvement from good initial classical strings on a 12
vertex, 3-regular graph with a maximum cut size of $16$. The average cut size
is $9$ and the number of parameters is $2p$. When warm starting at cut size
$11$, the number of strings which improve increases steadily with depth,
although all improvements are small. All improvements come in pairs because of
the bit flip symmetry of MaxCut. At cut size $15$ we see zero improvements.

---
Standard QAOA
$p$ | $1$ | $2$ | $3$ | $4$ | $5$ | $6$
Expected cut size | 12.15 | 13.43 | 14.28 | 14.86 | 15.20 | 15.41

Table 2: MaxCut. Performance of the standard QAOA for the same instance as
above, starting in the uniform superposition where the expected value of
$C_{\text{MC}}$ is $9$. The number of parameters is $2p$. Note the steady
improvement with depth.

###  3.2 Large system sizes and low depths

We now look at MaxCut on large $3$-regular graphs. We toss a representative
instance with $n=300$ vertices and a largest cut size of $415$. We prepare
good classical strings using two classical algorithms: simulated annealing and
Goemans-Williamson [GW95]. Our simulated annealing algorithm samples strings
from a thermal distribution using a Metropolis-Hastings cluster update rule
$1000n$ times. For temperatures of $1.25$ and $1.75$, we generate 1000 good
classical strings with average cut size $310.6$ and $287.8$, respectively. We
also produce 1000 classical strings with an average cut value of $398.3$ using
the Goemans-Williamson algorithm. We then simulate the QAOA at $p=3/2$ and
$p=5/2$ using the edge neighborhoods trick in Section 2.3, and see zero
improvement on any of the initial strings generated by either algorithm. Our
results suggest that the fraction of strings which improve goes to zero as the
system size grows.

##  4 Failure on a Decoupled Problem

A simple intuition for why starting from a good string might fail is as
follows: consider the cost function $C_{\langle i,j\rangle}$ on edge $\langle
i,j\rangle$ for MaxCut. For a given string $w$, the clause is either satisfied
or not, so we can suggestively write the expectation of $C$ after applying the
QAOA unitary $U$ as

$\displaystyle\bra{w}U^{\dagger}C_{\langle
i,j\rangle}U\ket{w}=1-\varepsilon_{\langle i,j\rangle}$ (10)

in the satisfied case, and

$\displaystyle\bra{w}U^{\dagger}C_{\langle i,j\rangle}U\ket{w}=\delta_{\langle
i,j\rangle}$ (11)

in the unsatisfied case (note that if $U=1$ then $\varepsilon_{\langle
i,j\rangle}$ and $\delta_{\langle i,j\rangle}$ are zero). Now imagine that the
average of $\varepsilon_{\langle i,j\rangle}$ over the satisfied edges is
equal to the average of $\delta_{\langle i,j\rangle}$ over the unsatisfied
edges. In a good string, there are more satisfied edges than unsatisfied, so
we have

$\displaystyle\bra{w}U^{\dagger}CU\ket{w}\leq\bra{w}C\ket{w},$ (12)

where $C$ is the total cost over all edges. Therefore, no improvement would be
possible.

We now give a simple example where exactly this happens. Consider a graph of
$2m$ vertices consisting of $m$ pairs of vertices, each pair connected by an
edge. Focus on the first copy which has edge $\langle 1,2\rangle$. At any
depth, the QAOA consists of applications of the unitaries that are
exponentials of phases times $X_{1}+X_{2}$ or $Z_{1}Z_{2}$. Note that these
operators commute with the swap operator on 1 and 2 as well as the operator
$X_{1}X_{2}$. The eigenstates and eigenvalues of these two operators are given
in Table 3.

Eigenstate | Eigenvalue of swap | Eigenvalue of $X_{1}X_{2}$
---|---|---
$\ket{a}=\frac{1}{\sqrt{2}}(\ket{+1,+1}-\ket{-1,-1})$ | $+1$ | $-1$
$\ket{b}=\frac{1}{\sqrt{2}}(\ket{+1,-1}-\ket{-1,+1})$ | $-1$ | $-1$
$\ket{c}=\frac{1}{\sqrt{2}}(\ket{+1,+1}+\ket{-1,-1})$ | $+1$ | $+1$
$\ket{d}=\frac{1}{\sqrt{2}}(\ket{+1,-1}+\ket{-1,+1})$ | $+1$ | $+1$
Table 3:  Eigenstates and eigenvalues of the swap and $X_{1}X_{2}$ operators.

Note that $\ket{a},\ket{b}$ have unique quantum numbers so under any QAOA
unitary they can each only pick up a phase, but $\ket{c},\ket{d}$ can mix as
(up to an overall phase)

$\displaystyle U\ket{c}$
$\displaystyle=\cos\theta\ket{c}+e^{i\phi}\sin\theta\ket{d},$ (13)
$\displaystyle U\ket{d}$
$\displaystyle=e^{-i\phi}\sin\theta\ket{c}-\cos\theta\ket{d}.$ (14)

Then the QAOA initialized in the unsatisfied string
$\ket{+1,+1}=\frac{1}{\sqrt{2}}(\ket{c}+\ket{a})$ evolves as

$\displaystyle
U\ket{+1,+1}=\frac{1}{\sqrt{2}}(\cos\theta\ket{c}+e^{i\phi}\sin\theta\ket{d}+e^{i\eta_{1}}\ket{a})$
(15)

where $\eta_{1}$ is another phase. Therefore, the expected value of $C$ goes
from 0 to $\frac{1}{2}\sin^{2}\theta$. Similarly, initializing the QAOA in the
satisfied string $\ket{+1,-1}$, we find that the expected value of $C$ goes
from 1 to $1-\frac{1}{2}\sin^{2}\theta$. So for the $m$-edge problem starting
in any string $w$, every unsatisfied clause is improved by
$\frac{1}{2}\sin^{2}\theta$ and every satisfied edge degrades by the same
amount. Therefore, no matter the depth, the QAOA starting in a good string
cannot improve upon its initial cost.

We contrast this with how the usual QAOA performs. Starting in the uniform
superposition at $p=1$ with $\gamma=\pi/2$ and $\beta=\pi/8$, we go to the
perfect cut with probability $1$. Note that for the standard QAOA, there is an
asymptotic performance guarantee in that the maximum expectation value is
guaranteed to reach the optimum as $p\rightarrow\infty$ [FGG14]. This example
is notable in showing that no such guarantee is present for the case of warm-
start QAOA.

##  5 Small angles and low depth

When improvements are seen in the numerical experiments, they are always
small. One explanation for this could be that the optimal $\beta$’s, which
drive the mixing, are also small. Therefore, in this section we examine when
improvements are possible for small $\beta$’s. First we show that for MaxCut
at $p=1/2$, no improvement is possible for any $\beta_{1}$. Next we give two
necessary and sufficient conditions for improvement at $p=3/2$ when
$\beta_{1},\beta_{2}$ are small. We find that in our MaxCut numerical
experiments at $p=3/2$, improvement was seen if and only if one of our
conditions were satisfied. Consistent with our intuition, improvement is
possible only if it is possible for small $\beta$’s.

###  5.1 Quantum walk starting on a classical string ($p=1/2$)

The expected cost for $p=1/2$ after evolving under $B$ is given by

$\displaystyle\bra{w}e^{i\beta_{1}B}C_{Z}e^{-i\beta_{1}B}\ket{w}$
$\displaystyle=-\sum_{\langle
i,j\rangle}\bra{w}e^{i\beta_{1}B}Z_{i}Z_{j}e^{-i\beta_{1}B}\ket{w}$
$\displaystyle=-\sum_{\langle
i,j\rangle}\bra{w}(\cos(2\beta_{1})Z_{i}+\sin(2\beta_{1})Y_{i})(\cos(2\beta_{1})Z_{j}+\sin(2\beta_{1})Y_{j})\ket{w}$
$\displaystyle=\cos^{2}(2\beta_{1})C_{Z}(w).$ (16)

Therefore, if $w$ is a good starting string, meaning that $C_{Z}(w)>0$, then
$\beta_{1}=0$ is optimal and the optimized expected cost remains $C_{Z}(w)$.

###  5.2 Warm starting at $p=3/2$ for MaxCut on $3$-regular graphs

We now look at the $p=3/2$ QAOA warm starting in $|w\rangle$ with both
$\beta$’s small but $\gamma$ arbitrary. We focus on MaxCut for 3-regular
graphs. We state a necessary and sufficient condition for improvement here,
and give the detailed derivation in Appendix D.

First, let us define the quantity

$\displaystyle\delta_{i}=(C_{i}-C(w))/2,$ (17)

where $C_{i}=\bra{w}X_{i}CX_{i}\ket{w}$ measures the cost of $w$ after
flipping bit $i$. For MaxCut on 3-regular graphs, $|\delta_{i}|=$ 1 or 3. At
$p=3/2$, we find that improvement of the cost is possible for small $\beta$’s
if and only if

$\displaystyle\sum_{|\delta_{i}|=1}\delta_{i}>0\qquad\text{or}\qquad\sum_{i}\delta_{i}^{3}>0.$
(18)

If $w$ is a local maximum with respect to bit flips, then all of the
$\delta_{i}$ are negative and neither condition can be met. We expect that for
most good strings, neither of these two conditions can be met. We make use of
the identity

$\displaystyle\sum_{i}\delta_{i}=-2C_{Z}(w),$ (19)

which is straightforward to establish. Because $C_{Z}(w)>0$ for a good
starting string, the $\delta_{i}$ are usually negative, meaning that both
conditions (18) are unlikely. As the goodness of the starting string increases
there will be fewer positive $\delta_{i}$, so the conditions are even less
likely to be met. This is consistent with the numerics on small MaxCut
instances at $p=3/2$ in Section 3.1 where there are fewer improvements on the
better strings. Further, we expect that as $n$ increases, fluctuations that
allow the conditions to be met will become even more rare. This is consistent
with the findings in Section 3.2 on large MaxCut instances, where the
condition is never met and improvement is never seen for thousands of initial
strings. In all of our numerics in Section 3, improvement was seen at $p=3/2$
if and only if equation (18) was satisfied.

##  6 Thermal argument for getting stuck

In this section we give two upper bounds for the progress made by the single-
string warm-start QAOA at constant depth on large bounded-degree graphs. The
first bound shows that strings chosen uniformly at random are likely to get
stuck. The second bound instead considers strings chosen from a finite-
temperature thermal ensemble, and the argument uses the principle of minimum
energy from thermodynamics in equation (97).

###  6.1 Starting from a uniformly random string

We first consider the case of starting the QAOA with a classical bit string
chosen uniformly at random. Our results apply to generic cost functions for
general bounded-degree graphs,

$C(z)=\sum_{\langle i,j\rangle\in E}C_{\langle i,j\rangle}(z_{i},z_{j}),$ (20)

with $m$ edges at any constant depth. We define the average value per edge of
the cost function,

$\displaystyle\overline{c}=\frac{1}{2^{n}}\sum_{z\in\\{-1,1\\}^{n}}\frac{1}{m}C(z).$
(21)

Using the fact that $C$ is a sum of terms, most of which are uncorrelated
because of the bounded degree, one can show that for any $\epsilon>0$, and $w$
chosen uniformly at random,

$\displaystyle\Pr_{w}\left(\left|\frac{1}{m}C(w)-\bar{c}\right|\geq\frac{1}{m^{1/2-\varepsilon}}\right)\longrightarrow
0,\quad\text{as }m\rightarrow\infty.$ (22)

This implies that in the limit of large graph size $m$, almost all strings
have cost function values extremely close to the average value $\overline{c}$.

In Appendix E.1 we prove the following theorem, which states that typical
strings cannot be improved by constant depth QAOA.

######  Theorem 6.1.

For any $\epsilon>0$, and $w$ chosen uniformly at random,

$\displaystyle\Pr_{w}\left(\frac{1}{m}\langle
w|U_{w}^{\dagger}CU_{w}|w\rangle-\frac{1}{m}C(w)\geq\frac{1}{m^{1/2-\varepsilon}}\right)\rightarrow
0,\qquad\text{as }m\rightarrow\infty,$ (23)

where $U_{w}$ is the optimal constant-depth QAOA unitary for each $w$.

Therefore, we have that for nearly all initial strings, the constant-depth
QAOA can only improve the cost function (per edge) by an amount that vanishes
in the limit of large graphs. While this result does not apply to warm starts,
whose starting cost value per edge $C(w)/m$ is substantially larger than
$\bar{c}$, it is very surprising that even starting from a mediocre string,
the QAOA fails to make progress.

Equation (22) implies that warm starts form a vanishingly small fraction of
all strings. Next, we give results on these rare warm-start strings.

###  6.2 Starting from a typical good string

We work in the setting of $d$-regular graphs with a cost function of the form
of equation (20). For typical large random $d$-regular graphs, almost all of
the local neighborhoods are trees. Fixing a neighborhood radius $r$
(corresponding to the QAOA with $p=r+\frac{1}{2}$, see Section 2.3), we define
the fraction $\delta$ of edges whose neighborhoods are not trees as

$\displaystyle\delta=1-\frac{|E_{T}|}{m},$ (24)

where $E_{T}$ denotes the set of edges whose neighborhood of radius $r$ is a
tree. Our argument will be useful in the case that $\delta$ is small. For
random $d$-regular graphs with $n\to\infty$ with $d$ and $r$ fixed,
$\delta=O\left(1/n\right)$ ([JLR00], Theorem 9.5) is vanishingly small.

We introduce two ensembles associated with the warm-start string $w$. For any
classical string $w\in\\{-1,1\\}^{n}$ and a mostly locally tree-like $G$ we
define its _local ensemble_ by

$\displaystyle\rho_{w,\mathrm{tree}}=\frac{1}{|E_{T}|}\sum_{\langle
i,j\rangle\in E_{T}}|w_{\langle i,j\rangle}\rangle\langle w_{\langle
i,j\rangle}|,$ (25)

where $w_{\langle i,j\rangle}$ denotes the restriction of $w$ onto the local
tree neighborhood $T_{\langle i,j\rangle}$, and $T_{\langle i,j\rangle}$
denotes the tree neighborhood centered around edge $\langle i,j\rangle\in
E_{T}$. Each tree neighborhood has a fixed number of vertices, so $w_{\langle
i,j\rangle}$ is a string of that length, and $\rho_{w,\mathrm{tree}}$ is a
density matrix over the corresponding number of qubits.

Let

$\displaystyle\rho_{\beta}=\frac{1}{\mathrm{Tr}\big{(}e^{-\beta(-C)}\big{)}}e^{-\beta(-C)}$
(26)

be the global thermal density matrix with respect to the Hamiltonian $H=-C$,
at inverse temperature $\beta$ chosen so that
$\mathrm{Tr}(C\rho_{\beta})=C(w)$. Here we introduce a minus sign because in
thermodynamics we associate low temperatures with low energies, whereas for us
good strings have high $C$.

We will consider the reduced density matrix of $\rho_{\beta}$ onto the tree
neighborhood $T_{\langle i,j\rangle}$, denoted $\mathrm{Tr}_{G\backslash
T_{\langle i,j\rangle}}\left(\rho_{\beta}\right)$. Because all the tree
neighborhoods $T_{\langle i,j\rangle}$ are isomorphic subgraphs, we can
identify their associated Hilbert spaces. We consider each reduced operator
$\mathrm{Tr}_{G\backslash T_{\langle i,j\rangle}}\left(\rho_{\beta}\right)$ to
act on the same abstract Hilbert space (the same Hilbert space implicit in the
definition of $\rho_{w,\mathrm{tree}}$). With this identification, we can
define the average over neighborhoods,

$\displaystyle\rho_{\beta,\mathrm{tree}}=\frac{1}{|E_{T}|}\sum_{\langle
i,j\rangle\in E_{T}}\mathrm{Tr}_{G\backslash T_{\langle
i,j\rangle}}\left(\rho_{\beta}\right).$ (27)

Again, both $\rho_{w,\mathrm{tree}}$ and $\rho_{\beta,\mathrm{tree}}$ act on
the Hilbert space of a single tree neighborhood: although their definitions
involve the sum of terms associated to different neighborhoods, these
neighborhoods are all isomorphic trees, and we implicitly identify the
neighborhoods when summing the terms.

We now give our main result, an upper bound on how much the cost function of a
warm-start string $w$ can improve under the QAOA at fixed depth. The upper
bound depends on a quantity $\varepsilon_{w}$, which we call the “thermality
coefficient”, that measures the distance between the ensembles
$\rho_{w,\mathrm{tree}}$ and $\rho_{\beta,\mathrm{tree}}$:

$\displaystyle\varepsilon_{w}=\|\rho_{\beta,\mathrm{tree}}-\rho_{w,\mathrm{tree}}\|_{1},$
(28)

where $\beta$ is the inverse temperature chosen so that

$\displaystyle\mathrm{Tr}(C\rho_{\beta})=C(w)$ (29)

and where
$\|\rho-\sigma\|_{1}\equiv\mathrm{Tr}\Big{(}\sqrt{(\rho-\sigma)^{\dagger}(\rho-\sigma)}\Big{)}$
denotes the trace norm. Both $\rho_{\beta,\mathrm{tree}}$ and
$\rho_{w,\mathrm{tree}}$ are diagonal in the computational basis, i.e., they
are classical probability distributions over strings, in which case
$\varepsilon_{w}$ is also equal to twice the total variation distance. When
$\varepsilon_{w}$ is small, we refer to $w$ as being “locally thermal”. Note
that $\varepsilon_{w}$ depends on the QAOA depth $p$ which defines the
neighborhood size. Our main result, stated next and proven in Appendix E.2,
shows that if $w$ is locally thermal, i.e., if $\varepsilon_{w}$ is small,
then $w$ can only improve by a small amount.

######  Theorem 6.2.

Consider the single-string warm-start QAOA initialized in a string $w$ with
thermality coefficient $\varepsilon_{w}$, and let $\delta$ be the fraction of
neighborhoods whose edges are not trees. Then

$\displaystyle\frac{1}{m}\langle w|U^{\dagger}_{w}CU_{w}|w\rangle\leq
c(w)+2\varepsilon_{w}+4\delta,$ (30)

where $c(w)=C(w)/m$ is the cut fraction of the original string $w$.

Because $\delta$ is small for random graphs, the heart of the result is the
dependence on $\varepsilon_{w}$. If $w$ is locally thermal, then $w$ can only
improve by a small amount. In Appendices E.3 and E.4, we give theoretical and
numerical evidence that $\varepsilon_{w}$ scales as $1/\sqrt{m}$ for typical
good strings $w$.

##  7 Compression argument for getting stuck

In this section we develop another argument to upper bound the progress made
by the QAOA starting from a good string. This result is complementary to the
previous results and uses a different assumption. We imagine that the initial
good string is chosen uniformly at random from the set of all strings with
cost $C_{0}$. We seek to improve the cost above some target $C_{1}$. Our
argument will produce a useful bound whenever the number of strings $d_{0}$ at
cost $C_{0}$ is much larger than the number of strings $d_{1}$ with cost at
least $C_{1}$. In particular, if the ratio $d_{1}/d_{0}$ is suppressed
exponentially in the size of the graph, then with high probability, the
randomly chosen initial string cannot be improved beyond $C_{1}$ using depth
$p=O(n^{q})$ for $q<1$.

We refer to this argument as a “compression” argument because of the following
intuition. Consider a fixed QAOA unitary $U$. If there are many more strings
at cost $C_{0}$ than at cost above $C_{1}$, then due to unitarity, $U$ cannot
map all (or even most) of the strings from cost $C_{0}$ to above $C_{1}$. That
is, the unitary cannot “compress” a larger space (of strings at $C_{0}$) to a
smaller space (of strings above $C_{1}$). This is the core of the argument. Of
course, there is more than just one QAOA unitary, so there is no need for a
single unitary $U$ to map all the strings at $C_{0}$ to above $C_{1}$.
Instead, one can use different QAOA unitaries $U_{w}$ that depend on the
initial string $w$, hoping that for each $w$ at cost $C_{0}$ there is some
$U_{w}$ such that $U_{w}|w\rangle$ has cost at least $C_{1}$. However, this is
impossible when the depth $p$ is not too large, because the space of unitaries
that can be generated by the QAOA at depth $p$ is small in the appropriate
sense.

Our results prior to this section only characterize the improvement in
expected cost, without explicitly bounding the probability of obtaining a good
string after measurement. However, for the case of states produced by
constant-depth circuits, one can show the distribution of measured costs is
concentrated about the expected cost [FGG14]. In contrast, here we will
consider circuits of super-constant depth, so we must take care with the
distinction between the expected cost and the distribution of measured costs.
To this end, we introduce the following notion of _improvable strings_.

######  Definition 7.1.

A string $w$ is $p$-improvable to cost $C_{1}$, with a selection probability
at least $\Delta$, if there exists a depth-$p$ QAOA unitary $U_{w}$ such that
a measurement of $U_{w}|w\rangle$ in the computational basis has a probability
at least $\Delta$ of yielding a string with cost at least $C_{1}$.

######  Theorem 7.2.

Consider warm-start QAOA at depth $p$, starting with a string chosen uniformly
at random among strings with cost $C_{0}$. Let $d_{0}$ be the number of
strings at cost $C_{0}$, and let $d_{1}$ be the number of strings with cost at
least $C_{1}$. Then with probability at least $1-\epsilon$, the initial string
will not be improvable to cost $C_{1}$ using selection probability at least
$\epsilon$, where

$\displaystyle\epsilon=\left(\frac{2d_{1}}{d_{0}}\right)^{\frac{1}{2p+2}}(16\pi
pn^{2})^{\frac{p}{p+1}}.$ (31)

This theorem is most useful when $d_{1}/d_{0}$ is exponentially suppressed in
$n$, i.e. when there are exponentially more strings near the starting cost
than above the target cost. Then $\epsilon$ will be small for $p$ sub-linear
in $n$, and we conclude that with high probability, the initial string will
not be improvable.

More concretely, suppose that there are exponentially (in $n$) more strings at
cost $C_{0}$ than there are strings with cost above $C_{1}$. This is often the
case when $C_{1}-C_{0}$ scales with $n$, and we provide further justification
below. In that case we have

$\displaystyle\frac{d_{1}}{d_{0}}=O(e^{-an})$ (32)

for some constant $a>0$. Consider a depth $p=O(n^{q})$ for $q<1$. Then Theorem
7.2 holds with

$\displaystyle\epsilon=O(e^{-bn^{1-q}}),$ (33)

for some constant $b>0$, decaying faster than any polynomial in $n$. Thus the
probability of improvement is very small at large $n$.

To further justify the scaling of (32), we consider the MaxCut cost function
of the decoupled graph in Section 4, which has $m=n/2$ pairs of vertices, each
pair connected by an edge. The number of strings as a function of cost (i.e.,
the density of states) is binomial, with variance $m$. For $C_{1}-C_{0}\propto
m$, one obtains (32). More generally, one also expects (32) whenever the free
energy associated to $C$ is extensive since $S=-\partial F/\partial T$ then
implies an extensive entropy. The free energy of MaxCut on $d$-regular graphs
exhibits this behavior, as shown (at least above the phase transition) in
[Coj+22]. For other classes of problems with random local terms, also see
Proposition 4 of [Dal+22], where their upper bound on the number of solutions
as a function of cost indicates similar exponential scaling.

##  8 Conclusion

This work was motivated by numerical experiments on the single-string warm-
start QAOA showing zero improvement for almost all good initial strings from
the starting cost value. We presented several theoretical results to explain
these consistent observations. This behavior stands in stark contrast to the
standard QAOA initialized in the uniform superposition over all bit strings,
which appears to make consistent progress toward the optimum.

Acknowledgments

M.C. acknowledges support from DOE CSG award fellowship (DESC0020347). D.R.
acknowledges support from NTT (Grant AGMT DTD 9/24/20). E.T. acknowledges
funding received from DARPA 134371-5113608, and DOD grant award KK2014. M.C.
and E.F. thank Boaz Barak, Beatrice Nash, and Leo Zhou for early discussions
of these ideas. D.R. and E.T. thank Aram Harrow for discussion.

## References

  * [Coj+22] Amin Coja-Oghlan, Philipp Loick, Balázs F Mezei and Gregory B Sorkin  “The Ising antiferromagnet and max cut on random regular graphs”  In _SIAM Journal on Discrete Mathematics_ 36.2 SIAM, 2022, pp. 1306–1342
  * [Dal+22] Alexander M Dalzell, Nicola Pancotti, Earl T Campbell and Fernando GSL Brandão  “Mind the gap: Achieving a super-Grover quantum speedup by jumping to the end”  In _arXiv preprint arXiv:2212.01513_ , 2022
  * [EMW21] Daniel J. Egger, Jakub Mareček and Stefan Woerner  “Warm-starting quantum optimization”  In _Quantum_ 5 Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften, 2021, pp. 479  DOI: 10.22331/q-2021-06-17-479
  * [Far+22] Edward Farhi, Jeffrey Goldstone, Sam Gutmann and Leo Zhou  “The Quantum Approximate Optimization Algorithm and the
Sherrington-Kirkpatrick Model at Infinite Size”  In _Quantum_ 6 Verein zur
Forderung des Open Access Publizierens in den Quantenwissenschaften, 2022, pp.
759  DOI: 10.22331/q-2022-07-07-759

  * [FGG14] Edward Farhi, Jeffrey Goldstone and Sam Gutmann  “A Quantum Approximate Optimization Algorithm”, 2014  arXiv:1411.4028 [quant-ph]
  * [GW95] Michel X. Goemans and David P. Williamson  “Improved Approximation Algorithms for Maximum Cut and Satisfiability Problems Using Semidefinite Programming”  In _J. ACM_ 42.6 New York, NY, USA: Association for Computing Machinery, 1995, pp. 1115–1145  DOI: 10.1145/227683.227684
  * [JLR00] Svante Janson, Tomasz Luczak and Andrzej Rucinski  “Random Regular Graphs”  In _Random Graphs_ John Wiley & Sons, Ltd, 2000, pp. 233–270  DOI: https://doi.org/10.1002/9781118032718.ch9
  * [Tat+20] Reuben Tate et al.  “Bridging Classical and Quantum with SDP initialized warm-starts for QAOA”, 2020  arXiv:2010.14021 [quant-ph]

###### List of appendices

  1. 1 Introduction
  2. 2 Standard and single-string warm-start QAOA
  3. 3 Numerical experiments
  4. 4 Failure on a Decoupled Problem
  5. 5 Small angles and low depth
  6. 6 Thermal argument for getting stuck
  7. 7 Compression argument for getting stuck
  8. 8 Conclusion
  9. A Using other types of starts
  10. B Maximum Independent Set
  11. C The Sherrington-Kirkpatrick model
  12. D Condition for MaxCut improvement at small angles for $p=3/2$
  13. E Thermality argument proofs
  14. F Compression argument proofs

In these appendices, we provide additional details and prove statements in the
main text. In Section A, we discuss other types of initial states for the
QAOA, including starting from a bad string and starting from a uniform
superposition of strings with the same cost. Next, we give evidence that the
single-string warm-start QAOA fails on two new problems: the Maximum
Independent Set problem on $d$-regular graphs (Section B) and the Sherrington-
Kirkpatrick model (Section C). In Section D we give conditions under which the
single-string warm-start QAOA can improve at $p=3/2$ for small mixing angles.
In Section E we prove that strings which are locally thermal cannot be
improved. We also give analytic and numerical evidence that warm strings are
locally thermal. Finally, in Section F we prove our compression argument,
which shows that the single-string warm-start QAOA cannot improve for sub-
linear depths when the number of strings at a higher cost is very small
compared to the number of strings at the initial cost.

##  Appendix A Using other types of starts

###  A.1 Starting from a bad string

A bad string is one whose cost function per edge $C(w)/m$ is less than the
average cost per edge $\bar{c}$, defined as

$\displaystyle\overline{c}=\frac{1}{2^{n}}\sum_{z\in\\{-1,1\\}^{n}}\frac{1}{m}C(z).$
(34)

In contrast to good strings, bad strings can all be improved by the lowest
depth QAOA by applying the one-parameter $p=1/2$ QAOA with $\beta=\pi/4$. This
rotates the state into a uniform superposition over all computational basis
states, each with an amplitude of $2^{-\frac{n}{2}}$ times a phase that
depends on $w$. Therefore, $C(w)$ improves to the mean of the cost function
over all strings. The thoughtful reader can check that this does not serve as
a counterexample to our claims.

###  A.2 Starting from superpositions of strings with the same cost

What about starting in a uniform superposition of basis states with the same
good value of the cost function? It may be difficult to use a classical
algorithm to produce such a superposition, but here we simply explore what
happens if you have such a state in hand.

We randomly pick a $16$ bit 3-regular graph whose largest cut value is $22$.
The mean over all strings of the MaxCut cost function is $12$. We begin with
the uniform superposition of all strings whose cost is exactly $12$. The
overlap (amplitude squared) of this normalized state with the uniform
superposition over all strings $|s\rangle$ is $0.162$. At $p=3/2$, optimal
parameters take the cost function to $12.064$. At $p=5/2$ and $7/2$, the
improvement is to $12.173$ and $12.246$, respectively. This is not much
improvement and should be contrasted with the usual QAOA starting state
$|s\rangle$, where the expected value of the cost is $12$ and where the QAOA
makes steady good progress as the depth increases. For warm-start
superpositions at higher values of the cost, such as $13$ up to $18$, we see
no improvements at all for $p=3/2,\ 5/2$, and $7/2$.

##  Appendix B Maximum Independent Set

In this section, we show using another example that the QAOA gets stuck
starting on a good string. We look at the Maximum Independent Set problem:
given a graph $G=(V,E)$, the goal is to find a maximum size subset of vertices
which have no edge connecting any pair of them. Formally, we want to find a
string of bits $b$ such that the Hamming weight $W(b)=\sum_{i}b_{i}$ is
maximized, subject to the constraint that $\sum_{\langle i,j\rangle\in
E}b_{i}b_{j}=0$. Note that in this section we are using bits $b_{i}$ that are
$\\{0,1\\}$-valued, with corresponding quantum operators
$\hat{b}_{i}=(I-Z_{i})/2$. To make this problem amenable to the usual QAOA,
where any bit string is a valid input, we use the relaxed cost function

$\displaystyle C(b)=\sum_{i\in V}b_{i}-\sum_{\langle i,j\rangle\in
E}b_{i}b_{j}\equiv W(b)-K(b),$ (35)

which we aim to maximize. Given a bit string $b$ with cost $C(b)$, we can
prune it, fixing violations $b_{i}b_{j}=1$ one at a time by setting either
$b_{i}$ or $b_{j}$ equal to 0. Fixing one violation decreases $W$ by $1$ but
also decreases $K$ by at least $1$, so $C$ does not decrease. Continuing to
prune until there are no violations, we obtain an independent set of size at
least $C(b)$. This also shows that the maximum of $C$ is the size of the
largest independent set. Note that for a $d$-regular graph we can write the
cost function as

$\displaystyle C(b)=W(b)-K(b)=\sum_{\langle j,k\rangle\in
E}\left[\frac{1}{d}(b_{j}+b_{k})-b_{j}b_{k}\right],$ (36)

which shows that this cost function is a sum of terms which act the same way
on each edge, satisfying the uniformity assumption required for our
statistical argument in Section 6.2.

We now provide numerical and analytic evidence that the single-string warm-
start QAOA fails for Maximum Independent Set. We first see numerically at high
$p$ that the warm-start QAOA fails at low bit number. Then, we show
analytically that improvement is impossible at $p=1/2$ if the QAOA is
initialized in an independent set obtained by running a standard greedy
algorithm.

###  B.1 Numerical experiments

We randomly sample a $16$ vertex $3$-regular graph whose largest independent
set size is $7$, with degeneracy $3$. The average over all strings of the cost
$C(b)$ is $2$, which is therefore also the expected value of $C$ in the
quantum state $|s\rangle$, where the usual QAOA starts. In Table 5 we show how
the usual QAOA performs when starting with the state $|s\rangle$. Note that as
$p$ gets bigger, performance improves, steadily approaching the largest
independent set possible which has size $7$.

Warm start at $C_{\text{MIS}}(w)=4$ with 371 independent sets $w$
---
$p$ | $3/2$ | $5/2$ | $7/2$ | $9/2$
Number of strings improved | 20 | 101 | 283 | 368
Mean cost of improved strings | $4.06$ | $4.06$ | 4.11 | 4.23
Largest cost of improved strings | $4.10$ | $4.27$ | 4.47 | 4.64
Warm start at $C_{\text{MIS}}(w)=5$ with 230 independents sets $w$
$p$ | $3/2$ | $5/2$ | $7/2$ | $9/2$
Number of strings improved | 0 | 0 | 1 | 1
Mean cost of improved strings | $-$ | $-$ | 5.002 | 5.002
Largest cost of improved strings | $-$ | $-$ | 5.002 | 5.002

Table 4: Maximum Independent Set. QAOA improvement from good initial classical
strings (corresponding to valid independent sets) on a 16 vertex, 3-regular
graph with a largest independent set size of 7. The number of parameters is
$2p$.

---
Standard QAOA
$p$ | $1$ | $2$ | $3$ | $4$
Expected cost | 4.40 | 5.14 | 5.61 | 5.86

Table 5: Maximum Independent Set. Performance of the standard QAOA for the
same instance as Table 5, starting in the uniform superposition where the
expected value of $C_{\text{MIS}}$ is $2$. The number of parameters is $2p$.
Note that there is no indication that the standard QAOA gets stuck.

We now look at what happens when starting with a good string. We only look at
starting strings which are valid independent sets, which means that $K(w)=0$.
Table 5 shows data for starting the QAOA with strings of cost $4$ and $5$.
Note that there is either no improvement or very small improvement, similar to
our numerical experiments for MaxCut in Section 3.1.

###  B.2 No improvement at $p=1/2$

We now analyze the performance of the $p=1/2$ QAOA on a $d$-regular graph
starting from a string $w$. Recall that in this section the bits $w_{i}$ are
$\\{0,1\\}$-valued. Using (35), for all $\beta_{1}$, we have

$\displaystyle\bra{w}e^{i\beta_{1}B}Ce^{-i\beta_{1}B}\ket{w}$
$\displaystyle=\sum_{i\in
V}\bra{w}e^{i\beta_{1}X_{i}}\hat{b}_{i}e^{-i\beta_{1}X_{i}}\ket{w}-\sum_{\langle
i,j\rangle\in
E}\bra{w}e^{i\beta_{1}X_{i}}\hat{b}_{i}e^{-i\beta_{1}X_{i}}e^{i\beta_{1}X_{j}}\hat{b}_{j}e^{-i\beta_{1}X_{j}}\ket{w}$
(37) $\displaystyle=\sum_{i\in
V}\bra{w}\left(\sin^{2}\beta_{1}+[1-2\sin^{2}\beta_{1}]\hat{b}_{i}\right)\ket{w}$
$\displaystyle\quad-\sum_{\langle ij\rangle\in
E}\bra{w}\left(\sin^{2}\beta_{1}+[1-2\sin^{2}\beta_{1}]\hat{b}_{i}\right)\left(\sin^{2}\beta_{1}+[1-2\sin^{2}\beta_{1}]\hat{b}_{j}\right)\ket{w}$
(38)
$\displaystyle=W(w)-K(w)+\frac{d}{2}\left[4W(w)-n\right]\sin^{4}\beta_{1}+[n-W(w)(d+2)]\sin^{2}\beta_{1}+K(w)\sin^{2}(2\beta_{1}).$
(39)

Let us now assume that we start with a string $w$ which corresponds to a valid
independent set, meaning that $K(w)=0$. The corresponding cost function value
is then just $W(w)$, the Hamming weight of the initial string $w$. We can
optimize over $\beta_{1}$ noting that we have a quadratic function of
$\sin^{2}\beta_{1}$. The optimum occurs when

$\displaystyle\sin^{2}\beta_{1}$
$\displaystyle=\frac{1}{d}\frac{n-W(w)(d+2)}{n-4W(w)}.$ (40)

Substituting this value back into equation (39) to get the optimal value of
the cost function, we find

$\displaystyle\bra{w}e^{i\beta_{1}B}Ce^{-i\beta_{1}B}\ket{w}$
$\displaystyle=W(w)+\frac{1}{2d}\frac{(n-W(w)(d+2))^{2}}{n-4W(w)}.$ (41)

For improvement we need the second term in (41) to be positive. This requires
$W<n/4$. Since $\sin^{2}\beta_{1}$ is also positive, we require the stronger
condition $W<n/(d+2)$. Therefore, improvement can only be made if
$C(w)=W(w)<n/(d+2)$.

Now, suppose that our starting string is an independent set obtained by
running a standard greedy algorithm which achieves an independent set of size
at least $n/(d+1)$. Then $K=0$ and $W\geq n/(d+1)$, so the condition is not
met, and no improvement is possible for $p=1/2$. Note that starting with the
empty set, that is with $W=0$, the $p=1/2$ QAOA will get to an independent set
of size $n/(2d)$.

##  Appendix C The Sherrington-Kirkpatrick model

The Sherrington-Kirkpatrick (SK) model is defined on the complete graph, and
on each edge there is a coupling with a random sign:

$\displaystyle C_{\text{SK}}=\sum_{i,j}J_{i,j}Z_{i}Z_{j},$ (42)

where each $J_{i,j}$ is $+1$ or $-1$ with probability $1/2$. Parisi
discovered, for any typical set of $J$’s, that the maximum energy divided by
$n^{\frac{3}{2}}$, in the limit as $n$ goes to infinity, is a computable
constant approximately equal to $0.763166$. It is known that the QAOA starting
in the uniform superposition $|s\rangle$ makes good progress toward the
optimum as the depth increases [Far+22].

Here we are on a complete graph, and each edge sees a different neighborhood
because of the varying $J$’s. Because our thermal argument and small angles
arguments now do not apply, it is interesting to confirm numerically that the
single-string warm-start QAOA fails on Sherrington-Kirkpatrick model.
Therefore, we look numerically at a random instance generated at $14$ bits.
The lowest energy is $-33$ and the highest is $+35$. The performance of the
usual QAOA starting on the state $|s\rangle$ is shown in Table 7. Turning to
warm starts in Table 7, we look at $50$ randomly chosen starting strings with
energy $11$. We see zero or little improvement out to depth $p=7/2$ for all
strings besides four notable exceptions which we will discuss below. At an
energy of $17$, there are no unusual improvements and the number of strings
which improve is fewer than at $11$. Aside from the exceptions which we
explain next, warm starts in the SK model also get stuck as they do in our
other examples.

Warm start at $C_{\text{SK}}(w)=11$
---
746 classical strings $w$, 50 samples, 4 exceptions removed
$p$ | $3/2$ | $5/2$ | $7/2$
Number of strings improved | 9 | 17 | 28
Mean cost of improved strings | $11.03$ | $11.23$ | $11.26$
Largest cost of improved strings | $11.05$ | $12.02$ | $12.96$
Warm start at $C_{\text{SK}}(w)=17$
262 classical strings $w$, 50 samples
$p$ | $3/2$ | $5/2$ | $7/2$
Number of strings improved | 1 | 4 | 5
Mean cost of improved strings | 17.003 | 17.18 | 17.28
Largest cost of improved strings | 17.003 | 17.39 | 17.95

Table 6: Sherrington-Kirkpatrick Model. QAOA improvement from good initial
classical strings on a 14-vertex instance of the SK model with lowest energy
$-33$ and highest energy $+35$. The number of parameters is $2p$. At energy
$11$, improvement was possible using magic angles on four classical strings,
two of which went to $19$ and two to $27$.

---
Standard QAOA
$p$ | $1$ | $2$ | $3$ | $4$
Expected cost | 15.05 | 20.40 | 24.27 | 26.19

Table 7: Sherrington-Kirkpatrick Model. Performance of the standard QAOA for
the same instance as Table 7, starting in the uniform superposition where the
expected value of $C_{\text{SK}}$ is 0. The number of parameters is $2p$. Note
the steady improvement with depth.

###  C.1 Magic angles for the Sherrington-Kirkpatrick model

We now discuss the exceptions. For the SK model on an even number of sites,
with any set of couplings $\\{J_{i,j}\\}$, there are parameters at $p=3/2$
which creates a cat state starting on any computational basis state. The
“magic angle” unitary which creates the cat state is given by:

$\displaystyle
U_{\text{magic}}=e^{-i\frac{\pi}{4}B}e^{i\frac{\pi}{4}C_{\text{SK}}}e^{i\frac{\pi}{4}B}.$
(43)

In this section we show that when $n$ is even, this unitary takes any initial
string to a cat state of two strings given (up to global phase) by

$\displaystyle
U_{\text{magic}}\ket{w}=\frac{1}{\sqrt{2}}\left(\ket{w^{\prime}}+e^{i\theta}\ket{-w^{\prime}}\right),$
(44)

where $\theta$ is a known phase, and where

$\displaystyle\ket{w^{\prime}}=\prod_{J_{i,j}=-1}(-iY_{i}Y_{j})\ket{w}.$ (45)

In other words, evolving with the QAOA unitary at these parameters takes
$\ket{w}$ to a cat state involving $\ket{w^{\prime}}$ and $\ket{-w^{\prime}}$,
where $w^{\prime}$ is obtained from $w$ by flipping the $i$th bit if the
product over $j$ of $J_{i,j}$ is $-1$. For a typical $\\{J_{i,j}\\}$ this
makes it seem that $C(w^{\prime})$ is essentially random, not different in
distribution from $C(w^{\prime\prime})$ where $w^{\prime\prime}$ is chosen at
random. If $w$ is a good string, it is unlikely that $w^{\prime}$ will be
better. On rare occasions, this transformation can improve the cost function.
However, improvement becomes less likely for better initial strings. We see
this in our numerics: when starting from strings with energy $17$, none of the
50 warm start samples improve under the magic angle unitary, whereas four do
improve starting at the lower energy of $11$.

To show this result, let us first consider the case where all $J_{i,j}=1$.
Using the fact that $e^{i\frac{\pi}{4}X}Ze^{-i\frac{\pi}{4}X}=Y$, we can
simplify the unitary to

$\displaystyle
e^{-i\frac{\pi}{4}B}e^{i\frac{\pi}{4}\sum_{i,j}Z_{i}Z_{j}}e^{i\frac{\pi}{4}B}\ket{w}=e^{i\frac{\pi}{4}\sum_{i,j}Y_{i}Y_{j}}\ket{w}=e^{-i\frac{\pi}{8}n}e^{i\frac{\pi}{8}(\sum_{i}Y_{i})^{2}}\ket{w}.$
(46)

We will evaluate (46) in the $y$-basis by writing the $Y_{i}$ operators in
terms of their eigenvalues $y_{i}$, which are $\pm 1$ valued bits. In
particular, we will show by induction that for $n$ even, we have

$\displaystyle\exp\bigg{(}{i\frac{\pi}{8}\Big{(}\sum_{i}y_{i}\Big{)}^{2}}\bigg{)}=\frac{e^{i\frac{\pi}{4}}}{\sqrt{2}}\left(1-i^{n+1}y_{1}y_{2}\cdots
y_{n}\right).$ (47)

The $n=2$ base case is immediate:

$\displaystyle\exp\left({i\frac{\pi}{8}(y_{1}+y_{2})^{2}}\right)=\frac{e^{i\frac{\pi}{4}}}{\sqrt{2}}(1-i^{3}y_{1}y_{2}).$
(48)

Now to go from the $n-2$ case to $n$ we have

$\displaystyle\exp\bigg{(}{i\frac{\pi}{8}\Big{(}\sum_{i}y_{i}\Big{)}^{2}}\bigg{)}$
$\displaystyle=\exp\left({i\frac{\pi}{8}(y_{1}+\dots+y_{n-2})^{2}+i\frac{\pi}{4}(y_{1}+\dots+y_{n-2})(y_{n-1}+y_{n})+i\frac{\pi}{8}(y_{n-1}+y_{n})^{2}}\right)$
(49)
$\displaystyle=\frac{e^{i\frac{\pi}{4}}}{\sqrt{2}}\left(1-i^{n-1}y_{1}y_{2}\cdots
y_{n-2}\right)\exp\left({i\frac{\pi}{4}(y_{1}+\dots+y_{n-2})(y_{n-1}+y_{n})+i\frac{\pi}{8}(y_{n-1}+y_{n})^{2}}\right).$
(50)

We now split the analysis into two cases: when $y_{n-1}=1$ and $y_{n}=-1$, and
when $y_{n-1}=1$ and $y_{n}=1.$ For the first case, we can simplify (50) to

$\displaystyle=\frac{e^{i\frac{\pi}{4}}}{\sqrt{2}}\left(1-i^{n-1}y_{1}\dots
y_{n-2}\right)$
$\displaystyle=\frac{e^{i\frac{\pi}{4}}}{\sqrt{2}}\left(1+i^{n-1}y_{1}\dots
y_{n}\right)=\frac{e^{i\frac{\pi}{4}}}{\sqrt{2}}\left(1-i^{n+1}y_{1}\dots
y_{n}\right),$ (51)

which satisfies the inductive hypothesis. For the second case, we have

$\displaystyle\frac{e^{i\frac{\pi}{4}}}{\sqrt{2}}(1-i^{n-1}y_{1}\dots
y_{n-2})e^{i\frac{\pi}{2}(y_{1}+\dots+y_{n-2})}e^{i\frac{\pi}{2}}$
$\displaystyle=\frac{e^{i\frac{\pi}{4}}}{\sqrt{2}}(1-i^{n-1}y_{1}\dots
y_{n-2})i^{n-2}(y_{1}\dots y_{n-2})i$ (52)
$\displaystyle=\frac{e^{i\frac{\pi}{4}}}{\sqrt{2}}(1-i^{n+1}y_{1}\dots
y_{n}),$ (53)

where in the last line we have used the fact that $n$ is even. This agrees
with the inductive hypothesis as well, including all phases, so we have shown
that equation (47) is true.

So the action of $U_{\text{magic}}$ on $\ket{w}$ is

$\displaystyle
U_{\text{magic}}\ket{w}=\frac{e^{-i\frac{\pi}{8}(n-2)}}{\sqrt{2}}\left(1-i^{n+1}Y_{1}Y_{2}\cdots
Y_{n}\right)\ket{w}.$ (54)

This operator creates a superposition of $\ket{w}$ and its complement
$\ket{-w}$ when all $J_{i,j}=1$.

Now consider what happens if we change a particular $J_{i,j}$ to $-1$. The new
unitary $U_{\text{magic}}^{\prime}$ is related to $U_{\text{magic}}$ as

$\displaystyle
U_{\text{magic}}^{\prime}=e^{-i\frac{\pi}{2}Y_{i}Y_{j}}U_{\text{magic}}=-iY_{i}Y_{j}U_{\text{magic}},$
(55)

so the net effect of flipping $J_{i,j}$ is to flip the corresponding bits in
the cat state. Flipping additional $J$’s repeats this effect, so we always end
up with a state (up to global phase) of the form

$\displaystyle\frac{1}{\sqrt{2}}\big{(}\ket{w^{\prime}}+e^{i\theta}\ket{-w^{\prime}}\big{)},$
(56)

where $w^{\prime}$ is obtained from the original string $w$ by flipping the
sequence of bits associated with the negative $J$’s as described in equation
(45).

##  Appendix D Condition for MaxCut improvement at small angles for $p=3/2$

Here we give conditions for the $p=3/2$ QAOA for $\beta_{1},\beta_{2}\ll 1$ to
improve upon its initial string. Our final result is stated in equation 18 in
the main text.

The expected cost produced by the $p=3/2$ warm started QAOA is, for the MaxCut
cost $C$,

$\displaystyle\langle w|e^{i\beta_{1}B}e^{i\gamma
C}e^{i\beta_{2}B}Ce^{-i\beta_{2}B}e^{-i\gamma C}e^{-i\beta_{1}B}|w\rangle.$
(57)

We now expand to order $\beta^{2}$. The zeroth-order term is $C(w)$ and the
higher order terms are the change from this value. Terms of order $\beta$
cancel, and the terms of order $\beta^{2}$ are

$\displaystyle-\beta_{1}\beta_{2}\langle w|Be^{i\gamma C}BCe^{-i\gamma
C}|w\rangle+\mathrm{c.c.}+\beta_{1}\beta_{2}\langle w|Be^{i\gamma
C}CBe^{-i\gamma C}|w\rangle+\mathrm{c.c.}$
$\displaystyle-\frac{\beta_{1}^{2}}{2}\langle w|B^{2}e^{i\gamma C}Ce^{-i\gamma
C}|w\rangle+\mathrm{c.c.}-\frac{\beta_{2}^{2}}{2}\langle w|e^{i\gamma
C}B^{2}Ce^{-i\gamma C}|w\rangle+\mathrm{c.c.}$
$\displaystyle+\beta_{1}^{2}\langle w|Be^{i\gamma C}Ce^{-i\gamma
C}B|w\rangle+\beta_{2}^{2}\langle w|e^{i\gamma C}BCBe^{-i\gamma C}|w\rangle$
$\displaystyle\qquad\qquad\qquad\qquad\qquad=-2\beta_{1}\beta_{2}C(w)\sum_{i}\cos[\gamma(C_{i}-C(w))]+2\beta_{1}\beta_{2}\sum_{i}C_{i}\cos[\gamma(C_{i}-C(w))]$
$\displaystyle\qquad\qquad\qquad\qquad\qquad\qquad-\beta_{1}^{2}nC(w)-\beta_{2}^{2}nC(w)+\beta_{1}^{2}\sum_{i}C_{i}+\beta_{2}^{2}\sum_{i}C_{i},$
(58)

where $C_{i}=\bra{w}X_{i}CX_{i}\ket{w}$. We define the quantity

$\displaystyle\delta_{i}=(C_{i}-C(w))/2.$ (59)

Then we can replace each factor of $n$ with a sum over $i$, and substitute the
definition of $\delta_{i}$ to obtain

$\displaystyle
2(\beta_{1}^{2}+\beta_{2}^{2})\sum_{i}\delta_{i}+4\beta_{1}\beta_{2}\sum_{i}\delta_{i}\cos
2\gamma\delta_{i}=2(\beta_{1}+\beta_{2})^{2}\sum_{i}\delta_{i}-8\beta_{1}\beta_{2}\sum_{i}\delta_{i}\sin^{2}\gamma\delta_{i}.$
(60)

Therefore we have improvement if we can find parameters for which

$\displaystyle
2(\beta_{1}+\beta_{2})^{2}\sum_{i}\delta_{i}-8\beta_{1}\beta_{2}\sum_{i}\delta_{i}\sin^{2}\gamma\delta_{i}>0.$
(61)

We restrict our attention to $3$-regular graphs, for which $|\delta_{i}|=1$ or
$3$. We want conditions on $\\{\delta_{i}\\}$ under which the inequality (61)
can be met for small $\beta_{1},\beta_{2}$, and some $\gamma$. Let us split
the analysis into two cases, depending on whether
$\sum_{i}\delta_{i}\sin^{2}(\gamma\delta_{i})$ is positive or negative.

If $\sum_{i}\delta_{i}\sin^{2}(\gamma\delta_{i})$ is positive, then we can
always meet (61), for example, by taking $\beta_{2}=-\beta_{1}$. So we seek
conditions on $\\{\delta_{i}\\}$ that guarantee that
$\sum_{i}\delta_{i}\sin^{2}(\gamma\delta_{i})$ is positive for some $\gamma$.
Now,

$\displaystyle\sum_{i}\delta_{i}\sin^{2}(\gamma\delta_{i})$
$\displaystyle=\sum_{|\delta_{i}|=1}\delta_{i}\sin^{2}\gamma+\sum_{|\delta_{i}|=3}\delta_{i}\sin^{2}(3\gamma)$
(62)
$\displaystyle=\sum_{|\delta_{i}|=1}\delta_{i}\sin^{2}\gamma+\sum_{|\delta_{i}|=3}\delta_{i}(3\sin\gamma-4\sin^{3}\gamma)^{2}$
(63)
$\displaystyle=\sin^{2}\gamma\bigg{[}\sum_{|\delta_{i}|=1}\delta_{i}+(3-4\sin^{2}\gamma)^{2}\sum_{|\delta_{i}|=3}\delta_{i}\bigg{]}.$
(64)

We have that $0\leq(3-4\sin^{2}\gamma)^{2}\leq 9$, so we see that the term in
brackets ranges from the first sum to the first sum plus $9$ times the second
sum as $\gamma$ varies. This means that (64) is positive for some $\gamma$ if
and only if

$\displaystyle\qquad\sum_{|\delta_{i}|=1}\delta_{i}>0\qquad\text{or}\qquad\sum_{|\delta_{i}|=1}\delta_{i}+9\sum_{|\delta_{i}|=3}\delta_{i}>0.$
(65)

The second condition is exactly equal to $\sum_{i}\delta_{i}^{3}>0$.

Therefore $\sum_{i}\delta_{i}\sin^{2}(\gamma\delta_{i})$ can be positive if
and only if

$\displaystyle\sum_{|\delta_{i}|=1}\delta_{i}>0\qquad\text{or}\qquad\sum_{i}\delta_{i}^{3}>0.$
(66)

Now let us examine the case where
$\sum_{i}\delta_{i}\sin^{2}(\gamma\delta_{i})$ is negative. In this case, we
can succeed in satisfying (61) as long as

$\displaystyle\sum_{i}\delta_{i}>\frac{4\beta_{1}\beta_{2}}{(\beta_{1}+\beta_{2})^{2}}\sum_{i}\delta_{i}\sin^{2}(\gamma\delta_{i})$
(67)

for some $\beta_{1},\beta_{2}$. The right-hand side is minimized at
$\beta_{1}=\beta_{2}$, so this condition can hold if and only if

$\displaystyle\sum_{i}\delta_{i}>\sum_{i}\delta_{i}\sin^{2}(\gamma\delta_{i}),$
(68)

or equivalently, if for some $\gamma$,

$\displaystyle\sum_{i}\delta_{i}\cos^{2}(\gamma\delta_{i})>0.$ (69)

Repeating now the analysis done for the
$\sum_{i}\delta_{i}\sin^{2}(\gamma\delta_{i})>0$ case, we obtain the same
conditions for success. In summary, at $p=3/2$ improvement of the cost is
possible for small $\beta$’s if and only if

$\displaystyle\sum_{|\delta_{i}|=1}\delta_{i}>0\qquad\text{or}\qquad\sum_{i}\delta_{i}^{3}>0$
(70)

which proves equation (18) in the main text.

##  Appendix E Thermality argument proofs

###  E.1 Proof that typical strings cannot be improved

In this section we will show for any $\epsilon>0$, with $w$ chosen uniformly
at random,

$\displaystyle\Pr_{w}\left(\frac{1}{m}\langle
w|U_{w}^{\dagger}CU_{w}|w\rangle-\frac{1}{m}C(w)\geq\frac{1}{m^{1/2-\varepsilon}}\right)\rightarrow
0,\qquad\text{as }m\rightarrow\infty,$ (71)

where $U_{w}$ is the optimal QAOA unitary for each $w$.

To streamline the presentation, we restrict ourselves to the $p=3/2$ QAOA on
triangle-free $d$-regular graphs, although the argument can be generalized to
any constant depth, and to general bounded-degree graphs. Let $G=(V,E)$ be a
triangle-free $d$-regular graph with $|V|=n$ vertices and $|E|=m=nd/2$ edges.
We consider cost functions of the generic form

$\displaystyle C(z)=\sum_{\langle i,j\rangle\in E}C_{\langle
i,j\rangle}(z_{i},z_{j}).$ (72)

We can use the observations of Section 2.3 to reorganize the QAOA expectation:
at $p=3/2$, the QAOA involves only a small tree around each edge consisting of
$2d$ vertices. That is, we can write the expected value of the cost operator
(normalized by the number of edges) as

$\displaystyle\frac{1}{m}\langle w|U^{\dagger}_{w}CU_{w}|w\rangle$
$\displaystyle=\frac{1}{m}\sum_{\langle i,j\rangle\in E}\langle
w|U_{w}^{\dagger}C_{\langle i,j\rangle}U_{w}|w\rangle,$ (73)

where each matrix element on the right-hand side only depends on the $2d$ bits
of $w$ which lie on the tree whose central edge is $\langle i,j\rangle$. We
call the restriction of $w$ to these bits $w_{\langle i,j\rangle}$. So we can
write

$\displaystyle\frac{1}{m}\langle w|U^{\dagger}_{w}CU_{w}|w\rangle$
$\displaystyle=\frac{1}{m}\sum_{\langle i,j\rangle\in E}\langle w_{\langle
i,j\rangle}|U_{w}^{\dagger}C_{\langle i,j\rangle}U_{w}|w_{\langle
i,j\rangle}\rangle,$ (74)

where each $w_{\langle i,j\rangle}$ is a bit string on $2d$ bits. Summing over
the possible values of such bit strings, we can rearrange the sum as

$\displaystyle\frac{1}{m}\langle w|U^{\dagger}_{w}CU_{w}|w\rangle$
$\displaystyle=\frac{1}{m}\sum_{\ell\in\\{-1,1\\}^{2d}}\\#_{w}(\ell)\langle\ell|U_{w}^{\dagger}C_{\mathrm{edge}}U_{w}|\ell\rangle,$
(75)

where $\\#_{w}(\ell)$ is the number of times the $2d$-bit string $\ell$
appears within the collection of $w_{\langle i,j\rangle}$, and where
$C_{\mathrm{edge}}$ denotes a generic edge term (for MaxCut,
$C_{\mathrm{edge}}=-Z_{a}Z_{b}$, where $\langle a,b\rangle$ labels the central
edge of a tree neighborhood). We consider
$U^{\dagger}_{w}C_{\mathrm{edge}}U_{w}$ as an operator on the $2d$-qubit
Hilbert space associated with the $2d$ vertices in the radius-1 tree
neighborhood of an edge.

Now we consider the case where the string $w\in\\{-1,1\\}^{n}$ is chosen
uniformly at random. We can think of $\\#_{w}(\ell)$ as a random variable
whose average value is $m/2^{2d}$. We conveniently partition the sum as

$\displaystyle\frac{1}{m}\langle w|U^{\dagger}_{w}CU_{w}|w\rangle$
$\displaystyle=\frac{1}{2^{2d}}\sum_{\ell\in\\{-1,1\\}^{2d}}\langle\ell|U_{w}^{\dagger}C_{\mathrm{edge}}U_{w}|\ell\rangle+\frac{1}{m}\sum_{\ell\in\\{-1,1\\}^{2d}}\left(\\#_{w}(\ell)-\frac{m}{2^{2d}}\right)\langle\ell|U_{w}^{\dagger}C_{\mathrm{edge}}U_{w}|\ell\rangle.$
(76)

The first term of the right-hand side of equation (76) turns out to be a
simple constant,

$\displaystyle\frac{1}{2^{2d}}\sum_{\ell\in\\{-1,1\\}^{2d}}\langle\ell|U_{w}^{\dagger}C_{\mathrm{edge}}U_{w}|\ell\rangle$
$\displaystyle=\frac{1}{2^{2d}}\sum_{\ell\in\\{-1,1\\}^{2d}}\mathrm{Tr}_{\textrm{tree}}\left(U_{w}^{\dagger}C_{\mathrm{edge}}U_{w}|\ell\rangle\langle\ell|\right)$
(77)
$\displaystyle=\frac{1}{2^{2d}}\mathrm{Tr}_{\textrm{tree}}\left(U_{w}^{\dagger}C_{\mathrm{edge}}U_{w}I\right)$
(78)
$\displaystyle=\frac{1}{2^{2d}}\mathrm{Tr}_{\textrm{tree}}(C_{\mathrm{edge}})$
(79) $\displaystyle=\frac{1}{2^{n}}\sum_{z\in\\{-1,1\\}^{n}}\frac{1}{m}\langle
z|C|z\rangle$ (80) $\displaystyle=\bar{c},$ (81)

where $\overline{c}$ is the average cost value per edge as defined in equation
(21), and where $\mathrm{Tr}_{\textrm{tree}}$ refers to the trace over the
Hilbert space of an abstract tree neighborhood.

The second term in (76) is then the deviation of the optimized cost function
$\frac{1}{m}\langle w|U^{\dagger}_{w}CU_{w}|w\rangle$ from the average cost
function $\bar{c}$. We want to upper bound this deviation, which we denote by
$\chi$, defined as

$\displaystyle\chi$ $\displaystyle=\frac{1}{m}\langle
w|U^{\dagger}_{w}CU_{w}|w\rangle-\bar{c}$ (82)
$\displaystyle=\frac{1}{m}\sum_{\ell\in\\{-1,1\\}^{2d}}\left(\\#_{w}(\ell)-\frac{m}{2^{2d}}\right)\langle\ell|U^{\dagger}_{w}C_{\mathrm{edge}}U_{w}|\ell\rangle.$
(83)

We can bound $\chi^{2}$ using the Cauchy-Schwarz inequality as

$\displaystyle\chi^{2}$
$\displaystyle\leq\frac{1}{m^{2}}\bigg{[}\sum_{\ell\in\\{-1,1\\}^{2d}}\left(\\#_{w}(\ell)-\frac{m}{2^{2d}}\right)^{2}\bigg{]}\bigg{[}\sum_{\ell\in\\{-1,1\\}^{2d}}\left|\langle\ell|U_{w}^{\dagger}C_{\mathrm{edge}}U_{w}|\ell\rangle\right|^{2}\bigg{]}$
(84)
$\displaystyle\leq\frac{1}{m^{2}}2^{2d}\sum_{\ell\in\\{-1,1\\}^{2d}}\left(\\#_{w}(\ell)-\frac{m}{2^{2d}}\right)^{2},$
(85)

where we use the fact that $|C_{\mathrm{edge}}|\leq 1$ in the second
inequality. For each $\ell\in\\{-1,1\\}^{2d}$, we can imagine $\\#_{w}(\ell)$
as a sum of indicator random variables $B_{\langle i,j\rangle}$. Each
$B_{\langle i,j\rangle}$ is $1$ if $w_{\langle i,j\rangle}=\ell$, where we
recall that $w_{\langle i,j\rangle}$ is the restriction of $w$ to the edge
neighborhood centered at edge $\langle i,j\rangle$, and $0$ otherwise:

$\displaystyle\\#_{w}(\ell)=\sum_{\langle i,j\rangle\in E}B_{\langle
i,j\rangle}.$ (86)

The mean of each $B_{\langle i,j\rangle}$ is $2^{-2d}$ because the string $w$
is chosen uniformly at random. Note $B_{\langle i,j\rangle}$ and $B_{\langle
i^{\prime},j^{\prime}\rangle}$ are independent when the tree neighborhoods of
the corresponding edges do not overlap. For each $B_{\langle i,j\rangle}$,
there are at most $D=2d^{3}$ distinct edge neighborhoods with which it has
non-trivial overlap. Averaging over the $w$ we get

$\displaystyle\operatorname*{\mathbb{E}}_{w}\left[\left(\\#_{w}(\ell)-\frac{m}{2^{2d}}\right)^{2}\right]$
$\displaystyle=\sum_{\langle i,j\rangle\in E}\sum_{\langle
i^{\prime},j^{\prime}\rangle\in
E}\operatorname*{\mathbb{E}}_{w}\left[\left(B_{\langle
i,j\rangle}-\frac{1}{2^{2d}}\right)\left(B_{\langle
i^{\prime},j^{\prime}\rangle}-\frac{1}{2^{2d}}\right)\right]$ (87)
$\displaystyle\leq mD\frac{1}{2^{2d}}\left(1-\frac{1}{2^{2d}}\right),$ (88)

because there are at most $mD$ pairs of overlapping neighborhoods in the
double sum (the other terms vanish), and for these nonzero terms, by Cauchy-
Schwarz, the covariance $\operatorname*{\mathbb{E}}_{w}\left[\cdots\right]$ is
upper bounded by the variance $\mu(1-\mu)$ of the indicator random variables
$B_{\langle i,j\rangle}$ with mean $\mu=2^{-2d}$.

Altogether, $\operatorname*{\mathbb{E}}_{w}[\chi^{2}]$ is bounded above as

$\displaystyle\operatorname*{\mathbb{E}}_{w}\left[\chi^{2}\right]$
$\displaystyle\leq\frac{1}{m^{2}}2^{2d}mD\frac{1}{2^{2d}}\left(1-\frac{1}{2^{2d}}\right)\leq\frac{D}{m}.$
(89)

By the Chebyshev inequality, for any $a>0$, we have

$\displaystyle\Pr_{w}\left(\left|\chi\right|\geq
a\right)\leq\frac{\operatorname*{\mathbb{E}}_{w}[\chi^{2}]}{a^{2}}\leq\frac{D}{ma^{2}}.$
(90)

Choosing $a=m^{-1/2+\varepsilon}$ for any $\varepsilon>0$, and plugging in the
definition of $\chi$ in equation (82), we get

$\displaystyle\Pr_{w}\left(\left|\frac{1}{m}\langle
w|U^{\dagger}_{w}CU_{w}|w\rangle-\bar{c}\right|\geq\frac{1}{m^{1/2-\varepsilon}}\right)\longrightarrow
0,\quad\text{as }m\rightarrow\infty..$ (91)

It follows that as the number of edges $m$ tends to infinity, the probability
of any non-negligible deviation from $\bar{c}$ tends to zero. Equation (91),
combined with the law of large numbers (equation (22), main text), finally
yields the bound

$\displaystyle\Pr_{w}\left(\frac{1}{m}\langle
w|U_{w}^{\dagger}CU_{w}|w\rangle-\frac{1}{m}C(w)\geq\frac{1}{m^{1/2-\varepsilon}}\right)\rightarrow
0,\qquad\text{as }m\rightarrow\infty.$ (92)

We conclude that for nearly all initial strings, the constant-depth QAOA can
only improve the cost function (per edge) by an amount that vanishes in the
limit of large graphs.

###  E.2 Proof that good strings cannot be improved

In this section we develop a statistical argument to upper bound the progress
made by the QAOA starting from a good string. The bound applies to the QAOA at
constant depth on large bounded-degree graphs. In the previous section, we
proved the QAOA makes little progress when starting from a string chosen
uniformly at random. Because such strings are not generally “good” strings, we
extend the argument to good strings we describe as “locally thermal.”

####  E.2.1 Intuition for the thermal argument

We begin with an intuitive explanation of our argument, then state the main
Theorem E.1 and its derivation. Our argument relies on the locality and the
uniformity of the operators appearing in the QAOA circuit. Recall that we
consider cost functions that are a sum of terms for each edge of a graph, as
in equation (2). Let $U$ be the QAOA operator from equation (5) at depth $p$.
The QAOA operator for a given edge is $U^{\dagger}C_{\langle i,j\rangle}U$,
which acts non-trivially only on the edge neighborhood of $\langle i,j\rangle$
with maximal radius $r=p-1/2$ (see Section 2.3). By uniformity, we mean that
the reduced operator on any subgraph depends only on the isomorphism type of
the underlying subgraph (i.e., the reduced operators on different subgraphs
are the same when the subgraphs are isomorphic). Note that the operators of
the standard QAOA satisfy this uniformity property as long as the $C_{\langle
i,j\rangle}$ do not depend on the edge $\langle i,j\rangle$. Our statistical
argument also relies on bounded degree, so it does not apply directly to
problems like the Sherrington-Kirpatrick model in Appendix C.

For MaxCut on $d$-regular graphs as $n\to\infty$ and at constant depth, all
but a vanishing fraction of edge neighborhoods are trees. Following the main
text, we define the fraction $\delta$ of edges whose neighborhoods are not
trees as

$\displaystyle\delta=1-\frac{|E_{T}|}{m},$ (93)

where $E_{T}$ denotes the set of edges whose neighborhood of radius $r$ is a
tree.

Recall the ensemble $\rho_{w,\mathrm{tree}}$ associated with the warm-start
string $w$. For any classical string $w\in\\{-1,1\\}^{n}$ and a mostly locally
tree-like $G$ we define its _local ensemble_ by

$\displaystyle\rho_{w,\mathrm{tree}}=\frac{1}{|E_{T}|}\sum_{\langle
i,j\rangle\in E_{T}}|w_{\langle i,j\rangle}\rangle\langle w_{\langle
i,j\rangle}|,$ (94)

where $w_{\langle i,j\rangle}$ denotes the restriction of $w$ onto the local
tree neighborhood $T_{\langle i,j\rangle}$, and $T_{\langle i,j\rangle}$
denotes the tree neighborhood centered around edge $\langle i,j\rangle\in
E_{T}$. Each tree neighborhood has a fixed number of vertices, so $w_{\langle
i,j\rangle}$ is a string of that length, and $\rho_{w,\mathrm{tree}}$ is a
density matrix over the corresponding number of qubits.

We now use the global thermal density matrix $\rho_{\beta}$ with respect to
$H=-C$, (see equation 26 in the main text) to define the reduced density
matrix onto the tree neighborhood $T_{\langle i,j\rangle}$, denoted
$\mathrm{Tr}_{G\backslash T_{\langle i,j\rangle}}\left(\rho_{\beta}\right)$,
and the ensemble

$\displaystyle\rho_{\beta,\mathrm{tree}}=\frac{1}{|E_{T}|}\sum_{\langle
i,j\rangle\in E_{T}}\mathrm{Tr}_{G\backslash T_{\langle
i,j\rangle}}\left(\rho_{\beta}\right).$ (95)

Again, both $\rho_{w,\mathrm{tree}}$ and $\rho_{\beta,\mathrm{tree}}$ act on
the Hilbert space of a single tree neighborhood.

Consider two strings $w$ and $w^{\prime}$ drawn from the thermal ensemble
$\rho_{\beta}$. While the strings may look totally different on any particular
neighborhood, you might expect that $\rho_{w,\mathrm{tree}}$ and
$\rho_{w^{\prime},\textrm{tree}}$ are nonetheless similar: both strings look
the same locally when averaged over neighborhoods. In that case, typical
strings from the thermal ensemble should all have the same expected cost
function under $U$, since the expected cost is completely determined by
$\rho_{w,\mathrm{tree}}$ up to small corrections in $\delta$. In particular,
the cost function should behave as if the thermal state $\rho_{\beta}$ were
itself the input to the QAOA. But a key property of the thermal state is that
it has the minimum expected energy of all states with the same entropy. That
is, fixing some $\beta>0$, we have

$\displaystyle\rho_{\beta}=\operatorname*{arg\,min}_{\rho\,:\,S(\rho)=S(\rho_{\beta})}\mathrm{Tr}(H\rho).$
(96)

In particular, since unitaries preserve entropy, we have

$\displaystyle\min_{U}\mathrm{Tr}(HU\rho_{\beta}U^{\dagger})=\mathrm{Tr}(H\rho_{\beta}).$
(97)

This means that no unitary applied to $\rho_{\beta}$ can lower the energy.

Suppose $\rho_{w,\mathrm{tree}}$ is well-approximated by the density matrix
$\rho_{\beta,\mathrm{tree}}$. Then $w$ gives the same expectation for the
cost-function as the associated $\rho_{\beta}$ under any QAOA unitary, so no
such unitary applied to $w$ can reduce the energy. We call such strings $w$
“locally thermal,” and we quantify this property with the “thermality
coefficient” $\varepsilon_{w}$,

$\displaystyle\varepsilon_{w}=\|\rho_{\beta,\mathrm{tree}}-\rho_{w,\mathrm{tree}}\|_{1},$
(98)

where $\beta$ is the inverse temperature chosen so that

$\displaystyle\mathrm{Tr}(C\rho_{\beta})=C(w).$ (99)

Note that $\varepsilon_{w}$ depends on the QAOA depth $p$ which defines the
neighborhood radius. Our main result, stated next (Theorem 6.2 in the main
text), shows that if $w$ is locally thermal, i.e., if $\varepsilon_{w}$ is
small, then $w$ can only improve by a small amount. Locally thermal strings
may be viewed as exhibiting a form of ergodicity: the average over local
neighborhoods for the fixed string looks like the thermal average over
different global strings.

####  E.2.2 Proof of the thermal argument

We now prove our main result, which bounds the improvement of the single-
string warm-start QAOA for locally thermal strings.

######  Theorem E.1.

Consider the single-string warm-start QAOA initialized in a string $w$ with
thermality coefficient $\varepsilon_{w}$, and let $\delta$ be the fraction of
neighborhoods whose edges are not trees. Then

$\displaystyle\frac{1}{m}\langle w|U^{\dagger}_{w}CU_{w}|w\rangle\leq
c(w)+2\varepsilon_{w}+4\delta,$ (100)

where $c(w)=C(w)/m$ is the cut fraction of the original string $w$.

Recalling equation (73) and the observations of Section 2.3, we have

$\displaystyle\frac{1}{m}\langle w|U^{\dagger}_{w}CU_{w}|w\rangle$
$\displaystyle=\frac{1}{m}\sum_{\langle i,j\rangle\in E}\langle
w|U_{w}^{\dagger}C_{\langle i,j\rangle}U_{w}|w\rangle$ (101)
$\displaystyle\leq\frac{1}{m}\sum_{\langle i,j\rangle\in E_{T}}\langle
w|U_{w}^{\dagger}C_{\langle i,j\rangle}U_{w}|w\rangle+\delta$ (102)
$\displaystyle=\frac{1}{m}\sum_{\langle i,j\rangle\in E_{T}}\langle w_{\langle
i,j\rangle}|U_{w}^{\dagger}C_{\langle i,j\rangle}U_{w}|w_{\langle
i,j\rangle}\rangle+\delta$ (103)
$\displaystyle=\frac{1}{m}\mathrm{Tr}_{\textrm{tree}}\big{(}U_{w}^{\dagger}C_{\mathrm{edge}}U_{w}\sum_{\langle
i,j\rangle\in E_{T}}|w_{\langle i,j\rangle}\rangle\langle w_{\langle
i,j\rangle}|\big{)}+\delta$ (104)
$\displaystyle=\frac{|E_{T}|}{m}\mathrm{Tr}_{\textrm{tree}}\big{(}U_{w}^{\dagger}C_{\mathrm{edge}}U_{w}\rho_{w,\mathrm{tree}}\big{)}+\delta.$
(105)

The second line drops the contribution from edges whose neighborhoods are not
trees. The $\mathrm{Tr}_{\textrm{tree}}$ refers to the trace over the Hilbert
space associated to an abstract tree neighborhood. The final line uses the
definition of $\rho_{w,\mathrm{tree}}$ in (94).

Next, we replace $\rho_{w,\mathrm{tree}}$ with $\rho_{\beta,\mathrm{tree}}$,
picking up an error proportional to $\varepsilon_{w}$, which measures the
local thermality of $w$. We use the property of the trace norm that

$\displaystyle\mathrm{Tr}(A^{\dagger}B)\leq\|A\|_{\infty}\cdot\|B\|_{1},$
(106)

where $\left\lVert A\right\rVert_{\infty}$ is the operator norm (the largest
singular value). Recall that we assume $C$ is normalized so that $|C_{\langle
i,j\rangle}|\leq 1$, or equivalently, $||C_{\textrm{edge}}||_{\infty}\leq 1$.
Then we find

$\displaystyle\frac{1}{m}\langle
w|U^{\dagger}_{w}CU_{w}|w\rangle\leq\frac{|E_{T}|}{m}\mathrm{Tr}_{\textrm{tree}}\left(U_{w}^{\dagger}C_{\mathrm{edge}}U_{w}\rho_{\beta,\mathrm{tree}}\right)+\varepsilon_{w}+\delta.$
(107)

Now we substitute (95), replace the partial trace $\mathrm{Tr}_{G\backslash
T_{\langle i,j\rangle}}(\rho_{\beta})$ with the full thermal operator
$\rho_{\beta}$, and re-sum the cost Hamiltonian $C$:

$\displaystyle\frac{1}{m}\langle w|U^{\dagger}_{w}CU_{w}|w\rangle$
$\displaystyle\leq\frac{1}{m}\sum_{\langle i,j\rangle\in
E_{T}}\mathrm{Tr}_{\textrm{tree}}\left(U_{w}^{\dagger}C_{\langle
i,j\rangle}U_{w}\mathrm{Tr}_{G\backslash T_{\langle
i,j\rangle}}(\rho_{\beta})\right)+\varepsilon_{w}+\delta$ (108)
$\displaystyle\leq\frac{1}{m}\sum_{\langle i,j\rangle\in
E}\mathrm{Tr}\left(U_{w}^{\dagger}C_{\langle
i,j\rangle}U_{w}\rho_{\beta}\right)+\varepsilon_{w}+2\delta$ (109)
$\displaystyle=\frac{1}{m}\mathrm{Tr}\left(U_{w}^{\dagger}CU_{w}\rho_{\beta}\right)+\varepsilon_{w}+2\delta.$
(110)

Finally, we apply the principle of minimum energy in thermodynamics (equation
(97)) to the Hamiltonian $H=-C$ with the thermal state $\rho_{\beta}$ of (26),
we get

$\displaystyle\frac{1}{m}\langle w|U^{\dagger}_{w}CU_{w}|w\rangle$
$\displaystyle\leq\frac{1}{m}\mathrm{Tr}\left(U_{w}^{\dagger}CU_{w}\rho_{\beta}\right)+\varepsilon_{w}+2\delta$
(111)
$\displaystyle\leq\frac{1}{m}\mathrm{Tr}(C\rho_{\beta})+\varepsilon_{w}+2\delta$
(112)
$\displaystyle\leq\frac{|E_{T}|}{m}\mathrm{Tr}_{\textrm{tree}}(C_{\textrm{edge}}\rho_{\beta,\mathrm{tree}})+\varepsilon_{w}+3\delta$
(113)
$\displaystyle\leq\frac{|E_{T}|}{m}\mathrm{Tr}_{\textrm{tree}}(C_{\textrm{edge}}\rho_{w,\mathrm{tree}})+2\varepsilon_{w}+3\delta$
(114) $\displaystyle\leq\frac{1}{m}\langle
w|C|w\rangle+2\varepsilon_{w}+4\delta$ (115)

or equivalently,

$\displaystyle\frac{1}{m}\langle w|U^{\dagger}_{w}CU_{w}|w\rangle\leq
c(w)+2\varepsilon_{w}+4\delta$ (116)

where $c(w)$ is the cut fraction of the original string $w$, reproducing the
desired result of Theorem (E.1). Since $\delta=O(1/n)$ is vanishingly small
for large graphs, we conclude that the improvement is controlled by
$\varepsilon_{w}$, which measures how close $w$ is to being locally thermal.

###  E.3 When are initial strings locally thermal?

Here we ask about the values of $\varepsilon_{w}$ for typical good strings $w$
drawn from the thermal ensemble: how close is $\rho_{w,\mathrm{tree}}$ to
$\rho_{\beta,\mathrm{tree}}$? While $\rho_{w,\mathrm{tree}}$ is not
immediately guaranteed to be close to $\rho_{\beta,\mathrm{tree}}$ for all
$w$, the relation holds on average over thermally sampled strings $w$, i.e.,

$\displaystyle\operatorname*{\mathbb{E}}_{w\sim\rho_{\beta}}[\rho_{w,\mathrm{tree}}]=\rho_{\beta,\mathrm{tree}},$
(117)

where $\operatorname*{\mathbb{E}}_{w\sim\rho_{\beta}}$ denotes expectation
with respect to samples of $w$ from the thermal distribution. This follows by
commuting the thermal average with the average over neighborhoods:

$\displaystyle\mathop{\mathbb{E}}_{w\sim\rho_{\beta}}[\rho_{w,\mathrm{tree}}]$
$\displaystyle=\frac{1}{Z}\sum_{w}e^{-\beta(-C(w))}\rho_{w,\mathrm{tree}}$
(118)
$\displaystyle=\frac{1}{Z}\sum_{w}e^{-\beta(-C(w))}\frac{1}{|E_{T}|}\sum_{\langle
i,j\rangle\in E_{T}}|w_{\langle i,j\rangle}\rangle\langle w_{\langle
i,j\rangle}|$ (119) $\displaystyle=\frac{1}{|E_{T}|}\sum_{\langle
i,j\rangle\in E_{T}}\frac{1}{Z}\sum_{w}e^{-\beta(-C(w))}|w_{\langle
i,j\rangle}\rangle\langle w_{\langle i,j\rangle}|$ (120)
$\displaystyle=\frac{1}{|E_{T}|}\sum_{\langle i,j\rangle\in
E_{T}}\mathrm{Tr}_{G\backslash T_{\langle
i,j\rangle}}\left(\rho_{\beta}\right)$ (121)
$\displaystyle=\rho_{\beta,\mathrm{tree}},$ (122)

where $Z=\mathrm{Tr}\big{(}e^{-\beta(-C)}\big{)}$. In going to the second and
fourth lines above, we use the definitions of $\rho_{w,\mathrm{tree}}$ and
$\rho_{\beta,\mathrm{tree}}$ in (94) and (95), respectively.

Since the average of $\rho_{w,\mathrm{tree}}$ over $w$ matches
$\rho_{\beta,\mathrm{tree}}$, to show that $\rho_{w,\mathrm{tree}}$ is close
to $\rho_{\beta,\mathrm{tree}}$ for typical $w$, it suffices to show that
$\rho_{w,\mathrm{tree}}$ has small variance with respect to choice of $w$.
Treating $w$ as a random variable distributed according to the thermal
ensemble, $\rho_{w,\mathrm{tree}}$ defined in (94) becomes an average over
random variables $|w_{\langle i,j\rangle}\rangle\langle w_{\langle
i,j\rangle}|$ defined on each neighborhood. If these variables have small
correlation across different neighborhoods, then $\rho_{w,\mathrm{tree}}$ has
small variance. So $\varepsilon_{w}$ is small for typical strings sampled from
the thermal distribution, assuming the thermal distribution has only small
spatial correlations across the graph. At fixed temperature, we therefore
expect the variance of $\rho_{w,\mathrm{tree}}$ shrinks with graph size as
$m^{-1}$, and $\varepsilon_{w}\propto m^{-1/2}$.

When is it reasonable to assume that $\rho_{\beta}$ has small spatial
correlations across the graph? At infinite temperature, the case discussed in
Section 6.1, the correlation is zero, so there $\varepsilon_{w}\propto
m^{-1/2}$, consistent with our conclusion there. In the high temperature
regime (where the strings are “good,” i.e. better than random guesses, but not
too good), we similarly expect $\rho_{\beta}$ to have small correlations. At
low temperatures, depending on the specific combinatorial problem, there may
be thermal phase transitions and development of long-range correlations.
However, since we are interested in warm starts which can be efficiently
generated by classical algorithms, this low temperature regime may be less
relevant in practice.

###  E.4 Numerical evidence for the thermality of typical good strings

In Section E.2, we proved that when using a warm start with a classical string
$w$, the cost function cannot improve much when $w$ is “locally thermal.” More
precisely, we showed the improvement of the cost function per edge is
controlled by thermality coefficient

$\displaystyle\varepsilon_{w}=\|\rho_{\beta,\mathrm{tree}}-\rho_{w,\mathrm{tree}}\|_{1}.$
(123)

When $w$ is locally thermal, meaning $\varepsilon_{w}$ is small, the average
of $w$ over local neighborhoods looks like the thermal average over different
global strings. In this section, we present numerical evidence that, for a
given cost function, typical good strings $w$ are indeed approximately locally
thermal. Moreover, it appears that the magnitude of the thermality coefficient
diminishes with larger graph sizes. In our investigations below, we only
perform numerical experiments for MaxCut, and we only analyze typical good
strings associated with one fixed temperature. We leave the analysis of other
problems besides MaxCut to future investigations.

We study MaxCut on random 3-regular graphs of $n=10000$ to $50000$ vertices.
The local thermality of typical strings is expected to hold with high accuracy
only in the limit of large graphs because it involves the concentration of
averages over neighborhoods. Fixing a temperature $T=1.75$, corresponding to a
cut fraction of $\sim 0.64$, we use simulated annealing to sample classical
strings $w$ from the thermal distribution $\rho_{\beta}$ of (26). That is, we
sample strings $w$ with probabilities proportional to $e^{-\beta(-C(w))}$.

We consider $k=10$ samples, $\\{w_{\alpha}\\}$ for $\alpha=1,\ldots,k$. For
each string $w_{\alpha}$, it is straightforward to compute the associated
density matrix $\rho_{w_{\alpha},\textrm{tree}}$ of
$\eqref{eq:local_ensemble}$. We consider tree neighborhoods of radius $r=2$,
i.e., all vertices within distance $2$ of a given edge $\langle i,j\rangle$.
For $d=3$, these have 14 vertices, so $\rho_{w_{\alpha},\textrm{tree}}$ lives
on a Hilbert space of 14 qubits.

To verify that the sampled $w_{\alpha}$ are locally thermal, ideally we would
calculate
$\left\lVert\rho_{w_{\alpha},\textrm{tree}}-\rho_{\beta,\mathrm{tree}}\right\rVert_{1}=\varepsilon_{w}$.
Unfortunately, for these large graphs with $\geq 10000$ vertices, direct
computation of $\rho_{\beta}$ and $\rho_{\beta,\mathrm{tree}}$ is impossible
in practice. To proceed, we restate (117), which says that

$\displaystyle\operatorname*{\mathbb{E}}_{w\sim\rho_{\beta}}[\rho_{w,\mathrm{tree}}]=\rho_{\beta,\mathrm{tree}},$
(124)

where the expectation is with respect to samples of $w$ from the thermal
distribution. That is, the average of $\rho_{w,\mathrm{tree}}$ over thermal
samples matches $\rho_{\beta,\mathrm{tree}}$. In fact we find that for our
numerically generated samples $w_{\alpha}$, all of the associated
$\rho_{w_{\alpha},\textrm{tree}}$ are approximately equal. Thus even with our
few $k=10$ samples, the LHS of (124) is already well-approximated by this
empirical sample average, and we consider the average deviation

$\displaystyle\mathcal{E}=\frac{1}{k}\sum_{\alpha=1}^{k}\left\lVert\rho_{w_{\alpha},\textrm{tree}}-\overline{\rho_{w,\textrm{tree}}}\right\rVert_{1},$
(125)

where

$\displaystyle\overline{\rho_{w,\textrm{tree}}}=\frac{1}{k}\sum_{\alpha=1}^{k}\rho_{w_{\alpha},\textrm{tree}}.$
(126)

The value of $\mathcal{E}$ measures the average deviation of
$\rho_{w_{\alpha},\textrm{tree}}$ over samples. When $\mathcal{E}$ is small,
it follows that typical samples $w$ are approximately locally thermal. We plot
the average deviation $\mathcal{E}$ as a function of the number of vertices
$n$ in Figure 1, with $10$ samples for each $n$. The fit line shows a fit with
$\mathcal{E}\propto n^{-1/2}$. The figure suggests that typical strings $w$ at
this temperature $T=1.75$ are approximately locally thermal with
$\varepsilon_{w}$ shrinking as $n^{-1/2}$. This behavior matches the estimate
in Section E.3.

Figure 1: Log-log plot of the average sample deviation $\mathcal{E}$ from
(125) as a function of the number of vertices $n$. The fit line shows a one-
parameter fit with $\mathcal{E}=cn^{-1/2}$ for the parameter $c$.

##  Appendix F Compression argument proofs

We aim to prove Theorem 7.2. We begin with some preliminaries.

###  F.1 Preliminary lemmas

First we review some general ideas about $\epsilon$-nets and
$\epsilon$-packings on metric spaces.

Given a set $S$ on a metric space, a subset $S_{c}\subset S$ is called an
$\epsilon$-covering when every point in $S$ is within distance $\epsilon$ of
some point in $S_{c}$. That is, the $\epsilon$-balls around each point in
$S_{c}$ together cover $S$.

A subset $S_{p}\subset S$ is called an $\epsilon$-packing when all points in
$S_{p}$ are distance at least $\epsilon$ apart. That is, the
$\epsilon/2$-balls around each point in $S_{p}$ are disjoint.

A subset which is both an $\epsilon$-net and an $\epsilon$-packing is called
an $\epsilon$-net. We first collect a few useful facts about
$\varepsilon$-nets.

######  Lemma F.1.

Every finite set has at least one $\epsilon$-net, for any $\epsilon>0$.

###### Proof.

To construct the $\epsilon$-net, choose any point in the set and put it in the
net. Throw away all points within an $\epsilon$-ball of the chosen point. If
there are no remaining points then we are done. Otherwise, pick a remaining
point, put it into the net, and throw away all the points within an
$\epsilon$-ball of the point. Continue this process until the set is
exhausted. Since the set is finite, this process must terminate. ∎

######  Lemma F.2.

A $2\epsilon$-packing cannot have larger cardinality than an
$\epsilon$-covering.

###### Proof.

We show, if $S$ has an $\epsilon$-covering $S_{c}\subset S$ and a
$2\epsilon$-packing $S_{p}\subset S$, then $|S_{p}|\leq|S_{c}|$. To see this,
note that all the points in $S_{p}$ must be within distance $\epsilon$ from
some point in $S_{c}$. And by triangle inequality, no two distinct points in
$S_{p}$ can be within distance $\epsilon$ of the same point in $S_{c}$
(otherwise they would be within $2\epsilon$ of each other). So there’s a
surjection from $S_{p}$ to $S_{c}$, i.e. every point in the packing must be
covered by a different point in $S_{c}$. ∎

We can show that there is an $\epsilon$-covering of the space of depth-$p$
QAOA unitaries with the following parameters.

######  Lemma F.3.

For any $\delta\in(0,1)$, the set of QAOA unitaries produced by using $2p$
parameters has an $\epsilon$-covering of size
$\left(\frac{2\pi}{\delta}\right)^{2p}$ for $\epsilon=p\delta n^{2}$, using
the operator norm distance.

###### Proof.

Consider the set $S$ of QAOA unitaries produced by using $2p$ parameters, each
in $[0,2\pi]$. Let $S_{0}\subset S$ be the set of QAOA unitaries obtained by
using discretized parameters $\\{0,\delta,2\delta,\ldots,2\pi\\}$. Then

$\displaystyle|S_{0}|=\left(\frac{2\pi}{\delta}\right)^{2p}.$ (127)

We want to show that any QAOA unitary is close (in operator norm) to one of
these unitaries with discretized parameters. That is, every point in $S$ is
close to some point in $S_{0}$.

Consider the rotation $e^{i\gamma C}$ that occurs in a single layer of the
QAOA circuit, for two different angles $\gamma_{1},\gamma_{2}$, for cost
operator $C$. Then in operator norm

$\displaystyle\left\lVert
e^{i\gamma_{1}C}-e^{i\gamma_{2}C}\right\rVert\leq|\gamma_{1}-\gamma_{2}|\left\lVert
C\right\rVert,$ (128)

where $\left\lVert C\right\rVert$ is then the maximum cost of any string. This
inequality can be shown by working in the computational basis. Likewise,

$\displaystyle\left\lVert
e^{i\beta_{1}B}-e^{i\beta_{2}B}\right\rVert\leq|\beta_{1}-\beta_{2}|\left\lVert
B\right\rVert\leq|\beta_{1}-\beta_{2}|n,$ (129)

where $n$ is the number of qubits.

Assuming the clauses in the cost-function are normalized and there are no more
than $n^{2}$, we conclude

$\displaystyle\left\lVert e^{i\gamma_{1}C}-e^{i\gamma_{2}C}\right\rVert$
$\displaystyle\leq|\gamma_{1}-\gamma_{2}|n^{2},$ (130)
$\displaystyle\left\lVert e^{i\beta_{1}B}-e^{i\beta_{2}B}\right\rVert$
$\displaystyle\leq|\beta_{1}-\beta_{2}|n.$ (131)

Now note that for a general product of unitaries, $U_{1},\cdots,U_{m}$ and
$V_{1},\cdots,V_{m}$, we have the identity

$\displaystyle\left\lVert U_{1}\ldots U_{m}-V_{1}\ldots
V_{m}\right\rVert\leq\sum_{i=1}^{m}\left\lVert U_{i}-V_{i}\right\rVert.$ (132)

If desired one can prove this after observing the $m=2$ case:

$\displaystyle\left\lVert U_{1}U_{2}-V_{1}V_{2}\right\rVert$
$\displaystyle=\left\lVert
U_{1}(U_{2}-V_{2})+U_{1}V_{2}-V_{1}V_{2}\right\rVert$ (133)
$\displaystyle\leq\left\lVert U_{1}(U_{2}-V_{2})\right\rVert+\left\lVert
U_{1}V_{2}-V_{1}V_{2}\right\rVert$ (134)
$\displaystyle=\left\lVert(U_{2}-V_{2})\right\rVert+\left\lVert(U_{1}-V_{1})V_{2}+V_{1}V_{2}-V_{1}V_{2}\right\rVert$
(135)
$\displaystyle=\left\lVert(U_{2}-V_{2})\right\rVert+\left\lVert(U_{1}-V_{1})\right\rVert.$
(136)

Now consider two QAOA unitaries $U,V$ for which each of their $2p$ parameters
differ by at most $\delta/2$. Then combining the general identity (132) with
(130) we obtain

$\displaystyle\left\lVert U-V\right\rVert\leq p\delta n^{2}.$ (137)

So for any QAOA unitary $U\in S$, there is a QAOA unitary $V\in S_{0}$ with
discretized parameters such that the parameters each differ by less than
$\delta/2$, and then the above holds. That is, $S_{0}$ forms an
$\epsilon$-covering of $S$ for $\epsilon=p\delta n^{2}$. ∎

We will need one more preliminary lemma.

######  Lemma F.4.

Take any $\epsilon>2\gamma>0.$ Let $\\{U_{i}\\}_{i}$ be a list of unitaries
$U_{i}$ satisfying $\left\lVert U_{i}-U_{j}\right\rVert\leq\gamma$. Let
$\\{|w_{m}\rangle\\}_{m=1}^{M}$ be a list of $M$ orthogonal states. Let $B$ be
an orthogonal projection. Consider projectors $B_{i}=U_{i}^{\dagger}BU_{i}$.
Assume that for all $\\{|w_{m}\rangle\\}_{m=1}^{M}$ we have

$\displaystyle\langle w_{m}|B_{j}|w_{m}\rangle>\epsilon$ (138)

for at least one $B_{j}$. Then

$\displaystyle M<\frac{\mathrm{Tr}(B)}{\epsilon-2\gamma}.$ (139)

###### Proof.

Note that $\left\lVert B_{i}-B_{j}\right\rVert\leq 2\gamma$. Fix some index
$j$. By assumption, for each $|w_{m}\rangle$ we have

$\displaystyle\epsilon<\langle w_{m}|B_{i}|w_{m}\rangle$ (140)

for some index $i$. Then

$\displaystyle\epsilon<\langle w_{m}|B_{i}|w_{m}\rangle=\langle
w_{m}|B_{j}+(B_{i}-B_{j})|w_{m}\rangle\leq\langle
w_{m}|B_{j}|w_{m}\rangle+2\gamma,$ (141)

and so

$\displaystyle\langle w_{m}|B_{j}|w_{m}\rangle>\epsilon-2\gamma$ (142)

holds for all $\\{|w_{m}\rangle\\}$. Finally, summing over these states, we
get

$\displaystyle(\epsilon-2\gamma)M<\sum_{m=1}^{M}\langle
w_{m}|B_{j}|w_{m}\rangle\leq\mathrm{Tr}(B_{j})=\mathrm{Tr}(B)$ (143)

and the conclusion follows. ∎

###  F.2 Proof of Theorem 7.2

To prove Theorem 7.2, we will focus on the following more basic framing.
Afterward, we will observe how it implies 7.2.

######  Theorem F.5.

Consider the depth-$p$ QAOA, and let $M$ be the total number of strings (of
any cost) that are improvable to cost $C_{1}$ with selection probability at
least $\Delta$. Let $d_{1}$ be the total number of strings with cost at least
$C_{1}$. Then

$\displaystyle M\leq\frac{2d_{1}}{\Delta}\left(\frac{16\pi
pn^{2}}{\Delta}\right)^{2p}.$ (144)

###### Proof.

Let $B$ be the orthogonal projection onto the “best” strings, specified by all
those with cost at least $C_{1}$. Let $d_{1}=\mathrm{Tr}(B)$ be the number of
such strings. Let $W$ be the set of strings $w$ with the property that there
exists some QAOA unitary $U_{w}$ (depending on $w$) of depth $p$ such that

$\displaystyle\langle w|U_{w}^{\dagger}BU_{w}|w\rangle>\Delta.$ (145)

Then Theorem F.5 is precisely the statement that

$\displaystyle|W|\leq 2\frac{d_{1}}{\Delta}|S_{0}|\leq
2\frac{d_{1}}{\Delta}\left(\frac{16\pi pn^{2}}{\Delta}\right)^{2p}.$ (146)

We now argue this inequality. For each $w\in W$, we can assign some $U_{w}$
such that (145) holds. Denote the assignment

$\displaystyle f:$ $\displaystyle W\to X,$ (147) $\displaystyle w\mapsto
U_{w}.$ (148)

where $X=\\{U_{w}:w\in W\\}=f(W)$. Note that $f$ may be a many-to-one
function.

Let $\gamma=\Delta/4.$ Choose a subset $X_{1}\subset X$ that is a
$\gamma$-net, i.e. a $\gamma$-packing and $\gamma$-cover. (See Section F.1.)
That is, the points in $X_{1}$ are at least $\gamma$ apart, and every point in
$X$ is within $\gamma$ of $X_{1}$. For any $U\in X_{1}$, consider the
$\gamma$-ball $\text{Ball}_{\gamma}(U)\subset X_{1}$. Consider the strings
$f^{-1}(\text{Ball}_{\gamma}(U))\subset W$. Applying Lemma F.4 to the
unitaries $\text{Ball}_{\gamma}(U)$ and the strings
$f^{-1}(\text{Ball}_{\gamma}(U))$, we conclude

$\displaystyle|f^{-1}(\text{Ball}_{\gamma}(U))|\leq\frac{\mathrm{Tr}(B)}{\Delta-2\gamma}=2\frac{d_{1}}{\Delta}.$
(149)

We apply the above for every $U\in X_{1}$. Because $X=\cup_{U\in
X_{1}}\text{Ball}_{\gamma}(U)$, we have

$\displaystyle|W|=\left|f^{-1}(X)\right|\leq\left|\bigcup_{U\in
X_{1}}f^{-1}(\text{Ball}_{\gamma}(U))\right|\leq
2\frac{d_{1}}{\Delta}|X_{1}|.$ (150)

From Lemma F.3 we see that the space $S$ of QAOA unitaries with $2p$
parameters has an $\epsilon$-covering $S_{0}\subset S$ for $\epsilon=p\delta
n^{2}$, with

$\displaystyle|S_{0}|=\left(\frac{2\pi}{\delta}\right).$ (151)

We choose $\delta=\frac{\Delta}{8pn^{2}}$ so that $S_{0}$ is an
$\epsilon$-covering of $S$ for $\epsilon=\frac{\Delta}{8}$. Then $X_{1}$,
which is a $(\frac{\Delta}{4})$-packing, can be no larger than the cover
$S_{0}$. So

$\displaystyle|W|\leq 2\frac{d_{1}}{\Delta}|S_{0}|\leq
2\frac{d_{1}}{\Delta}\left(\frac{16\pi pn^{2}}{\Delta}\right)^{2p},$ (152)

as desired. ∎

For convenience we will restate111In contrast to the version stated in the
main text, we consider an initial string chosen randomly from within some
finite window of costs, rather than at a single fixed cost. Using a window
accommodates cost functions where all strings may have distinct costs. Theorem
7.2 and then see how it follows from the above result, Theorem F.5.

######  Theorem F.6.

Consider warm-start QAOA at depth $p$, starting with a string of cost within
$[C_{0},C_{0}^{\prime}]$ chosen uniformly at random. Let $d_{0}$ be the number
of strings with cost within $[C_{0},C_{0}^{\prime}]$, and let $d_{1}$ be the
number of strings with cost at least $C_{1}$. Then with probability at least
$1-\epsilon$, the initial string will not be improvable to cost $C_{1}$ using
selection probability at least $\epsilon$, where

$\displaystyle\epsilon=\left(\frac{2d_{1}}{d_{0}}\right)^{\frac{1}{2p+2}}(16\pi
pn^{2})^{\frac{p}{p+1}}.$ (153)

###### Proof.

For convenience let

$\displaystyle A=\frac{2d_{1}}{d_{0}}(16\pi pn^{2})^{2p}.$ (154)

Then by the previous theorem,

$\displaystyle M\leq d_{0}A\Delta^{-(2p+1)}.$ (155)

where $M$ is the number of strings improvable to cost $C_{1}$, with selection
probability at least $\Delta$, and within depth at most $p$. Take

$\displaystyle\Delta=A^{\frac{1}{2p+2}}.$ (156)

Then

$\displaystyle\frac{M}{d_{0}}\leq
A\Delta^{-\frac{2p+1}{2p+2}}=A^{\frac{1}{2p+2}}=\Delta.$ (157)

Note the left-hand side is precisely the fraction of strings within cost
$[C_{0},C^{\prime}_{0}]$ that are improvable in the desired sense. Therefore
we can define $\epsilon=\Delta$ and the corollary holds. ∎