# Noise amplification at spin-glass bottlenecks of quantum annealing:
a solvable model

David Roberts  Department of Physics, University of Chicago, Chicago, Illinois
60637, USA  NASA Ames Research Center Quantum Artificial Intelligence
Laboratory (QuAIL), Moffett Field, CA 94035, USA  Theoretical Division, Los
Alamos National Laboratory, Los Alamos, NM 87545, USA  Lukasz Cincio
Theoretical Division, Los Alamos National Laboratory, Los Alamos, NM 87545,
USA  Avadh Saxena  Theoretical Division, Los Alamos National Laboratory, Los
Alamos, NM 87545, USA  Andre Petukhov  NASA Ames Research Center Quantum
Artificial Intelligence Laboratory (QuAIL), Moffett Field, CA 94035, USA
Google, Venice, CA 90291, USA  Sergey Knysh  NASA Ames Research Center Quantum
Artificial Intelligence Laboratory (QuAIL), Moffett Field, CA 94035, USA
Google, Venice, CA 90291, USA  SGT Inc., 7701 Greenbelt Rd., Greenbelt, MD
20770

###### Abstract

To gain better insight into the complexity theory of quantum annealing, we
propose and solve a class of spin systems which contain bottlenecks of the
kind expected to dominate the runtime of quantum annealing as it tries to
solve difficult optimization problems. We uncover a noise amplification effect
at these bottlenecks, whereby tunneling rates caused by flux-qubit noise scale
in proportion to the number of qubits $\mathcal{N}$ in the limit that
$\mathcal{N}\to\infty$. By solving the incoherent annealing dynamics exactly,
we find a wide range of regimes where the probability that a quantum annealer
remains in the ground-state upon exiting the bottleneck is close to one-half.
We corroborate our analysis with detailed simulations of the performance of
the D-Wave 2X quantum annealer on our class of computational problems.

##  I Introduction

Quantum Annealing (QA), a quantum heuristic for approximately solving NP-hard
binary optimization problems, is already in commercial use Boixo  _et al._
(2014); King  _et al._ (2018); Venturelli and Kondratyev (2019); Venturelli
_et al._ (2018); Neukart  _et al._ (2017); Rosenberg  _et al._ (2016); Rieffel
_et al._ (2015) in machine learning and artificial intelligence applications.
The algorithm works by mapping Quadratic Unconstrained Binary Optimization
(QUBO) problems to the problem of solving for the ground state of a spin glass
Hamiltonian. The time-complexity of QA, however, that is, how the required
resources for running the algorithm scale with problem size, is still under
investigation. The scaling behavior has been computed only for several
optimization problems Knysh (2015); Young  _et al._ (2010); Morita and
Nishimori (2006); Santoro  _et al._ (2002).

A key benchmarking problem in QA is the question of how an adiabatic quantum
computer performs on spin glass bottlenecks. Those are time intervals during
the annealing schedule where the gap shrinks exponentially with problem size,
see Fig. 1. A cascade of hard bottlenecks was found Santoro  _et al._ (2002)
in the ordered phase of the annealing process. Over a decade later, another
work Knysh (2015) provided an exactly solvable spin glass system, where the
scaling of the gap at these bottlenecks was obtained via analytical arguments,
as opposed to the usual, numerical treatment. As a result, it is now
understood that the time-complexity of quantum annealing for large problems is
dominated by spin glass bottlenecks Lanting  _et al._ (2017); King  _et al._
(2016); Steiger  _et al._ (2015); Boixo  _et al._ (2014); Dickson  _et al._
(2013); Altshuler  _et al._ (2010). There are two general features of these
bottlenecks, (i) an exponentially small gap as the system size $\mathcal{N}$
grows, and (ii) a quantum tunneling event that flips
$\mathcal{O}(\mathcal{N})$ spins.

These features can be embedded in a simple model, which can then be solved
exactly (some properties are accurately accessible only in the asymptotic
limit of $\mathcal{N}\rightarrow\infty$). To the best of our knowledge, there
have been no analytical studies of the effects of realistic (i.e.
longitudinal) qubit noise at bottlenecks of QA in the presence of frustration,
in the limit of large $\mathcal{N}$ Keck  _et al._ (2017); Deng  _et al._
(2013). In this study, we ultimately find that, at an annealing bottleneck,
the effects of frustration on multiqubit tunneling are washed-out in the
large-$\mathcal{N}$ limit, leaving behind a large-$\mathcal{N}$ noise
amplification effect. In particular, we find that tunneling rates in a wide
class of frustrated spin chains diverge as $\mathcal{N}M^{2}$, where $M$ is a
suitably-defined bulk spontaneous magnetization. This gives analytical
confirmation of prior work, which has found that the effective multiqubit
noise spectral density at an annealing bottleneck grows as the multiqubit
Hamming distance between the crossing states Boixo  _et al._ (2016); Amin  _et
al._ (2009).

Figure 1:  One-dimensional bottlenecks of quantum annealing. The plot shows
some exponentially-small gaps in the spectrum (obtained by exact
diagonalization) of a 1+1 dimensional $\mathcal{N}=7$ transverse-field Ising
spin glass. Only one is a bottleneck (i.e. involves the instantaneous ground
state $|\mathrm{GS}\rangle$, shown in the inset). Multiqubit-tunneling at this
bottleneck is asymptotically proportional to the number of qubits
$\mathcal{N}$, magnifying annealing errors in the adiabatic limit. The figure
shows instantaneous eigenenergies $E$ of the Hamiltonian in Eq. (1) as a
function of $B(t)$ for representative values of $J_{j}$ couplings in Eq. (3).

The rest of the paper is organized as follows. We introduce and discuss basic
properties of our exactly solvable model of bottlenecks in QA in Section II.
Section III concentrates on the effects of ambient noise at the QA
bottlenecks. We solve the Redfield equation to predict the behavior of the
annealing processor at the bottleneck at finite temperature in Section IV. We
conclude with the main results in Section V.

##  II A minimal model of a spin glass bottleneck of QA

We now search for the simplest class of Ising spin glasses containing a spin
glass bottleneck, where the minimum gap decreases exponentially as the number
of qubits $\mathcal{N}\to\infty$. Note that spin glass bottlenecks with
frustration are impossible to realize with mean-field-like problem
Hamiltonians (i.e. problem Hamiltonians with all-to-all interactions), thus
motivating an investigation of the one-dimensional case. Defining Pauli
matrices $\sigma^{\alpha}_{j}$, $\alpha=x,z$ acting on sites $j$ of a lattice,
the one-dimensional transverse-field Ising spin glass has Hamiltonian

$\displaystyle\hat{H}_{0}(t)$
$\displaystyle\equiv\hat{H}_{P}+B(t)\sum_{j}\hat{\sigma}^{x}_{j}.$ (1)

The parameter $B(t)$ here represents a uniform transverse magnetic field, and
the problem Hamiltonian $\hat{H}_{P}$ for the one-dimensional Ising spin glass
is

$\displaystyle\hat{H}_{P}$
$\displaystyle\equiv-\sum_{j=1}^{\mathcal{N}}J_{j}\sigma^{z}_{j}\sigma^{z}_{j+1},$
(2)

where here, $J_{j}$ denotes a coupler connecting qubits $j$ and $j+1$, and it
is understood that the qubit indices $j$ are to be interpreted modulo
$\mathcal{N}$. The one-dimensional transverse-field Ising model can be mapped
to free fermions Lieb  _et al._ (1961), and is thus a good place to gain some
useful physical intuition about these bottlenecks. The simplest one-
dimensional annealing problem containing a spin glass bottleneck is the
Frustrated Ring, the one-dimensional spin system depicted in Figure 2. The
couplings $J_{j}$ for the Frustrated Ring are given as follows:

$J_{j}=\begin{cases}J_{L}&j=n,n+1\\\ -J_{R}&j=2n+1\\\
J&\text{otherwise}\end{cases}\ ,$ (3)

here, $0<J_{R}<J_{L}<J$, and we make the total number of qubits
$\mathcal{N}\equiv 2n+1$ odd, to make the problem more symmetric (and thus
more amenable to an exact calculation). The Frustrated Ring is a minimal model
of a spin glass bottleneck, because, in one dimension, one must modify at
least three couplers in an otherwise uniform graph to achieve a spin glass
bottleneck; the Frustrated Ring saturates this lower bound.

Figure 2: The Frustrated Ring (c.f. Eq. (2)) is specified by the above
weighted graph. Links correspond to couplings between sites represented by
circles. It is a solvable 1D model of a spin glass bottleneck of QA. Red
(blue) circle denotes spin up (down). Figure 3: Performance of the D-Wave 2X
quantum annealer on the Frustrated Ring spin-glass benchmark (c.f. Figure 2).
In the regime $0<J_{R}<J_{L}<J$, $JJ_{R}>J_{L}^{2}$ (the region between the
two black curves), the annealing schedule of the Frustrated Ring contains a
spin-glass bottleneck. Within the bottleneck regime, the probability that the
D-Wave 2X returns the groundstate of the Ising spin glass in Eq. (2) decreases
noticeably from $\sim 1$ (yellow) to $\sim 0.4$ (dark blue). Here,
$\mathcal{N}=8$, and the coupling $J\equiv 1$ in the bulk of the chain.

The Frustrated Ring is frustrated, and therefore has a forced excitation in
its groundstate. At zero transverse field $B(t)\equiv 0$, there are two
generic positions where this excitation likes to reside: (i) at the
antiferromagnetic coupler $J_{R}$ (forming the frustrated groundstate
$|\Psi_{R}\rangle$), and (ii) at either of the two weak ferromagnetic couplers
$J_{L}$ (forming degenerate first-excited states $|\Psi_{L}\rangle$), see Fig.
4. At a special value of the transverse-field $B_{b}$ within the ordered phase
of the anneal, the $|\Psi_{R}\rangle$ states and a pair of $|\Psi_{L}\rangle$
states form an avoided crossing with a gap that scales as

$\displaystyle\Delta_{\text{min}}$
$\displaystyle\underset{\mathcal{N}\to\infty}{\propto}\bigg{(}\frac{J(J_{L}^{2}-J_{R}^{2})}{J_{R}(J^{2}-J_{L}^{2})}\bigg{)}^{\mathcal{N}},$
(4)

which is exponentially small in $\mathcal{N}$, as desired (see Fig. 5).
Representative performance of the D-Wave 2X quantum annealer in the bottleneck
regime, $JJ_{R}>J_{L}^{2}$, is depicted in Fig. 3. Since $|\Psi_{L}\rangle$
and $|\Psi_{R}\rangle$ differ by flipping half of the spins, the avoided
crossing of these states has two key features in common with spin glass
bottlenecks: (i) an exponentially small gap, and (ii) a quantum tunneling
event that flips $\mathcal{O}(\mathcal{N})$ spins.

Figure 4: Lowest energy states of the Frustrated Ring, at the end of the
annealing process. The green loop denotes a bond that gives a positive
contribution to the energy of the Hamiltonian in Eq. (2). In (a),
$|\Psi_{R}\rangle$ is formed by violating the anti-ferromagnetic bond $J_{R}$.
$|\Psi_{L}\rangle$ is obtained by violating either of the two weak
ferromagnetic bonds $J_{L}$, as shown in (b). Figure 5: (a) The low-energy
spectrum of an $\mathcal{N}=7$ Frustrated Ring computed for representative
values of couplings $J_{j}$ in Eq. (1) and Eq. (3). Note the avoided crossing.
(b) Due to $\mathbb{Z}_{2}$ Ising symmetry, the spin glass bottleneck consists
of two crossings, one occurring in each symmetry sector. In the Frustrated
Ring, the odd-parity crossing is gapless. However, only the even-parity
crossing is seen by the coherent annealing dynamics (see Dziarmaga (2005) for
details), and thus the even-parity gap (see Eq. (16)) determines the QA time-
complexity of this problem.

###  II.1 Annealing schedule

We now analyze the annealing schedule of the Frustrated Ring, and demonstrate
that it runs in exponential time (assuming completely coherent processor
dynamics). The first step in the analysis consists of reinterpreting the
system of interacting spins as a system of non-interacting fermionic
excitations (which represent dressed domain-walls in the spin representation).
In this new description, the global spin-flip symmetry becomes a symmetry
$(-1)^{N_{F}}$, which counts the number of fermionic excitations modulo $2$:

$\displaystyle(-1)^{N_{F}}\equiv\prod_{j=1}^{\mathcal{N}}\hat{\sigma}^{x}_{j}\
,~{}~{}~{}~{}~{}[\hat{H}_{0}(t),(-1)^{N_{F}}]=0\ .$ (5)

The appropriate fermionic operators
$\hat{\gamma}_{1},\hat{\gamma}_{2},\cdots,\hat{\gamma}_{2\mathcal{N}}$ are
Majorana fermions, i.e. they generate the Clifford algebra

$\displaystyle\hat{\gamma}_{i}\hat{\gamma}_{j}+\hat{\gamma}_{j}\hat{\gamma}_{i}\equiv
2\delta_{ij}.$ (6)

These Majorana fermions are written in terms of the original spin operators
via the Jordan-Wigner transformation

$\displaystyle\hat{\sigma}^{x}_{j}$ $\displaystyle=$
$\displaystyle-i\hat{\gamma}_{2j-1}\hat{\gamma}_{2j}\ ,$
$\displaystyle\hat{\sigma}^{z}_{j}$ $\displaystyle=$
$\displaystyle(-i)^{j-1}\hat{\gamma}_{1}\cdots\hat{\gamma}_{2j-1}\ .$ (7)

In terms of the fermionic operators, the theory decouples into two free
theories:

$\begin{split}\hat{H}^{\pm}_{0}(t)=&-i\sum_{j}J_{j}^{\pm}\,\hat{\gamma}_{2j}\hat{\gamma}_{2j+1}\\\
&+iB(t)\sum_{j}\hat{\gamma}_{2j-1}\hat{\gamma}_{2j}\ ,\end{split}$ (8)

where $J^{\pm}_{j}\equiv J_{j}$ for $j\neq\mathcal{N}$;
$J_{\mathcal{N}}^{\pm}\equiv\pm J_{\mathcal{N}}$, and $\hat{H}^{\pm}_{0}(t)$
denotes the annealing Hamiltonian $\hat{H}_{0}(t)$ restricted to the sector
with an even and odd number of Majorana fermions, respectively. The odd-parity
Hamiltonian $\hat{H}^{-}_{0}(t)$ is simplest to analyze, as all of its
coupling constants are positive in the limit $B\to 0$, and thus all fermionic
excitations (for sufficiently small transverse field) have positive energy.
For $B>0$, the energies $\epsilon>0$ of these excitations will in general have
some non-trivial dependence on the transverse field, leading to an energy
dispersion curve $\epsilon(B)$. When any one of these dispersion curves
crosses the horizontal line $\epsilon(B)\equiv 0$, the model becomes gapless.
We call the smallest transverse field at which this happens $B_{c}$, i.e. the
critical value of the transverse-field.

