# De-Signing Hamiltonians for Quantum Adiabatic Optimization

Elizabeth Crosson  Center for Quantum Information and Control (CQuIC),
Department of Physics and Astronomy , University of New Mexico, Albuquerque,
NM 87131, USA  Tameem Albash  Center for Quantum Information and Control
(CQuIC), Department of Physics and Astronomy , University of New Mexico,
Albuquerque, NM 87131, USA  Electrical and Computer Engineering, University of
New Mexico, Albuquerque, NM 87131, USA  Itay Hen  Information Sciences
Institute, University of Southern California, Marina del Rey, California
90292, USA  Department of Physics and Astronomy and Center for Quantum
Information Science & Technology, University of Southern California, Los
Angeles, California 90089, USA  A. P. Young  Department of Physics, University
of California, Santa Cruz, California 95064, USA

###### Abstract

Quantum fluctuations driven by non-stoquastic Hamiltonians have been
conjectured to be an important and perhaps essential missing ingredient for
achieving a quantum advantage with adiabatic optimization. We introduce a
transformation that maps every non-stoquastic adiabatic path ending in a
classical Hamiltonian to a corresponding stoquastic adiabatic path by
appropriately adjusting the phase of each matrix entry in the computational
basis. We compare the spectral gaps of these adiabatic paths and find both
theoretically and numerically that the paths based on non-stoquastic
Hamiltonians have generically smaller spectral gaps between the ground and
first excited states, suggesting they are less useful than stoquastic
Hamiltonians for quantum adiabatic optimization. These results apply to any
adiabatic algorithm which interpolates to a final Hamiltonian that is diagonal
in the computational basis.

##  1 Introduction

Quantum adiabatic optimization (QAO) [Finnila et al.(1994)Finnila, Gomez,
Sebenik, Stenson, and Doll, Brooke et al.(1999)Brooke, Bitko, F., Rosenbaum,
and Aeppli, Kadowaki and Nishimori(1998), Farhi et al.(2000)Farhi, Goldstone,
Gutmann, and Sipser, Santoro et al.(2002)Santoro, Martoňák, Tosatti, and Car]
is a quantum algorithm that uses adiabatic evolution in Hamiltonian ground
states to solve classical combinatorial optimization problems. The
computational cost of the algorithm is given by the scaling with system size
of the adiabatic condition [Wannier(1965), Farhi et al.(2002)Farhi, Goldstone,
and Gutmann, Elgart and Hagedorn(2012), Jansen et al.(2007)Jansen, Ruskai, and
Seiler, Lidar et al.(2009)Lidar, Rezakhani, and Hamma], which in turn depends
on the minimum spectral gap encountered along the adiabatic path. While QAO is
able to reproduce the known oracular speedup for quantum search [Roland and
Cerf(2002)], the method has not yet theoretically or empirically demonstrated
an advantage over state-of-the-art classical algorithms in optimization [Young
et al.(2008)Young, Knysh, and Smelyanskiy, Young et al.(2010)Young, Knysh, and
Smelyanskiy, Hen and Young(2011), Farhi et al.(2012)Farhi, Gosset, Hen,
Sandvik, Shor, Young, and Zamponi].

The standard proposal for QAO uses an adiabatic path defined by a one
parameter family of Hamiltonians $\\{H(s)\\}_{s\in[0,1]}$ that are all
_stoquastic_ , meaning that $H(s)$ has real and non-positive off-diagonal
matrix elements in the computational basis for each $s\in[0,1]$ [Bravyi and
Terhal(2009)]. Empirically it has been observed that this stoquastic QAO can
in many cases be efficiently classically simulated by quantum Monte Carlo
(QMC) methods [Isakov et al.(2016)Isakov, Mazzola, Smelyanskiy, Jiang, Boixo,
Neven, and Troyer], meaning that QMC simulations are able to effectively
follow the instantaneous ground state of the interpolating Hamiltonian with
the same computational cost _scaling_ as QAO. (QMC simulations can
approximately sample equilibrium states in the computational basis and
estimate the expectation values of local observables.) There are now several
rigorous results on polynomial-time QMC simulations for various classes of
equilibrium states of stoquastic Hamiltonians [Bravyi and Terhal(2009),
Bravyi(2015), Crosson and Harrow(2016), Bravyi and Gosset(2017), Crosson and
Harrow(2018), Harrow et al.(2019)Harrow, Mehraban, and Soleimanifar], however
there are also counterexamples where QMC methods fail to converge efficiently
[Hastings(2013), Jarret et al.(2016)Jarret, Jordan, and Lackey, Andriyash and
Amin(2017)].

In terms of computational complexity, estimating the ground state energy of a
stoquastic Hamiltonian can be done in the complexity class AM which has a
classical prover and classical verifier [Bravyi et al.(2008)Bravyi,
Divincenzo, Oliveira, and Terhal], whereas estimating the ground energy of
general local Hamiltonians is QMA-complete [A.Yu. Kitaev, A.H. Shen, M.N.
Vyalyi(2000)]. Similarly, stoquastic adiabatic computation cannot be universal
for quantum computing unless the Polynomial Hierarchy collapses [Bravyi et
al.(2006)Bravyi, Bessen, and Terhal]. Therefore, a significant open question
is whether ‘non-stoquastic’ Hamiltonians (which have positive or non-real off-
diagonal elements in every choice of local basis [Bravyi and Terhal(2009),
Marvian et al.(2019)Marvian, Lidar, and Hen, Klassen and Terhal(2019), Klassen
et al.(2019)Klassen, Marvian, Piddock, Ioannou, Hen, and Terhal]) could
improve the performance of QAO [Nishimori and Takada(2017), Hormozi et
al.(2017)Hormozi, Brown, Carleo, and Troyer, Susa et al.(2017)Susa, Jadebeck,
and Nishimori, Crosson et al.(2014)Crosson, Farhi, Yen-Yu Lin, Lin, and Shor,
Albash(2019), Durkin(2019), Özgüler et al.(2018)Özgüler, Joynt, and Vavilov].
Adiabatic computation based on non-stoquastic Hamiltonians can be universal
for quantum computing [Aharonov et al.(2008)Aharonov, van Dam, Kempe, Landau,
Lloyd, and Regev, Biamonte and Love(2008)] and is not efficiently simulable by
QMC due to the sign problem [Loh et al.(1990)Loh, Gubernatis, Scalettar,
White, Scalapino, and Sugar, Troyer and Wiese(2005), Marvian et
al.(2019)Marvian, Lidar, and Hen, Gupta and Hen(2020)].

In this work we define a locality-preserving mapping which takes every non-
stoquastic QAO protocol to a corresponding stoquastic QAO protocol.
Considering various ensembles (dense matrices, signed graphs, and local
Hamiltonians) we find that the non-stoquastic adiabatic paths have smaller
spectral gaps than the corresponding stoquastic adiabatic paths, with high
probability. Using random matrix theory, spectral graph theory, and other
analytical techniques we develop an explanation of this phenomenon based on
the low-energy spectrum of stoquastic and non-stoquastic Hamiltonians.

##  2 Background and Overview

In QAO, we assume that the global optima of discrete classical optimization
problems are encoded in the ground states of a problem Hamiltonian $H_{p}$
that is diagonal in the computational basis [Farhi et al.(2000)Farhi,
Goldstone, Gutmann, and Sipser, Young et al.(2008)Young, Knysh, and
Smelyanskiy, Young et al.(2010)Young, Knysh, and Smelyanskiy, Hen and
Young(2011), Hen(2012), Farhi et al.(2012)Farhi, Gosset, Hen, Sandvik, Shor,
Young, and Zamponi]. To reach a minimizing configuration of $H_{p}$, the
system is initially prepared in the ground state of a non-diagonal ‘driver’
Hamiltonian $H_{d}$, with $\left[H_{p},H_{d}\right]\neq 0$. The total
Hamiltonian $H(s)$ of the system interpolates between $H_{d}$ and $H_{p}$,
with $s$ being the interpolation parameter. (We suppress the dependence on $s$
unless otherwise noted.) If this process is carried out sufficiently slowly,
the adiabatic theorem of quantum mechanics [Kato(1950), Jansen et
al.(2007)Jansen, Ruskai, and Seiler, Lidar et al.(2009)Lidar, Rezakhani, and
Hamma, Elgart and Hagedorn(2012)] ensures that the system will stay close to
the ground state of the instantaneous Hamiltonian throughout the evolution,
such that one obtains a state close to the ground state of $H_{p}$ by the end
of the interpolation. For the adiabatic approximation to hold it suffices for
the running time of the algorithm to be inversely proportional to a low power
of the minimum gap — the difference between the second lowest and lowest
eigenvalue of the Hamiltonian — throughout the evolution [Wannier(1965), Farhi
et al.(2002)Farhi, Goldstone, and Gutmann, Elgart and Hagedorn(2012), Jansen
et al.(2007)Jansen, Ruskai, and Seiler, Lidar et al.(2009)Lidar, Rezakhani,
and Hamma].

In what follows, we focus solely on the gap of $H(s)$ and do not consider the
role of different parameterizations of the interpolation parameter $s$ in
terms of the physical time $t$. While appropriate reparameterizations of
$s(t)$ can soften the dependence on the spectral gap, as in the adiabatic
version of the Grover search algorithm [Roland and Cerf(2002)], in general
these techniques do not appear capable of removing the gap dependence
associated with the adiabatic condition, unless the notion of adiabaticity is
sacrificed altogether.

To compare the performance of QAO driven by stoquastic and non-stoquastic
fluctuations, we associate every non-stoquastic interpolating $n$-qubit
Hamiltonian $H=\sum_{i,j\in\\{0,1\\}^{n}}H_{ij}|i\rangle\langle j|$ to a
‘stoquasticized’ version of it, i.e., a stoquastic Hamiltonian whose sparsity
structure (the location of non-zero off-diagonal matrix elements) is identical
to that of the non-stoquastic one. We will consider two types of
stoquastization. In the first, which we refer to as ‘de-signed’
stoquastization, the de-signed stoquastic Hamiltonian is

$H^{\text{(de-signed)}}=\sum_{i\in\\{0,1\\}^{n}}H_{ii}|i\rangle\langle
i|-\sum_{\begin{subarray}{c}i,j\in\\{0,1\\}^{n}\\\ i\neq
j\end{subarray}}|H_{ij}||i\rangle\langle j|\,.$ (1)

The de-signing operation leaves the diagonal entries (corresponding to the
classical cost function in QAO) unchanged, while adjusting the phases of the
off-diagonal elements so that $H^{\text{(de-signed)}}$ is stoquastic in the
computational basis. The transformation does not change the sparsity structure
of the Hamiltonian, and in many cases the decomposition of $H^{\text{(de-
signed)}}$ into local Pauli terms can be determined from $H$ by inspection. In
the case where the off-diagonal entries arise purely from products of Pauli
$X$ and $Y$ terms, we provide an algorithm for de-signing in Appendix A.

A second form of stoquastization that we will consider applies to Hamiltonians
with real matrix entries,

$H^{\text{(shifted)}}=\frac{1}{2}\left(H-|\max_{i\neq j}H_{ij}|\sum_{i\neq
j:H_{ij}\neq 0}|i\rangle\langle j|\right)\ ,\,$ (2)

which we refer to as ‘shifting.’

We primarily consider shifting in the context of dense random matrices with
i.i.d. entries, where it takes the form,

$H^{\text{(shifted)}}=\frac{1}{2}\left(H-|\max_{i\neq
j}H_{ij}||s\rangle\langle s|\right)\,.$ (3)

where $|s\rangle=\sum_{z\in\\{0,1\\}^{n}}|z\rangle$ is the unnormalized
uniform superposition. Similar to $H$, both $H^{\textrm{(de-signed)}}$ and
$H^{\text{(shifted)}}$ define a path through the space of Hamiltonians that
end at the same point $H_{p}$. We ask the natural question: which of the
Hamiltonian paths has a larger minimum spectral gap, the non-stoquastic or the
stoquasticized Hamiltonian?

To answer this question, we provide a series of results that cover different
cases, all of which favor a larger spectral gap for the stoquasticized
Hamiltonians. (i) For a random $N\times N$ Hermitian matrix $H$ with
independent and identically distributed (i.i.d.) entries drawn uniformly from
$[-1,1]$ we prove that $\Delta_{H^{\text{(de-signed)}}}$ is larger than
$\Delta_{H}$ by a factor of $N^{3/2}$, with probability
$1-\exp(-\mathrm{poly}(N))$, where $\Delta$ denotes the energy gap between the
ground state and first excited state. (ii) For local Hamiltonians we first
prove that if the total Hamiltonian $H$ is diagonal in the $X$ basis, then the
stoquastization in the $Z$ basis, $H^{\text{(de-signed)}}$, always obeys
$\Delta_{H^{\text{(de-signed)}}}\geq\Delta_{H}$. (iii) To show that these
properties extend throughout the interpolation path, we present numerical
simulations of QAO up to $n=22$ qubits which demonstrate that the fraction of
QAO Hamiltonian paths with a larger minimum spectral gap than $H^{\text{(de-
signed)}}$ or $H^{\text{(shifted)}}$ rapidly goes to zero with $n$. (iv) One
may also consider quantum annealing algorithms which do not necessarily
satisfy the adiabatic approximation, and for these we show by simulations of
Schrödinger time-evolution up to $n=20$ qubits that the time-to-solution
metric [Rønnow et al.(2014)Rønnow, Wang, Job, Boixo, Isakov, Wecker, Martinis,
Lidar, and Troyer] also favors stoquastic Hamiltonians. (v) Finally, we apply
techniques from spectral graph theory called signed graph Cheeger inequalities
[Atay and Liu(2020)] to derive new theorems relating the low-energy spectrum
of signed (non-stoquastic) and unsigned (stoquasticized) versions of a graph.
Although these theorems do not fully capture the quantitative results that we
find in the numerical simulations, we believe they present a valuable
intuitive explanation for why spectral gaps of non-stoquastic Hamiltonians
tend to be smaller than those of their stoquastic counterparts. We begin with
a couple of preliminary observations.

###  2.1 Preliminary Observations

Our first observation is that de-signing always reduces the ground state
energy.

###### Observation 1

For any $H$, $H^{\text{(de-signed)}}$ with ground state energies $E_{0}$ and
$E^{\text{(de-signed)}}_{0}$ respectively, the ground state energies satisfy