We then define $B(t)<B_{c}$ to be the spin glass phase of the anneal, and the
remaining regime $B(t)>B_{c}$ to be the paramagnetic phase of the anneal. In
the spin-glass phase, the Bogoliubov de-Gennes (BdG) equations centered on the
bond $J_{\mathcal{N}}^{-}\equiv J_{R}$ may be solved exactly, producing a
fermion bound state $\hat{c}_{R}$ exponentially localized at the right-end of
the graph, creating the odd-parity ground state.

$\displaystyle|\Psi_{R}^{-}\rangle:=\hat{c}_{R,-}^{\dagger}|\Omega_{-}\rangle.$
(9)

Similarly, in the limit $\mathcal{N}\rightarrow\infty$, the BdG equations
centered on the bond $J_{L}$ may also be solved exactly, see Appendix A. They
yield also a low-energy bound state $\hat{c}_{L}$ exponentially localized at
the left-end of the graph, so that the next-lowest energy state with odd-
parity is

$\displaystyle|\Psi_{L}^{-}\rangle:=\hat{c}_{L,-}^{\dagger}|\Omega_{-}\rangle.$
(10)

The corresponding energies of the states Eqs. (9-10) are
$\epsilon_{vac}^{-}+\epsilon_{R}^{-}$, and
$\epsilon_{vac}^{-}+\epsilon_{L}^{-}$, respectively, where
$\epsilon_{vac}^{-}$ is the energy of the odd-parity vacuum state
$|\Omega^{-}\rangle$. From the definition, it is then clear that, whenever the
energy dispersion curves $\epsilon_{R}^{-}(B)$ and $\epsilon_{L}^{-}(B)$
cross, the corresponding spin-chain eigenstates Eqs. (9-10) cross in energy.

In the even-parity sector, a similar picture emerges, although the energy
considerations are complicated by the fact that some defects have negative
energy in the spin glass phase, as the even-parity Hamiltonian
$\hat{H}^{+}_{0}$ contains a coupling constant $J_{\mathcal{N}}^{+}\equiv-
J_{R}$ which is negative. However, after some book-keeping, one can deduce the
two-lowest energy states in the even-fermion sector, which we list below:

$\displaystyle|\Psi_{R}^{+}\rangle$ $\displaystyle:=|\Omega_{+}\rangle,$ (11)
$\displaystyle|\Psi_{L}^{+}\rangle$
$\displaystyle:=\hat{c}_{R,+}^{\dagger}\hat{c}_{L,+}^{\dagger}|\Omega_{+}\rangle.$
(12)

As in the odd-parity case, the corresponding energies of the states Eqs.
(11-12) are $\epsilon_{vac}^{+}$, and
$\epsilon_{vac}^{+}+\epsilon_{L}^{+}+\epsilon_{R}^{+}$, respectively, where
$\epsilon_{vac}^{+}$ is the energy of the even-parity vacuum state
$|\Omega^{+}\rangle$. Again, this means that when the energy dispersion curves
$|\epsilon_{R}^{+}(B)|$ and $\epsilon_{L}^{+}(B)$ cross, the corresponding
spin-chain eigenstates Eqs. (9-10) cross in energy. Here, we have taken the
absolute value of the energy of the right-localized defect
$\hat{c}_{R,+}^{\dagger}$, as this defect has negative energy throughout the
spin glass phase $B(t)<B_{c}$ of the anneal.

Figure 6: The bonds $J_{L}$ support a pair of fermion bound states
$c^{\dagger}_{L}$ and $c^{\dagger}_{L^{\prime}}$, shown in (a) with energies
$\epsilon_{L}(B)$ and $\epsilon_{L^{\prime}}(B)$ shown in (b). Figure 7: The
BdG-boundstate crossing (a) A fermion bound state (a dressed 0-dimensional
domain wall) tunnels across the graph from left to right. It flips all of the
qubits along its way. (b) Bound-state energies as a function of $B$. As
external field $B$ is lowered, the defect $\hat{c}_{R}^{\dagger}$ becomes
energetically favorable at $B_{b}$ and the tunneling shown in panel (a) takes
place.

The origin of the spin glass bottleneck becomes clear once one realizes that
the doubling of the $J_{L}$-bond means that we have left-out a second
$L$-localized boundstate $\hat{c}_{L^{\prime}}$, which deflects the energy
dispersion curve $\epsilon_{L}(B)$ of the $\hat{c}_{L}$-defect downwards (see
Figure 6), so that, for $JJ_{R}>J_{L}^{2}$, it crosses with the energy of the
$\hat{c}_{R}$ defect at a tunable $B\equiv B_{b}$ value of the transverse-
field within the spin-glass phase of the anneal:

$B_{b}\equiv\frac{1}{J_{R}}\frac{(J^{2}-J_{L}^{2})(J_{L}^{2}-J_{R}^{2})}{J^{2}+J_{R}^{2}-2J_{L}^{2}}<B_{c}\
.$ (13)

A rigorous derivation of the identity in Eq. (13) is carried out in Appendix
A. The level crossing produces the situation in the odd-fermion sector
depicted in Figure 7, where a forced excitation (forced by parity constraints)
must quantum-mechanically tunnel from left to right in the graph. A similar
situation occurs in the even-fermion sector, leading to a second level
crossing at $B\equiv B_{b}$. So, in total, at $B=B_{b}$, two pairs of energy
levels cross.

####  II.1.1 Scaling of the gap

The previous analysis was only exact in the limit $\mathcal{N}\to\infty$. At
finite $\mathcal{N}$, in each parity sector, there will be hybridization
between boundstates localized at opposite ends of the graph (due to finite-
size effects), and so, directly at the minimum gap region, the true fermonic
eigenmodes will sweep rapidly through a mixture of left- and right-modes,
producing an avoided (Landau- Zener) crossing. For example, in the even-
fermion sector, one can define a Landau-Zener approach angle

$\tan
2\theta_{LZ}(B)\equiv\frac{\Delta(B)}{\epsilon_{R}^{+}(B)-\epsilon_{L}^{+}(B)}\
,$

where $\Delta(B)$ is defined as the (exponentially-small) overlap between the
left- and right-localized even-partity fermion boundstates. In terms of
$\theta_{LZ}$, the two lowest-energy excitations become:

$\displaystyle\hat{c}_{0,+}^{\dagger}$
$\displaystyle=\hat{c}_{R,+}^{\dagger}\sin\theta_{LZ}+\hat{c}_{L,+}^{\dagger}\cos\theta_{LZ}\
,$ (14) $\displaystyle\hat{c}_{1,+}^{\dagger}$
$\displaystyle=\hat{c}_{L,+}^{\dagger}\sin\theta_{LZ}-\hat{c}_{R,+}^{\dagger}\cos\theta_{LZ}\
.$ (15)

In contrast, the odd-parity bound states do not hybridize, as they have
different parities under spatial reflection $j\to\mathcal{N}-(j-1)$ (see
Appendix A), and the crossing there is exact, for all $\mathcal{N}<\infty$.
Therefore, at $B=B_{b}$, in the large-$\mathcal{N}$ limit, there is a pair of
crossings, with each crossing occurring in a distinct eigenspace of
$(-1)^{N_{F}}$, i.e. each crossing is labelled by a distinct $\mathbb{Z}_{2}$
quantum number, see bottom portion of Fig. 5. The scaling of the hybridization
of the even-parity boundstates at the bottleneck location gives the inverse QA
runtime

$\Delta(B_{b})\underset{\mathcal{N}\to\infty}{\propto}\mathcal{O}\left(\frac{J(J_{L}^{2}-J_{R}^{2})}{J_{R}(J^{2}-J_{L}^{2})}\right)^{\mathcal{N}}\
,$ (16)

which is exponentially small in $\mathcal{N}$, as desired. Note that the
spectral data in the odd-parity sector is irrelevant in analyzing the time-
complexity of the closed-system annealing dynamics, as the odd-parity sector
is never visited during the coherent evolution. This is because the initial
state of the QA protocol always has even spin-flip parity (see, e.g. Dziarmaga
(2005)), and spin-flip parity is conserved throughout the annealing schedule.

##  III Analysis of flux qubit noise at the annealing bottleneck

In this section we turn our attention to the effects of ambient flux qubit
noise at a frustrated spin glass bottleneck. In the D-Wave 2X quantum
annealer, fluctuations in onsite qubit flux bias form the dominant source of
noise Boixo  _et al._ (2016); Amin  _et al._ (2009). This flux bias noise is
accurately modelled by the following system-bath Hamiltonian:

$\displaystyle\hat{H}_{\text{D-Wave}}$ $\displaystyle\equiv$
$\displaystyle\hat{H}_{0}+\sum_{j=1}^{\mathcal{N}}\hat{Q}_{j}\hat{\sigma}^{z}_{j}+\hat{H}_{B}\
,$ (17) $\displaystyle\hat{Q}_{j}$ $\displaystyle\equiv$
$\displaystyle\sum_{u}\lambda_{u}(\hat{b}_{j,u}+\hat{b}_{j,u}^{\dagger})\ ,$
(18) $\displaystyle\hat{H}_{B}$ $\displaystyle=$
$\displaystyle\sum_{j,u}\hbar\omega_{u}(\hat{b}_{j,u}^{\dagger}\hat{b}_{j,u}+1/2)\
,$ (19)

where the bath operators $\\{\hat{b}_{j,u}\\}_{u}$ for each flux qubit satisfy
standard bosonic commutation relations
$[\hat{b}_{j,u},\hat{b}_{j,u^{\prime}}^{\dagger}]=\delta_{u,u^{\prime}}$, and
$\omega_{u}$ is the frequency of mode $u$ and $\lambda_{u}$ sets the
interaction strength between that mode and its corresponding qubit. For weak
noise strength, the effects of the flux bias fluctuations on the system
dynamics are uniquely characterized by the noise spectral density of these
fluctuations:

$\displaystyle S(\omega)\equiv\int_{0}^{\infty}dte^{i\omega t}\langle
e^{iH_{B}t/\hbar}\hat{Q}_{j}e^{-iH_{B}t/\hbar}\hat{Q}_{j}\rangle\ ,$ (20)

which we assume to be identical for each qubit. For simplicity, in this study
we assume the spectral density of the noise to be Ohmic:

$S(\omega)\equiv\hbar^{2}\frac{\eta\omega
e^{-\omega\tau_{c}}}{1-\exp(-\hbar\omega/k_{B}T)}$ (21)

at temperature $T$. Here, $\eta$ characterizes the strength of the
fluctuations in the flux bias, and is typically measured in macroscopic
resonant tunneling experiments on the individual qubits in the processing
unit. For the D-Wave 2X annealer at NASA QuAIL, $\eta$ was measured to be
$\sim 0.24$ in the regime $B\equiv 0$ Boixo  _et al._ (2016). We use this
value of $\eta$ for our numerical simulations of the D-Wave 2X at Los Alamos
National Laboratory.

Figure 8: Probability of success vs. $J_{L}$ for the D-Wave 2X. The plot shows
probability $P$ that the D-Wave 2X at Los Alamos National Laboratory finds the
optimal answer to the Frustrated Ring MAXCUT problem, as a function of the
parameter $J_{L}$ of the Frustrated Ring for system size $\mathcal{N}=6,8,10$.
We considered the Frustrated Ring defined by the following coupling
parameters: $J=1$, $J_{R}=0.2$ and $0.2<J_{L}<0.5$. The simulation on D-Wave
2X was run with annealing time $t_{\text{QA}}=5~{}\mu$s and temperature
$T=15.5$ mK. We find qualitative agreement of numerical Redfield simulations
with the D-Wave 2X.

We treat the open-system dynamics specified by Eqs. (17-19) in the Bloch-
Redfield approximation, which, at the qualitative level, closely predicts the
probability $P$ that the D-Wave 2X machine returns a global minimum of the
Frustrated Ring MAXCUT problem:

$\displaystyle P$ $\displaystyle\equiv\langle 00\cdots
0|\hat{\rho}_{f}|00\cdots 0\rangle+\langle 11\cdots 1|\hat{\rho}_{f}|11\cdots
1\rangle,$ (22)

where here, $\hat{\rho}_{f}$ is the collective density matrix of the qubits in
the annealer at the end of the anneal, and $\\{000\cdots 0,111\cdots 1\\}$ is
the complete set of bit strings which solve the Frustrated Ring MAXCUT
problem. The actual success probability observed in the D-Wave 2X quantum
annealer, compared with the simulated success probability (according to the
Bloch-Redfield simulation of the quantum processor) is plotted in Fig. 8.

Assuming the annealing processor is completely incoherent, i.e. the off-
diagonal matrix elements of $\hat{\rho}$ vanish in the energy eigenbasis, then
the Redfield master equation degenerates into a kinetic equation involving
tunneling rates between instantaneous eigenstates. These are given by Fermi’s
golden rule as (c.f. Amin  _et al._ (2009)):

$\displaystyle\Gamma_{i\to f}$ $\displaystyle=$
$\displaystyle\frac{1}{2\hbar^{2}}S(\omega_{i\to f})\cdot O_{i\to f}\ ,$ (23)
$\displaystyle O_{i\to f}$ $\displaystyle\equiv$
$\displaystyle\sum_{j=1}^{\mathcal{N}}|\mbox{$\langle\Psi_{i}|$}\hat{\sigma}^{z}_{j}\mbox{$|\Psi_{f}\rangle$}|^{2}\
,$ (24)

where here, $\omega_{i\to f}$ is the gap frequency $(E_{i}-E_{f})/\hbar$
between the initial $|\Psi_{i}\rangle$ and final eigenstate
$|\Psi_{f}\rangle$. Directly at the bottleneck in our spin glass benchmark, we
will find this incoherent evolution to be analytically solvable in the
large-$\mathcal{N}$ limit. Symmetry simplifies the problem: since
$\hat{\sigma}^{z}$ flips the $\mathbb{Z}_{2}$ quantum number corresponding to
spin-flip parity, the relevant form-factors that need to be calculated are
(assuming the temperature is sufficiently low so that we can assume that the
four-lowest levels are populated during the evolution):