$E^{\text{(de-signed)}}_{0}\leq E_{0}.$ (4)

with equality holding if and only if there exists a unitary transformation $U$
such that $UHU^{\dagger}=H^{\text{(de-signed)}}$, where $U$ is diagonal in the
basis of the stoquastization.

This bound [Eq. (4)] is proven by using the variational method with a ground
state ansatz for $H^{\text{(de-signed)}}$ that is formed from the absolute
value of the components of the ground state of $H$. (Details of the proof are
given in Appendix B.) In fact, this relationship between the ground state
energies has previously been studied in a different but related context. In
Ref. [Nie et al.(2013)Nie, Katsura, and Oshikawa, Nie et al.(2018)Nie,
Katsura, and Oshikawa] the authors consider many-body systems consisting of
particles hopping on a graph, and interacting by a potential (i.e., Hubbard
models on a general graph). In our terminology, they prove that if the hopping
part of the Hamiltonian is stoquastic then bosons always have a _strictly_
lower energy than fermions. However, if the hopping Hamiltonian is non-
stoquastic then fermions can have a lower ground energy (note that the
spectral gaps of these systems are not considered in [Nie et al.(2013)Nie,
Katsura, and Oshikawa, Nie et al.(2018)Nie, Katsura, and Oshikawa]).

While the de-signed Hamiltonian $H^{\text{(de-signed)}}$ always has a lower
ground state energy, it is easy to generate examples in which the first
excited energies satisfy $E^{\text{(de-signed)}}_{1}<E_{1}$. Therefore,
showing that $\Delta^{\text{(de-signed)}}\geq\Delta$ with high probability
requires a more sophisticated understanding of how much the first excited
energy can be decreased by de-signing.

Note that we can always shift our non-stoquastic Hamiltonian to obtain a
positive semidefinite matrix $G=\|H\|I-H$, with the ground state of $H$
becoming the principal eigenvector of $G$ (here $\|H\|$ denotes the operator
norm of $H$). Therefore we can reformulate our problem in terms of the
positive semidefinite matrix $G$ and its counterpart $G^{+}$ that is the non-
negative matrix formed by taking the entrywise absolute values of $G$. We now
compare the spectral gap between the largest and next largest eigenvalues of
$G$ and $G^{+}$, which leads to the following observation:

###### Observation 2

Let $G,G^{+}$ be as above. Then $\|G^{+}\|\geq\|G\|$ by Eq. (4), but
$\mathrm{Tr}(G)=\mathrm{Tr}(G^{+})$, so at least some of the eigenvalue gaps
in the spectrum of $G$ must be smaller than the corresponding gaps in $G^{+}$.

In the remainder of this work we will provide theoretical and numerical
evidence that this “compression” of the spectrum is concentrated in the low-
energy sector.

Finally, our third preliminary observation pertains to the first-order
perturbative correction that arises when a Hamiltonian $H_{0}$ that is
stoquastic (in, say, the computational basis) is perturbed by a Hamiltonian
$V$ with non-negative entries in the computational basis (therefore $V$
perturbs $H$ towards becoming non-stoquastic). If $|\psi_{0}^{0}\rangle$ is
the ground state of $H_{0}$ with energy $E_{0}^{0}$, then
$|\psi_{0}^{0}\rangle$ has all non-negative amplitudes in the computational
basis. The perturbed Hamiltonian $H_{s}=H_{0}+sV$ has ground energy
$E_{0}^{0}+s\langle\psi_{0}^{0}|V|\psi_{0}^{0}\rangle$ to first order in $s$.
Similarly, if $|\psi_{0}^{1}\rangle$ is the first excited state of $H_{0}$
with energy $E_{0}^{1}$, then to first order in $s$ the first excited energy
of $H_{s}$ is
$E_{s}^{1}=E_{0}^{1}+s\langle\psi_{0}^{1}|V|\psi_{0}^{1}\rangle$. Therefore,
up to first order in $s$ we have

$\Delta_{s}=\Delta_{0}+s\left(\langle\psi_{0}^{1}|V|\psi_{0}^{1}\rangle-\langle\psi_{0}^{0}|V|\psi_{0}^{0}\rangle\right)$

The fact that $V$ has non-negative entries, and $|\psi_{0}^{0}\rangle$ has
non-negative amplitudes, means that the
$\langle\psi_{0}^{0}|V|\psi_{0}^{0}\rangle$ is non-negative (it is a sum of
non-negative numbers). Meanwhile, $\langle\psi_{0}^{1}|V|\psi_{0}^{1}\rangle$
is a sum of numbers with opposite signs. This suggests that a perturbation in
the direction of becoming non-stoquastic increases the ground energy, and may
either increase or decrease the first excited energy, but likely by a lesser
amount (due to the cancellation) unless the unperturbed first excited state
aligns with the perturbation in a finely tuned way. Such an effect was
demonstarted in Ref. [Albash(2019)], where an example was provided where a
non-stoquastic intermediate Hamiltonian appears to mitigate (the study was
limited to $n\leq 24$) a perturbative crossing [Amin and Choi(2009)] that the
de-signed Hamiltonian could not.

##  3 Rigorous results

We rigorously compare general Hamiltonians to their de-signed and shifted
counterparts in three complimentary regimes: random dense matrices with i.i.d.
entries (compared to their shifted counterparts), Hamiltonians which are
diagonal in the $X$ basis compared to their counterparts which have been de-
signed in the $Z$ basis, and non-stoquastic Hamiltonians corresponding to
signed graph Laplacians, which are compared to their de-signed counterparts
(i.e., the underlying unsigned graphs).

###  3.1 Random matrices

In this section we apply results from random matrix theory to compare the
spectral gap (between the largest two eigenvalues) of $N\times N$ random real
symmetric matrices to the corresponding spectral gap of their shifted
counterparts (which form an ensemble of symmetric matrices with non-negative
entries). The random matrices we consider have i.i.d. entries, and therefore
these matrices are dense with non-zero entries, almost surely. For the real
symmetric matrices we will consider a distribution $\mathcal{W}$ of non-
Gaussian Wigner matrices (which are defined in general to have entries
distributed with mean 0 and finite variance). In our case the matrices in
$\mathcal{W}$ are defined to have entries that are uniformly distributed in
$[-1,1]$, in order to use $\max_{i,j}|H_{i,j}|=1$ in Eq. (3).

We will compare these matrices to a distribution $\mathcal{W}^{+}$ of random
matrices with nonnegative entries drawn uniformly from $[0,1]$ — these would
be the ‘shifted’ matrices. The key observation that enables the analysis is
that these two matrix distributions are related by a rank 1 shift matrix,
$A_{ij}=1$ for all $i,j=1,...,N$. Specifically, for every random matrix
$\hat{W}^{+}$ drawn from $\mathcal{W}^{+}$ there exists a $\hat{W}$ drawn from
$\mathcal{W}$ such that

$\hat{W}^{+}=A+\frac{1}{2}\hat{W}\quad,\quad\textrm{Pr}_{\mathcal{W}^{+}}(\hat{W}^{+})=\textrm{Pr}_{\mathcal{W}}(\hat{W}),$
(5)

where $\textrm{Pr}_{\mathcal{W}^{+}}$ denotes the probability of drawing the
matrix $W^{+}$ from the ensemble $\mathcal{W}^{+}$, and
$\textrm{Pr}_{\mathcal{W}}(\hat{W})$ is defined similarly. We note that
similar arguments involving finite rank perturbations have previously appeared
in the random matrix literature [Féral and Péché(2007)], however our
application to comparing spectral gaps of stoquastic and non-stoquastic
Hamiltonians is novel.

We will apply a large deviation bound that can be found as corollary 2.3.5 in
Ref. [Tao(2012)], which we reproduce here for completeness.
_Lemma._ Suppose that the entries $\hat{w}_{ij}$ of $W$ are independent, have
mean zero, and are uniformly bounded in magnitude by 1. Then there exist
absolute constants $C,c>0$ such that

$\textrm{Pr}_{\hat{W}}[\|\hat{W}\|>\ell\sqrt{N}]\leq Ce^{-c\ell N}$ (6)

for all $\ell\geq C$. This result states that the largest eigenvalue of
$\hat{W}$ is $\mathcal{O}(\sqrt{N})$ with probability exponentially close to
1. Even tighter bounds than this are known, which show that $\|\hat{W}\|$ lies
in the interval
$[2\sqrt{N}-\mathcal{O}(N^{1/6},2\sqrt{N}+\mathcal{O}(N^{1/6})]$, but Eq. (6)
has the advantage of a simple tail bound and suffices for our purposes.

Using Eqs. (5-6) together with Weyl’s inequality [Horn et al.(1990)Horn, Horn,
and Johnson, Franklin(1993)] allows us to show that the spectral gap of
$W^{+}$ is $\Omega(N)$111The notation $\Omega(f(n))$ means “asymptotically no
smaller than $f(n)$”.  with high probability. Let the eigenvalues of $W^{+}$
be $\lambda^{+}_{1}\geq...\geq\lambda^{+}_{N}$, the eigenvalues of $A$ be
$a_{1}=N\geq a_{2}=0\geq....\geq a_{N}=0$, and the eigenvalues of $W$ be
$\lambda_{1}\geq...\geq\lambda_{N}$. Then Weyl’s inequality implies

$\lambda^{+}_{1}\geq a_{1}+\frac{1}{2}\lambda_{N}\geq N+\mathcal{O}(\sqrt{N})$

and also

$\lambda^{+}_{2}\leq a_{2}+\frac{1}{2}\lambda_{1}\leq 0+\mathcal{O}(\sqrt{N})$

therefore we have $\Delta_{W^{+}}=\lambda^{+}_{1}-\lambda^{+}_{2}\geq
N+\mathcal{O}(\sqrt{N})$. Meanwhile, from the famous Wigner semicircle
distribution [Wigner(1958), Tao(2012)] we have that
$\Delta_{W}=\lambda_{1}-\lambda_{2}=\mathcal{O}(N^{-1/2})$. Therefore, in this
normalization as $N\to\infty$ we have $\Delta_{W}\to 0$ and
$\Delta_{W^{+}}\to\infty$.

###  3.2 Gaps of $X$-stoquastic matrices

We next show that if $H$ that is diagonal in the Pauli-$X$ basis (and is
therefore obviously stoquastic) then the spectral gap is not reduced by de-
signing in the $Z$ basis. To show this, let us denote the two lowest
eigenvalues of $H$ by $\lambda_{0}$ and $\lambda_{1}$ and the two lowest
eigenvalues of $H^{\text{(de-signed)}}$ by $\lambda_{0}^{\text{(de-signed)}}$
and $\lambda_{1}^{\text{(de-signed)}}$. In our proof, we shall use the
following representation of $H$ 222Note that the number of free parameters
$\alpha,\alpha_{i},\alpha_{ij},\ldots$ is precisely $2^{n}$, where $n$ is the
number of spins, hence the representation is unique. :

$H=\alpha+\sum_{i}\alpha_{i}X_{i}+\sum_{i<j}\alpha_{ij}X_{i}X_{j}+\sum_{i<j<k}\alpha_{ijk}X_{i}X_{j}X_{k}+\ldots$
(7)

We further decouple the magnitude of the various $\alpha$ parameters from
their signs and denote

$\alpha_{i}=|\alpha_{i}|(-1)^{a_{i}},\alpha_{ij}=|\alpha_{ij}|(-1)^{a_{ij}},\ldots$
(8)

with $a_{i},a_{ij},a_{ijk},\ldots\in\\{0,1\\}$. The de-signed version of $H$
is

$\displaystyle H^{\text{(de-signed)}}$ $\displaystyle=$
$\displaystyle\alpha-\sum_{i}|\alpha_{i}|X_{i}-\sum_{i<j}|\alpha_{ij}|X_{i}X_{j}$
(9) $\displaystyle-$
$\displaystyle\sum_{i<j<k}|\alpha_{ijk}|X_{i}X_{j}X_{k}-\ldots$

and since both $H$ and $H^{\text{(de-signed)}}$ are diagonal in the $x$-basis,
we can replace the Pauli operators $X_{i}$ with their bit representations
$X_{i}=(-1)^{x_{i}}$, where $x_{i}\in\\{0,1\\}$.

For convenience and without loss of generality we will fix the constant
$\alpha$ to be

$\alpha=\sum_{i}|\alpha_{i}|+\sum_{i<j}|\alpha_{ij}|+\sum_{i<j<k}|\alpha_{ijk}|+\ldots$
(10)

so that $H$ and $H^{\text{(de-signed)}}$ can be written as:

$\displaystyle H$ $\displaystyle=$
$\displaystyle\sum_{i}|\alpha_{i}|\left(1-(-1)^{a_{i}\oplus x_{i}}\right]$
$\displaystyle+$
$\displaystyle\sum_{i<j}|\alpha_{ij}|\left(1-(-1)^{a_{ij}\oplus x_{i}\oplus
x_{j}}\right)$ $\displaystyle+$
$\displaystyle\sum_{i<j<k}|\alpha_{ijk}|\left(1-(-1)^{a_{ijk}\oplus
x_{i}\oplus x_{j}\oplus x_{k}}\right)+\ldots)$

and similarly

$\displaystyle H^{\text{(de-signed)}}$ $\displaystyle=$
$\displaystyle\sum_{i}|\alpha_{i}|\left(1-(-1)^{x_{i}}\right)$
$\displaystyle+$
$\displaystyle\sum_{i<j}|\alpha_{ij}|\left(1-(-1)^{x_{i}\oplus x_{j}}\right)$
$\displaystyle+$
$\displaystyle\sum_{i<j<k}|\alpha_{ijk}|\left(1-(-1)^{x_{i}\oplus x_{j}\oplus
x_{k}}\right)+\ldots$

where $\oplus$ denotes bitwise XOR. It is easy to see that $H^{\text{(de-
signed)}}$ is minimized by setting $x_{i}=x^{G}_{i}=0$ giving
$\lambda_{0}^{\text{(de-signed)}}=0$. Further denoting the ground and first
excited state configurations of $H$ by $\tilde{x}^{G}_{i}$ and
$\tilde{x}^{E}_{i}$, respectively, and the first excited state configuration
of $H^{\text{(de-signed)}}$ by $x^{E}_{i}$, let us now prove that
$\Delta^{\text{(de-signed)}}=\lambda^{\text{(de-
signed)}}_{1}\geq\Delta=\lambda_{1}-\lambda_{0}$. The eigenvalue
$\lambda_{1}^{\text{(de-signed)}}$ evaluates to

$\displaystyle\lambda_{1}^{\text{(de-signed)}}$ $\displaystyle=$
$\displaystyle\sum_{i}|\alpha_{i}|\left(1-(-1)^{x^{E}_{i}}\right)$
$\displaystyle+$
$\displaystyle\sum_{i<j}|\alpha_{ij}|\left(1-(-1)^{x^{E}_{i}\oplus
x^{E}_{j}}\right)$ $\displaystyle+$
$\displaystyle\sum_{i<j<k}|\alpha_{ijk}|\left(1-(-1)^{x^{E}_{i}\oplus
x^{E}_{j}\oplus x^{E}_{k}}\right)+\ldots$

and similarly

$\displaystyle\Delta$ $\displaystyle=$
$\displaystyle\sum_{i}|\alpha_{i}|(-1)^{a_{i}}\left((-1)^{\tilde{x}^{G}_{i}}-(-1)^{\tilde{x}^{E}_{i}}\right)$
(14) $\displaystyle+$
$\displaystyle\sum_{i<j}|\alpha_{ij}|(-1)^{a_{ij}}\left((-1)^{\tilde{x}^{G}_{i}\oplus\tilde{x}^{G}_{j}}-(-1)^{\tilde{x}^{E}_{i}\oplus\tilde{x}^{E}_{j}}\right)$
$\displaystyle+$
$\displaystyle\sum_{i<j<k}|\alpha_{ijk}|(-1)^{a_{ijk}}\left((-1)^{\tilde{x}^{G}_{i}\oplus\tilde{x}^{G}_{j}\oplus\tilde{x}^{G}_{k}}\right.$
$\displaystyle-$
$\displaystyle\left.(-1)^{\tilde{x}^{E}_{i}\oplus\tilde{x}^{E}_{j}\oplus\tilde{x}^{E}_{k}}\right)\ldots$

Rearranging $\Delta$ above, we get:

$\displaystyle\Delta$ $\displaystyle=$
$\displaystyle\sum_{i}|\alpha_{i}|(-1)^{\tilde{a}_{i}}\left(1-(-1)^{\delta_{i}}\right)$
$\displaystyle+$
$\displaystyle\sum_{i<j}|\alpha_{ij}|(-1)^{\tilde{a}_{ij}}\left(1-(-1)^{\delta_{i}\oplus\delta_{j}}\right)$
$\displaystyle+$
$\displaystyle\sum_{i<j<k}|\alpha_{ijk}|(-1)^{\tilde{a}_{ijk}}\left(1-(-1)^{\delta_{i}\oplus\delta_{j}\oplus\delta_{k}}\right)+\ldots$

where $\delta_{i}=\tilde{x}^{G}_{i}\oplus\tilde{x}^{E}_{i}$,
$\tilde{a}_{i}=a_{i}\oplus\tilde{x}^{G}_{i},\tilde{a}_{ij}=a_{ij}\oplus\tilde{x}^{G}_{i}\oplus\tilde{x}^{G}_{j},\tilde{a}_{ijk}=a_{ijk}+\tilde{x}^{G}_{i}\oplus\tilde{x}^{G}_{j}\oplus\tilde{x}^{G}_{k}$
and so forth.

We can upper-bound the gap $\Delta$ by replacing the first excited state
configuration by a (possibly) different configuration (which may have a higher
cost) given by $\tilde{x}^{G}_{i}\oplus x^{E}_{i}$. This gives
$\delta_{i}=x^{E}_{i}$ and a bound on the gap, $\Delta\leq\tilde{\Delta}$,
where

$\displaystyle\tilde{\Delta}$ $\displaystyle=$
$\displaystyle\sum_{i}|\alpha_{i}|(-1)^{\tilde{a}_{i}}\left(1-(-1)^{x^{E}_{i}}\right)$
$\displaystyle+$
$\displaystyle\sum_{i<j}|\alpha_{ij}|(-1)^{\tilde{a}_{ij}}\left(1-(-1)^{x^{E}_{i}\oplus
x^{E}_{j}}\right)$ $\displaystyle+$
$\displaystyle\sum_{i<j<k}|\alpha_{ijk}|(-1)^{\tilde{a}_{ijk}}\left(1-(-1)^{x^{E}_{i}\oplus
x^{E}_{j}\oplus x^{E}_{k}}\right)+\ldots$

Comparing $\tilde{\Delta}$ above with the expression obtained for
$\lambda_{1}^{\text{(de-signed)}}$, Eq. (3.2), we conclude that
$\tilde{\Delta}\leq\lambda_{1}^{\text{(de-signed)}}$ and so

$\Delta^{\text{(de-signed)}}=\lambda_{1}^{\text{(de-
signed)}}\geq\tilde{\Delta}\geq\Delta\,.$ (17)

Thus, the gaps of $X$-diagonal matrices are never decreased by de-signing in
the $Z$ basis.

###  3.3 Spectral graph theory

In this section, we consider signed graph Laplacians, which serve as an
interesting class of non-stoquastic Hamiltonians (including some sparse and
local Hamiltonians), and enable the use of signed graph Cheeger inequalities
[Atay and Liu(2020)] to derive new theorems that relate the low-energy
spectrum of a signed (non-stoquastic) graph Laplacian to that of its unsigned
(stoquastic) counterpart. This work belongs to a line of progress in adapting
discrete Cheeger inequalities [Chung and Graham(1997)] and related bounds to
the setting of quantum Hamiltonians [Al-Shimary and Pachos(2010), Jarret and
Jordan(2015), Crosson and Bowen(2017)], including the recent adaptation of
signed graph Cheeger inequalities [Gournay(2016), Martin(2017), Atay and
Liu(2020)] to non-stoquastic Hamiltonians [Jarret(2018), Jarret et
al.(2018)Jarret, Lackey, Liu, and Wan]. The bounds we obtain are not
probabilistic, but the drawback is that they also depend on some geometric
properties of the associated ground states. Roughly speaking, the cases where
the non-stoquastic spectral gap can be larger than the stoquastic spectral gap
correspond to highly localized non-stoquastic ground states that are only
nonzero in a small sector of the local basis. Despite this limitation, we
present these results in part because they lead to an appealing intuitive
explanation for the general observations we make about stoquastic _vs._ non-
stoquastic spectra.

The Laplacian of an unsigned graph $G=(\mathcal{V},\mathcal{E})$, where
$\mathcal{V}=\\{v_{1},...,v_{N}\\}$ is a set of vertices and
$\mathcal{E}\subseteq\mathcal{V}\times\mathcal{V}$ is a set of edges between
those vertices, is an $N\times N$ symmetric matrix $L$ with the degree of each
vertex along the diagonal, and off-diagonal matrix entries that are zero
except for $L_{ij}=-1$ corresponding to edges $(v_{i},v_{j})\in\mathcal{E}$
(see appendix C for full details including the generalization to graphs with
weighted edges). Therefore these unsigned graph Laplacians always correspond
to stoquastic Hamiltonians, with vertices corresponding to basis states and
weighted edges correspoinding to off-diagonal matrix elements. In a signed
graph each edge $(v_{i},v_{j})$ is associated with a signature
$\sigma_{ij}\in\\{+1,-1\\}$, and the signed Laplacian matrix $L^{\sigma}$ has
off-diagonal entries $L^{\sigma}_{ij}=-\sigma_{ij}$, while the diagonal
entries are again given by the (unsigned) degrees of the vertices. Since
$L^{\sigma}$ can now contain positive off-diagonal elements, such signed graph
Laplacians can be non-stoquastic Hamiltonians. Our goal is to compare the
eigenvalues $\\{\lambda^{\sigma}_{i}\\}_{i=1}^{|V|}$ of a graph with signature
$\sigma$, enumerated in nondecreasing order, to the eigenvalues
$\\{\lambda^{+}_{i}\\}_{i=1}^{|V|}$ of its unsigned counterpart.

Since signed graph Laplacians can contain a sign problem, one may wonder about
the conditions under which this problem might be cured. The natural class of
transformations to consider in this context are of the form
$S^{\dagger}L^{\sigma}S$, where $S$ is a signature matrix (a diagonal unitary
with real entries). For this class of transformations it is possible to
completely characterize the cases in which the non-stoquasticity can be cured,
and these signed graphs are called “balanced.” A signed graph is balanced if
and only if the product of $\sigma_{ij}$ around every cycle in the graph is
positive. Another equivalent characterization is that every subset $S\subseteq
V$ of the graph can be partitioned into two sets $S=S_{1}\cup S_{2}$, with no
negative edges ($\sigma_{ij}=-1$) within the sets, and no positive edges
between them. If we denote the number of positive edges between $S_{1}$ and
$S_{2}$ by $|\mathcal{E}^{+}(S_{1},S_{2})|$, and the number of negative edges
within the sets by $|\mathcal{E}^{-}(S_{1})|$ and $|\mathcal{E}^{-}(S_{2})|$
respectively, then a balanced graph satisfies
$|\mathcal{E}^{+}(S_{1},S_{2})|+|\mathcal{E}^{-}(S_{1})|+|\mathcal{E}^{-}(S_{2})|=0$.

It turns out that this idea of bipartitioning a subset of vertices
$S\subseteq{V}$ into subsets $S_{1}$, $S_{2}$ leads to a useful quantity
$F(S)$ called the (intensive) frustration index (note that we modify the
notation of Ref. [Atay and Liu(2020)] to better suit a comparison of signed
and unsigned graphs),

$\displaystyle
F(S):=\frac{1}{\textup{vol}(S)}\cdot\min_{\begin{subarray}{c}S_{1}\cap
S_{2}=\emptyset\\\ S_{1}\cup
S_{2}=S\end{subarray}}\bigl{(}2|\mathcal{E}^{+}(S_{1},S_{2})|$
$\displaystyle+|\mathcal{E}^{-}(S_{1})|+|\mathcal{E}^{-}(S_{2})|\bigr{)},$
(18)

where $\textup{vol}(S)$ is the sum of the vertex degrees in $S$. Through the
signed Cheeger inequalities we will see that the frustration index has an
essential role in characterizing the low-energy spectrum of the graph.

For unsigned graphs, Cheeger’s inequality and its “multi-way” generalizations
characterize the low energy spectrum in terms of a quantity called the
_expansion_ , which detects bottlenecks in the graph. For any nonempty subset
$S\subseteq V$ the _expansion_ is defined by

$\Phi(S)=\frac{|\mathcal{E}(S,\bar{S})|}{\textup{vol}(S)}.$

where $|\mathcal{E}(S,\bar{S})|$ denotes the number of (unsigned) edges
leaving $S$. The expansion $\Phi(S)$ is also sometimes called the “bottleneck
ratio”, since it measures the size of the boundary of the set to the size of
its interior. For any $k\geq 1$ the $k$-th order Cheeger constant is

$h^{+}_{k}=\min_{\begin{subarray}{c}S_{1},...,S_{k}\subseteq\mathcal{V}\\\
S_{i}\cap
S_{j}=\emptyset\end{subarray}}\max\left\\{\Phi(S_{1}),...,\Phi(S_{k})\right\\}.$
(19)

In words, $S_{1},...,S_{k}$ is the sub-partition that minimizes the expansion
of all the subsets, and $h^{+}_{k}$ is the largest expansion amongst those
subsets in the sub-partition. Cheeger’s inequality relates $h_{k}$ to the
$k$-eigenvalue,

$\frac{\lambda^{+}_{k}}{2}\leq h_{k}^{+}\leq
Ck^{3}\sqrt{2D_{\max}\lambda_{k}^{+}},$ (20)

where $C$ is a constant and $D_{\max}$ is the maximum (unsigned) degree of any
vertex. The conclusion from Eq. (20) is that the low-energy spectrum of an
unsigned graph (and in fact any stoquastic Hamiltonian) is characterized by
sub-partitioning the ground space into subsets of minimal expansion: one has
$k$ small eigenvalues if and only if there are at least $k$ disjoint subsets
with bottlenecks.

To generalize Cheeger’s inequality to signed graphs, one defines the following
signed Cheeger constant

$h^{\sigma}_{k}=\min_{\begin{subarray}{c}S_{1},...,S_{k}\subseteq\mathcal{V}\\\
S_{i}\cap
S_{j}=\emptyset\end{subarray}}\max\left\\{F(S_{1})+\Phi(S_{1}),...,F(S_{k})+\Phi(S_{k})\right\\}\
,$ (21)

and then the generalization of Eq. (20) is

$\frac{\lambda^{\sigma}_{k}}{2}\leq h_{k}^{\sigma}\leq
Ck^{3}\sqrt{2D_{\max}\lambda_{k}^{\sigma}}.$ (22)

Therefore a signed graph has at least $k$ small eigenvalues above the ground
state if and only if it can be sub-partitioned into at least $k$ disjoint
subsets that all have low expansion and a small frustration index.

The Cheeger inequalities already provide an argument why we might generically
expect non-stoquastic Hamiltonians to have smaller spectral gaps. Consider a
stoquastic spectrum and the associated Cheeger subsets, $\lambda^{+}_{2}$ with
$S_{1}^{(2)},S_{2}^{(2)}$, $\lambda^{+}_{3}$ with
$S_{1}^{(3)},S_{2}^{(3)},S_{3}^{(3)}$, etc. These subsets all try to minimize
their expansion. What upper bounds on the non-stoquastic eigenvalues do we get
by considering these subsets? The upper bound we obtain on
$\lambda^{\sigma}_{1},\lambda^{\sigma}_{2},\lambda^{\sigma}_{3}$ is now
increased by the frustration index of these subsets. But note that
$S_{1}^{(2)},S_{2}^{(2)}$ will usually be bigger subsets than
$S_{1}^{(3)},S_{2}^{(3)},S_{3}^{(3)}$, and so in the typical case
$S_{1}^{(2)},S_{2}^{(2)}$ will have a larger frustration index. This rough
arguments suggests that the ground state energy is pushed up most by phase
frustration, the first excited energy is pushed up slightly less, etc. We
illustrate this intuition in Fig. 1. This then provides an explanation for why
non-stoquastic Hamiltonians tend to have smaller spectral gaps.

Figure 1: An intuitive general picture of the energy spectrum of a stoquastic
Hamiltonian compared to its de-signed counterpart.