$\displaystyle O_{0^{+}\to L^{-}}$ $\displaystyle=$
$\displaystyle\sum_{j}|\mbox{$\langle\Psi_{0}^{+}|$}\hat{\sigma}^{z}_{j}\mbox{$|\Psi_{L}^{-}\rangle$}|^{2}\
,$ (25) $\displaystyle O_{0^{+}\to R^{-}}$ $\displaystyle=$
$\displaystyle\sum_{j}|\mbox{$\langle\Psi_{0}^{+}|$}\hat{\sigma}^{z}_{j}\mbox{$|\Psi_{R}^{-}\rangle$}|^{2}\
,$ (26) $\displaystyle O_{1^{+}\to L^{-}}$ $\displaystyle=$
$\displaystyle\sum_{j}|\mbox{$\langle\Psi_{1}^{+}|$}\hat{\sigma}^{z}_{j}\mbox{$|\Psi_{L}^{-}\rangle$}|^{2}\
,$ (27) $\displaystyle O_{1^{+}\to R^{-}}$ $\displaystyle=$
$\displaystyle\sum_{j}|\mbox{$\langle\Psi_{1}^{+}|$}\hat{\sigma}^{z}_{j}\mbox{$|\Psi_{R}^{-}\rangle$}|^{2}\
.$ (28)

All other matrix elements vanish by symmetry, because $\hat{\sigma}^{z}$ mixes
fermionic $\mathbb{Z}_{2}$ parity symmetry. To calculate the transition rates,
we expand them so that they are written completely in terms of the basis
$\\{\mbox{$|\Psi_{L}^{-}\rangle$},\mbox{$|\Psi_{R}^{-}\rangle$},\mbox{$|\Psi_{L}^{+}\rangle$},\mbox{$|\Psi_{R}^{+}\rangle$}\\}$
of crossing states:

$\begin{split}O_{0^{+}\to{L,R}^{-}}=\sum_{j}&\left|\sin\theta_{LZ}\mbox{$\langle\Psi_{R}^{+}|$}\hat{\sigma}^{z}_{j}\mbox{$|\Psi_{L,R}^{-}\rangle$}\right.\\\
&+\left.\cos\theta_{LZ}\mbox{$\langle\Psi_{L}^{+}|$}\hat{\sigma}^{z}_{j}\mbox{$|\Psi_{L,R}^{-}\rangle$}\right|^{2}\
,\end{split}$ (29)

$\begin{split}O_{1^{+}\to{L,R}^{-}}=\sum_{j}&\left|\cos\theta_{LZ}\mbox{$\langle\Psi_{R}^{+}|$}\hat{\sigma}^{z}_{j}\mbox{$|\Psi_{L,R}^{-}\rangle$}\right.\\\
&\left.-\sin\theta_{LZ}\mbox{$\langle\Psi_{L}^{+}|$}\hat{\sigma}^{z}_{j}\mbox{$|\Psi_{L,R}^{-}\rangle$}\right|^{2}\
.\end{split}$ (30)

Some comments are in order. In general, tunneling due to non-fermionizable
(i.e. $\hat{\sigma}^{z}$) noise in a one-dimensional quantum spin glass is
analytically intractable due to the fact that the interacting portion of the
Hamiltonian in Eq. (17) maps to a Jordan-Wigner string

$\sum_{j}\hat{\sigma}^{z}_{j}\hat{Q}_{j}=\sum_{j}(-i)^{j}\hat{\gamma}_{1}\cdots\hat{\gamma}_{2j-1}\sum_{u}\lambda_{u}(\hat{b}_{j,u}+\hat{b}_{j,u}^{\dagger})\
.$ (31)

Therefore, solving the full D-Wave dynamics even at the perturbative,
Markovian level is widely considered to be analytically intractable Keck  _et
al._ (2017); Deng  _et al._ (2013). For example, one of the tunneling matrix
elements above involves an inner-product of the form

$\mbox{$\langle\Psi_{R}^{+}|$}\hat{\sigma}^{z}_{j}\mbox{$|\Psi_{R}^{-}\rangle$}=\mbox{$\langle\Omega_{+}|$}(-i)^{j}\hat{\gamma}_{1}\cdots\hat{\gamma}_{2j-1}\hat{c}_{R,-}^{\dagger}\mbox{$|\Omega_{-}\rangle$}\
.$ (32)

The Jordan-Wigner string in the above equation means that the matrix element
evaluates to a determinant of growing size. Furthermore, the parity-dependent
boundary conditions and broken translational invariance of the model, make the
attempts of obtaining the closed-form solution futile. What is more, the
perturbative treatment of this matrix element is also ill-fated because of the
short radius of convergence of perturbation theory in $B$ in generic spin
glasses (inevitably occurring at the first closing of the gap). In this work,
we treat the transverse-field at the non-perturbative level by performing a
field-theoretic calculation (see Appendix B), leading to an analytical
understanding of flux qubit noise at a spin glass annealing bottleneck.

###  III.1 Non-perturbative large-$\mathcal{N}$ calculation of tunneling rates

We begin by computing the off-diagonal, i.e.
$\mbox{$|\Psi_{L}\rangle$}\to\mbox{$|\Psi_{R}\rangle$}$, matrix elements.
These vanish in the large-$\mathcal{N}$ limit as a consequence of Lieb-
Robinson bounds Bravyi  _et al._ (2010). For example, we can factor

$\mbox{$\langle\Psi_{L}^{+}|$}\hat{\sigma}_{j}^{z}\mbox{$|\Psi_{R}^{-}\rangle$}=\mbox{$\langle\Psi_{L}^{+}(0)|$}\hat{\sigma}_{j}^{z}(B)\mbox{$|\Psi_{R}^{-}(0)\rangle$}\
,$ (33)

where
$\hat{\sigma}_{j}^{z}(B)=\hat{U}^{\dagger}(B)\hat{\sigma}^{z}_{j}\hat{U}(B)$,
and the unitary $\hat{U}(B)$ has the general form

$\displaystyle\hat{U}(B)$
$\displaystyle\equiv\mathcal{T}[e^{-i\int_{0}^{B}dB^{\prime}\widetilde{H}(B^{\prime})}]$
(34)

with $\widetilde{H}$ defined in Bravyi  _et al._ (2010). Now, suppose
$B<B_{b}$ is fixed. Since $\hat{H}$ has a spectral gap which is at least
$\mathcal{O}(1)$ for all $B^{\prime}<B$, $\hat{U}(B)$ is a constant-depth
unitary circuit Chen  _et al._ (2010). That is, $\hat{\sigma}^{z}_{j}(B)$, up
to exponentially small corrections constant in $\mathcal{N}$, is supported on
a region of constant size. However, $|\Psi_{L}^{+}\rangle$ and
$|\Psi_{R}^{-}\rangle$ at $B=0$ are separated by $\sim\mathcal{N}/2$ spin
flips. Therefore, for any fixed $B<B_{b}$, the matrix elements mixing
$|\Psi_{L}\rangle$ with $|\Psi_{R}\rangle$ are exponentially small in
$\mathcal{N}$, i.e.

$\displaystyle\mbox{$\langle\Psi_{R}^{+}|$}\hat{\sigma}^{z}_{j}\mbox{$|\Psi_{L}^{-}\rangle$}$
$\displaystyle\underset{\mathcal{N}\to\infty}{\sim}\mathcal{O}(e^{-c\mathcal{N}/2})\
,$ (35)

with $c$ a constant. Within a sufficiently small neighborhood of the crossing,
we can assume the diabatic crossing states $|\Psi_{L}^{\pm}\rangle$ and
$|\Psi_{R}^{\pm}\rangle$ to be approximately independent of $B$ (with the
$B$-dependence of the true eigenstates due to mixing within the subspace
spanned by these crossing states). Therefore, for $B>B_{b}$, sufficiently near
the crossing, the off-diagonal matrix elements are also exponentially small.
Via the exact same reasoning, we also have the asymptotic behavior

$\displaystyle\mbox{$\langle\Psi_{R}^{-}|$}\hat{\sigma}^{z}_{j}\mbox{$|\Psi_{L}^{+}\rangle$}$
$\displaystyle\underset{\mathcal{N}\to\infty}{\sim}\mathcal{O}(e^{-c^{\prime}\mathcal{N}/2})\
,$ (36)

for the other off-diagonal matrix element with $c^{\prime}$ another constant.
Again, this follows from the fact that at $B=0$ the state
$|\Psi_{R}^{-}\rangle$ is separated from the state $|\Psi_{L}^{+}\rangle$ by
$\sim\mathcal{N}/2$ spin flips.

Figure 9:  Noise amplification at a spin-glass bottleneck. Very close to the
annealing bottleneck, provided that the qubit index $j$ is in the bulk of the
chain, the noise matrix element $O_{0\to
2}^{(j)}=\theta(B_{b}-B)|\mbox{$\langle\Psi_{0}^{+}|$}\hat{\sigma}^{z}_{j}\mbox{$|\Psi_{L}^{-}\rangle$}|^{2}+\theta(B-B_{b})|\mbox{$\langle\Psi_{0}^{+}|$}\hat{\sigma}^{z}_{j}\mbox{$|\Psi_{R}^{-}\rangle$}|^{2}$
(c.f. Eqs. (25-28)) approaches the predicted value of
$(1-(B_{b}/J)^{2})^{1/4}/2$ (dashed line). This is $1/2$ the squared
magnetization of the uniform quantum Ising chain. Therefore, the corresponding
transition rate (which is a sum over all qubits) is
$\mathcal{O}(\mathcal{N})$. See text for details.

In summary, the off-diagonal contributions to multiqubit tunneling
asymptotically vanish near the crossing in the large-$\mathcal{N}$ limit.
Therefore, provided that we are sufficiently close to the crossing point so
that neither $\tan\theta_{LZ}$ nor $\cot\theta_{LZ}$ are exponentially small
in $\mathcal{N}$, we can ignore these off-diagonal contributions. In this
limit, the large-$\mathcal{N}$ tunneling form factors have the asymptotics

$\displaystyle O_{0^{+}\to R^{-}}$ $\displaystyle\underset{B\to
B_{b}}{\sim}\sum_{j}\sin^{2}\theta_{LZ}|\langle\Psi_{R}^{+}|\sigma^{z}_{j}|\Psi_{R}^{-}\rangle|^{2}\
,$ (37) $\displaystyle O_{0^{+}\to L^{-}}$ $\displaystyle\underset{B\to
B_{b}}{\sim}\sum_{j}\cos^{2}\theta_{LZ}|\langle\Psi_{L}^{+}|\sigma^{z}_{j}|\Psi_{L}^{-}\rangle|^{2}\
.$ (38)

with analogous expressions for $O_{1^{+}\to R^{-},L^{-}}$. To calculate the
simplified form factors given by Eqs. (37-38), we begin with the following
generic observation: for each time-dependent annealing Hamiltonian $H_{0}(t)$
specified in Eq. (1), let $\widetilde{H}_{0}(t)$ denote the annealing
Hamiltonian obtained by flipping the sign of $J_{\mathcal{N}}$. Upon taking
the Jordan-Wigner transformation (c.f. Eq. (8)), we then have the following
relations:

$H^{\pm}_{0}(t)=\widetilde{H}^{\mp}_{0}(t)\ .$ (39)

These relations are completely general and hold for any quantum spin glass on
a 2-regular graph. Crucially, if $H_{0}$ is frustrated, $\widetilde{H}_{0}$
lacks frustration, and thus perhaps easier to characterize. For the Frustrated
Ring, we can use the above relation to obtain a complete solution to the
incoherent tunneling rates (c.f. Eqs. (25-28)) in the large-$\mathcal{N}$
limit.

Indeed, in Appendix B, we derive the following crucial identities relating
low-lying eigenstates of the Frustrated Ring spin glass benchmark with those
of its ferromagnetic counterpart $\widetilde{H}$:

$\displaystyle\langle\Psi_{R,L}^{+}|\sigma^{z}_{j}|\Psi_{R,L}^{-}\rangle$
$\displaystyle=-\langle\widetilde{\Psi}_{R,L}^{-}|\sigma^{z}_{j}|\widetilde{\Psi}_{R,L}^{+}\rangle+\mathcal{O}(e^{-\kappa_{R}|j-j_{R}|})\
,$ (40)

here, $j_{R}$ is the position of the antiferromagnetic coupler $J_{R}$, and
$\kappa_{R}$ is the wavenumber of the boundstate $\hat{c}_{R}^{\dagger}$. Note
that these errors are localized at the position of the $J_{R}$-coupler, and
thus do not grow if we sum over all qubits in the graph.

To summarize, by the replacements
$\mbox{$|\Psi_{L,R}^{\pm}\rangle$}\to\mbox{$|\widetilde{\Psi}_{L,R}^{\pm}\rangle$}$,
we can relate our frustrated tunneling form factors to those in an
unfrustrated spin system $\widetilde{H}$ (c.f. Eq. 39), at the cost of
inducing an error which does not grow with the total number of qubits
$\mathcal{N}$. We thus have

$\displaystyle O_{0^{+}\to R^{-}}$
$\displaystyle\underset{\mathcal{N}\to\infty}{\sim}\sum_{j}\sin^{2}\theta_{LZ}|\langle\widetilde{\Psi}_{R}^{+}|\sigma^{z}_{j}|\widetilde{\Psi}_{R}^{-}\rangle|^{2},$
(41) $\displaystyle O_{0^{+}\to L^{-}}$
$\displaystyle\underset{\mathcal{N}\to\infty}{\sim}\sum_{j}\cos^{2}\theta_{LZ}|\langle\widetilde{\Psi}_{L}^{+}|\sigma^{z}_{j}|\widetilde{\Psi}_{L}^{-}\rangle|^{2},$
(42)

with analogous expressions for $O_{1^{+}\to R^{-},L^{-}}$. Note that the above
asymptotics are not valid unless the expressions in Eqs. (41-42) are
asymptotically greater than $\mathcal{O}(1)$; we will find that this is the
case (c.f. Eqs. (46-47)), so that our calculation is self-consistent. The
frustration-free version ($\widetilde{H}_{0}$) of our problem is much easier
to solve: in particular, any frustration-free spin system is gauge-equivalent
to a ferromagnet via a local $\mathbb{Z}_{2}$ gauge-transformation of the form

$\displaystyle\hat{U}(g)\equiv\prod_{j}(\sigma^{x}_{j})^{g_{j}},$ (43)

with $g_{j}\in\\{0,1\\}$. In fact, we find that the matrix elements in Eqs.
(41-42) are related to the spontaneous magnetization of the ferromagnetic spin
chain $\widetilde{H}$. Indeed, at $B=0$, we have

$\displaystyle\mbox{$\langle\widetilde{\Psi}_{R}^{+}|$}\hat{\sigma}^{z}_{j}\mbox{$|\widetilde{\Psi}_{R}^{-}\rangle$}$
$\displaystyle=$ $\displaystyle 1\ ,$ (44)
$\displaystyle\mbox{$\langle\widetilde{\Psi}_{L}^{+}|$}\hat{\sigma}^{z}_{j}\mbox{$|\widetilde{\Psi}_{L}^{-}\rangle$}$
$\displaystyle\sim$ $\displaystyle\text{sgn}(j)\ .$ (45)