Next we apply these Cheeger inequalities to prove a new result that relates
the spectral gap of a signed graph with its de-signed counterpart. We have
already seen in Eq. (4) that $\lambda_{1}^{+}\leq\lambda_{1}^{\sigma}$ for all
$\sigma$ (an unbalanced signature $\sigma$ cannot decrease the ground energy),
and so we now seek to obtain an upper bound on $\lambda_{2}^{\sigma}$. To do
this we can construct a variational excited state for $L^{\sigma}$ as follows.
From $\lambda_{1}^{\sigma}$ and Eq. (22) we can upper-bound the expansion and
the frustration index of the subset $\Omega$ corresponding to the support of
the non-stoquastic ground state. From $\lambda^{+}_{2}$ and the unsigned
Cheeger inequality Eq. (20) we also know there is a subset $S_{1}$ and $S_{2}$
with minimal expansion. Therefore we can upper bound the expansion of the
intersections $S_{1}^{\prime}=S_{1}\cap\Omega$ and
$S_{2}^{\prime}=S_{2}\cap\Omega$ using Eq. (20), and upper bound the
frustration with respect to a bipartition $S_{1}^{\prime}=V_{1}\cup V_{2}$,
$S_{2}^{\prime}=V_{3}\cup V_{4}$ inherited from the non-stoquastic ground
state (see fig. 2). These subsets are used to obtain the upper bound on
$\lambda_{2}^{\sigma}$ in the following theorem.

###### Theorem 1

Let $L^{\sigma}$ be a signed graph Laplacian with ground state
$\phi_{1}^{\sigma}$ with energy $\lambda^{\sigma}_{1}$. Define
$\Omega:=\\{v\in V:\phi_{1}^{\sigma}(v)\neq 0\\}$ and consider the unsigned
Laplacian $L^{+}$ on the same graph. By Cheeger’s inequality there must be a
subset $S\subseteq V$ with $\Phi(S)\leq\sqrt{2D_{\max}\lambda^{+}_{2}}$, and
for any subset $S$ with expansion $\Phi(S)$ satisfying this relation we have

$\lambda^{\sigma}_{2}\leq
2\sqrt{2D_{\max}}\left(\frac{\textup{vol}(\Omega)}{\textup{vol}(S\cap\Omega)}\sqrt{\lambda^{\sigma}_{1}}+\frac{2\;\textup{vol}(S)}{\textup{vol}(S\cap\Omega)}\sqrt{\lambda^{+}_{2}}\right)$

The proof is presented in Appendix C, with the proof strategy illustrated in
Fig. 2. However, using simpler techniques, we can also obtain the following
theorem upper bounding $\lambda_{2}^{+}$.

###### Theorem 2

(converse bounds): For any graph $G$ and any signature $\sigma$, we have

$\lambda_{2}^{+}\leq\sqrt{2D_{\max}\lambda^{\sigma}_{2}}$

Figure 2: An illustration of our proof strategy for Theorem 1. Details are
provided in Appendix C. The figure shows the support of the non-stoquastic
ground state $\phi_{1}^{\sigma}$ and two subsets $S^{\prime}_{1}=V_{1}\cup
V_{2}$ and $S^{\prime}_{2}=V_{3}\cup V_{4}$ with a small bottleneck ratio and
a small frustration index that is determined by the phase frustration that
already exists in the non-stoquastic ground state. Together with the signed
and unsigned Cheeger inequalities, we show these subsets provide a decent
upper bound on the non-stoquastic first excited energy.

In the context of $n$-qubit local Hamiltonians with bounded interaction degree
one always has $D_{\max}=\mathcal{O}(n)$. The fact that we have
$\sqrt{\lambda^{\sigma}_{1}}$ and $\sqrt{\lambda_{2}^{+}}$ on the RHS weakens
the bound, but in appendix C we describe how improved Cheeger inequalities and
standard assumptions about the low-energy spectra of QAO Hamiltonians (in
particular, that their exists a gap somewhere in the low energy spectrum)
would eliminate these square roots and strengthen the bound.

Finally, recall that $\Omega$ is the size of the basis support set of the non-
stoquastic Hamiltonian, and $S$ is the size of the set that minimizes the
bottleneck ratio in the ground state of the stoquastic Hamiltonian. Typically,
$S$ is large and encompasses a constant fraction of the total number of
vertices (for example, in a path graph with $N$ vertices
$\textup{vol}(S)=N/2$, and similarly for a hypercube with $N$ vertices).
Therefore in many cases this ratio of volume factors is $\mathcal{O}(1)$, and
together with the improved Cheeger inequality the bound becomes as tight as we
expect. In contrast, there will also be some fraction of cases in which
$\Omega$ or the intersection $\Omega\cap S$ is very small, and in these cases
the bound predicts that the non-stoquastic first excited energy can be much
larger than its stoquastic counterpart. These correspond to cases in which the
stoquastic and non-stoquastic ground states are very different from one
another.

In conclusion, if larger subsets tend to have (proportionally) larger phase
frustration, then the stoquastic and non-stoquastic spectra are similar with
generally larger gaps between the stoquastic eigenvalues. On the other hand,
if the phase frustration is nonuniformly distributed then the non-stoquastic
eigenstates can look very different from the stoquastic ones. Specifically,
the subsets with small expansion will have extra large frustration, so that
the sets that simultaneously minimize expansion and frustration look very
different from the ones that minimize the expansion by itself. For these cases
the stoquastic and non-stoquastic spectra can look almost arbitrarily
different from one another.

###  3.4 Important caveat

Our results so far have concerned the spectrum of the Hamiltonian, but
adiabatic evolutions are sometimes restricted to specific subspaces of the
entire Hilbert space due to symmetries of the Hamiltonian. We will refer to
this as the ‘evolution subspace.’ In this case, the relevant minimum gap for
the adiabatic condition is not the energy gap between the ground state and
first excited state of the total Hamiltonian but the energy gap between the
lowest two energy states in evolution subspace, which need not necessarily
coincide with the ground state and first excited state of the Hamiltonian. In
this case, it may very well be that the non-stoquastic Hamiltonian gap is
smaller than its stoquastic counterpart, with the opposite being the case in
the evolution subspace.

##  4 Numerical simulations

To complete our discussion, in this section we provide numerical evidence in
support of the analytical analysis presented in the preceding sections. We
demonstrate that the stoquasticized variants of various classes of random
matrices become increasingly more favorable to their non-stoquastic versions
with increasing system size. We study the gaps of dense and local matrices as
well as quantum annealing runtimes for a few classes of problems. In each case
we consider both the de-signed and shifted stoquastizations.

###  4.1 Dense matrices

We start off by considering random dense matrices. Here, we generate random
(i) real-valued and (ii) complex-valued Hermitian matrices of different
dimensions and compute their gaps. In the real case, matrix entries are drawn
independently and uniformly from the range $[-1,1]$ whereas in the complex
case the sampling is carried out for the real and imaginary parts separately.
To enforce Hermiticity, we average the generated matrices with their conjugate
transpositions. As a next step, we calculate numerically the gaps of the
stoquasticized counterparts of the generated matrices. The figure of merit we
focus on is the ‘fraction of non-stoquastic wins’— the fraction of occurrences
for which the energy gap of the (generally) non-stoquastic matrix is strictly
larger than its stoquasticized counterpart. We examine the behavior of this
fraction as a function of matrix dimension. The results are summarized in Fig.
3. As is evident, the fraction decays with the matrix dimension, and already
at $N=10$ the fraction is incredibly small, which is consistent with our
analytical derivation in Sec. 3.1.

Figure 3: Fraction of non-stoquastic wins for dense matrices (described in
Sec. 4.1) as a function of matrix dimension $N$. Each data point is the mean
over $10^{7}$ matrix instances, with the error bars being twice the standard
error of the mean.

###  4.2 Minimum gaps Max-Cut

When written in terms of Pauli operators, dense matrices are highly non-local
in nature and as such are not expected to be easily realizable in a physical
implementation of QAO. We therefore also consider the more physical setting
where the Hamiltonian has bounded locality. Furthermore, the efficiency of QAO
is determined by the minimum gap along the the entire interpolation from the
initial to the final Hamiltonian. To address these two issues, we consider a
time-dependent Hamiltonian of the form [Crosson et al.(2014)Crosson, Farhi,
Yen-Yu Lin, Lin, and Shor]:

$H(s)=(1-s)H_{D}+s(1-s)H_{C}+sH_{I}\,.$ (23)

where $s$ is the dimensionless annealing parameter, $H_{D}$ is the initial
‘driver’ Hamiltonian, $H_{I}$ is the final Hamiltonian that encodes the
computational problem, and $H_{C}$ is a catalyst Hamiltonian. We take $H_{D}$
to be the standard transverse-field Hamiltonian, $H_{D}=-\sum_{i}X_{i}$. We
take $H_{I}$ to be an Ising Hamiltonian representing Max-Cut problem instances
defined on random 3-regular graphs $H_{I}=\sum_{\langle ij\rangle}Z_{i}Z_{j}$
[Farhi et al.(2012)Farhi, Gosset, Hen, Sandvik, Shor, Young, and Zamponi,
Albash et al.(2017)Albash, Wagenbreth, and Hen]. This class of problem
instances is known to be NP-hard (see, e.g., Refs. [Farhi et al.(2012)Farhi,
Gosset, Hen, Sandvik, Shor, Young, and Zamponi, Liu et al.(2015)Liu,
Polkovnikov, and Sandvik]). The Ising Hamiltonian has each spin coupled
antiferromagnetically (with strength $J_{ij}=1$) with exactly three other
spins picked at random. To incorporate non-stoquasticity [Vinci and
Lidar(2017), Nishimori and Takada(2017), Hormozi et al.(2017)Hormozi, Brown,
Carleo, and Troyer, Susa et al.(2017)Susa, Jadebeck, and Nishimori] we choose
the catalyst Hamiltonian $H_{C}$ to be

$H_{C}=\sum_{\langle ij\rangle}\alpha_{ij}X_{i}X_{j}$ (24)

with the same connectivities $\langle ij\rangle$ as $H_{I}$. The coefficients
$\alpha_{ij}$ are chosen: (i) uniformly from $[-1,1]$ and (ii) randomly with
equal probability from the set $\\{-1,1\\}$. For the Hamiltonian $H(s)$ above,
the off-diagonal entries arise solely from purely off-diagonal Pauli terms, so
we implement de-signed stoquastization by the replacement
$\alpha_{ij}\to-|\alpha_{ij}|$ and shifted stoquastization (Eq. (2)) by the
replacement $\alpha_{ij}\to\frac{1}{2}\left(\alpha_{ij}-1\right)$. Our choice
of a shift by $1$ for shifted stoquastization is constant for all instances in
both classes of problems, even if the individual instances with uniform
$\alpha\in[-1,1]$ may exhibit a maximum value of $\alpha_{ij}$ that is less
than $1$.

Before proceeding, we note that as defined, the Hamiltonian Eq. (23) is
invariant under the transformation $P=\prod_{i}X_{i}$, which we refer to as
the global bit-flip symmetry of the Hamiltonian. Since the ground state of
$H(0)$ is the uniform superposition state and has eigenvalue $+1$ under $P$,
the evolution under $H(s)$ with this initial state is restricted to the $P=+1$
subspace [Hen and Spedalieri(2016), Hen and Sarandy(2016)]. This subspace is
our evolution subspace (see Sec. 3.4), and we denote its energy eigenvalues by
$\varepsilon_{i}(s)$ for $i=0,1,\dots,2^{n-1}-1$. Therefore, the relevant gap
for the QAO algorithm is the minimum gap in this subspace. This is relevant
because the lowest energy state in the evolution subspace may not be
correspond to the global ground state, whose eigenvalue we denote by
$E_{0}(s)$. We will see that this may have important consequences.

We study the minimum gaps of randomly generated $n$-spin problems with sizes
ranging from $n=6$ to $n=20$. For each size we generate 100 random instances
with a unique satisfying assignment (up to the global bit-flip symmetry) and
further consider up to 100 non-stoquastic $\\{\alpha_{ij}\\}$ realizations for
each Max-Cut instance yielding a maximum of $10^{4}$ Hamiltonian realizations
per problem size.

We first show in Fig. 4 that at the point $s_{\ast}$ in the interpolation
where the minimum gap occurs, a non-negligible fraction of the non-stoquastic
instances have $E_{0}(s_{\ast})<\varepsilon_{0}(s_{\ast})$, meaning the lowest
energy state in the evolution subspace is not the global ground state. We
therefore choose to distinguish between these two cases, when
$E_{0}(s_{\ast})=\varepsilon_{0}(s_{\ast})$ and when
$E_{0}(s_{\ast})<\varepsilon_{0}(s_{\ast})$. While the latter fraction appears
to be more or less constant over the range of $n$ studied, we cannot rule out
the possibility that it will decay to zero at larger $n$ values.

Figure 4: Fraction of non-stoquastic instances for Max-Cut problems with an
interpolating Hamiltonian of the form in Eq. (23) that have
$E_{0}(s_{\ast})<\varepsilon_{0}(s_{\ast})$ at their minimum gap point
$s_{\ast}$. Error bars correspond to $2\sigma$ confidence calculated with a
bootstrap over the instances, $10^{4}$ instances. Solid lines connecting the
data points are to aid the eye.

For every Hamiltonian instance, we inspect the minimum gap of $H(s)$
throughout the evolution and compare it against the minimum gap of its
stoquasticized variants. The results are summarized in Fig. 5 showing the
‘fraction of non-stoquastic wins’ as a function of system size. As both panels
of the figure indicate, the fraction is typically very low, more so for the
shifted case where the $2\sigma$ error bars prevent us from concluding
anything statistically relevant. We therefore focus on the de-signed case. We
first observe that that the $\pm 1$ non-stoqaustic instances exhibit
measurably fewer wins despite having a larger fraction of cases with
$E_{0}(s_{\ast})<\epsilon_{0}(s_{\ast})$ (Fig. 4). For the uniform case, we
observe that while the instances with
$E_{0}(s_{\ast})=\varepsilon_{0}(s_{\ast})$ appear to have a constant fraction
of wins as a function of system size, the fraction of wins with instances with
$E_{0}(s_{\ast})<\varepsilon_{0}(s_{\ast})$ grows with system size $n$. While
this result may indicate a positive trend, it is important to emphasize that
when compared to _both_ the de-signed and shifted cases, the results are more
in line with the shifted case, meaning that the shifted case almost always
beats the non-stoquastic case.