Therefore, at zero transverse field, the above matrix elements have the
physical meaning of being the local magnetization of each state (in Eqs.
(44-45), we have implicitly re-indexed the qubits from
$j=-n,\cdots,0,\cdots,n$, where $\mathcal{N}=2n+1$). Exact analytical
expressions for the matrix elements in Eqs. (44-45) in the more general case
$B>0$ can be obtained by performing a field-theoretic calculation in the
corresponding two-dimensional classical Ising model (see Appendix B). There,
we find that the absolute values of the magnetizations in Eqs. (44-45)
approach the bulk value $M\equiv(1-(B/J)^{2})^{1/8}$. Note that $M$ is equal
to the bulk spontaneous magnetization of a quantum Ising chain with uniform
ferromagnetic coupling $J$ Iorgov (2011). A transfer matrix argument in
Appendix B is used to show that this convergence is exponentially fast in the
distance from the $J_{L},J_{R}$ defects. We confirm this prediction with exact
diagonalization for $\mathcal{N}$ up to $23$ sites, see Fig. 9.

As a result, the multiqubit tunneling rates at the spin glass bottleneck have
the following large-$\mathcal{N}$ asymptotic form:

$\displaystyle\Gamma_{0^{+}\to L^{-}}$
$\displaystyle\underset{\mathcal{N}\to\infty}{\sim}$ $\displaystyle
S(\omega_{0^{+}\to
L^{-}})\frac{\mathcal{N}M^{2}}{2\hbar^{2}}\cos^{2}\theta_{LZ}\ ,$ (46)
$\displaystyle\Gamma_{0^{+}\to R^{-}}$
$\displaystyle\underset{\mathcal{N}\to\infty}{\sim}$ $\displaystyle
S(\omega_{0^{+}\to
R^{-}})\frac{\mathcal{N}M^{2}}{2\hbar^{2}}\sin^{2}\theta_{LZ}\ ,$ (47)

which is $\mathcal{O}(\mathcal{N})$, with similar expressions for
$\Gamma_{1^{+}\to L^{-},R^{-}}$. Again, $M\equiv(1-(B_{b}/J)^{2})^{1/8}$, the
bulk value of the spontaneous magnetization of the one-dimensional transverse-
field Ising model, sets the coefficent of scaling. The above expressions are
in excellent agreement with exact-diagonalization for $\mathcal{N}$ up to $23$
sites, as shown in Fig. 10.

The physical implications of Eqs. (46-47) above are clear: in the Landau-Zener
formalism, at $t=-\infty$, $(\sin\theta,\cos\theta)=(0,1)$, and then, at
$t=\infty$, we have that $(\sin\theta,\cos\theta)=(1,0)$. Therefore, at
$t=\pm\infty$, the transition rate is predominantly the exponentially-small
$\mbox{$|\Psi_{L}\rangle$}\to\mbox{$|\Psi_{R}\rangle$}$ cross-terms (which
were neglected in deriving (46-47)), and the approximation breaks down.
However, at the bottleneck $t\sim 0$, the transition rate quickly reaches a
peak which is asymptotic to $\mathcal{N}M^{2}/2$, times the noise-spectral
density evaluated at the minimum gap frequency.

Figure 10: Analytical description of a spin glass bottleneck of quantum
annealing. Very close to the bottleneck, the multiqubit tunneling rate
$\Gamma_{0\to 2}=\theta(B_{b}-B)\Gamma_{0^{+}\to
L^{-}}+\theta(B-B_{b})\Gamma_{0^{+}\to R^{-}}$ (black) is given exactly by the
analytical expression (46-47) (red). We utilize this analytical understanding
to probe the dynamics of a finite-temperature anneal through this region.

##  IV Large-$\mathcal{N}$ limit of quantum annealing through the bottleneck
at finite-temperature

The simple analytical formulae (46-47) demonstrate the existence of a linear
$\mathcal{O}(\mathcal{N})$ tunneling peak near a quantum annealing bottleneck,
and establish the relation of the scaling coefficient to a suitably defined
bulk spontaneous magnetization, $M$, in our spin glass benchmark. Using these
asymptotics, we can rigorously analyze the effects of flux-bias noise on a
quantum annealing chip at a spin glass bottleneck, in the limit that the
number of qubits tends to infinity.

Assuming that the annealing processor is fully incoherent, the density matrix
$\rho$ of the system is diagonal in the eigenbasis
$\\{\mbox{$|\Psi_{0}^{+}\rangle$},\mbox{$|\Psi_{1}^{+}\rangle$},\mbox{$|\Psi_{R}^{-}\rangle$},\mbox{$|\Psi_{L}^{-}\rangle$}\\}$
of the coherent portion $\hat{H}_{0}$ of the quantum annealing Hamiltonian
(17):

$\begin{split}\hat{\rho}&=P_{0}^{+}\mbox{$|\Psi_{0}^{+}\rangle$}\mbox{$\langle\Psi_{0}^{+}|$}+P_{1}^{+}\mbox{$|\Psi_{1}^{+}\rangle$}\mbox{$\langle\Psi_{1}^{+}|$}\\\
&+P_{R}^{-}\mbox{$|\Psi_{R}^{-}\rangle$}\mbox{$\langle\Psi_{R}^{-}|$}+P_{L}^{-}\mbox{$|\Psi_{L}^{-}\rangle$}\mbox{$\langle\Psi_{L}^{-}|$}\
.\end{split}$ (48)

Under those assumptions, the density matrix satisfies incoherent time-
evolution in terms of rates of the form $\Gamma_{i\to j}$

$\begin{split}\partial_{t}P_{0}^{+}=&\Gamma_{L^{-}\to
0^{+}}P_{L}^{-}+\Gamma_{R^{-}\to 0^{+}}P_{R}^{-}\\\
&-\sum_{L^{-},R^{-}}\Gamma_{0^{+}\to R^{-},L^{-}}P_{0}^{+}\ ,\end{split}$ (49)

constituting a kinetic equation of Pauli type. Via Eqs. (46-47), the
multiqubit tunneling rates in the above equation can then be computed exactly
in the large-$\mathcal{N}$ limit, within a sufficient radius of the crossing
point such that the approximation (37-38) is valid. It is thus convenient to
define a tunneling region $t_{i}<t<t_{f}$ within which this assumption holds.
In this case, the instantaneous gap is much smaller than the temperature, and
the Ohmic noise spectral density $S(\omega)$ defined in (21) saturates at its
low-frequency value $S(\omega)\underset{\hbar\omega/k_{B}T\to
0}{\equiv}S^{(0)}$. Therefore, in the tunneling region $t_{i}<t<t_{f}$, the
incoherent master equation Eq. (49) takes the rather symmetric form

$\displaystyle\frac{\partial P_{0}^{+}}{\partial
t}\underset{\mathcal{N}\to\infty}{\sim}\frac{S^{(0)}\mathcal{N}M^{2}}{2\hbar^{2}}(P_{L}^{-}\cos^{2}\theta_{LZ}+P_{R}^{-}\sin^{2}\theta_{LZ}-P_{0}^{+})\
,$ $\displaystyle\frac{\partial P_{1}^{+}}{\partial
t}\underset{\mathcal{N}\to\infty}{\sim}\frac{S^{(0)}\mathcal{N}M^{2}}{2\hbar^{2}}(P_{L}^{-}\sin^{2}\theta_{LZ}+P_{R}^{-}\cos^{2}\theta_{LZ}-P_{1}^{+})\
,$ $\displaystyle\frac{\partial P_{R}^{-}}{\partial
t}\underset{\mathcal{N}\to\infty}{\sim}\frac{S^{(0)}\mathcal{N}M^{2}}{2\hbar^{2}}(P_{0}^{+}\sin^{2}\theta_{LZ}+P_{1}^{+}\cos^{2}\theta_{LZ}-P_{R}^{-})\
,$ $\displaystyle\frac{\partial P_{L}^{-}}{\partial
t}\underset{\mathcal{N}\to\infty}{\sim}\frac{S^{(0)}\mathcal{N}M^{2}}{2\hbar^{2}}(P_{0}^{+}\cos^{2}\theta_{LZ}+P_{1}^{+}\sin^{2}\theta_{LZ}-P_{L}^{-}).\
$ (50)

The above master equation represents the open-system dynamics of a fully
incoherent quantum annealing processor at the spin glass bottleneck, in the
limit $\mathcal{N}\to\infty$. We can vectorize the density matrix populations
by defining $\mathbb{P}\equiv[P_{0}^{+},P_{1}^{+},P_{R}^{-},P_{L}^{-}]^{T}$.
The kinetic equation (50) then takes the following matrix form:

$\displaystyle\frac{\partial\mathbb{P}}{\partial
t}=\frac{S^{(0)}\mathcal{N}M^{2}}{2\hbar^{2}}\left(\hat{\tau}^{x}_{1}\left(\sin^{2}\theta_{LZ}+\hat{\tau}^{x}_{2}\cos^{2}\theta_{LZ}\right)-1_{4\times
4}\right)\mathbb{P}\ .$ (51)

where here, we have introduced a pseudospin

$\displaystyle\hat{\tau}^{x}_{1}$ $\displaystyle\equiv\begin{pmatrix}0&1\\\
1&0\end{pmatrix}\otimes 1_{2\times 2},$ (52) $\displaystyle\hat{\tau}^{x}_{2}$
$\displaystyle\equiv 1_{2\times 2}\otimes\begin{pmatrix}0&1\\\
1&0\end{pmatrix}.$ (53)

Figure 11: Freezing of annealing dynamics after a spin glass bottleneck. The
plots show ground state population $P_{\textrm{GS}}\equiv P_{0}^{+}+P_{R}^{-}$
as a function of dimensionless annealing parameter $s=t/t_{\text{QA}}$ for two
temperatures of the annealing chip, $T=15.5$ mK in panel (a) and $T=1.55$ mK
in panel (b). At typical operating temperatures of the D-Wave 2X, both $P_{L}$
and $P_{R}$ are nontrivial (c.f. Frustrated Ring depicted in panel (a)) but at
low-temperatures, $P_{R}$ is negligible (c.f. Frustrated Ring depicted in
panel (b)). In both regimes however, we note that nontrivial population
transfer occurs directly at the bottleneck and then stops completely, making
bottleneck physics particularly relevant to the performance of the quantum
annealer. In the simulations, we considered an $\mathcal{N}=8$ Frustrated Ring
defined by $(J_{R},J_{L},J)=(0.2,0.24,1)$ and assumed annealing time
$t_{\text{QA}}=5~{}\mu$s. The insets show $t_{\text{QA}}\Gamma_{0\to 2}$ (c.f.
Eqs. (46-47)) as a function of $s$.

The matrix representation Eq. (51) manifestly diagonalizes the Liouvillian for
the effective classical master equation (49), allowing us to solve for the
density matrix at all times. We begin by defining (anti-)symmetric
combinations of the populations via

$\displaystyle
P_{\tau_{1}\tau_{2}}\equiv(P_{0}^{+}+\tau_{2}P_{1}^{+})+\tau_{1}(P_{R}^{-}+\tau_{2}P_{L}^{-}).$
(54)

Equivalently, $P_{\tau_{1}\tau_{2}}$ represents the projection of the
vectorized density matrix $\mathbb{P}$ onto an arbitrary eigenspace of the
time-dependent Liouvillian (51), with $\tau_{1},\tau_{2}\in\\{+1,-1\\}$
denoting the eigenvalues under application of $\tau_{1}^{x},\tau_{2}^{x}$,
respectively. In this eigenbasis, the ground state population upon exiting the
crossing is given by

$P_{GS}(t_{f})\equiv(P_{R}^{-}+P_{0}^{+})\Bigr{|}_{t=t_{f}}=\frac{1}{2}(1+P_{+-}(t_{f}))\
.$ (55)

The ground state population (55) upon exiting the crossing can be computed
analytically with arbitrary initial conditions. In particular, defining an
effective rate $\Gamma_{\text{eff}}(t)\equiv
S^{(0)}M^{2}\cos^{2}\theta_{LZ}(B(t))/2\hbar^{2}$ which sets the timescale of
the multiqubit dynamics, we then have

$\displaystyle P_{GS}(t_{f})$
$\displaystyle\underset{\mathcal{N}\to\infty}{\sim}\frac{1}{2}\left(1+e^{-2\mathcal{N}\int_{t_{i}}^{t_{f}}\Gamma_{\text{eff}}(t)\,dt}P_{+-}(t_{i})\right)\
.$ (56)

Since this prediction only gives the ground-state population upon exiting the
bottleneck region, the above analytical formula is relevant provided that
$P_{GS}(t=t_{f})=P_{GS}(t=t_{QA})\equiv P$ (c.f. Eq. (22)). This is the case,
e.g. if the density matrix stops evolving non-trivially after the bottleneck
(so-called freeze-out, see e.g. Marshall  _et al._ (2017); Amin (2015);
Johnson  _et al._ (2011)). Crucially, we witness this stoppage of evolution in
numerical simulations of the Redfield master equation in the range $1.55-15.5$
mK, as shown Fig. 11. As we can see, up to $\mathcal{N}=10$ (the performance
limit of our simulations), population transfer is nontrivial and limits the
performance of the quantum annealer.

We now focus on a specific set of initial conditions, supposing that the four
populations in the density matrix are pairwise thermalized. Before the
crossing point, we have $E_{L}^{-}-E_{0}^{+}\ll 1$ and $E_{R}^{-}-E_{1}\ll 1$.
Also, the rates in the annealing process are larger earlier in the annealing
(due to larger transverse-field $B$). It is thus reasonable to assume that,
entering the crossing (i.e. at $t=t_{i}$), the density matrix populations
satisfy

$P_{L}^{-}-P_{0}^{+}\ll 1,\quad P_{R}^{-}-P_{1}^{+}\ll 1.$ (57)

Since the levels in each pair correspond to states with the fermionic
excitation localized at the same location, this is a reasonable assumption to
make. In this limit, $P_{+,-}(t_{i})\to 0$, and so the success probability
(56) is asymptotic to one half.

##  V Discussion

In this paper we proposed and analytically solved a model that exhibits the
effects of frustration on bottlenecks of quantum annealing. By investigating a
simple class of one-dimensional annealing bottlenecks, we are able to
rigorously extract the scaling of tunneling rates caused by longitudinal qubit
noise, in the large-$\mathcal{N}$ (i.e. complexity-theoretic) limit. In
conclusion, in our model, we have found that the effective noise spectral
density at an annealing bottleneck is $\mathcal{O}(\mathcal{N})$, which is of
the order of the Hamming distance between the crossing states. This exact
result provides analytical confirmation of and is in agreement with results
obtained in Boixo  _et al._ (2016); Amin  _et al._ (2009). Furthermore, in
spite of the non-integrability of the flux bias noise (c.f. (32)), by treating
the transverse-field $B$ at the non-perturbative level, we were able to
extract the scaling coefficient accurate to all orders in the transverse-field
and elucidate its relation to spontaneous magnetization. Finally, we have
confirmed using Redfield-type simulations that the ground-state occupation
$P_{GS}$ upon exiting a spin glass bottleneck is especially pertinent for the
performance of a quantum annealer, and so we have identified a range of
temperatures where our analytical scaling formula should directly predict the
annealing performance, in the limit of completely incoherent system dynamics.
In the future, we will investigate the effects of including coherences, i.e.
off-diagonal elements of the density matrix, on the open-system dynamics. This
will allow us to gain more nuanced insight into the scaling performance of
combinatorial optimization and sampling problems on near-term quantum
annealers.