Figure 5: Fraction of non-stoquastic occurrences of larger non-stoquastic
minimum gap relative to their stoquasticized analogues, ‘de-signed’ (top) and
‘shifted’ (bottom), as a function of problem size, for Max-Cut problems with
an interpolating Hamiltonian of the form in Eq. (23). Error bars correspond to
$2\sigma$ confidence calculated with a bootstrap over $10^{4}$ instances.

###  4.3 Time evolution simulations

We note that the fraction of non-stoquastic wins as measured by the gaps (Fig.
5) does not necessarily translate to the same fraction of wins as measured by
an optimized computational cost $t_{f}/p_{\mathrm{GS}}$, often referred to as
the ‘average time to solution’. For each instance, we find the annealing time
that minimizes this quantity and calculate the median computational cost as a
function of system size for the same group of instances. We show our results
in Fig. 6, and we see no increase in the fraction of non-stoquastic wins. This
discrepancy between the gaps and the computational cost can be attributed to
the smallness of the problem instances: these small instances still have
relatively large gaps (we still do not see the exponential decay with system
size that might be expected for this class of instances), so the gap alone
does not quantitatively predict the computational cost.

Figure 6: Fraction of non-stoquastic occurrences of smaller non-stoquastic
average time to solution relative to their stoquasticized analogues as a
function of problem size, for Max-Cut problems with an interpolating
Hamiltonian of the form in Eq. (23). Error bars correspond to $2\sigma$
confidence calculated with a bootstrap over $10^{3}$ instances.

##  5 Conclusions and discussion

In this study, we provided analytical as well as numerical evidence in favor
of the assertion that non-stoquastoic driver Hamiltonians are inferior to
their stoquastic variants for quantum annealing optimization tasks. We
analyzed the gaps of several types of random non-stoquastic Hamiltonians
comparing them against their ‘stoquasticized’ counterparts. We find that
generically the non-positivity of the latter Hamiltonians renders their gap
larger than that of non-stoquastic ones, making non-stoquastic Hamiltonian
less favorable for quantum annealing optimization. Our results imply that
stoquastic Hamiltonians should generally be preferable to non-stoquastic ones,
at least as far as runtimes of quantum adiabatic algorithms are concerned.

It should be noted that examples to the contrary nonetheless exist. One well
understood example where a non-stoquastic Hamiltonian exhibits an
exponentially larger minimum gap over its de-signed counterpart is the case of
the ferromagnetic fully-connected $p$-spin models with a non-stoquastic
intermediate (or catalyst) Hamiltonian [Seki and Nishimori(2012), Seoane and
Nishimori(2012), Nishimori and Takada(2017), Susa et al.(2017)Susa, Jadebeck,
and Nishimori, Albash(2019), Durkin(2019)], with the caveat that while it is
non-stoquastic in the computational $Z$ basis, it is stoquastic in the $X$
basis.

Another example exhibiting a similar non-stoquastic advantage over its de-
signed counterpart is the introduction of a non-stoquastic intermediate
Hamiltonian in the strong-weak cluster problem [Boixo et al.(2016)Boixo,
Smelyanskiy, Shabani, Isakov, Dykman, Denchev, Amin, Smirnov, Mohseni, and
Neven] between the two clusters [Albash(2019), Takada et al.(2020)Takada,
Yamashiro, and Nishimori]. This example illustrates an important point: while
one choice of intermediate Hamiltonian exhibits an exponentially larger
minimum gap over its de-signed counterpart, other choices of the intermediate
Hamiltonian can exhibit the opposite effect, with the de-signed Hamiltonian
exhibiting an exponentially larger minimum gap over the non-stoquastic
Hamiltonian [Takada et al.(2020)Takada, Yamashiro, and Nishimori]. This
example illustrates that even if one adiabatic path may exhibit an
advantageous minimum gap scaling for the non-stoquastic Hamiltonian, there may
be _other_ adiabatic paths with stoquastic Hamiltonians that exhibit similar
minimum gap scalings.

While the above examples provide flashes of optimism about the prospects of
non-stoquastic drivers in QAO, our results call into question the promise
attributed to non-stoquastic drivers to serve as _generic_ catalysts of
quantum speedups.

We note that we have not studied here the possibility of specifically
tailoring driver Hamiltonians (stoquastic as well as non-stoquastic) to
instances of optimization problems with the goal of raising the minimum gap
along the evolution. Since nonetheless such tailoring usually requires
detailed knowledge of the spectrum of the problem to be solved, in most cases
doing so optimally may turn out to be as difficult to gain knowledge about as
the original problem to be solved.

## Acknowledgements

Computation for the work described in this paper was supported by the
University of Southern California’s Center for High-Performance Computing
(hpc.usc.edu) and by ARO grant number W911NF1810227. The research is based
upon work (partially) supported by the Office of the Director of National
Intelligence (ODNI), Intelligence Advanced Research Projects Activity (IARPA),
via the U.S. Army Research Office contract W911NF-17-C-0050. This material is
based on research sponsored by the Air Force Research laboratory under
agreement number FA8750-18-1-0044. The U.S. Government is authorized to
reproduce and distribute reprints for Governmental purposes notwithstanding
any copyright notation thereon." The views and conclusions contained herein
are those of the authors and should not be interpreted as necessarily
representing the official policies or endorsements, either expressed or
implied, of the ODNI, IARPA, or the U.S. Government. The U.S. Government is
authorized to reproduce and distribute reprints for Governmental purposes
notwithstanding any copyright annotation thereon.