###### Acknowledgements.

This work was initiated at NASA QuAIL in 2016 under the USRA Quantum Academy
program, and was also supported in part by the U.S. Department of Energy and
in part by ASC Beyond Moore’s Law project. LC was supported by the DOE through
the J. Robert Oppenheimer fellowship. LC and AS also acknowledge support from
the LDRD program at LANL. DR would like to thank Barry M. McCoy for a
productive discussion.

## References

  * Boixo  _et al._ (2014) S. Boixo, T. F. Ronnow, S. V. Isakov, Z. Wang, and D. et. al. Wecker, “Evidence for quantum annealing with more than one hundred qubits,” Nature Physics 10, 218–224 (2014).
  * King  _et al._ (2018) A. D. King, J. Carrasquilla, J. Raymond, I. Ozfidan, and E. et. al. Andriyash, “Observation of topological phenomena in a programmable lattice of 1,800 qubits,” Nature 560, 456–460 (2018).
  * Venturelli and Kondratyev (2019) D. Venturelli and A. Kondratyev, “Reverse quantum annealing approach to portfolio optimization problems,” Quantum Machine Intelligence 1, 17–30 (2019).
  * Venturelli  _et al._ (2018) D. Venturelli, M. Do, E. Rieffel, and J. Frank, “Compiling quantum circuits to realistic hardware architectures using temporal planners,” Quantum Science and Technology 3, 025004 (2018).
  * Neukart  _et al._ (2017) F. Neukart, G. Compostella, C. Seidel, D. von Dollen, and S. et. al. Yarkoni, “Traffic Flow Optimization Using a Quantum Annealer,” Frontiers in ICT 4 (2017), 10.3389/fict.2017.00029.
  * Rosenberg  _et al._ (2016) G. Rosenberg, P. Haghnegahdar, P. Goddard, P. Carr, and K. et. al. Wu, “Solving the Optimal Trading Trajectory Problem Using a Quantum Annealer,” IEEE Journal of Selected Topics in Signal Processing 10, 1053–1060 (2016).
  * Rieffel  _et al._ (2015) E. G. Rieffel, D. Venturelli, B. O’Gorman, M. B. Do, and E. M. et. al. Prystay, “A case study in programming a quantum annealer for hard operational planning problems,” Quantum Information Processing 14, 1–36 (2015).
  * Knysh (2015) S. Knysh, “Computational Bottlenecks of Quantum Annealing,” arXiv:1506.08608 (2015).
  * Young  _et al._ (2010) A. P. Young, S. Knysh, and V. N. Smelyanskiy, “First-Order Phase Transition in the Quantum Adiabatic Algorithm,” Physiccal Review Letters 104, 020502 (2010).
  * Morita and Nishimori (2006) S. Morita and H. Nishimori, “Convergence theorems for quantum annealing,” Journal of Physics A Mathematical General 39, 13903–13920 (2006).
  * Santoro  _et al._ (2002) G. E. Santoro, R. Martonak, E. Tosatti, and R. Car, “Theory of Quantum Annealing of an Ising Spin Glass,” Science 295, 2427–2430 (2002).
  * Lanting  _et al._ (2017) T. Lanting, A. D. King, B. Evert, and E. Hoskinson, “Experimental demonstration of perturbative anticrossing mitigation using nonuniform driver Hamiltonians,” Physical Review A 96, 042322 (2017).
  * King  _et al._ (2016) A. D. King, E. Hoskinson, T. Lanting, E. Andriyash, and M. H. Amin, “Degeneracy, degree, and heavy tails in quantum annealing,” Physical Review A 93, 052320 (2016).
  * Steiger  _et al._ (2015) D. S. Steiger, T. F. Ronnow, and M. Troyer, “Heavy Tails in the Distribution of Time to Solution for Classical and Quantum Annealing,” Physical Review Letters 115, 230501 (2015).
  * Dickson  _et al._ (2013) N. G. Dickson, M. W. Johnson, M. H. Amin, R. Harris, and F. et. al. Altomare, “Thermally assisted quantum annealing of a 16-qubit problem,” Nature Communications 4, 1903 (2013).
  * Altshuler  _et al._ (2010) B. Altshuler, H. Krovi, and J. Roland, “Anderson localization makes adiabatic quantum optimization fail,” Proceedings of the National Academy of Sciences 107, 12446–12450 (2010).
  * Keck  _et al._ (2017) M. Keck, S. Montangero, G. E. Santoro, R. Fazio, and D. Rossini, “Dissipation in adiabatic quantum computers: lessons from an exactly solvable model,” New Journal of Physics 19, 113029 (2017).
  * Deng  _et al._ (2013) Q. Deng, D. V. Averin, M. H. Amin, and P. Smith, “Decoherence induced deformation of the ground state in adiabatic quantum computation,” Scientific Reports 3, 1479 (2013).
  * Boixo  _et al._ (2016) S. Boixo, V. N. Smelyanskiy, A. Shabani, S. V. Isakov, M. Dykman, and others, “Computational multiqubit tunnelling in programmable quantum annealers,” Nature communications 7, 10327 (2016).
  * Amin  _et al._ (2009) M. H. S. Amin, C. J. S. Truncik, and D. V. Averin, “Role of single-qubit decoherence time in adiabatic quantum computation,” Physical Review A 80, 022303 (2009).
  * Lieb  _et al._ (1961) E. Lieb, T. Schultz, and D. Mattis, “Two soluble models of an antiferromagnetic chain,” Annals of Physics 16, 407–466 (1961).
  * Dziarmaga (2005) J. Dziarmaga, “Dynamics of a Quantum Phase Transition: Exact Solution of the Quantum Ising Model,” Physical Review Letters 95, 245701 (2005).
  * Bravyi  _et al._ (2010) Sergey Bravyi, Matthew B. Hastings, and Spyridon Michalakis, “Topological quantum order: Stability under local perturbations,” Journal of Mathematical Physics 51, 093512 (2010), https://doi.org/10.1063/1.3490195 .
  * Chen  _et al._ (2010) X. Chen, Z. C. Gu, and X. G. Wen, “Local unitary transformation, long-range quantum entanglement, wave function renormalization, and topological order,” Physical Review B 82, 155138 (2010).
  * Iorgov (2011) Nikolai Iorgov, “Form factors of the finite quantumXY-chain,” Journal of Physics A: Mathematical and Theoretical 44, 335005 (2011).
  * Marshall  _et al._ (2017) J. Marshall, E. G. Rieffel, and I. Hen, “Thermalization, Freeze-out, and Noise: Deciphering Experimental Quantum Annealers,” Physical Review Applied 8, 064025 (2017).
  * Amin (2015) M. H. Amin, “Searching for quantum speedup in quasistatic quantum annealers,” Physical Review A 92, 052323 (2015).
  * Johnson  _et al._ (2011) M. W. Johnson, M. H. S. Amin, S. Gildert, T. Lanting, and F. et. al. Hamze, “Quantum annealing with manufactured spins,” Nature 473, 194–198 (2011).
  * Palmer (2007) J. Palmer, “The Thermodynamic Limit,” in  _Planar Ising Correlations_, Progress in Mathematical Physics, edited by J. Palmer (Birkhauser Boston, Boston, MA, 2007) pp. 1–61.
  * Sachdev (2000) S. Sachdev, “Quantum Phase Transitions,”  (2000).
  * Costello (2011) K. Costello,  _Renormalization and effective field theory_ , 170 (American Mathematical Soc., 2011).
  * Schultz  _et al._ (1964) T. Schultz, D. Mattis, and E. Lieb, “Two-Dimensional Ising Model as a Soluble Problem of Many Fermions,” Reviews of Modern Physics 36, 856–871 (1964).
  * Yang (1952) C. N. Yang, “The Spontaneous Magnetization of a Two-Dimensional Ising Model,” Physical Review 85, 808–816 (1952).

##  Appendix A Exact diagonalization of the Frustrated Ring

In this Appendix we systematically and rigorously solve for the bound states
of the Frustrated Ring, deriving their crossing properties and quantum
numbers. Our starting point is the free-fermion representation of the one-
dimensional transverse-field Ising spin glass:

$\hat{H}_{0}^{\pm}(t)=-i\sum_{j=1}^{\mathcal{N}}J_{j}^{\pm}\,\hat{\gamma}_{2j}\hat{\gamma}_{2j+1}+iB(t)\sum_{j=1}^{\mathcal{N}}\hat{\gamma}_{2j-1}\hat{\gamma}_{2j}\
,$ (58)

where $J^{\pm}_{j}\equiv J_{j}$ for $j\neq\mathcal{N}$ and
$J_{\mathcal{N}}^{\pm}\equiv\pm J_{\mathcal{N}}$. $\hat{H}^{\pm}_{0}(t)$
denotes the quantum annealing Hamiltonian restricted to the sector with an
even and odd number of fermions respectively. Note that the representation
(58) of the Frustrated Ring as a pair of free fermion models is a two-fold
redundant description, with each free fermion theory being valid only in its
corresponding parity sector (the sector with an even number of fermions is
called the Ramond sector, and the sector with an odd number is called the
Neveu-Schwarz sector).

The vector space of all quadratic polynomials in Majorana fermions, i.e. all
expressions of the form

$\displaystyle\hat{H}=\sum_{1\leq i<j\leq
2\mathcal{N}}\lambda_{ij}\hat{\gamma}_{i}\hat{\gamma}_{j},$ (59)

form a closed Lie algebra isomorphic to $\mathfrak{spin}_{2\mathcal{N}}$, i.e.
the Lie algebra of the Spin group $\text{Spin}(2\mathcal{N})$. It is well-
known that this Lie algebra is isomorphic to $\mathfrak{so}_{2\mathcal{N}}$,
i.e. the Lie algebra of real, $2\mathcal{N}\times 2\mathcal{N}$ antisymmetric
matrices. The isomorphism is given by

$\displaystyle\hat{H}=\sum_{1\leq i<j\leq
2\mathcal{N}}\lambda_{ij}\hat{\gamma}_{i}\hat{\gamma}_{j}~{}\mapsto~{}\mathbb{H}_{\text{BdG}}\equiv\begin{pmatrix}&\lambda_{ij}\\\
-\lambda_{ij}&\end{pmatrix}.$ (60)

This maps a free-fermion model to its corresponding Bogoliubov de-Gennes (BdG)
Hamiltonian. The Bogoliubov de-Gennes Hamiltonian is a much more lucid
representation of a free-fermion model, because the physical data of interest,
namely, the quasiparticle operators expressed in the Majorana basis, are given
by the eigenvectors of this matrix, and the quasiparticle dispersion
corresponds to the eigenvalues. The BdG representation of the one-dimensional
transverse-field Ising spin glass is

$\displaystyle\mathbb{H}_{\text{BdG}}^{\pm}$
$\displaystyle=\begin{pmatrix}0&B(t)&&&&\pm J_{\mathcal{N}}\\\
-B(t)&0&J_{1}&&&\\\ &-J_{1}&&\ddots&\\\ &&\ddots&&J_{\mathcal{N}-1}&\\\
&&&-J_{\mathcal{N}-1}&0&B(t)\\\ \mp J_{\mathcal{N}}&&&&-B(t)&0\end{pmatrix}$
(61)

In the particular case of the Frustrated Ring, after a change-of-basis

$\hat{\Gamma}_{2j}\equiv
i\hat{\gamma}_{2j},\quad\hat{\Gamma}_{2j-1}\equiv\hat{\gamma}_{2j-1}\ ,$ (62)

the matrices specified by (61) admit a $\mathbb{Z}_{2}$ symmetry. It reverses
the order of the basis elements, corresponding to the reflection symmetry of
the Frustrated Ring ($J_{j}\to J_{\mathcal{N}-(j-1)}$). As is standard, the
symmetry splits our eigenvalue problem into two subspaces, indexed by the
eigenvalue under reversion (which we denote by $\mu$). The symmetric subspace
(i.e. $\mu=1$) is $\mathcal{N}$-dimensional, with basis

$\displaystyle\hat{\Gamma}_{j}^{+}$
$\displaystyle\equiv\hat{\Gamma}_{j}+\hat{\Gamma}_{2\mathcal{N}-(j-1)}\ ,$
(63)

whereas the antisymmetric subspace (i.e. $\mu=-1$) is also
$\mathcal{N}$-dimensional, with basis

$\displaystyle\hat{\Gamma}_{j}^{-}$
$\displaystyle\equiv\hat{\Gamma}_{j}-\hat{\Gamma}_{2\mathcal{N}-(j-1)}.$ (64)

Under this splitting, the pair of BdG Hamiltonians (61) take the block-
diagonal form

$\mathbb{H}_{\text{BdG}}^{\sigma}\sim\begin{pmatrix}\mathbb{H}_{\text{BdG}}^{\sigma,+}&\mathbb{0}_{\mathcal{N}\times\mathcal{N}}\\\
\mathbb{0}_{\mathcal{N}\times\mathcal{N}}&\mathbb{H}_{\text{BdG}}^{\sigma,-}\end{pmatrix}\
,$ (65)

where

$\mathbb{H}_{\text{BdG}}^{\sigma,\mu}=\begin{pmatrix}-\sigma\mu
J_{R}&B(t)&&&\\\ B(t)&0&-J&&\\\ &-J&&\ddots&\\\ &&\ddots&0&-J_{L}\\\
&&&-J_{L}&\mu B(t)\end{pmatrix}\ .$ (66)

Where, here, $\sigma=\pm 1$ denotes fermion parity. As outlined in the main
body of the text, we now find exact low-energy solutions to the BdG equations
in the limit $\mathcal{N}\to\infty$. In this limit, we can treat the BdG
boundstate problem as a pair of semi-infinite bound state problems,

$\displaystyle\mathbb{H}^{\sigma,\mu}_{\text{BdG}}\psi_{\sigma,\mu}=\epsilon_{\sigma,\mu}\psi_{\sigma,\mu}.$
(67)

The first such problem looks for a boundstate localized at the right end of
the graph:

$\displaystyle\psi^{R}_{\sigma\mu}$
$\displaystyle\equiv\begin{pmatrix}\alpha_{\sigma\mu}\\\ \beta_{\sigma\mu}\\\
e^{-\kappa_{\sigma\mu}}\alpha_{\sigma\mu}\\\
e^{-\kappa_{\sigma\mu}}\beta_{\sigma\mu}\\\
e^{-2\kappa_{\sigma\mu}}\alpha_{\sigma\mu}\\\
e^{-2\kappa_{\sigma\mu}}\beta_{\sigma\mu}\\\ \vdots\end{pmatrix}\ ,$ (68)

where here, $\alpha_{\sigma\mu},\beta_{\sigma\mu}$ are written so that it is
clear that they only depend on $\sigma$ and $\mu$ through their product. This
is because, in the limit $\mathcal{N}\to\infty$, the decay of the mode (68)
means that the matrix element $\mu B(t)$ in the bottom-right corner of (66)
does not enter the eigenvalue problem (67). Similarly, we can solve the left-
localized eigenvalue problem:

$\displaystyle\psi^{L}_{\mu}$
$\displaystyle\equiv\begin{pmatrix}\alpha_{\mu}\\\ \beta_{\mu}\\\
e^{+\kappa_{\mu}}\alpha_{\mu}\\\ e^{+\kappa_{\mu}}\beta_{\mu}\\\
e^{+2\kappa_{\mu}}\alpha_{\mu}\\\ e^{+2\kappa_{\mu}}\beta_{\mu}\\\
\vdots\end{pmatrix}.$ (69)

Again, here, $\alpha_{\mu},\beta_{\mu}$ are written so that it is clear that
they are independent of $\sigma$. This is because, in the limit
$\mathcal{N}\to\infty$, the decay of the mode (69) means that the only matrix
element containing $\sigma$ (the matrix element in the upper-left corner of
(66)) does not enter the eigenvalue problem (67).

Substituting the ansätze (68-69) into the eigenvalue problem (67), and letting

$e^{-\lambda}\equiv\alpha/\beta$

parametrize the ratio of $\alpha$ to $\beta$, we get two main types of
equations: bulk conditions, and boundary conditions. The equations in the bulk
give

$\displaystyle\epsilon$ $\displaystyle=e^{-\lambda}(B-Je^{+\kappa}),\ ,$ (70)
$\displaystyle\epsilon$ $\displaystyle=e^{+\lambda}(B-Je^{-\kappa})\ .$ (71)

From Eqs. (70-71), we get the dispersion relation, as well as (after some
hyperbolic trigonometry) some useful bulk identities involving $\lambda$:

$\displaystyle\epsilon^{2}$ $\displaystyle=J^{2}+B^{2}-2JB\cosh\kappa\ ,$ (72)
$\displaystyle B^{2}$
$\displaystyle=\epsilon^{2}+J^{2}-2J\epsilon\cosh(\lambda-\kappa)\ ,$ (73)
$\displaystyle\tanh\lambda=\frac{J\sinh\kappa}{J\cosh\kappa-B}\ .$ (74)

For the boundary conditions, we get different conditions at opposite ends (as
would be expected; c.f. (66)): for the right-localized boundstate ansätz (68),
the boundary conditions are

$Be^{\lambda}=\epsilon+\sigma\mu J_{R}\ ,$ (75)

whereas, for the left-localized boundstate ansätz (69), the boundary
conditions are

$Be^{-\lambda}=\epsilon-\frac{J_{L}^{2}}{\epsilon-\mu B}\ .$ (76)

The right-boundary condition (75) generically yields one solution,
$\psi^{R}_{\sigma\mu}$ for each value of the product $\sigma\mu$. When
$\sigma\mu=+1$, we denote this solution as $\psi^{R}_{+}$, and when
$\sigma\mu=-1$, we denote this solution as $\psi^{R}_{-}$. For $B\to 0$, these
solutions have the limiting form

$\displaystyle\psi^{R}_{\pm}\underset{B\to 0}{\sim}\begin{pmatrix}1\\\ 0\\\
0\\\ \vdots\end{pmatrix}\ .$ (77)

Similarly, the left-boundary condition (76) generically yields two solutions
for each value of $\mu$. For $B\to 0$, the solution whose eigenvalue is least
in magnitude limits to

$\displaystyle\psi^{L}_{\mu}\underset{B\to 0}{\sim}\begin{pmatrix}\vdots\\\
0\\\ 0\\\ 1\\\ \mu\end{pmatrix}\ ,$ (78)

whereas, for $B\to 0$, the solution whose eigenvalue is greatest in magnitude
limits to

$\displaystyle\psi^{L^{\prime}}_{\mu}\underset{B\to
0}{\sim}\begin{pmatrix}\vdots\\\ 0\\\ 0\\\ 1\\\ -\mu\end{pmatrix}\ .$ (79)

In summary, putting together both the left- and right-eigenvalue problems,
there are six subgap states in total for our spin glass benchmark.

To write down the quasiparticle/quasihole excitations corresponding to a given
boundstate, we simply contract the boundstate vector with the Gamma matrices.
This is succinctly captured by the Feynman slash notation, which is the
standard physics notation for such expressions:

$\displaystyle\not{\psi}\equiv\sum_{j=1}^{2\mathcal{N}}\psi_{j}\hat{\gamma}_{j}\
.$ (80)

with $\psi_{j}$ the components of the BdG eigenvector in the original basis
$\hat{\gamma}_{j}$ (c.f. (61)). Having enumerated the subgap states in
equations (77-79), we must now physically identify them as localized
excitations in our spin glass. To do this, we define

$\displaystyle\hat{H}^{\pm}_{0}\underset{B\to
0}{\sim}\sum_{j=1}^{\mathcal{N}}J^{\pm}_{j}\hat{c}_{j,\pm}^{\dagger}\hat{c}_{j,\pm}.$
(81)

Cross-matching with Eqs. (77-79), we get, in the $\mu=+1$ sector:

$\displaystyle\not{\psi}_{\pm}^{R}\underset{B\to
0}{\propto}\hat{c}_{2n+1,\pm}^{\dagger},$ (82)
$\displaystyle\not{\psi}_{+}^{L}\underset{B\to
0}{\propto}\hat{c}_{n,\pm}+\hat{c}_{n+1,\pm},$ (83)
$\displaystyle\not{\psi}_{+}^{L^{\prime}}\underset{B\to
0}{\propto}\hat{c}_{n,\pm}^{\dagger}-\hat{c}_{n+1,\pm}^{\dagger},$ (84)

where here, we have factored $\mathcal{N}\equiv 2n+1$. Similarly, in the
$\mu=-1$ sector, we get

$\displaystyle\not{\psi}_{\pm}^{R}\underset{B\to
0}{\propto}\hat{c}_{2n+1,\mp},$ (85)
$\displaystyle\not{\psi}_{-}^{L}\underset{B\to
0}{\propto}\hat{c}_{n,\pm}^{\dagger}+\hat{c}_{n+1,\pm}^{\dagger},$ (86)
$\displaystyle\not{\psi}_{-}^{L^{\prime}}\underset{B\to
0}{\propto}\hat{c}_{n,\pm}-\hat{c}_{n+1,\pm}.$ (87)

This concludes the main exposition of the boundstate problem for the
Frustrated Ring. In the following sections, we will apply this knowledge to
derive all identities used in the main text.

####  A.0.1 Definitions of spin-glass excitations used in the main text

Our analysis thus culminates in our first result, which is to give a precise
definition of the excitations used in the main text: the identities (82-87)
derived in the previous subsection physically motivate the following
definitions at $B=0$:

$\displaystyle c_{R,\pm}^{\dagger}|_{B=0}$
$\displaystyle\equiv\hat{c}_{2n+1,\pm}^{\dagger}\ ,$ (88) $\displaystyle
c_{L,\pm}^{\dagger}|_{B=0}$
$\displaystyle\equiv\hat{c}_{n,\pm}^{\dagger}+\hat{c}_{n+1,\pm}^{\dagger}\ ,$
(89) $\displaystyle c_{L^{\prime},\pm}^{\dagger}|_{B=0}$
$\displaystyle\equiv\hat{c}_{n,\pm}^{\dagger}-\hat{c}_{n+1,\pm}^{\dagger}\ .$
(90)

We can now use (82-87) to analytically continue the above definitions to non-
zero transverse-field $B\neq 0$, by simply tracking the BdG boundstates as
they evolve:

$\displaystyle\hat{c}_{R,\pm}^{\dagger}(B)$
$\displaystyle:=\sum_{j}(\psi^{R}_{+})_{j}\hat{\Gamma}_{j}^{\pm}\ ,$ (91)
$\displaystyle\hat{c}_{L,\pm}^{\dagger}(B)$
$\displaystyle:=\sum_{j}(\psi^{L}_{-})_{j}\hat{\Gamma}_{j}^{-}\ ,$ (92)
$\displaystyle\hat{c}_{L^{\prime},\pm}^{\dagger}(B)$
$\displaystyle:=\sum_{j}(\psi^{L^{\prime}}_{+})_{j}\hat{\Gamma}_{j}^{+}\ .$
(93)

Eqs. (91-93), along with the definition of the BdG eigenvectors (68-69), give
a mathematically precise notion of these excitations existing throughout the
spin glass phase $B<B_{c}$.

Armed with Eqs. (91-93), we can now prove that, in our spin glass benchmark,
the crossing in the odd-parity sector is exact, whereas the even-parity
crossing is not. It suffices to look at the positive-energy crossing, as
states with energies of opposite sign cannot cross in the spin glass phase
$B<B_{c}$ (by definition). For $\sigma=+1$, the only right-localized
boundstate with positive eigenvalue is the quasihole

$\displaystyle\hat{c}_{R,+}.$ (94)

By taking the adjoint of (91), we see that this excitation consists only of
$\mu=-1$ Gamma matrices, as (c.f. 62-64)

$\displaystyle(\hat{\Gamma}^{+}_{j})^{\dagger}$
$\displaystyle\propto\hat{\Gamma}_{j}^{-}\ .$ (95)

In contrast, for $\sigma=-1$, the only right-localized boundstate with
positive eigenvalue is the quasiparticle

$\displaystyle\hat{c}_{R,-}^{\dagger}.$ (96)

Again, the reversion quantum number for this boundstate satisfies $\mu=+1$,
which follows from direct inspection of (91). On the other hand, on the left-
hand-side of the graph, the positive-energy excitation

$\displaystyle\hat{c}_{L,\pm}^{\dagger}$ (97)

has reversion number $\mu=-1$ (c.f. (92)). Crucially, this quantum number is
insensitive to the value of $\sigma$, as $\sigma$ does not show up in the
left-boundary condition (c.f. (76)). In summary, therefore, when $\sigma=-1$,
the left- and right-boundstates with positive energy have differing reversion
quantum number $\mu$, and thus cannot hybridize. In contrast, when
$\sigma=+1$, the left- and right-boundstates with positive energy are both
antisymmetric ($\mu=-1$) under reversion, and can thus hybridize. The analysis
for the case of the negative energy crossing proceeds in the exact same
fashion.

####  A.0.2 Location of crossings, and scaling of the gap

We now derive the conditions for the existence of a spin glass bottleneck in
the Frustrated Ring annealing schedule, as well as compute its location
$B\equiv B_{b}$. Furthermore, we analytically calculate the scaling of the gap
at the bottleneck location. To obtain the crossing point of the left- and
right-bound state energies, we set them equal to each other, i.e.
$\epsilon_{\sigma\mu}^{R}=\epsilon^{L}_{\mu}\equiv\epsilon_{b}$. We will deal
with both crossings at the same time: from the discussion in the previous
paragraph, we have that the left-localized boundstate involved in the
positive-energy crossing has $\mu=-1$ for both the even and odd-crossing, so
the left-localized boundstate involved in the positive-energy crossing is
always

$\displaystyle\psi^{L}_{-}.$ (98)

For the right-localized boundstate involved in the positive-energy crossing,
from the discussion in the previous paragraph, the value of $\mu$ depends on
the fermion parity $\sigma$. However, we can compute the product
$\sigma\mu=-1$, which is the same in both cases. Therefore, the right-
localized boundstate involved in the positive-energy crossing is

$\displaystyle\psi^{R}_{-}.$ (99)

Furthermore, we note that these states have the same energy
$\epsilon\equiv\epsilon_{b}$, so by the dispersion relation (72), we have that
these crossing states have equal and opposite $\kappa\equiv\pm\kappa_{b}$.
Therefore, by (74), the states also have equal and opposite
$\lambda\equiv\pm\lambda_{b}$. Thus, at the crossing, these states therefore
satisfy the boundary conditions

$\displaystyle B_{b}e^{\lambda_{b}}$ $\displaystyle=\epsilon_{b}-J_{R}\ ,$
(100) $\displaystyle B_{b}e^{\lambda_{b}}$
$\displaystyle=\epsilon_{b}-\frac{J_{L}^{2}}{\epsilon_{b}+B_{b}}\ ,$ (101)

which yield the identity

$\displaystyle\epsilon_{b}+B_{b}=\frac{J_{L}^{2}}{J_{R}}.$ (102)

Combining this with one of the bulk equation (70) yields

$\displaystyle e^{\kappa_{b}-\lambda_{b}}$ $\displaystyle=\frac{J_{R}}{J}.$
(103)

Lastly, we can also consider using the bulk equation (73). The triplet of
equations (102), (103) and (73), considered together, yield the bottleneck
location, as well as the crossing energy (e.g., using Solve in Mathematica):

$\displaystyle B_{b}$
$\displaystyle=\frac{1}{J_{R}}\frac{(J^{2}-J_{L}^{2})(J_{L}^{2}-J_{R}^{2})}{J_{R}^{2}+J^{2}-2J^{2}_{L}},~{}~{}~{}\epsilon_{b}=\frac{1}{J_{R}}\frac{J_{R}^{2}J^{2}-J_{L}^{4}}{J_{R}^{2}+J^{2}-2J_{L}^{2}}.$
(104)

Note that $JJ_{R}>J_{L}^{2}$ is thus a necessary condition for the crossing
point to exist. Also, crucially, the bottleneck location is independent of
$\sigma$, and thus happens in the same location for both the even- and odd-
fermion sectors. Using expressions for $B_{b}$ and $\epsilon_{b}$ to solve for
$\cosh\kappa_{b}$, we obtain

$\kappa_{b}=\log\frac{J_{R}(J^{2}-J_{L}^{2})}{J(J_{L}^{2}-J_{R}^{2})}\ ,$
(105)

which determines the scaling of the hybridization of the boundstates,
$\Delta_{\text{min}}\sim\mathcal{O}(e^{-\kappa_{b}\mathcal{N}})$. The location
and the value of the gap can be tuned by adjusting the parameters of the
model.

##  Appendix B Field-theoretic calculation of the tunneling matrix elements

####  B.0.1 Relation to the corresponding ferromagnetic problem