## References

  * [Aharonov et al.(2008)Aharonov, van Dam, Kempe, Landau, Lloyd, and Regev] Dorit Aharonov, Wim van Dam, Julia Kempe, Zeph Landau, Seth Lloyd, and Oded Regev.  Adiabatic quantum computation is equivalent to standard quantum computation.  _SIAM Review_ , 50(4):755–787, 2008.  doi: https://doi.org/10.1137/080734479.
  * [Al-Shimary and Pachos(2010)] Abbas Al-Shimary and Jiannis K. Pachos.  Energy gaps of Hamiltonians from graph Laplacians.  _arXiv e-prints_ , art. arXiv:1010.4130, October 2010.
  * [Albash(2019)] Tameem Albash.  Role of nonstoquastic catalysts in quantum adiabatic optimization.  _Phys. Rev. A_ , 99:042334, Apr 2019.  doi: https://doi.org/10.1103/PhysRevA.99.042334.
  * [Albash et al.(2017)Albash, Wagenbreth, and Hen] Tameem Albash, Gene Wagenbreth, and Itay Hen.  Off-diagonal expansion quantum monte carlo.  _Phys. Rev. E_ , 96:063309, Dec 2017.  doi: https://doi.org/10.1103/PhysRevE.96.063309.
  * [Amin and Choi(2009)] M. H. S. Amin and V. Choi.  First-order quantum phase transition in adiabatic quantum computation.  _Phys. Rev. A_ , 80:062326, Dec 2009.  doi: https://doi.org/10.1103/PhysRevA.80.062326.
  * [Andriyash and Amin(2017)] Evgeny Andriyash and Mohammad H. Amin.  Can quantum Monte Carlo simulate quantum annealing?  _arXiv e-prints_ , art. arXiv:1703.09277, March 2017.
  * [Atay and Liu(2020)] Fatihcan M. Atay and Shiping Liu.  Cheeger constants, structural balance, and spectral clustering analysis for signed graphs.  _Discrete Mathematics_ , 343(1):111616, 2020.  ISSN 0012-365X.  doi: https://doi.org/10.1016/j.disc.2019.111616.
  * [A.Yu. Kitaev, A.H. Shen, M.N. Vyalyi(2000)] A.Yu. Kitaev, A.H. Shen, M.N. Vyalyi.  _Classical and Quantum Computation_ , volume 47 of _Graduate Studies in Mathematics_.  American Mathematical Society, Providence, RI, 2000.
  * [Biamonte and Love(2008)] Jacob D. Biamonte and Peter J. Love.  Realizable hamiltonians for universal adiabatic quantum computers.  _Phys. Rev. A_ , 78:012352, Jul 2008.  doi: https://doi.org/10.1103/PhysRevA.78.012352.
  * [Boixo et al.(2016)Boixo, Smelyanskiy, Shabani, Isakov, Dykman, Denchev, Amin, Smirnov, Mohseni, and Neven] Sergio Boixo, Vadim N. Smelyanskiy, Alireza Shabani, Sergei V. Isakov, Mark Dykman, Vasil S. Denchev, Mohammad H. Amin, Anatoly Yu Smirnov, Masoud Mohseni, and Hartmut Neven.  Computational multiqubit tunnelling in programmable quantum annealers.  _Nature Communications_ , 7:10327, 01 2016.  doi: https://doi.org/10.1038/ncomms10327.
  * [Bravyi and Terhal(2009)] S. Bravyi and B. Terhal.  Complexity of stoquastic frustration-free hamiltonians.  _SIAM Journal on Computing_ , 39(4):1462–1485, 2015/05/22 2009.  doi: https://doi.org/10.1137/08072689X.
  * [Bravyi(2015)] Sergey Bravyi.  Monte carlo simulation of stoquastic hamiltonians.  _Quantum Info. Comput._ , 15(13–14):1122–1140, October 2015.  ISSN 1533-7146.
  * [Bravyi and Gosset(2017)] Sergey Bravyi and David Gosset.  Polynomial-time classical simulation of quantum ferromagnets.  _Phys. Rev. Lett._ , 119:100503, Sep 2017.  doi: https://doi.org/10.1103/PhysRevLett.119.100503.
  * [Bravyi et al.(2006)Bravyi, Bessen, and Terhal] Sergey Bravyi, Arvid J. Bessen, and Barbara M. Terhal.  Merlin-Arthur Games and Stoquastic Complexity.  _arXiv e-prints_ , art. quant-ph/0611021, November 2006.
  * [Bravyi et al.(2008)Bravyi, Divincenzo, Oliveira, and Terhal] Sergey Bravyi, David P. Divincenzo, Roberto Oliveira, and Barbara M. Terhal.  The complexity of stoquastic local hamiltonian problems.  _Quantum Info. Comput._ , 8(5):361–385, May 2008\.  ISSN 1533-7146.
  * [Brooke et al.(1999)Brooke, Bitko, F., Rosenbaum, and Aeppli] J. Brooke, D. Bitko, T. F., Rosenbaum, and G. Aeppli.  Quantum annealing of a disordered magnet.  _Science_ , 284(5415):779–781, 1999.  doi: https://doi.org/10.1126/science.284.5415.779.
  * [Chung and Graham(1997)] Fan RK Chung and Fan Chung Graham.  _Spectral graph theory_.  Number 92 in CBMS Regional Conference Series. American Mathematical Society, 1997.
  * [Crosson and Bowen(2017)] Elizabeth Crosson and John Bowen.  Quantum ground state isoperimetric inequalities for the energy spectrum of local Hamiltonians.  _arXiv e-prints_ , art. arXiv:1703.10133, March 2017.
  * [Crosson and Harrow(2016)] Elizabeth Crosson and Aram W Harrow.  Simulated quantum annealing can be exponentially faster than classical simulated annealing.  In _2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS)_ , pages 714–723. IEEE, 2016.  doi: https://doi.org/10.1109/FOCS.2016.81.
  * [Crosson and Harrow(2018)] Elizabeth Crosson and Aram W. Harrow.  Rapid mixing of path integral Monte Carlo for 1D stoquastic Hamiltonians.  _arXiv e-prints_ , art. arXiv:1812.02144, December 2018.
  * [Crosson et al.(2014)Crosson, Farhi, Yen-Yu Lin, Lin, and Shor] Elizabeth Crosson, Edward Farhi, Cedric Yen-Yu Lin, Han-Hsuan Lin, and Peter Shor.  Different Strategies for Optimization Using the Quantum Adiabatic Algorithm.  _arXiv e-prints_ , art. arXiv:1401.7320, January 2014.
  * [Durkin(2019)] Gabriel A. Durkin.  Quantum speedup at zero temperature via coherent catalysis.  _Phys. Rev. A_ , 99:032315, Mar 2019.  doi: https://doi.org/10.1103/PhysRevA.99.032315.
  * [Elgart and Hagedorn(2012)] Alexander Elgart and George A. Hagedorn.  A note on the switching adiabatic theorem.  _Journal of Mathematical Physics_ , 53(10):102202, 2012.  doi: https://doi.org/10.1063/1.4748968.
  * [Farhi et al.(2000)Farhi, Goldstone, Gutmann, and Sipser] Edward Farhi, Jeffrey Goldstone, Sam Gutmann, and Michael Sipser.  Quantum Computation by Adiabatic Evolution.  _arXiv e-prints_ , art. quant-ph/0001106, January 2000.
  * [Farhi et al.(2002)Farhi, Goldstone, and Gutmann] Edward Farhi, Jeffrey Goldstone, and Sam Gutmann.  Quantum Adiabatic Evolution Algorithms versus Simulated Annealing.  _arXiv e-prints_ , art. quant-ph/0201031, January 2002.
  * [Farhi et al.(2012)Farhi, Gosset, Hen, Sandvik, Shor, Young, and Zamponi] Edward Farhi, David Gosset, Itay Hen, A. W. Sandvik, Peter Shor, A. P. Young, and Francesco Zamponi.  Performance of the quantum adiabatic algorithm on random instances of two optimization problems on regular hypergraphs.  _Phys. Rev. A_ , 86:052334, Nov 2012.  doi: https://doi.org/10.1103/PhysRevA.86.052334.
  * [Féral and Péché(2007)] Delphine Féral and Sandrine Péché.  The largest eigenvalue of rank one deformation of large wigner matrices.  _Communications in Mathematical Physics_ , 272(1):185–228, 2007.  doi: https://doi.org/10.1007/s00220-007-0209-3.
  * [Finnila et al.(1994)Finnila, Gomez, Sebenik, Stenson, and Doll] A. B. Finnila, M. A. Gomez, C. Sebenik, C. Stenson, and J. D. Doll.  Quantum annealing: A new method for minimizing multidimensional functions.  _Chemical Physics Letters_ , 219(5–6):343–348, 3 1994.  doi: https://doi.org/10.1016/0009-2614(94)00117-0.
  * [Franklin(1993)] Joel. N Franklin.  _Matrix Theory (Dover Books on Mathematics)_.  Dover Publications, Inc., Mineola, NY, USA, 1993.
  * [Gournay(2016)] Antoine Gournay.  An isoperimetric constant for signed graphs.  _Expositiones Mathematicae_ , 34(3):339 – 351, 2016.  ISSN 0723-0869.  doi: https://doi.org/10.1016/j.exmath.2015.10.002.
  * [Gupta and Hen(2020)] Lalit Gupta and Itay Hen.  Elucidating the interplay between non-stoquasticity and the sign problem.  _Advanced Quantum Technologies_ , 3(1):1900108, 2020.  doi: https://doi.org/10.1002/qute.201900108.
  * [Harrow et al.(2019)Harrow, Mehraban, and Soleimanifar] Aram Harrow, Saeed Mehraban, and Mehdi Soleimanifar.  Classical algorithms, correlation decay, and complex zeros of partition functions of quantum many-body systems.  _arXiv e-prints_ , art. arXiv:1910.09071, October 2019.
  * [Hastings(2013)] Matthew B. Hastings.  Obstructions to classically simulating the quantum adiabatic algorithm.  _Quantum Info. Comput._ , 13(11–12):1038–1076, November 2013.  ISSN 1533-7146.
  * [Hen(2012)] Itay Hen.  Excitation gap from optimized correlation functions in quantum monte carlo simulations.  _Phys. Rev. E_ , 85:036705, Mar 2012.  doi: https://doi.org/10.1103/PhysRevE.85.036705.
  * [Hen and Sarandy(2016)] Itay Hen and Marcelo S. Sarandy.  Driver hamiltonians for constrained optimization in quantum annealing.  _Phys. Rev. A_ , 93:062312, Jun 2016.  doi: https://doi.org/10.1103/PhysRevA.93.062312.
  * [Hen and Spedalieri(2016)] Itay Hen and Federico M. Spedalieri.  Quantum annealing for constrained optimization.  _Phys. Rev. Applied_ , 5:034007, Mar 2016.  doi: https://doi.org/10.1103/PhysRevApplied.5.034007.
  * [Hen and Young(2011)] Itay Hen and A. P. Young.  Exponential complexity of the quantum adiabatic algorithm for certain satisfiability problems.  _Phys. Rev. E_ , 84:061152, Dec 2011.  doi: https://doi.org/10.1103/PhysRevE.84.061152.
  * [Hormozi et al.(2017)Hormozi, Brown, Carleo, and Troyer] Layla Hormozi, Ethan W. Brown, Giuseppe Carleo, and Matthias Troyer.  Nonstoquastic hamiltonians and quantum annealing of an ising spin glass.  _Phys. Rev. B_ , 95:184416, May 2017.  doi: https://doi.org/10.1103/PhysRevB.95.184416.
  * [Horn et al.(1990)Horn, Horn, and Johnson] Roger A Horn, Roger A Horn, and Charles R Johnson.  _Matrix analysis_.  Cambridge university press, 1990.
  * [Isakov et al.(2016)Isakov, Mazzola, Smelyanskiy, Jiang, Boixo, Neven, and Troyer] Sergei V. Isakov, Guglielmo Mazzola, Vadim N. Smelyanskiy, Zhang Jiang, Sergio Boixo, Hartmut Neven, and Matthias Troyer.  Understanding quantum tunneling through quantum monte carlo simulations.  _Phys. Rev. Lett._ , 117:180402, Oct 2016.  doi: https://doi.org/10.1103/PhysRevLett.117.180402.
  * [Jansen et al.(2007)Jansen, Ruskai, and Seiler] Sabine Jansen, Mary-Beth Ruskai, and Ruedi Seiler.  Bounds for the adiabatic approximation with applications to quantum computation.  _J. Math. Phys._ , 48(10):–, 2007.  doi: https://doi.org/10.1063/1.2798382.
  * [Jarret(2018)] Michael Jarret.  Hamiltonian surgery: Cheeger-type gap inequalities for nonpositive (stoquastic), real, and Hermitian matrices.  _arXiv e-prints_ , art. arXiv:1804.06857, April 2018.
  * [Jarret and Jordan(2015)] Michael Jarret and Stephen P. Jordan.  Adiabatic optimization without local minima.  _Quantum Info. Comput._ , 15(3–4):181–199, March 2015.  ISSN 1533-7146.
  * [Jarret et al.(2016)Jarret, Jordan, and Lackey] Michael Jarret, Stephen P. Jordan, and Brad Lackey.  Adiabatic optimization versus diffusion monte carlo methods.  _Phys. Rev. A_ , 94:042318, Oct 2016.  doi: https://doi.org/10.1103/PhysRevA.94.042318.
  * [Jarret et al.(2018)Jarret, Lackey, Liu, and Wan] Michael Jarret, Brad Lackey, Aike Liu, and Kianna Wan.  Quantum adiabatic optimization without heuristics.  _arXiv e-prints_ , art. arXiv:1810.04686, October 2018.
  * [Kadowaki and Nishimori(1998)] Tadashi Kadowaki and Hidetoshi Nishimori.  Quantum annealing in the transverse ising model.  _Phys. Rev. E_ , 58:5355–5363, Nov 1998.  doi: https://doi.org/10.1103/PhysRevE.58.5355.
  * [Kato(1950)] T. Kato.  On the adiabatic theorem of quantum mechanics.  _J. Phys. Soc. Jap._ , 5:435, 1950.  doi: https://doi.org/10.1143/JPSJ.5.435.
  * [Klassen and Terhal(2019)] Joel Klassen and Barbara M. Terhal.  Two-local qubit Hamiltonians: when are they stoquastic?  _Quantum_ , 3:139, May 2019.  ISSN 2521-327X.  doi: https://doi.org/10.22331/q-2019-05-06-139.
  * [Klassen et al.(2019)Klassen, Marvian, Piddock, Ioannou, Hen, and Terhal] Joel Klassen, Milad Marvian, Stephen Piddock, Marios Ioannou, Itay Hen, and Barbara Terhal.  Hardness and Ease of Curing the Sign Problem for Two-Local Qubit Hamiltonians.  _arXiv e-prints_ , art. arXiv:1906.08800, Jun 2019.
  * [Lidar et al.(2009)Lidar, Rezakhani, and Hamma] Daniel A. Lidar, Ali T. Rezakhani, and Alioscia Hamma.  Adiabatic approximation with exponential accuracy for many-body systems and quantum computation.  _Journal of Mathematical Physics_ , 50(10):102106, 2009.  doi: https://doi.org/10.1063/1.3236685.
  * [Liu et al.(2015)Liu, Polkovnikov, and Sandvik] Cheng-Wei Liu, Anatoli Polkovnikov, and Anders W. Sandvik.  Quantum versus classical annealing: Insights from scaling theory and results for spin glasses on 3-regular graphs.  _Phys. Rev. Lett._ , 114:147203, Apr 2015.  doi: https://doi.org/10.1103/PhysRevLett.114.147203.
  * [Loh et al.(1990)Loh, Gubernatis, Scalettar, White, Scalapino, and Sugar] E. Y. Loh, J. E. Gubernatis, R. T. Scalettar, S. R. White, D. J. Scalapino, and R. L. Sugar.  Sign problem in the numerical simulation of many-electron systems.  _Phys. Rev. B_ , 41:9301–9307, May 1990.  doi: https://doi.org/10.1103/PhysRevB.41.9301.
  * [Martin(2017)] Florian Martin.  Frustration and isoperimetric inequalities for signed graphs.  _Discrete Applied Mathematics_ , 217:276 – 285, 2017.  ISSN 0166-218X.  doi: https://doi.org/10.1016/j.dam.2016.09.015.
  * [Marvian et al.(2019)Marvian, Lidar, and Hen] Milad Marvian, Daniel A. Lidar, and Itay Hen.  On the computational complexity of curing non-stoquastic hamiltonians.  _Nature Communications_ , 10(1):1571, 2019.  doi: https://doi.org/10.1038/s41467-019-09501-6.
  * [Nie et al.(2013)Nie, Katsura, and Oshikawa] Wenxing Nie, Hosho Katsura, and Masaki Oshikawa.  Ground-state energies of spinless free fermions and hard-core bosons.  _Phys. Rev. Lett._ , 111:100402, Sep 2013.  doi: https://doi.org/10.1103/PhysRevLett.111.100402.
  * [Nie et al.(2018)Nie, Katsura, and Oshikawa] Wenxing Nie, Hosho Katsura, and Masaki Oshikawa.  Particle statistics, frustration, and ground-state energy.  _Phys. Rev. B_ , 97:125153, Mar 2018.  doi: https://doi.org/10.1103/PhysRevB.97.125153.
  * [Nishimori and Takada(2017)] Hideyoshi Nishimori and Kabuki Takada.  Exponential enhancement of the efficiency of quantum annealing by non-stoquastic hamiltonians.  _Frontiers in ICT_ , 4:2, 2017.  ISSN 2297-198X.  doi: https://doi.org/10.3389/fict.2017.00002.
  * [Özgüler et al.(2018)Özgüler, Joynt, and Vavilov] A. Barış Özgüler, Robert Joynt, and Maxim G. Vavilov.  Steering random spin systems to speed up the quantum adiabatic algorithm.  _Phys. Rev. A_ , 98:062311, Dec 2018.  doi: https://doi.org/10.1103/PhysRevA.98.062311.
  * [Roland and Cerf(2002)] Jérémie Roland and Nicolas J. Cerf.  Quantum search by local adiabatic evolution.  _Phys. Rev. A_ , 65(4):042308–, 03 2002.  doi: https://doi.org/10.1103/PhysRevA.65.042308.
  * [Rønnow et al.(2014)Rønnow, Wang, Job, Boixo, Isakov, Wecker, Martinis, Lidar, and Troyer] Troels F. Rønnow, Zhihui Wang, Joshua Job, Sergio Boixo, Sergei V. Isakov, David Wecker, John M. Martinis, Daniel A. Lidar, and Matthias Troyer.  Defining and detecting quantum speedup.  _Science_ , 345(6195):420–424, 07 2014.  doi: https://doi.org/10.1126/science.1252319.
  * [Santoro et al.(2002)Santoro, Martoňák, Tosatti, and Car] Giuseppe E. Santoro, Roman Martoňák, Erio Tosatti, and Roberto Car.  Theory of quantum annealing of an Ising spin glass.  _Science_ , 295(5564):2427–2430, 2002.  doi: https://doi.org/10.1126/science.1068774.
  * [Seki and Nishimori(2012)] Yuya Seki and Hidetoshi Nishimori.  Quantum annealing with antiferromagnetic fluctuations.  _Phys. Rev. E_ , 85:051112, May 2012.  doi: https://doi.org/10.1103/PhysRevE.85.051112.
  * [Seoane and Nishimori(2012)] Beatriz Seoane and Hidetoshi Nishimori.  Many-body transverse interactions in the quantum annealing of the p -spin ferromagnet.  _J. Phys. A_ , 45(43):435301, 2012.  doi: https://doi.org/10.1088/1751-8113/45/43/435301.
  * [Susa et al.(2017)Susa, Jadebeck, and Nishimori] Yuki Susa, Johann F. Jadebeck, and Hidetoshi Nishimori.  Relation between quantum fluctuations and the performance enhancement of quantum annealing in a nonstoquastic hamiltonian.  _Phys. Rev. A_ , 95:042321, Apr 2017.  doi: https://doi.org/10.1103/PhysRevA.95.042321.
  * [Takada et al.(2020)Takada, Yamashiro, and Nishimori] Kabuki Takada, Yu Yamashiro, and Hidetoshi Nishimori.  Mean-field solution of the weak-strong cluster problem for quantum annealing with stoquastic and non-stoquastic catalysts.  _Journal of the Physical Society of Japan_ , 89(4):044001, 2020.  doi: https://doi.org/10.7566/JPSJ.89.044001.
  * [Tao(2012)] Terence Tao.  Topics in random matrix theory.  _Graduate studies in Mathematics_ , 132:46–47, 2012.
  * [Troyer and Wiese(2005)] Matthias Troyer and Uwe-Jens Wiese.  Computational complexity and fundamental limitations to fermionic quantum monte carlo simulations.  _Phys. Rev. Lett._ , 94:170201, May 2005.  doi: https://doi.org/10.1103/PhysRevLett.94.170201.
  * [Vinci and Lidar(2017)] Walter Vinci and Daniel A. Lidar.  Non-stoquastic hamiltonians in quantum annealing via geometric phases.  _npj Quantum Information_ , 3(1):38, 2017.  doi: https://doi.org/10.1038/s41534-017-0037-z.
  * [Wannier(1965)] Gregory H. Wannier.  Probability of violation of the ehrenfest principle in fast passage.  _Physics Physique Fizika_ , 1:251–253, May 1965.  doi: https://doi.org/10.1103/PhysicsPhysiqueFizika.1.251.
  * [Wigner(1958)] Eugene P. Wigner.  On the distribution of the roots of certain symmetric matrices.  _Annals of Mathematics_ , 67(2):325–327, 1958\.  ISSN 0003486X.  doi: https://doi.org/10.2307/1970008.
  * [Young et al.(2008)Young, Knysh, and Smelyanskiy] A. P. Young, S. Knysh, and V. N. Smelyanskiy.  Size dependence of the minimum excitation gap in the quantum adiabatic algorithm.  _Phys. Rev. Lett._ , 101:170503, Oct 2008.  doi: https://doi.org/10.1103/PhysRevLett.101.170503.
  * [Young et al.(2010)Young, Knysh, and Smelyanskiy] A. P. Young, S. Knysh, and V. N. Smelyanskiy.  First-order phase transition in the quantum adiabatic algorithm.  _Phys. Rev. Lett._ , 104:020502, Jan 2010.  doi: https://doi.org/10.1103/PhysRevLett.104.020502.

##  Appendix A Method for de-signing off-diagonal Pauli terms