We now turn to the relations used in the text, which transform a calculation
in a transverse-field Ising spin glass to one in a corresponding ferromagnetic
model $\widetilde{H}$. We then take advantage of this transformation to
calculate the tunneling rates exactly via the quantum-classical
correspondence. Indeed, recall that the transverse-field Ising chain maps to
two free fermion models $H^{\pm}$ (c.f. (58)) (Ramond/Neveu-Schwarz), leading
to an unphysical doubling of the number of eigenstates. In our calculations up
to this point, we have only considered the low-energy states

$|\Psi_{R}^{-}\rangle$
$\displaystyle=c_{R,-}^{\dagger}\mbox{$|\Omega_{-}\rangle$}\ ,\quad$
$|\Psi_{L}^{-}\rangle$
$\displaystyle=c_{L,-}^{\dagger}\mbox{$|\Omega_{-}\rangle$}\ ,$ (106)
$|\Psi_{R}^{+}\rangle$ $\displaystyle=\mbox{$|\Omega_{-}\rangle$}\ ,\quad$
$|\Psi_{L}^{+}\rangle$
$\displaystyle=c_{L,+}^{\dagger}c_{R,+}^{\dagger}\mbox{$|\Omega_{+}\rangle$}\
,$ (107)

and have implicitly discarded the low-energy states

$|\widetilde{\Psi}_{R}^{+}\rangle$
$\displaystyle\equiv\mbox{$|\Omega_{-}\rangle$}\ ,\quad$
$|\widetilde{\Psi}_{L}^{+}\rangle$ $\displaystyle\equiv
c_{R,-}^{\dagger}c_{L,-}^{\dagger}\mbox{$|\Omega_{-}\rangle$}\ ,$ (108)
$|\widetilde{\Psi}_{R}^{-}\rangle$ $\displaystyle\equiv
c_{R,+}^{\dagger}\mbox{$|\Omega_{+}\rangle$}\ ,\quad$
$|\widetilde{\Psi}_{L}^{-}\rangle$ $\displaystyle\equiv
c_{L,+}^{\dagger}\mbox{$|\Omega_{+}\rangle$}\ ,$ (109)

as they are not genuine eigenstates of the original spin chain Hamiltonian
(they have the wrong parity). However, utilizing the identity
$H^{\pm}=\widetilde{H}^{\mp}$ ($\widetilde{H}$ is the ferromagnetic
modification of the original spin glass Hamiltonian; see Eq. (39) in the main
text, c.f. Figure 12 for a depiction of this modification for the case of the
Frustrated Ring), we can reinterpret the unphysical states of $H$ as physical
states for $\widetilde{H}$:

$|\widetilde{\Psi}_{R}^{+}\rangle$
$\displaystyle=\mbox{$|\widetilde{\Omega}_{+}\rangle$}\ ,\quad$
$|\widetilde{\Psi}_{L}^{+}\rangle$
$\displaystyle=\widetilde{c}_{R,+}^{\dagger}\widetilde{c}_{L,-}^{\dagger}\mbox{$|\widetilde{\Omega}_{+}\rangle$}\
,$ (110) $|\widetilde{\Psi}_{R}^{-}\rangle$
$\displaystyle=\widetilde{c}_{R,-}^{\dagger}\mbox{$|\widetilde{\Omega}_{-}\rangle$}\
,\quad$ $|\widetilde{\Psi}_{L}^{-}\rangle$
$\displaystyle=\widetilde{c}_{L,-}^{\dagger}\mbox{$|\widetilde{\Omega}_{-}\rangle$}\
,$ (111)

with similar relations for the remaining (i.e. bulk) eigenstates. Therefore,
one can interpret the general situation in the following way: when one
diagonalizes $H^{+}$ and $H^{-}$ in (58), yielding two full sets of fermonic
Fock states, half unphysical, it is actually valid to say that one obtains two
full sets of physical spin chain eigenstates, one for the original spin chain,
and the remaining set corresponding to the eigenstates of its frustration-free
version.

Now, consider the central problem encountered in the main text, namely, that
of computing

$\displaystyle\mbox{$\langle\Psi_{R}^{+}|$}\sigma_{j}^{z}\mbox{$|\Psi_{R}^{-}\rangle$},~{}~{}~{}\mbox{$\langle\Psi_{L}^{+}|$}\sigma_{j}^{z}\mbox{$|\Psi_{L}^{-}\rangle$}.$
(112)

Naively, we can try to take advantage of the above observation and convert the
matrix elements in our glassy problem $H$ into matrix elements in our
ferromagnetic problem $\widetilde{H}$. Indeed, substituting, we get

$\displaystyle\mbox{$\langle\Psi_{R}^{+}|$}\sigma^{z}_{j}\mbox{$|\Psi_{R}^{-}\rangle$}$
$\displaystyle=\mbox{$\langle\Omega_{+}|$}\sigma^{z}_{j}c_{R,-}^{\dagger}\mbox{$|\Omega_{-}\rangle$}$
$\displaystyle=\mbox{$\langle\widetilde{\Omega}_{-}|$}\sigma^{z}_{j}\widetilde{c}_{R,+}\mbox{$|\widetilde{\Omega}_{+}\rangle$},$
(113)
$\displaystyle\mbox{$\langle\Psi_{L}^{+}|$}\sigma^{z}_{j}\mbox{$|\Psi_{L}^{-}\rangle$}$
$\displaystyle=\mbox{$\langle\Omega_{+}|$}c_{L,+}c_{R,+}\sigma^{z}_{j}c_{R,-}^{\dagger}\mbox{$|\Omega_{-}\rangle$}$
$\displaystyle=\mbox{$\langle\widetilde{\Omega}_{-}|$}\widetilde{c}_{L,-}\widetilde{c}_{R,-}\sigma^{z}_{j}\widetilde{c}_{R,+}^{\dagger}\mbox{$|\widetilde{\Omega}_{+}\rangle$}.$
(114)

Unfortunately, all of these matrix elements are between unphysical states,
suggesting that one must pass excitations across the $\sigma^{z}$ operator, to
amend the situation.

In general, since $\sigma^{z}$, when written-out in terms of
$\hat{\gamma}$-matrices, is an element of the Pin group
$\text{Pin}(2\mathcal{N})$ (see Palmer (2007) for a standard reference),
passing $\sigma^{z}$ past a fermionic excitation will rotate that excitation
by an orthogonal matrix Palmer (2007), producing a new fermionic excitation:

$\displaystyle\not{\psi^{\prime}}$
$\displaystyle\equiv\sigma^{z}_{j}\not{\psi}\sigma^{z}_{j}\ ,$ (115)

where

$\displaystyle\psi^{\prime}=R_{j}\psi\ ,$ (116)

with $R_{j}\in O(2N)$ a rotation matrix. Utilizing this fact, we have

$\displaystyle\mbox{$\langle\Psi_{R}^{+}|$}\sigma^{z}_{j}\mbox{$|\Psi_{R}^{-}\rangle$}$
$\displaystyle=\mbox{$\langle\Omega_{+}|$}\sigma^{z}_{j}c_{R,-}^{\dagger}\mbox{$|\Omega_{-}\rangle$}$
$\displaystyle=\mbox{$\langle\widetilde{\Omega}_{-}|$}R_{j}[c_{R,-}^{\dagger}]\sigma^{z}_{j}\mbox{$|\widetilde{\Omega}_{+}\rangle$},$
(117)
$\displaystyle\mbox{$\langle\Psi_{L}^{+}|$}\sigma^{z}_{j}\mbox{$|\Psi_{L}^{-}\rangle$}$
$\displaystyle=\mbox{$\langle\Omega_{+}|$}c_{L,+}c_{R,+}\sigma^{z}_{j}c_{L,-}^{\dagger}\mbox{$|\Omega_{-}\rangle$}$
$\displaystyle=\mbox{$\langle\widetilde{\Omega}_{-}|$}\widetilde{c}_{L,-}\sigma^{z}_{j}R_{j}[c_{R,+}]\widetilde{c}_{L,+}^{\dagger}\mbox{$|\widetilde{\Omega}_{+}\rangle$}\
$ (118)

where in deriving (118), we have utilized the fact that
$R_{j}^{2}=1_{2\mathcal{N}\times 2\mathcal{N}}$. Computing the rotation
$\mathcal{R}_{j}\in O(2\mathcal{N})$ implemented by $\sigma^{z}_{j}$ is
straightforward. In particular, by writing everything out in terms of
$\hat{\gamma}$ matrices, we find, that, for $i<2j-1<2\mathcal{N}-i$,

$\mathcal{R}_{j}(\hat{\Gamma}_{i}^{\mu})=-\hat{\Gamma}^{-\mu}_{i},\\\ $ (119)

i.e. $\mathcal{R}_{j}$ flips the reversion-symmetry quantum number. From this,
due to the localized nature of the $R$-bound states, we obtain our desired
result:

$\displaystyle\mathcal{R}_{j}(c_{R,\pm}^{\dagger})$
$\displaystyle=\mathcal{R}_{j}\bigg{(}\sum_{i}(\psi^{R}_{\pm})_{i}\hat{\Gamma}_{i}^{+}\bigg{)}$
$\displaystyle=-\sum_{i}(\psi^{R}_{\pm})_{i}\hat{\Gamma}_{i}^{-}+\mathcal{O}(e^{-\kappa
j})$ $\displaystyle=~{}~{}~{}~{}-c_{R,\mp}+\mathcal{O}(e^{-\kappa j})\ ,$
(120)

which is essential to derive the main results of the paper. Substituting the
identity (120) into Eq.’s (117-118) and comparing with Eqs. (110-111), we get
the relations Eqs. (40) used in the main text:

$\displaystyle\mbox{$\langle\Psi_{R}^{+}|$}\hat{\sigma}^{z}_{j}\mbox{$|\Psi_{R}^{-}\rangle$}$
$\displaystyle=$
$\displaystyle-\mbox{$\langle\widetilde{\Psi}_{R}^{-}|$}\hat{\sigma}^{z}_{j}\mbox{$|\widetilde{\Psi}_{R}^{+}\rangle$}+\mathcal{O}(e^{-\kappa|j-j_{R}|}),\
$ (121)
$\displaystyle\mbox{$\langle\Psi_{L}^{+}|$}\hat{\sigma}^{z}_{j}\mbox{$|\Psi_{L}^{-}\rangle$}$
$\displaystyle=$
$\displaystyle-\mbox{$\langle\widetilde{\Psi}_{L}^{-}|$}\hat{\sigma}^{z}_{j}\mbox{$|\widetilde{\Psi}_{L}^{+}\rangle$}+\mathcal{O}(e^{-\kappa|j-j_{R}|}).\
$ (122)

Figure 12: “Unwinding” the Frustrated Ring. Passing an excitation from the
left to the right of the qubit noise operator restores parity. More
specifically, it removes frustration from the relevant matrix element,
effectively restoring the gap. The left panel shows the spectrum of original
Frustrated Ring. The bottleneck is removed by flipping the sign of
$J_{\mathcal{N}}$, as shown in the right panel. See text for details.

####  B.0.2 Field-theoretic treatment of the ferromagnetic problem

We now give exact expressions for the matrix elements given in Eqs. (121-122),
involving eigenstates of the ferromagnetic Hamiltonian $\widetilde{H}$. We
begin by calculating the matrix element corresponding to the ferromagnetic
groundstate:

$\displaystyle\mbox{$\langle\widetilde{\Psi}_{R}^{+}|$}\sigma^{z}_{j}\mbox{$|\widetilde{\Psi}_{R}^{-}\rangle$}\
.$ (123)

Since the frustration-free model is globally gapped in the spin glass (i.e.
ferromagnetic) phase $B<B_{c}$, there are no crossings involving the
groundstate manifold (See Figure 12), and

$|\Psi_{GS}^{+}\rangle$
$\displaystyle\equiv\mbox{$|\widetilde{\Psi}_{R}^{+}\rangle$}\ ,$ (124)
$|\Psi_{GS}^{-}\rangle$
$\displaystyle\equiv\mbox{$|\widetilde{\Psi}_{R}^{-}\rangle$}\ ,$ (125)

span the degenerate ground state manifold in the thermodynamic limit of
infinite-chain length $\mathcal{N}\to\infty$. We begin by showing that the
quantity we wish to compute, is really the spontaneous magnetization of our
quantum spin chain, in disguise. Since the model is completely ferromagnetic
(as we have removed frustration), if we perturb the model with an
appropriately-aligned longitudinal field, i.e. define

$\displaystyle\widetilde{H}_{0}(h)\equiv\widetilde{H}_{0}+\frac{h}{\mathcal{N}}\sum_{j=1}^{\mathcal{N}}\hat{\sigma}^{z}_{j},$
(126)

then the groundstate degeneracy is broken. Here, the external field is scaled
as $\sim O(1/\mathcal{N})$ in order to ensure the perturbation is bounded in
the thermodynamic limit $\mathcal{N}\to\infty$. Since the perturbation mixes
fermion parity, simple degenerate perturbation theory in the groundstate
manifold Eqs. (124-125) yields that the perturbed ground-state, in the limit
$h\to 0^{+}$, is

$\displaystyle|\Psi_{GS}^{(0)}\rangle$ $\displaystyle\equiv\lim_{h\to
0^{+}}\lim_{\mathcal{N}\to\infty}|\Psi_{GS}(h)\rangle$ (127)
$\displaystyle=\lim_{\mathcal{N}\to\infty}\frac{1}{\sqrt{2}}(\mbox{$|\widetilde{\Psi}_{R}^{+}\rangle$}+\mbox{$|\widetilde{\Psi}_{R}^{-}\rangle$}).$
(128)

The reason we consider this perturbation of the frustration-free model is
because this allows us to relate our transition matrix element to the
spontaneous magnetization of this model. Indeed, since $\hat{\sigma}^{z}_{j}$
mixes fermion parity,

$\displaystyle\lim_{\mathcal{N}\to\infty}\mbox{$\langle\widetilde{\Psi}_{R}^{+}|$}\hat{\sigma}^{z}_{j}\mbox{$|\widetilde{\Psi}_{R}^{-}\rangle$}$
$\displaystyle=\lim_{\mathcal{N}\to\infty}\frac{1}{2}(\mbox{$\langle\widetilde{\Psi}_{R}^{+}|$}+\mbox{$\langle\widetilde{\Psi}_{R}^{-}|$})\hat{\sigma}^{z}_{j}(\mbox{$|\widetilde{\Psi}_{R}^{+}\rangle$}+\mbox{$|\widetilde{\Psi}_{R}^{-}\rangle$})$
$\displaystyle~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}=\mbox{$\langle\Psi_{GS}^{(0)}|$}\hat{\sigma}^{z}_{j}\mbox{$|\Psi_{GS}^{(0)}\rangle$}.$
(129)

To compute this spontaneous magnetization, we write

$\displaystyle\lim_{\mathcal{N}\to\infty}\mbox{$\langle\widetilde{\Psi}_{R}^{+}|$}\hat{\sigma}^{z}_{j}\mbox{$|\widetilde{\Psi}_{R}^{-}\rangle$}$
$\displaystyle=\lim_{h\to
0^{+}}\lim_{\mathcal{N}\to\infty}\mbox{$\langle\Psi_{GS}(h)|$}\hat{\sigma}^{z}_{j}\mbox{$|\Psi_{GS}(h)\rangle$}$
$\displaystyle=\lim_{h\to 0^{+}}\lim_{\mathcal{N}\to\infty}\lim_{T\to
0}\text{Tr}[e^{-\widetilde{H}_{0}(h)/T}\hat{\sigma}^{z}_{j}].$ (130)

This allows us to probe this matrix element using the quantum-classical
correspondence: we begin by defining a partition function via

$\displaystyle Z_{\mathcal{N},h}$ $\displaystyle\equiv\lim_{T\to
0}\text{Tr}[e^{-\widetilde{H}_{0}(h)/T}].$ (131)

As is standard, to obtain the correspondence with a classical model, we apply
the Suzuki-Trotter transformation with a time-step $\tau_{c}>0$ to the
partition function, producing a family of effective actions
$\\{S[\tau_{c}]\\}_{\tau_{c}>0}$ describing (classical) stochastic
fluctuations of an Ising spin system on a cylindrical spacetime lattice. After
a straightforward manipulation, one gets Sachdev (2000):

$Z_{\mathcal{N},h}=\sum_{\\{s_{j\tau}=\pm 1\\}}e^{-S[\tau_{c},h]}\ .$ (132)

Here, $\tau_{c}\ll 1$ is a UV cutoff defining a non-perturbative
renormalization group flow in imaginary time Costello (2011). For small values
of the UV cutoff, the action of the statistical field theory simplifies to
Sachdev (2000):

$\displaystyle S[\tau_{c},h]$ $\displaystyle\underset{\tau_{c}\to
0}{\sim}\sum_{j,\,\tau\in\tau_{c}\mathbb{Z}}(J_{j}[\tau_{c}]s_{j\tau}s_{j+1,\tau}+J_{\perp}[\tau_{c}]s_{j\tau}s_{j,\tau+\tau_{c}}$
$\displaystyle~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}+H[\tau_{c}]s_{j,\tau})\
,$ (133)

where the coupling constants in our theory have the following dependence on
the cutoff (for small values of the cutoff):

$\displaystyle J_{\perp}[\tau_{c}]$
$\displaystyle\equiv\ln\tanh(B\tau_{c}),~{}~{}~{}~{}~{}~{}~{}~{}H[\tau_{c}]\equiv\tau_{c}h/\mathcal{N},$
$\displaystyle J_{j}[\tau_{c}]$ $\displaystyle\equiv\tau_{c}J_{j}.$

Thus, we have

$\displaystyle\lim_{\mathcal{N}\to\infty}\mbox{$\langle\widetilde{\Psi}_{R}^{+}|$}\hat{\sigma}^{z}_{j}\mbox{$|\widetilde{\Psi}_{R}^{-}\rangle$}$
$\displaystyle=\lim_{\alpha\to
0^{+}}\lim_{\begin{subarray}{c}\mathcal{N}\to\infty,\\\
H=\alpha/\mathcal{N}\end{subarray}}\lim_{\mathcal{N}_{\perp}\to\infty}\langle
s_{j,\tau}\rangle_{H}\ ,$ (134)

which is exactly Yang’s definition (as reviewed in Schultz  _et al._ (1964))
of the spontaneous magnetization of the two-dimensional classical Ising model
(133). Following Schultz  _et al._ (1964), we denote this with the shorthand
$M_{j}$, so that Eq. (134) is equivalently stated as

$\displaystyle\lim_{\mathcal{N}\to\infty}\mbox{$\langle\widetilde{\Psi}_{R}^{+}|$}\hat{\sigma}^{z}_{j}\mbox{$|\widetilde{\Psi}_{R}^{-}\rangle$}$
$\displaystyle=M_{j}\ ,$ (135)

where it is understood that we are applying Yang’s definition of the
spontaneous magnetization to the action Eq. (133), which lacks translational
symmetry in the spatial direction.

In the case that the weights in our MAXCUT problem are uniform in absolute
value, i.e. when $|J_{j}|\equiv J$ for all $j$, then the two-dimensional Ising
model corresponding to the ferromagnet $\widetilde{H}$ is uniform, and we can
cite Yang’s result Yang (1952) here for the exact matrix element, which is
independent of $j$:

$\displaystyle M_{j}$ $\displaystyle=M,~{}~{}~{}~{}M\equiv(1-k^{-2})^{1/8}\ .$
(136)

Here, $k$ is called the spectral parameter, and has the following exact form
Palmer (2007):

$\displaystyle k\equiv\sinh J[\tau_{c}]\sinh J_{\perp}[\tau_{c}]\ .$ (137)

In this (uniform) case, we can calculate the spectral parameter in the UV
limit of our field theory, in which case we get the ratio $J/B$ coming from
the quantum spin chain:

$\displaystyle k$ $\displaystyle=\sinh J[\tau_{c}]\sinh J_{\perp}[\tau_{c}]$
$\displaystyle\underset{\tau_{c}\to
0}{\sim}J[\tau_{c}]e^{-J_{\perp}[\tau_{c}]}\underset{\tau_{c}\to
0}{\sim}\frac{J}{B}.$ (138)

In other words, in the uniform case $|J_{j}|\equiv\text{const}$, the matrix
element in the spin chain comes out to, in the large-$\mathcal{N}$ limit:

$\displaystyle\lim_{\mathcal{N}\to\infty}\mbox{$\langle\widetilde{\Psi}_{R}^{+}|$}\hat{\sigma}^{z}_{j}\mbox{$|\widetilde{\Psi}_{R}^{-}\rangle$}$
$\displaystyle=(1-k^{-2})^{1/8}\ ,$ (139)

for all $B(t)<J$ (i.e. the ordered phase for the ferromagnetic problem).

####  B.0.3 Transfer matrix calculation

In the quantum spin glass problem that we consider, the couplings are non-
uniform. However, the broken translation invariance in the spin chain is due
to the modification of only $3$ couplers, namely the couplers

$\displaystyle J_{n}=J_{n+1}$ $\displaystyle\equiv J_{L},$ $\displaystyle
J_{2n+1}$ $\displaystyle\equiv J_{R}.$ (140)

(Note that here, we are using the values of these couplers in the
ferromagnetic version $\widetilde{H}$ of our model). Due to the finite
correlation length in the classical model, the effect of local changes to the
coupling constants in the theory is washed-out in the thermodynamic limit,
when we sum the spontaneous magnetization over all sites $j$. That is, we can
expect the behavior

$\displaystyle\sum_{j=1}^{\mathcal{N}}M_{j}^{2}\underset{\mathcal{N}\to\infty}{\sim}\mathcal{N}M^{2}.$
(141)

where, here, $M\equiv(1-k^{-2})^{1/8}$ is the result for the uniform chain. To
demonstrate the asymptotic result Eq. (141), we must demonstrate a boundary
effect in the classical model. To do this, we calculate the local spontaneous
magnetization using the row transfer matrix.

Indeed, consider computing the spontaneous magnetization (representing the
tunneling matrix element in the quantum spin glass) using Yang’s algorithm (as
reviewed in Schultz  _et al._ (1964)), but now applied to the row transfer
matrix, as opposed to the column transfer matrix:

$\displaystyle M_{\text{$j$}}=\lim_{\alpha\to
0^{+}}\lim_{\mathcal{N}\to\infty}\lim_{\begin{subarray}{c}\mathcal{N}_{\perp}\to\infty,\\\
H=\alpha/\mathcal{N}_{\perp}\end{subarray}}\langle s_{j,\tau}\rangle_{H}$
$\displaystyle=\lim_{\alpha\to
0^{+}}\lim_{\mathcal{N}\to\infty}\lim_{\begin{subarray}{c}\mathcal{N}_{\perp}\to\infty,\\\
H=\alpha/\mathcal{N}_{\perp}\end{subarray}}\frac{\text{Tr}[T[J_{1};H]\cdots\hat{\sigma}^{z}_{\tau}\cdots
T[J_{\mathcal{N}};H]]}{\text{Tr}[T[J_{1};H]\cdots
T_{\mathcal{N}}[J_{\mathcal{N}};H]]}.$ (142)

Here, the row transfer matrix is (see, e.g. Palmer (2007))

$\displaystyle T[J_{l};H]$
$\displaystyle\equiv\bigg{(}\prod_{\tau}e^{J_{\perp}[\tau_{c}]\hat{\sigma}^{z}_{\tau}\hat{\sigma}^{z}_{\tau+1}+H\hat{\sigma}^{z}_{\tau}}\bigg{)}$
$\displaystyle~{}~{}~{}\cdot\bigg{(}\prod_{\tau}e^{J_{l}[\tau_{c}]}(1+e^{-2J_{l}[\tau_{c}]}\hat{\sigma}^{x}_{\tau})\bigg{)}.$
(143)

The spectral parameter for this transfer matrix when $H\equiv 0$ can be
calculated, and comes out to

$\displaystyle k_{l}$ $\displaystyle=\sinh J_{l}[\tau_{c}]\sinh
J_{\perp}[\tau_{c}]$ $\displaystyle\underset{\tau_{c}\to
0}{\sim}J_{l}[\tau_{c}]e^{-J_{\perp}[\tau_{c}]}\underset{\tau_{c}\to
0}{\sim}\frac{J_{l}}{B}.$ (144)

Note that, since the model is no longer translation-invariant, this spectral
parameter is now dependent on the qubit location
$l\in\\{1,\cdots,\mathcal{N}\\}$. We can then proceed with the calculation,
letting $d$ denote the distance between the site $j$ (where we are calculating
the local spontaneous magnetization), and the nearest defect (e.g. the $J_{L}$
or $J_{R}$ coupler):

$\displaystyle M_{\text{$j$}}=\lim_{\alpha\to
0^{+}}\lim_{\mathcal{N}\to\infty}\lim_{\begin{subarray}{c}\mathcal{N}_{\perp}\to\infty,\\\
H=\alpha/\mathcal{N}_{\perp}\end{subarray}}$
$\displaystyle\frac{\text{Tr}[T[J;H]^{d}\hat{\sigma}^{z}_{\tau}T[J;H]^{N-d}T[J_{L};H]^{2}T[J;H]^{N}T[J_{R};H]]}{\text{Tr}[T[J;H]^{N}T[J_{L};H]^{2}T[J;H]^{N}T[J_{R};H]]}$

with $N\equiv n-1$ equal to the bulk chain length. We can now see the
emergence of a boundary effect in the classical model (and thus, by the
quantum-classical correspondence, in the quantum ferromagnet $\widetilde{H}$
as well): letting $|\Psi_{+}\rangle$ denote the maximal eigenvector of
$T[J;H]$, we have, by analogous arguments to Eqs. (124-128), the following
limiting behavior:

$\displaystyle\lim_{\alpha\to
0^{+}}\lim_{\begin{subarray}{c}\mathcal{N}_{\perp}\to\infty\\\
H=\alpha/\mathcal{N}_{\perp}\end{subarray}}|\Psi_{+}\rangle$
$\displaystyle=\frac{1}{\sqrt{2}}(|\Psi^{+}_{0}\rangle+|\Psi^{-}_{k=0}\rangle)\
,$ (145)

where here, $|\Psi_{0}^{+}\rangle$ and $|\Psi_{k=0}^{-}\rangle$ are the even-
and odd-parity maximal-eigenvectors of $T[J;H\equiv 0]$ (following the
notation of Schultz  _et al._ (1964)). Therefore, we can write

$\displaystyle\lim_{\alpha\to
0^{+}}\lim_{\begin{subarray}{c}\mathcal{N}_{\perp}\to\infty\\\
H=\alpha/\mathcal{N}_{\perp}\end{subarray}}T[J;H]^{d}$
$\displaystyle=|\Psi_{+}\rangle\langle\Psi_{+}|+O(e^{-d\Delta})\ ,$ (146)

where, here, $\Delta$ is the spectral gap for the unperturbed transfer matrix
$T[J;H\equiv 0]$, which sets the correlation length in the spatial direction
of the lattice. Using Eqs. (145-146), we have

$\displaystyle
M_{\text{$j$}}=\frac{\langle\Psi_{+}|\hat{\sigma}^{z}_{\tau}|\Psi_{+}\rangle}{\langle\Psi_{+}|\Psi_{+}\rangle}+O(e^{-\Delta
d})\ ,$ (147)

where we have used the fact that, for large $\mathcal{N}$, $N-d\to\infty$,
where $N\equiv n-1$ is the bulk chain length. According to Schultz  _et al._
(1964), the leading-order term in the above expression comes out to

$\displaystyle\frac{\langle\Psi_{+}|\hat{\sigma}^{z}_{\tau}|\Psi_{+}\rangle}{\langle\Psi_{+}|\Psi_{+}\rangle}$
$\displaystyle=(1-k_{0}^{-2})^{1/8},$ (148)

where $k_{0}$ is the spectral parameter for the bulk transfer matrix
$T[J;H\equiv 0]$, which is simply $J/B$. Therefore, in total, at a distance
$d$ away from either the right- or left-end of the chain,

$\mbox{$\langle\widetilde{\Psi}_{R}^{-}|$}\hat{\sigma}^{z}_{j}\mbox{$|\widetilde{\Psi}_{R}^{+}\rangle$}\underset{\mathcal{N}\to\infty}{\sim}M+\mathcal{O}(e^{-\Delta
d})\ .$ (149)

This bulk convergence behavior is confirmed by exact diagonalization with up
to $\mathcal{N}=23$ sites, see Figure 9 in the main text. The other tunneling
matrix

$\displaystyle\mbox{$\langle\widetilde{\Psi}_{L}^{+}|$}\hat{\sigma}^{z}_{j}\mbox{$|\widetilde{\Psi}_{L}^{-}\rangle$}$
(150)

can be computed similarly: one begins by noting that $|\Psi_{L}^{+}\rangle$ is
related to $|\Psi_{R}^{+}\rangle$ by applying two quasiparticle operators (and
the same is true for the relationship between $|\Psi_{L}^{-}\rangle$ and
$|\Psi_{R}^{-}\rangle$). Since these operators are localized at opposite
locations of the graph, their product gets mapped, under the Jordan-Wigner
transformation, to a string of spin flips $\prod_{j}\sigma^{x}_{j}$ between
the centers $j_{L}$ and $j_{R}$ of the corresponding bound state wave
functions. Therefore, because conjugation by a product of spin flips only has
the potential to flip the sign of the magnetization, the tunneling form
factors corresponding to (150) has the exact same asymptotics (a tunneling
form factor is given by the squared absolute value of a matrix element of the
type considered above).