Suppose the Hamiltonian has the form $H=H_{Z}+H_{O}$, where $H_{Z}$ is
diagonal in the computational basis and $H_{O}$ is a sum of $k$-local Pauli
strings composed of only Pauli $X$ and $Y$ operators. If $b,b^{\prime}$ are
bit strings that are more than Hamming distance $k$ apart, then $\langle
b|H|b^{\prime}\rangle=0$. Therefore we can efficiently compute each non-zero
off-diagonal element of $H_{O}$ by the following algorithm. For each subset of
$k$ qubits, one sums together the terms of $H_{O}$ that act entirely within
this subset. This sum of terms $H_{O}^{(S)}$ is a Hamiltonian matrix of
dimension $2^{k}\times 2^{k}$ with $2^{k}$ non-zero terms, so the
corresponding de-signed Hamiltonian $(H_{O}^{(S)})^{\text{(de-signed)}}$ can
be computed in time $\mathcal{O}(2^{k})$. The full de-signed Hamiltonian has
the form:

$\displaystyle H^{\text{(de-signed)}}$ $\displaystyle=$ $\displaystyle
H_{Z}+H_{O}^{\text{(de-signed)}}$ (25) $\displaystyle=$ $\displaystyle
H_{Z}+\sum_{\begin{subarray}{c}S\subseteq\\{1,...,n\\}\\\
|S|=k\end{subarray}}(H_{O}^{(S)})^{\text{(de-signed)}}\ .$

A Pauli-basis representation can then be computed in the usual way using the
Hilbert-Schmidt inner product. For example, the coefficient of the Pauli $X$
operator acting on the $i$-th qubit in the expansion would be proportional to
$\mathrm{Tr}(H_{O}^{\text{(de-signed)}}X_{i})$.

##  Appendix B Ground state energies

In this section we give the proof of Observation (1) in the introduction. Let
$H$ have ground state energy $E_{0}$ and ground state wave function

$|\psi\rangle=\sum_{z\in\mathcal{B}}\psi_{z}|z\rangle$

expressed in the basis $\mathcal{B}$. Therefore we have

$E=\langle\psi|H|\psi\rangle=\sum_{z\in\mathcal{B}}|\psi_{z}|^{2}H_{zz}+\sum_{\begin{subarray}{c}z,z^{\prime}\in\mathcal{B}\\\
z\neq z^{\prime}\end{subarray}}\psi^{*}_{z}H_{z,z^{\prime}}\psi_{z^{\prime}}$
(26)

Let $H^{\text{(de-signed)}}$ be the de-signed stoquastization of $H$ in the
basis $\mathcal{B}$, and consider the following variational ansatz for the
ground state of $H^{\text{(de-signed)}}$,

$|\phi\rangle=\sum_{z\in\mathcal{B}}|\psi_{z}||z\rangle.$

The energy of this ansatz is

$\displaystyle\langle\phi|H^{\text{(de-signed)}}|\phi\rangle$
$\displaystyle=\sum_{z\in\mathcal{B}}|\psi_{z}|^{2}H_{zz}-\sum_{\begin{subarray}{c}z,z^{\prime}\in\mathcal{B}\\\
z\neq
z^{\prime}\end{subarray}}|\psi_{z}||H_{z,z^{\prime}}||\psi_{z^{\prime}}|$
$\displaystyle\leq E$

where the inequality follows because

$\sum_{\begin{subarray}{c}z,z^{\prime}\in\mathcal{B}\\\ z\neq
z^{\prime}\end{subarray}}\psi^{*}_{z}H_{z,z^{\prime}}\psi_{z^{\prime}}\leq\sum_{\begin{subarray}{c}z,z^{\prime}\in\mathcal{B}\\\
z\neq
z^{\prime}\end{subarray}}|\psi_{z}||H_{z,z^{\prime}}||\psi_{z^{\prime}}|$

by the triangle inequality for real numbers. For equality to hold, we must
have

$\sum_{\begin{subarray}{c}z,z^{\prime}\in\mathcal{B}\\\ z\neq
z^{\prime}\end{subarray}}\psi^{*}_{z}H_{z,z^{\prime}}\psi_{z^{\prime}}=\sum_{\begin{subarray}{c}z,z^{\prime}\in\mathcal{B}\\\
z\neq
z^{\prime}\end{subarray}}|\psi_{z}||H_{z,z^{\prime}}||\psi_{z^{\prime}}|$

which can only hold if
$\psi^{*}_{z}H_{z,z^{\prime}}\psi_{z^{\prime}}=|\psi_{z}||H_{z,z^{\prime}}||\psi_{z^{\prime}}|$
for each $z,z^{\prime}\in\mathcal{B}$. But this latest condition implies that
the following signature matrix,

$\Lambda=\sum_{\begin{subarray}{c}z\in\mathcal{B}\\\ \psi_{z}\neq
0\end{subarray}}\frac{\psi_{z}}{|\psi_{z}|}|z\rangle\langle z|$

satisfies $\Lambda H\Lambda^{\dagger}=H^{\text{(de-signed)}}$. Since $\Lambda$
is unitary this implies that $H$ was secretly stoquastic.

##  Appendix C Spectra of signed graphs

A signed graph $\Gamma=(G,\sigma)$ is a graph $G=(\mathcal{V},\mathcal{E})$
with vertex set $\mathcal{V}$ and edge set $\mathcal{E}$, together with a
signature function $\sigma:\mathcal{E}\rightarrow\\{-1,+1\\}$ that associates
a sign to each edge. Each edge $(u,v)\in\mathcal{E}$ can also be assigned a
nonnegative weight $w_{uv}\geq 0$. The degree of a vertex is

$d_{u}:=\sum_{v:(u,v)\in\mathcal{E}}w_{uv},$

which does not depend on $\sigma$. For a subset $S\subseteq(\mathcal{V})$
define $\textup{vol}(S)=\sum_{v\in\ \mathcal{V}}d_{v}$. Define
$L^{\sigma}:=D-A^{\sigma}$, where

$D:=\sum_{u\in\mathcal{V}}d_{u}|u\rangle\langle u|\quad,\quad
A^{\sigma}:=\sum_{(u,v)\in\mathcal{E}}\sigma_{uv}w_{uv}|u\rangle\langle v|,$

which are the diagonal degree matrix, the signed adjacency matrix, and the
signed graph Laplacian. Denote the eigenvectors of $L^{\sigma}$ by
$\\{\phi^{\sigma}_{i}\\}_{i=1}^{n}$ with the corresponding eigenvalues,

$0\leq\lambda_{1}^{\sigma}\leq\lambda_{2}^{\sigma}\leq...\leq\lambda_{n}^{\sigma}\leq
2D_{\max}.$

In the special case of the all-positive signature, i.e., $\sigma_{uv}=+1$ for
all $(u,v)\in E$, the corresponding Laplacian $L^{+}$ is the standard graph
Laplacian of $G$ and is an explicitly stoquastic Hamiltonian. In general
$L^{\sigma}$ can be non-stoquastic, and in these cases its stoquastization
corresponds to $L^{+}$. We’ve already seen the bound

$\lambda_{1}^{+}\leq\lambda^{\sigma}_{1}$

(and in fact $\lambda^{+}_{1}=0$ for all unsigned graph Laplacians). Therefore
it remains to find relations between the non-stoquastic first excited energy
$\lambda^{\sigma}_{2}$ in terms of the spectrum of $L^{+}$, and our original
results of this nature are derived in Section C.2.

###  C.1 Background

First we describe the important class of balanced graphs, for which the sign
problem in the signed graph Laplacian is curable. Then we define the
frustration index, which is a quantitative measure of how far a graph is from
being balanced. Then we review Cheeger inequalities for unsigned graphs, in
order to appreciate how they become modified by the frustration index to
obtain the signed Cheeger inequalities.

#### Balanced graphs.

Let $\theta$ be a diagonal matrix with $\pm 1$ along the diagonal. Taking
$L^{\sigma}$ to $\theta^{-1}L^{\sigma}\theta$ is a unitary transformation, and
so in quantum mechanics we view it as a change of basis. Graph theorists
called $\theta$ a switching function, and the new signed graph defined by
$\theta^{-1}A^{\sigma}\theta=A^{\sigma^{\prime}}$ is called switching-
equivalent to the original. Needless to say, switching preserves the spectrum.
Equivalence under switching defines a partition of the set of signatures into
equivalence classes $[\sigma]$. A signed graph in the same switching class as
the all-positive signature is called _balanced_. It has the property that the
product of the edge signatures around every cycle is positive. This is the
equivalence class of Hamiltonians that have a sign problem that is curable in
the vertex label basis.

It turns out we will need another characterization of balance throughout the
following sections. A graph is balanced if and only if there exists a
bipartition $\mathcal{V}=V_{1}\cup V_{2}$, with $V_{1}\cap V_{2}=\emptyset$,
such that each positive edge connects to elements of the same subset, and each
negative edge connects elements of opposite subsets. We call this a balanced
bipartition. For the graph with all-positive signature this is achieved by
taking $V_{1}=\mathcal{V}$ and $V_{2}=\emptyset$. In general the bipartition
may be nontrivial.

#### Frustration Index.

In the previous section we saw that a graph is balanced iff it admits a
balanced bipartition. In this section we define the frustration index of an
arbitrary subset of vertices, which captures the residual frustration in the
most-balanced possible bipartition of the subset. To define the most-balanced
bipartition we need some additional notation.

Let $V_{1},V_{2}\subseteq\mathcal{V}$ and define functions that count the
number of edges between $V_{1}$ and $V_{2}$ of positive, negative, or either
type:

$\displaystyle|\mathcal{E}^{+}(V_{1},V_{2})|$
$\displaystyle:=\sum_{\begin{subarray}{c}(u,v)\in\mathcal{E},\;\sigma_{uv}=+1\\\
u\in V_{1},v\in V_{2}\end{subarray}}w_{uv},$ (27)
$\displaystyle|\mathcal{E}^{-}(V_{1},V_{2})|$
$\displaystyle:=\sum_{\begin{subarray}{c}(u,v)\in\mathcal{E},\;\sigma_{uv}=-1\\\
u\in V_{1},v\in V_{2}\end{subarray}}w_{uv},$ (28)

and
$|\mathcal{E}(V_{1},V_{2})|=|\mathcal{E}^{+}(V_{1},V_{2})|+|\mathcal{E}^{-}(V_{1},V_{2})|$.
define $|\mathcal{E}^{+}(V_{1})|=|\mathcal{E}^{+}(V_{1},V_{1})|$ and similarly
for $|\mathcal{E}^{-}(V_{1})|$ and $|\mathcal{E}(V_{1})|$. Note that each edge
is counted twice in these sums. Now for any subset $S\subseteq\mathcal{V}$
define the frustration index $F(S)$, which captures the minimum residual
energy due to non-stoquastic frustration in that subset,

$\displaystyle
F(S):=\frac{1}{\textup{vol}(S)}\cdot\min_{\begin{subarray}{c}S_{1},S_{2}\subseteq
S\\\ S_{1}\cap
S_{2}=\emptyset\end{subarray}}\bigl{(}2|\mathcal{E}^{+}(S_{1},S_{2})|$
$\displaystyle+|\mathcal{E}^{-}(S_{1})|+|\mathcal{E}^{-}(S_{2})|\bigr{)}.$
(29)

It turns out that $F(S)$ is also related to the minimum number of edges which
need to be removed from the subgraph induced on $S$ in order to put it in the
balanced signature equivalence class.

#### (Unsigned) Cheeger inequalities.

Figure 7: Top: An illustration of a graph as a geometric space (vertices and
edges are not explicitly shown) with two disjoint subsets $S_{1}$, $S_{2}$
which could achieve the minimum in Eq. (30). Bottom: An example of 4 subsets
that could determine $h_{4}^{+}$ as in Eq. (32). Using the higher-order
Cheeger inequality in Eq. (33) these 4 sets could determine the 3 lowest
eigenvalues of $L^{+}$.

For any subset $S\subseteq\mathcal{V}$ the _expansion_ is defined by

$\Phi(S)=\frac{|\mathcal{E}(S,\bar{S})|}{\textup{vol}(S)}\ .$

This quantity is also sometimes called the bottleneck ratio, because a small
value of $\Phi(S)$ indicates a relatively large number of vertices and small
number of edges, corresponding to a bottleneck in the graph.

For an unsigned graph the following Cheeger constant captures the minimum
possible expansion over all disjoint pairs of subsets,

$h^{+}_{2}=\min_{\begin{subarray}{c}S_{1},S_{2}=\mathcal{V}\\\ S_{1}\cap
S_{2}=\emptyset\end{subarray}}\max\left\\{\Phi(S_{1}),\Phi(S_{2})\right\\}.$
(30)

Taking the maximum expansion of two disjoint subsets ensures that at least one
of them has $\textup{vol}(S_{i})\leq\textup{vol}(\mathcal{V})/2$.

Cheeger’s inequality relates Eq. (30) to $\lambda_{2}^{+}$ (which is the
spectral gap because $\lambda^{+}_{1}=0$),

$\frac{\lambda^{+}_{2}}{2}\leq h^{+}_{2}\leq\sqrt{2D_{\max}\lambda_{2}^{+}}.$
(31)

The proof for the bound $\lambda^{+}_{2}\leq 2h^{+}_{2}$ is that for any $S$
we can take a first excited state ansatz that is positive on $S$ and negative
on $\bar{S}:=\mathcal{V}-S$,

$\hat{\phi}_{2}^{+}(x)=\begin{cases}\textup{vol}(\bar{S})&,x\in S\\\
-\textup{vol}(S)&,x\in\bar{S}\end{cases}.$

The upper bound $h^{+}_{2}\leq\sqrt{2D_{\max}\lambda_{2}^{+}}$ says that if
the gap is small, then there is a subset with small expansion. The proof is
based on a spectral clustering algorithm. The idea is that the first excited
state can be divided into vertices with positive amplitude and vertices with
negative amplitude. Then these sets are further refined a bit to obtain the
subsets $S_{1},S_{2}$.

The Cheeger constant and it’s relation to the first excited energy can also be
generalized to the rest of the spectrum by what are called higher-order
Cheeger inequalities. Define the $k$-th order Cheeger constant to be

$h^{+}_{k}=\min_{\begin{subarray}{c}\bigcup_{i=1}^{k}S_{i}=\mathcal{V}\\\
S_{i}\cap
S_{j}=\emptyset\end{subarray}}\max\left\\{\Phi(S_{1}),...,\Phi(S_{k})\right\\}.$
(32)

which are related to the $k$-eigenvalue,

$\frac{\lambda^{+}_{k}}{2}\leq h_{k}^{+}\leq
Ck^{3}\sqrt{2D_{\max}\lambda_{k}^{+}},$ (33)

where $C$ is a constant. Figure 7 illustrates a sub-partition with 4 subsets
which can be used to upper bound $h_{4}^{+}$ and hence upper bound
$\lambda_{k}^{+}$.

#### Signed Cheeger inequalities.

Figure 8: Top: The set $S=V_{1}\cup V_{2}$ that simultaneously minimizes its
frustration index $F(S)$ and its edge expansion $\Phi(S)$ determines the
signed Cheeger constant in Eq. (34) and the ground energy in Eq. (35). Bottom:
Two subsets $S_{1}=V_{1}\cup V_{2}$ and $S_{2}=V_{3}\cup V_{4}$ that
simultaneously minimize frustration and edge expansion. These sets could
determine the first excited energy $\lambda_{2}^{\sigma}$ according to Eq.
(37).

The lowest order signed Cheeger constant is defined to be

$h_{1}^{\sigma}=\min_{S\subseteq\mathcal{V}}F(S)+\Phi(S).$ (34)

The meaning of this quantity is that it seeks to find the subset of vertices
in the graph which is simultaneously close to balanced and has small
expansion. Such a subset can be used to construct a good ansatz for the ground
state, which is nonzero in $S$ and vanishes outside of $S$. The most-balanced
bipartition $S=V_{1}\cup V_{2}$ is then used to assign the ansatz positive
values in $V_{1}$ and negative values in $V_{2}$. This leads to the lowest
order signed Cheeger inequality,

$\frac{\lambda_{1}^{\sigma}}{2}\leq
h_{1}^{\sigma}\leq\sqrt{2D_{\max}\lambda_{1}^{\sigma}}$ (35)

It is also possible to define a series of higher order signed Cheeger
constants which bound the eigenvalues above the ground state of $L^{\sigma}$,

$h^{\sigma}_{k}=\min_{\begin{subarray}{c}\bigcup_{i=1}^{k}S_{i}=\mathcal{V}\\\
S_{i}\cap
S_{j}=\emptyset\end{subarray}}\max\left\\{F(S_{1})+\Phi(S_{1}),...,F(S_{k})+\Phi(S_{k})\right\\}.$
(36)

which for any signature $\sigma$ satisfy

$\frac{\lambda^{\sigma}_{k}}{2}\leq h_{k}^{\sigma}\leq
Ck^{3}\sqrt{2D_{\max}\lambda_{k}^{\sigma}}.$ (37)

In particular we will use the case $k=2$ (for which the definition 36 is
illustrated in Fig. 8) to upper $\lambda^{\sigma}_{2}$ and hence upper bound
the non-stoquastic spectral gap.

###  C.2 New Results

Figure 9: Top: The interior region $\Omega$ is the support of the ground state
of $L^{\sigma}$. The sets $S_{1},S_{2}$ are Cheeger subsets for the unsigned
Laplacian $L^{+}_{\Omega}$ restricted to the subgraph $\Omega$. Using Eq. (31)
the edge expansions $\Phi(S_{1}),\Phi(S_{2})$ are upper bounded in terms of
$\lambda^{+}_{2,\Omega}$. Bottom: The most-balanced bipartitions
$S_{1}=V_{1}\cup V_{2}$ and $S_{2}=V_{3}\cup V_{4}$ are used to upper bound
$\lambda^{\sigma}_{2}$ with Eq. (37). The frustration index of these sets is
upper bounded by
$\frac{\textup{vol}(\Omega)}{\textup{vol}(S_{i})}\sqrt{\lambda_{1}^{\sigma}}$
by Eq. (35) , and the edge expansion is upper bounded by
$\sqrt{\lambda_{2,\Omega}^{+}}$ by Eq. (31).

Let $\Omega\subseteq\mathcal{V}$ be the support of the ground state of the
signed Laplacian,

$\Omega:=\left\\{v\in\mathcal{V}:\phi^{\sigma}_{1}(v)\neq 0\right\\},$

The first bound we present is given in terms of the first excited energy of
the unsigned graph $\Omega$, considered as a subgraph of $G$. The proof
strategy is illustrated in Fig. 9. This unsigned subgraph Laplacian is
$L^{+}_{\Omega}$, and the eigenvalue and eigenvector are
$\lambda^{+}_{2,\Omega}$, $\phi_{2,\Omega}^{+}$. By Cheeger’s inequality we
know there exists sets $S_{1},S_{2}$ with

$\max\left\\{\Phi(S_{1}),\Phi(S_{2})\right\\}\leq\sqrt{2D_{\max}\lambda^{+}_{2,\Omega}}$

Now we use $S_{1},S_{2}$ to upper bound the second eigenvalue of unsigned
Laplacian

$\displaystyle\lambda^{\sigma}_{2}$ $\displaystyle\leq
2\max\left\\{F(S_{1})+\Phi(S_{1}),F(S_{2})+\Phi(S_{2})\right\\}$
$\displaystyle\leq
2\max\left\\{F(S_{1}),F(S_{2})\right\\}+\sqrt{2D_{\max}\lambda^{+}_{2,\Omega}}.$

In order to upper bound $F(S_{1}),F(S_{2})$ we need the fact that for any
subsets $S\subseteq S^{\prime}$ we have

$F(S)\leq\frac{\textup{vol}(S^{\prime})}{\textup{vol}(S)}F(S^{\prime}).$

This is a comparison of the numerators in Eq. (29), which states that the
most-balanced bipartition does not get better as more vertices and signed
edges are added. Therefore

$\displaystyle\lambda^{\sigma}_{2}$ $\displaystyle\leq
2\textup{vol}(\Omega)F(\Omega)\max\left\\{\frac{1}{\textup{vol}(S_{1})},\frac{1}{\textup{vol}(S_{2})}\right\\}$
$\displaystyle+\sqrt{2D_{\max}\lambda^{+}_{2,\Omega}}.$

and this leads to the following theorem.

###### Theorem 3

Let $L^{\sigma}=D-A^{\sigma}$ be a signed graph Laplacian with ground state
$\phi_{1}^{\sigma}$ with energy $\lambda^{\sigma}_{1}$. Define
$\Omega:=\\{v\in V:\phi_{1}^{\sigma}(v)\neq 0\\}$ and consider the unsigned
Laplacian $L^{+}_{\Omega}$ on the subgraph $\Omega$. By Cheeger’s inequality
there must be a subset $S\subseteq\Omega$ with
$\Phi(S)\leq\sqrt{2D_{\max}\lambda^{+}_{2,\Omega}}$, and for any subset $S$
with expansion $\Phi(S)$ satisfying this relation we have

$\lambda^{\sigma}_{2}\leq
2\sqrt{2D_{\max}}\left(\frac{\textup{vol}(\Omega)}{\textup{vol}(S)}\sqrt{\lambda^{\sigma}_{1}}+\sqrt{\lambda^{+}_{2,\Omega}}\right),$

where $\lambda^{+}_{2,\Omega}$ is the first excited energy of the unsigned
subgraph Laplacian $L^{+}_{\Omega}$.

Using the same proof idea we can also obtain an upper bound directly in terms
of $\lambda^{+}_{2}$ without restricting to the subgraph $\Omega$, at the cost
of introducing more volume factors. This time the subsets $S_{1},S_{2}$ come
from applying Cheeger’s inequality to the full unsigned Laplacian $L^{+}$, and
then forming the intersections $R_{1}=S_{1}\cap\Omega$ and
$R_{2}=S_{2}\cap\Omega$ to take the variational upper bound

$\lambda^{\sigma}_{2}\leq
2\max\left\\{F(R_{1})+\Phi(R_{1}),F(R_{2})+\Phi(R_{2})\right\\}.$

As before we can upper bound the frustration

$F(S)\leq\frac{\textup{vol}(\Omega)}{\textup{vol}(R)}F(\Omega)\leq\frac{\textup{vol}(\Omega)}{\textup{vol}(R)}\sqrt{2D_{\max}\lambda^{\sigma}_{1}}$

where $R$ is either $R_{1}$ or $R_{2}$. Next observe that every vertex on the
boundary of $R=S\cap\Omega$ is either on the boundary of $S$ or the boundary
of $\Omega$, and so

$\displaystyle\Phi(R)$
$\displaystyle\leq\frac{\textup{vol}(\Omega)}{\textup{vol}(R)}\Phi(\Omega)+\frac{\textup{vol}(S)}{\textup{vol}(R)}\Phi(S)$
$\displaystyle\leq\frac{\textup{vol}(\Omega)}{\textup{vol}(R)}\sqrt{2D_{\max}\lambda^{\sigma}_{1}}+\frac{\textup{vol}(S)}{\textup{vol}(R)}\sqrt{2D_{\max}\lambda^{+}_{2}}$

Therefore we have now shown the following variant of the theorem.

###### Theorem 4

Let $L^{\sigma}=D-A^{\sigma}$ be a signed graph Laplacian with ground state
$\phi_{1}^{\sigma}$ with energy $\lambda^{\sigma}_{1}$. Define
$\Omega:=\\{v\in V:\phi_{1}^{\sigma}(v)\neq 0\\}$ and consider the unsigned
Laplacian $L^{+}$ on the same graph. By Cheeger’s inequality there must be a
subset $S\subseteq V$ with $\Phi(S)\leq\sqrt{2D_{\max}\lambda^{+}_{2}}$, and
for any subset $S$ with expansion $\Phi(S)$ satisfying this relation we have

$\lambda^{\sigma}_{2}\leq
2\sqrt{2D_{\max}}\left(\frac{\textup{vol}(\Omega)}{\textup{vol}(S\cap\Omega)}\sqrt{\lambda^{\sigma}_{1}}+\frac{2\;\textup{vol}(S)}{\textup{vol}(S\cap\Omega)}\sqrt{\lambda^{+}_{2}}\right)$

Finally we present a cleaner theorem that unfortunately produces a statement
that goes in the opposite direction from what we want.

#### Theorem 3 (converse bounds):

For any graph $G$ and any signature $\sigma$, we have

$\lambda_{2}^{+}\leq\sqrt{2D_{\max}\lambda^{\sigma}_{2}}$

#### Proof.

$\displaystyle\lambda^{+}_{2}$ $\displaystyle\leq 2h^{+}_{2}$
$\displaystyle=\min_{\begin{subarray}{c}S_{1},S_{2}\subseteq V\\\ S_{1}\cap
S_{2}=\emptyset\end{subarray}}\max\left\\{\Phi(S_{1}),\Phi(S_{2})\right\\}$
$\displaystyle\leq\min_{\begin{subarray}{c}S_{1},S_{2}\subseteq V\\\ S_{1}\cap
S_{2}=\emptyset\end{subarray}}\max\left\\{F(S_{1})+\Phi(S_{1}),F(S_{2})+\Phi(S_{2})\right\\}$
$\displaystyle=h^{\sigma}_{2}$
$\displaystyle\leq\sqrt{2D_{\max}\lambda^{\sigma}_{2}}$

#### Comments.

This shows that the first excited energy of the unsigned graph cannot be too
much larger than the first excited energy of the signed graph. However since
$\lambda^{+}_{1}\leq\lambda^{\sigma}_{1}$, the unsigned graph could still have
a larger spectral gap.

###  C.3 How tight are these bounds?

In the case of theorem 1, the only volume factor is
$\textup{vol}(\Omega)/\textup{vol}(S)$. Here $S$ is a Cheeger subset for a
graph defined on $\Omega$. Usually the Cheeger subset occupies about half of
the vertices, for example in a path graph $\\{1,...,k\\}$ the subset
$S=\\{1,...,\lfloor k/2\rfloor\\}$ achieves the minimum expansion. Or in an
$n$-dimensional hypercube, we would take a Hamming ball of radius $\lfloor
n/2\rfloor.$ So in many cases we expect
$\textup{vol}(\Omega)/\textup{vol}(S)=\mathcal{O}(1)$ and we’ll have

$\lambda^{\sigma}_{2}=\mathcal{O}\left(\sqrt{D_{\max}\lambda^{\sigma}_{1}}+\sqrt{D_{\max}\lambda^{+}_{2,\Omega}}\right).$

For theorem 2 in the previous section, the RHS can blow up when
$S\cap\Omega=\emptyset$, and this does in fact sometimes happen. What this
means is that the first excited state in stoquastic case is very different
from the non-stoquastic ground state. In other words, the subset that
minimizes the expansion does a very poor job at minimizing the phase
frustration. The best case for theorem 2 occurs when $\Omega=V$, and theorem 1
and 2 coincide. The only advantage theorem 2 ever has is that it refers to the
eigenvalue $\lambda^{+}_{2}$ instead of $\lambda^{+}_{2,\Omega}$.

#### Improved Cheeger inequalities and the square root.

The topic of improved Cheeger inequalities is based on using higher
eigenvalues to obtain tighter bounds. For any signed graph and any
$k\in\\{1,...,N\\}$ we have [Atay and Liu(2020)]

$h_{1}^{\sigma}\leq
16\sqrt{2\|D\|}k\frac{\lambda_{1}^{\sigma}}{\sqrt{\lambda^{\sigma}_{k}}}.$

The key point being the absence of the square root on $\lambda^{\sigma}_{1}$
on the RHS. The meaning of this inequality is that we can get a quadratically
improved connection between expansion and gap, in the cases when there one of
the higher eigenvalues (for $k\geq 2$ but not too large because of the $k$ on
the RHS above) is much larger than the bare spectral gap.

For example, consider a transverse Ising model in the ferromagnetic regime. It
has two exponentially close eigenvalues, then a constant gap to the rest of
the spectrum. The improved Cheeger inequality tells us that the expansion and
the gap scale with the same order in this ground state.

An interesting thing about this is that it is similar to the condition under
which diabatic QA succeeds: the low energy spectrum (which may have
polynomially many states, say) is separated from the rest of the spectrum by a
gap. There is also higher order improved signed Cheeger inequality, which says
that there exists a constant C such that for any signed graph and any $1\leq
k\leq l\leq N$,

$h_{k}^{\sigma}\leq
C\sqrt{\|D\|}lk^{6}\frac{\lambda_{k}^{\sigma}}{\sqrt{\lambda^{\sigma}_{l}}}$

Therefore, if QA succeeds then there should be a gap after
$k=\mathrm{poly}(n)$ eigenvalues, and so we expect that in many cases the
bound tightens to

$\lambda^{\sigma}_{2}=\mathcal{O}\left(\mathrm{poly}(n)\left(\lambda^{\sigma}_{1}+\lambda^{+}_{2,\Omega}\right)\right).$