# End-to-end Alexa device arbitration

###### Abstract

We introduce a variant of the speaker localization problem, which we call
_device arbitration_. In the device arbitration problem, a user utters a
keyword that is detected by multiple distributed microphone arrays (smart home
devices), and we want to determine which device was closest to the user.
Rather than solving the full localization problem, we propose an end-to-end
machine learning system. This system learns a feature embedding that is
computed independently on each device. The embeddings from each device are
then aggregated together to produce the final arbitration decision. We use a
large-scale room simulation to generate training and evaluation data, and
compare our system against a signal-processing baseline.

Index Terms—  keyword-spotting, speech-recognition, source-localization

##  1 Introduction

A growing number of households own multiple smart speaker voice-assistant
devices, such as Amazon Alexa or Google Home. These devices typically operate
by listening for a specific wakeword (such as “Alexa” or “Hey Google”; also
referred to as a _keyword_ or _hotword_) to trigger processing user speech and
generating responses. When multiple devices are present, they may all detect
the same wakeword, creating ambiguity about which device is the correct one to
service the user’s request. While there may be specific context relevant to
the request (for example, a request to play a video should be serviced by a
video-capable device), we focus on a heuristic where we want to choose the
device that is _physically closest to the user_. We refer to this process as
_device arbitration_.

Fig. 1: The end-to-end arbitration model architecture. We produce feature
embeddings for each device, which are then fused in the cloud to produce a
prediction. The entire system is trained end-to-end with simulated data.

This yields a concrete technical problem: _given short segments of audio
(containing the wakeword) recorded from a set of $N$ (heterogeneous)
microphone arrays, we want to determine which device is closest to the user_.
Furthermore, this must be done without any a priori knowledge of the spatial
relationships between the devices or the acoustic environment that they are
in. We also desire the system to be able to operate on resource-constrained
edge devices with minimal latency.

This problem can be seen as a variant of the source localization problem,
which has been well-studied in the literature. When multiple microphones are
present on a single device, time difference of arrival (TDOA) algorithms [1,
2, 3] can be used to estimate the range from the device to the speaker;
however, these generally require physically large arrays to achieve the
required accuracy for our problem. With the small footprints of consumer smart
speakers, these methods become very sensitive to small errors in the TDOA
estimates. TDOA between _devices_ may work in principal, but introduces other
complexities such as clock and data synchronization between devices, and a
solution that avoids these is preferable.

Another class of signal processing methods are _energy-based methods_ [4, 5,
6], which exploit the free-field relationship $E\propto 1/R^{2}$ between
energy and range; when this holds, the closest device will have receive the
maximum energy from the source. These methods face difficulties when applied
to home smart speakers in reverberant rooms with high levels of noise and
interference (such as TVs and air conditioners).

Most recently, deep learning methods have been applied to source localization;
these attempt to directly regress the source location directly from features
[7, 8, 9, 10, 11]. This problem is also related to the channel selection
problem [12, 13, 14]; however, the physically closest device may not actually
provide the best channel, due to room effects and interference.

One limitation of applying the previous source localization algorithms to the
device arbitration problem is that it is trying to solve a harder problem
(estimating the range) than what we care about (finding the device with the
smallest range). To overcome this limitation and directly solve the problem of
interest, we propose an end-to-end neural network approach, which we
illustrate in Figure 1. We train a common feature extractor that runs on each
device, along with classification network that combines features from an
arbitrary numbers of devices. We optimize the entire system to predict the
optimal arbitration decision.

Due to the lack of large-scale arbitration datasets with known ground truth,
we study this problem using a simulation of room and device acoustics. We
build a pipeline for generating simulated rooms populated with devices,
speakers, and noise sources, then computing both the device audio signals and
spatial ground truth.

The rest of the paper is organized as follows: First, we detail our dataset
simulation method for generating audio signals with spatial ground truth.
Next, we discuss our end-to-end model. Third, we discuss our experiment setup,
baseline, and results. Lastly, we conclude and discuss future work.

##  2 Dataset Simulation

Our dataset simulation pipeline is shown in Figure 2. First, we sample
_arbitration scenarios_ from a generative process. An arbitration scenario
consists of a room with its physical and acoustic properties, the spatial
locations of a number of devices placed in the room, and locations and dB SPL
of both a human speaker and a number of noise sources. We will refer to these
sampled parameters as _arbitration metadata_. We then use the metadata to
simulate a set of room impulse responses (RIRs) between each sound source
(speech/noise) and each device microphone, using a room simulator. Finally, we
apply these RIRs to a _source audio dataset_ and mix. This gives us the
microphone signals for each device, along with the metadata that we need to
compute our arbitration ground truth. The rest of this section details each of
these sub-components.

Fig. 2: Pipeline for generating an arbitration scenario from a source audio
dataset.

###  2.1 Generative process

We generate arbitration scenarios by sampling the scenario parameters from the
distributions listed in Table 1. The parameters for room size, reverberation
time, and speech/noise levels are taken from [15]. First, we sample the room
properties: its size and reverberation time. Next, we populate it with
devices, speakers, and noise sources; Figure 3 shows examples of how the
devices and speakers are placed in a room. Finally, we apply rejection
sampling to enforce a constraint that the minimum distance between the speaker
and a device is at least 1 meter.

Parameter | Distribution
---|---
Room length/width (m) | Uniform(3.0, 10.0)
Room height (m) | Uniform(2.5, 6.0)
Reverberation time (s) | Beta(2.5, 1.8)
Number of devices |  Categorical: P(2,3,4,5)=0.7,0.25,0.03,0.02
Device location | Beta(0.2, 0.2)
Speaker location | Beta(3.0, 3.0)
Number of noise sources | Poisson(2)
Noise source location | Uniform(0, 1)
Noise level (dB SPL) | Uniform(25, 80)
Speech level (dB SPL) | Uniform(45, 70)
Table 1: The distributions used to sample the arbitration scenario parameters.
The device, speaker, and noise source location distributions are relative to
the room size.

###  2.2 RIR simulation

The room acoustics model that we use is a variant of the image source method
[16], which we augment with high-fidelity COMSOL models of the farfield
responses for different microphone arrays of interest. Specifically, our
COMSOL models allow us to define a function $\phi_{m}(\hat{\mathbf{r}},t)$
which gives the response of microphone $m$ to an impulse from farfield
direction $\hat{\mathbf{r}}$. The resulting RIR is given by a sum over image
sources:

$h_{m}(t)\propto\sum_{k=0}^{\infty}\frac{\beta^{n_{k}}}{t_{k}^{m}}\phi_{m}(\hat{\mathbf{r}}_{k}^{m},t-t_{k}^{m})$
(1)

Fig. 3: Samples of devices and speakers in a single room. We constrain the
devices and speakers to be at least 10cm from a wall.

where $\beta$ is the room absorption coefficient (estimated from the desired
reverberation time [17]); $n_{k}$ is the order (number of reflections) of the
$k$th image source; $t_{k}^{m}$ and $\hat{\mathbf{r}}_{k}^{m}$ are the time
delay and DOA vector from microphone $m$ on the device to the image source.
Using the per-microphone time delay is important for correctly capturing the
wavefront curvature across the device.

###  2.3 Source audio

We use two source audio datasets: Google SpeechCommands v2 (GSCv2) [18] and an
internal source audio dataset (which we will refer to as the “Alexa” dataset).
For the GSCv2, we used 2377 utterances of the “seven” keyword and the provided
background audio (11 minutes). The internal audio consisted of 1000 recordings
of the “Alexa” wakeword (male and female speakers, recorded in quiet but not
perfectly anechoeic conditions) as the speech audio. For the background audio,
we used internally-collected recordings of ambient background noise (air
conditioners, running water, etc.) as well as 30 hours of TV show and movie
audio from Amazon Prime Video. For both source audio datasets, the speech
segments were partitioned into train/val/test splits, and the background audio
segments were divided into non-overlapping subsegments before being assigned
to train/val/test splits. All audio is sampled at 16kHz.

To generate the audio data for each device, we sample speech and interference
segments from the appropriate source audio dataset. These are then convolved
with the speech and background RIRs computed by the room simulator before
being mixed together. Lastly, the audio for each device has an independent
timing jitter applied (Gaussian with $\sigma=0.1$s) before being trimmed to a
fixed length. The timing jitter mimics the lack of synchronization between
devices.

##  3 Method

Our model consists of two components: a feature extractor, which runs on each
device and produces a feature embedding, and a classifier, which runs in the
cloud (or some other central hub) to compute the final prediction and make the
arbitration decision (Figure 1).

As input data, we use a 2 second window of single-microphone audio; we assume
that the wakeword speech is present somewhere in this window. Next, we convert
this audio to log-filterbank energy (LFBE) features: we compute a spectrogram
with a 25ms frame size and a 10ms frame skip, followed by a mel transform
(with 64 mel bands) and a log transform. This results in a $201\times 64$ LFBE
image that we feed to our network.

The feature extraction network consists of 5 convolution layers, followed by a
single fully connected layer, with a total of 132k parameters. This produces a
128 dimensional embedding, which is passed to the $N$-ary classifier. The
$N$-ary classifier is designed to map $N$ 128-dimensional embeddings to $N$
output probabilities. If we denote the feature embedding from device $j$ as
$\mathbf{z}_{j}$, the network calculates the corresponding logit $\ell_{j}$
by:

$\ell_{j}=g\left(\mathbf{z}_{j},\sum_{i}\mathbf{z}_{i}\right)$ (2)

where $g$ is a two-layer fully connected neural network. The final network
output is given by applying a softmax function to the vector of logits. This
approach to fusing the embeddings of the other devices to make a permutation-
equivariant scoring function is maximally generic (see Theorem 2 in [17]).

The feature extraction and $N$-ary classifier networks are simultaneously
trained end-to-end using Adam and the standard cross-entropy loss, where
ground truth is extracted from the scenario metadata.

Train Dataset | Test Dataset | Rel. error rate
---|---|---
Alexa | Alexa | 52.8%
GSCv2 | 60.1%
GCSv2 | GCSv2 | 50.6%
Alexa | 63.7%
Table 2: Arbitration relative error rate of the end-to-end DNN over the
baseline. We test each model on both test sets to get a sense of how sensitive
the results are to the specific keywords.

##  4 Experiments

###  4.1 Baseline

We use a simple energy-based method as a baseline. Denoting the microphone
signal (assumed to contain the wakeword) from device $k$ as $\mathbf{x}_{k}$,
our decision rule becomes:

$k_{\text{closest}}=\operatorname*{arg\,max}_{k}\|\mathbf{h}_{\text{bandpass}}*\mathbf{x}_{k}\|^{2}$
(3)

where $\mathbf{h}_{\text{bandpass}}$ is a bandpass filter that passes 1500Hz
through 6500Hz. These parameters were chosen by optimizing accuracy over a
validation set.

###  4.2 Experimental procedure

For each source audio dataset (GSCv2 and our Alexa dataset), we generate
train/val/test sets of 50k/2k/10k scenarios, respectively; we used the same
scenarios for each source audio dataset. We also generate a separate dataset
(from the same distribution) of 10k _noise free_ scenarios, which we used in
an ablation to evaluate our baseline in ideal conditions. We train our end-to-
end model on the training set for 30 epochs and take the model with the best
validation accuracy. We then compare the results against the baseline (Section
4.1) using 3 metrics: overall accuracy (probability of correctly identifiying
the closest device), $\Delta$-accuracy, and $\epsilon$-accuracy. We define
these last two metrics next.

For a given scenario, let $d_{1}$ be the distance of the closest device to the
user and $d_{2}$ be the distance of the _second_ closest device to the user.
Then we define $\Delta$-accuracy to be the accuracy when the difference
$d_{2}-d_{1}$ is equal to $\Delta$ (where $\Delta\geq 0$ is a given
parameter). This captures the idea that low-$\Delta$ scenarios are both harder
(more ambiguous) and less impactful to the user’s experience - it is worse to
fail in cases where $\Delta$ is large than when it is small.

Similarly, let $d$ be the distance of the _chosen_ device (e.g., the argmax of
the classifier output) to the user. We define $\epsilon$-accuracy, where
$\epsilon\geq 0$, as:

$\epsilon\text{-accuracy}\overset{\text{def}}{=}P(d-d_{1}<\epsilon)$ (4)

In other words, this is the probability of choosing a device that is
$\epsilon$-close to the optimal device. The case of $\epsilon=0$ coincides
with the normal accuracy metric. This metric is most useful with scenarios of
3 or more devices; for example, if the distance from each device to the user
is 2.0m, 2.2m, and 6.0m, $\epsilon$-accuracy will capture the idea that
choosing the second device is better than choosing the third.

##  5 Results

We present our results in terms of _relative error rate_ over the baseline.
Given the accuracies $\text{acc}_{\text{bl}},\text{acc}_{\text{dnn}}$ of the
baseline model and the DNN model, respectively, the relative error rate is
computed via:

$\text{err}_{\text{rel}}=\frac{1-\text{acc}_{\text{dnn}}}{1-\text{acc}_{\text{bl}}}$
(5)

Our main results on are shown in Table 2. Our end-to-end method substantially
outperforms the baseline, even though the baseline method was tested in a
noise free environment, and reduces classification error by 49% and 47% for
the GSCv2 and Alexa datasets, respectively. We also test on the other dataset
to get a sense of out-of-domain generalization (e.g., a completely different
wakeword) and still see substantial improvement over baseline, although less
than the in-domain case. Our model also exhibits relative performance
improvements on both our $\Delta$-accuracy (Figure 4) and $\epsilon$-accuracy
(Figure 5) metrics vs. the baseline for all values of $\Delta$ and $\epsilon$.

Fig. 4: Relative error rate as a function of $\Delta$, binned in 1m
increments. Our model uniformly outperforms the baseline for all values of
$\Delta$. Fig. 5: Relative error rate as a function of $\epsilon$. Our model
uniformly outperforms the baseline for all values of $\epsilon$.

We ran three additional ablations: First, we tried a non-end-to-end version of
the model where we independently predicted the range to the speaker on each
device, resulting in worse performance. This is expected, since predicting the
absolute range should be harder than determining the closest device. Second,
we experimented with using data from multiple microphones, with both LFBE
features as well as complex STFT and cross-correlations between channels. None
of these resulted in better performance than single-mic LFBEs. We conjecture
that while phase information is critical for DOA estimation, it does not carry
much information about range, at least for small arrays. Third, we looked at
baseline performance on a noise-free dataset. We found only very small
differences in accuracy ($<$ 1%), suggesting that room reverberation is the
dominant source of baseline error.

##  6 Conclusion

In this paper, we have presented an end-to-end deep learning system for device
arbitration among smart speakers. We use simulation to generate large datasets
with spatial ground truth, which we use to generate training and evaluation
data for our model. Our model shows substantial performance improvements over
our signal-processing based baseline.

We have several directions for future work. One is to collect data in real-
world acoustic environments (where spatial ground truth is known) to validate
and possibly train our models. We are also exploring improving our room
simulator to support multi-room environments as well as model speaker
directivity [19]. Lastly, we are exploring self-supervised learning to fuse
representations learned from real data with the high-fidelity ground truth
that our simulations provide, with the goal of improving performance and
generalization.

## References

  * [1] J Abel and J Smith,  “The spherical interpolation method for closed-form passive source localization using range difference measurements,”  in ICASSP’87. IEEE International Conference on Acoustics, Speech, and Signal Processing. IEEE, 1987, vol. 12, pp. 471–474.
  * [2] Yiteng Huang, Jacob Benesty, Gary W Elko, and Russell M Mersereati,  “Real-time passive source localization: A practical linear-correction least-squares approach,”  IEEE transactions on Speech and Audio Processing, vol. 9, no. 8, pp. 943–956, 2001.
  * [3] Amir Beck, Petre Stoica, and Jian Li,  “Exact and approximate solutions of source localization problems,”  IEEE Transactions on signal processing, vol. 56, no. 5, pp. 1770–1778, 2008.
  * [4] Xiaohong Sheng and Yu-Hen Hu,  “Energy based acoustic source localization,”  in Information Processing in Sensor Networks. Springer, 2003, pp. 285–300.
  * [5] Chartchai Meesookho, Urbashi Mitra, and Shrikanth Narayanan,  “On energy-based acoustic source localization for sensor networks,”  IEEE Transactions on Signal Processing, vol. 56, no. 1, pp. 365–377, 2007.
  * [6] Wei Meng and Wendong Xiao,  “Energy-based acoustic source localization methods: a survey,”  Sensors, vol. 17, no. 2, pp. 376, 2017.
  * [7] Fabio Vesperini, Paolo Vecchiotti, Emanuele Principi, Stefano Squartini, and Francesco Piazza,  “A neural network based algorithm for speaker localization in a multi-room environment,”  in 2016 IEEE 26th International Workshop on Machine Learning for Signal Processing (MLSP). IEEE, 2016, pp. 1–6.
  * [8] Eric L Ferguson, Stefan B Williams, and Craig T Jin,  “Sound source localization in a multipath environment using convolutional neural networks,”  in 2018 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP). IEEE, 2018, pp. 2386–2390.
  * [9] Sharath Adavanne, Archontis Politis, Joonas Nikunen, and Tuomas Virtanen,  “Sound event localization and detection of overlapping sources using convolutional recurrent neural networks,”  IEEE Journal of Selected Topics in Signal Processing, vol. 13, no. 1, pp. 34–48, 2018.
  * [10] Soumitro Chakrabarty and Emanuël AP Habets,  “Broadband doa estimation using convolutional neural networks trained with noise signals,”  in 2017 IEEE Workshop on Applications of Signal Processing to Audio and Acoustics (WASPAA). IEEE, 2017, pp. 136–140.
  * [11] Michela Ricciardi Celsi, Simone Scardapane, and Danilo Comminiello,  “Quaternion neural networks for 3d sound source localization in reverberant environments,”  in 2020 IEEE 30th International Workshop on Machine Learning for Signal Processing (MLSP), 2020, pp. 1–6.
  * [12] Martin Wolf and Climent Nadeu,  “Channel selection measures for multi-microphone speech recognition,”  Speech Communication, vol. 57, pp. 170–180, 2014.
  * [13] Samuele Cornell, Alessio Brutti, Marco Matassoni, and Stefano Squartini,  “Learning to rank microphones for distant speech recognition,” 2021\.
  * [14] Israel Cohen, Baruch Berdugo, and Joseph Marash,  “Real-time microphone selection in noisy reverberant environments for teleconferencing systems,”  in International Conference on Acoustics, Speech, and Signal Processing, ICASSP, volume Show and Tell. IEEE, 2014.
  * [15] Chanwoo Kim, Ananya Misra, Kean Chin, Thad Hughes, Arun Narayanan, Tara Sainath, and Michiel Bacchiani,  “Generation of large-scale simulated utterances in virtual rooms to train deep-neural networks for far-field speech recognition in google home,”  2017\.
  * [16] Jont B Allen and David A Berkley,  “Image method for efficiently simulating small-room acoustics,”  The Journal of the Acoustical Society of America, vol. 65, no. 4, pp. 943–950, 1979.
  * [17] Manzil Zaheer, Satwik Kottur, Siamak Ravanbakhsh, Barnabas Poczos, Ruslan Salakhutdinov, and Alexander Smola,  “Deep sets,”  arXiv preprint arXiv:1703.06114, 2017.
  * [18] Pete Warden,  “Speech commands: A dataset for limited-vocabulary speech recognition,”  arXiv preprint arXiv:1804.03209, 2018.
  * [19] Brian B Monson, Eric J Hunter, and Brad H Story,  “Horizontal directivity of low-and high-frequency energy in speech and singing,”  The Journal of the Acoustical Society of America, vol. 132, no. 1, pp. 433–441, 2012.
  * [20] Xiong Xiao, Shengkui Zhao, Xionghu Zhong, Douglas L Jones, Eng Siong Chng, and Haizhou Li,  “A learning-based approach to direction of arrival estimation in noisy and reverberant environments,”  in 2015 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP). IEEE, 2015, pp. 2814–2818.


# Anti-crossings occurrence as exponentially closing gaps
in Quantum Annealing

Arthur Braida  Atos Quantum Lab, Les Clayes-sous-Bois, France  LIFO -
Laboratoire d’Informatique Fondamentale d’Orléans, Université d’Orléans,
France  Simon Martiel  Atos Quantum Lab, Les Clayes-sous-Bois, France  Ioan
Todinca  LIFO - Laboratoire d’Informatique Fondamentale d’Orléans, Université
d’Orléans, France

(April 2023)

###### Abstract

This paper explores the phenomenon of avoided level crossings in quantum
annealing, a promising framework for quantum computing that may provide a
quantum advantage for certain tasks. Quantum annealing involves letting a
quantum system evolve according to the Schrödinger equation, with the goal of
obtaining the optimal solution to an optimization problem through measurements
of the final state. However, the continuous nature of quantum annealing makes
analytical analysis challenging, particularly with regard to the instantaneous
eigenenergies. The adiabatic theorem provides a theoretical result for the
annealing time required to obtain the optimal solution with high probability,
which is inversely proportional to the square of the minimum spectral gap.
Avoided level crossings can create exponentially closing gaps, which can lead
to exponentially long running times for optimization problems. In this paper,
we use a perturbative expansion to derive a condition for the occurrence of an
avoided level crossing during the annealing process. We then apply this
condition to the MaxCut problem on bipartite graphs. We show that no
exponentially small gaps arise for regular bipartite graphs, implying that QA
can efficiently solve MaxCut in that case. On the other hand, we show that
irregularities in the vertex degrees can lead to the satisfaction of the
avoided level crossing occurrence condition. We provide numerical evidence to
support this theoretical development, and discuss the relation between the
presence of exponentially closing gaps and the failure of quantum annealing.

##  1 Introduction

Quantum annealing (QA) is one of the two promising frameworks for quantum
computing that may end with a quantum advantage on some specific tasks. Also
named adiabatic quantum computing (AQC), it has been introduced by Fahri et.
al [1] in 2000 and stands for the analog part of the gate-based model.
Although the two frameworks are known to be equivalent (one can efficiently
simulate the other) [2], their studies rely on different theoretical tools. QA
has gained lots of attention in the last decade because it seems well-suited
to solve combinatorial optimization problems. One largely studied gate-based
algorithm, namely QAOA [3], is QA-inspired and has brought a lot of attention
to the NISQ era. The goal of quantum annealing is to let a quantum system
evolve along a trajectory according to the Schrödinger equation. Given some
hypotheses, if the Hamiltonians are well defined, measuring the final state
after a long enough evolution gives (with high probability) the optimal
solution to the optimization problem. This result is guaranteed by the
adiabatic theorem. This theoretical result describes the annealing time
requested to obtain with high probability the optimal solution as a function
of the minimum spectral gap $\Delta_{\min}$. The latter is defined as the
minimum, over the whole adiabatic process, of the difference between the two
lowest eigenenergies of the instantaneous Hamiltonian. The adiabatic theorem
states that, by allowing a runtime inversely proportional to the square of the
minimum gap, this ensures a constant probability of observing the optimal
solution. In general, exponentially closing minimum gaps yields a running time
exponential in the input size but this is only an empirical result.

One major obstacle to this computing model is its analytical analysis, the
continuous part of QA makes the equations very difficult to manipulate. The
adiabatic theorem has focused a great deal of research on the study of these
instantaneous eigenenergies. Since [4], a physical phenomenon called avoided
level crossing (or anti-crossing AC) is known to create an exponentially
closing gap bringing the provable runtime to solve an optimization problem to
be exponential in the size of the problem. AC is also often referred as first-
order quantum phase transition [5]. This observation has justified numerous
studies of anti-crossings to derive the complexity of quantum annealing
runtime. In [6], the authors show that for NP-hard problem 3-SAT, an AC will
occurs at the end of the evolution, called perturbative crossing, leading to
the failure of quantum annealing. However, the appearance of an AC is closely
related to the Hamiltonian that one chooses to solve a specific problem. In
particular, changing this Hamiltonian can remove or mitigate the avoided
crossing [7]. Other authors have focused on giving a more mathematical
definition of this phenomenon considering different settings [7, 8]. Finally,
in another approach called diabatic annealing, the goal is to manage to create
a second AC to compensate for the probability leak of measuring the ground
state created by the first AC [9]. It is important for the reader to note that
there is still no consensus on a formal definition of an AC. Nevertheless, all
definitions agree that an AC only occurs in case of an exponentially closing
gap. Some authors [6, 7] consider that exponentially small gaps can appear
without constituting an AC because in some situations it is unclear that such
gaps come from first-order quantum phase transition. In the rest of the paper,
we will call AC an exponentially closing gap following the work of [10]. We
will moderate this assertion, as well as the computational inefficiency of QA,
in the discussion after the numerical study.

In general, studying the instantaneous eigen pairs, and a fortiori ACs, is a
hard problem since there is no closed form expression for them. In this work,
we use a perturbative expansion of the initial state, the ground state and the
first excited state as in [10] to manipulate simpler expressions while still
being able to say something about the eigenenergies. This perturbative
analysis allows us to derive a condition on the occurrence of an AC during the
process. We then apply this condition to the well-known MaxCut problem, a
fundamental combinatorial optimization problem that has numerous applications
in various fields, including computer science (Pinter problem) and physics
(Ising models) [11]. We show that on regular bipartite graphs, there is no
appearance of AC during the annealing but if we remove the regularity
constraint, we can construct a family of bipartite graphs that satisfies the
condition of AC’s occurrence. The striking outcome is that exponentially
closing gaps can arise while solving MaxCut on a bipartite graph if it is
irregular enough. Although MaxCut on bipartite graphs is known to be solved
trivially by classical algorithms, there is no formal proof of efficient (or
non-efficient) resolution in the quantum regime. To the best of our knowledge,
these are the first proven results on MaxCut using QA. To support this
theoretical development, we provide numerical analyses of the gaps of small
instances, demonstrating the presence of ACs. A final uncommon observation is
that QA seems to efficiently solve MaxCut on such instances, despite the
presence of exponentially small gaps, thus raising the question of the
relation between QA failure and exponential closing gaps.

#### Organization of the paper:

The paper is organized as follows. In Section 2, we introduce the mathematical
notations for QA and the preliminaries on the perturbative analysis. In
Section 3, we develop the perturbative analysis on QA from which we derive the
condition of occurrence of an anti-crossing. We also show a more practical
corollary to use on concrete problems. In Section 4, we apply the construction
to the MaxCut problem on bipartite graphs. First, we show that no AC will
appear during annealing if the graph is regular, we then demonstrate that high
irregularity can lead to a satisfaction of the AC occurrence condition. We
finally construct such a bipartite graph family and we use small instances to
plot the eigenvalues and observe the exponentially closing minimum gap from a
numerical point of view. We finish with a discussion on AC definition and QA
computational efficiency.

##  2 Quantum annealing and perturbative analysis

This section introduces the quantum annealing (QA) framework and explains the
general concepts of perturbative analysis.

#### Computing with quantum annealing:

In QA, the instantaneous physical system is represented by the vector
$|\psi(t)\rangle$, where the time parameter $t$ goes from 0 to $T$, the
runtime of the process. The evolution of this state is governed by the
Schrödinger equation subject to a time-dependent Hamiltonian $H(t)$:

$i\frac{d}{dt}|\psi(t)\rangle=H(t)|\psi(t)\rangle$

where $\hbar$ is taken as unity. The initial state
$|\psi_{0}\rangle=|\psi(t=0)\rangle$ is taken to be the ground state, i.e. the
state of minimal eigenvalue, of the initial Hamiltonian $H_{0}=H(t=0)$. So
$H_{0}$ needs to be easy enough to be able to prepare the initial state. Then
the Hamiltonian is smoothly changed toward the final one $H_{1}=H(T)$ which
encodes the solution of a combinatorial optimization problem in its ground
state $|GS\rangle$, in the sense that $|GS\rangle$ corresponds to a classical
state encoding the optimal solution $x_{opt}$ of our problem. The time-
dependent $H(t)$ can be viewed as an interpolation $(1-s(t))H_{0}+s(t)H_{1}$
where $s(t)$ denotes the time trajectory going from 0 at $t=0$ to 1 at $t=T$.
For a standard linear interpolation $s(t)=\frac{t}{T}$. It is usual to look at
the Hamiltonian and the state vector as a function of $s$ and the Schrodinger
equation becomes :

$i\frac{d}{ds}|\psi(s)\rangle=TH(s)|\psi(s)\rangle,\hskip
28.45274pt\text{where }H(s)=(1-s)H_{0}+sH_{1}\text{ for }s\in[0,1].$

The restriction on starting from the ground state of the initial Hamiltonian
comes from the adiabatic theorem. In its more general form, it stipulates that
for a “long enough” runtime a quantum state $|\psi(t)\rangle$ under a
Hamiltonian $H(t)$ stays in the same instantaneous eigenspace during the whole
process. Here, “long enough” is characterized by the minimum gap
$\Delta_{\min}$, namely $T\sim\mathcal{O}\left(\Delta_{\min}^{-2}\right)$.
Given that there is a very natural way to encode an optimization problem in a
Hamiltonian such that its ground state encodes the solution [1], the adiabatic
theorem ensures success if the state is initialized in the ground state of
$H_{0}$ motivating the restriction on $|\psi_{0}\rangle$. It is important to
notice that this restriction is not mandatory if the annealing is out of the
adiabatic regime.

#### Perturbative analysis:

In general, the perturbative analysis is used to study the effect a
perturbation has on a system well defined without. For example, given two
Hermitian matrices $A$ and $B$, we know an eigenpair ($x,\lambda$) of $A$,
i.e. $Ax=\lambda x$ and we are interested in how a perturbation $B$ will
change this state. In other words, if ($x,\lambda$) represents the $k^{th}$
eigenpair of $A$, we are interested in the $k^{th}$ eigenpair
($x_{\mu},\lambda_{\mu}$) of $A+\mu B$ for a small parameter $\mu$. We suppose
then that there exists a polynomial expansion in $\mu$ computing
($x_{\mu},\lambda_{\mu}$). We write these expansions as:

$\displaystyle x_{\mu}$
$\displaystyle=x+x^{(1)}\mu+x^{(2)}\mu^{2}+x^{(3)}\mu^{3}+...$
$\displaystyle\lambda_{\mu}$
$\displaystyle=\lambda+\lambda^{(1)}\mu+\lambda^{(2)}\mu^{2}+\lambda^{(3)}\mu^{3}+...$

where $x^{(i)}$ and $\lambda^{(i)}$ represent the different coefficients of
the polynomial expansion being respectively vectors and scalars. In practice,
to be able to say something interesting, we stop the expansion at some order
$i$. The validation of the truncation is justified by the ratio of the
$(i+1)^{th}$ term over the $i^{th}$ being small.

The different coefficients are derived iteratively by identification in the
eigen relation of the perturbed matrices. Namely, we identify each term in
$\mu^{j}$ in the relation $(A+\mu B)x_{\mu}=\lambda_{\mu}x_{\mu}$. Finally,
the obtained relations for each order in $\mu$ are vector equations. After
choosing a right basis for the entire space (usually the eigen vectors of
$A$), we project along the different basis vectors each relation. Projecting
along $x$ gives the $\lambda^{(i)}$ terms and along others basis vectors gives
the different coordinates of the vector $x^{(i)}$. For details of the
expressions used in quantum mechanics, we refer the reader to an MIT course
[12].

In this section, we present two concepts: one is how we can use a quantum
evolution to compute a solution to an optimization problem, and the second is
how to study the evolution of some variables under small perturbation via a
perturbative analysis. In the next section, we apply the perturbation analysis
directly to QA and see how this helps us to talk about anti-crossing and
qualify their occurrences.

##  3 Perturbative Analysis to QA

In this section, we apply the perturbative analysis presented in the previous
section to the quantum annealing process. This idea has already been explored
by other authors [6, 10] to derive different results and intuitions about the
evolution. The perturbative analysis can be naturally applied at the beginning
($s(0)=0$) and at the end ($s(T)=1$) of the evolution. Typically, we know the
diagonalizing basis of the Hamiltonians $H_{0}$ and $H_{1}$ which allows us to
deduce relevant features about the process. Building on the work of [10], we
develop here an expansion of the energy $E_{0}^{I}$ of the initial state
$|\psi_{0}\rangle$, i.e. the ground state of $H_{0}$ and one for the energies
$E_{gs}$ of the ground state $|GS\rangle$ and $E_{fs}$ of the first excited
state $|FS\rangle$ of $H_{1}$, supposing that the first excited subspace of
$H_{1}$ is degenerated. We are interested in the occurrence of AC which is
directly related to the behavior of the instantaneous eigenenergies. Recall
that AC refers to the point where the gap is closing exponentially fast, i.e.
when the two lowest instantaneous eigenenergies are getting exponentially
close to each other. Intuitively, the energy curves almost cross but change
directions just before. The expansions of the energies are detailed below in
the different subsections.

Let us set the time-dependent Hamiltonian on which we work. We need to define
$H_{0}$, $H_{1}$ and the trajectory $s(t)$. We choose to stay in the standard
setting of QA for solving classical optimization problems defined over the
bitstrings of size $n$ where $s(t)=t/T$, $H_{0}=-\sum_{i}\sigma_{x}^{(i)}$
where the sum is over the $n$ qubits of the considered quantum system and
$H_{1}=\text{diag}(E_{x})_{x\in\\{0,1\\}^{n}}$. $E_{x}$ is the value for a
classical $n-$ bitstring $x$ of the function we want to optimize, i.e. if $C$
is a cost function to minimize, $C(x)=E_{x}$. We detail an example with MaxCut
problem in section 4. From this setting, we know that $|\psi_{0}\rangle$ is
the uniform superposition over all bitstrings and the associated eigenspace is
non-degenerated. We further assume that the ground space of $H_{1}$ is non-
degenerated as well, i.e. $\exists!i,E_{i}=E_{gs}$ where $E_{gs}$ is the
ground state energy (i.e. the optimal value of the target problem) while the
first excited subspace is degenerate, i.e. $\exists i\neq
j,E_{i}=E_{j}=E_{fs}>E_{gs}$, with $E_{fs}$ being the value of the first
eigenenergy of $H_{1}$ above $E_{gs}$.

We now introduce different graphs that help us to better visualize some
quantities. As defined above, $H_{0}$ can be seen as the negative adjacency
matrix of an $n-$regular graph. If each node represents a bitstring $x$, this
state is connected to another one $y$ via $H_{0}$ if $y$ is exactly one
bitflip ($\sigma_{x}$ operation) away from $x$. For any bitstring of size $n$,
there are exactly $n$ possible bitflips. $-H_{0}$ represents the search graph
which is the hypercube in dimension $n$ among all possible solutions $x$. We
can isolate the nodes that belong to the degenerated first excited subspace of
energy $E_{fs}^{T}$ among all $x$, i.e.
$\text{Loc}=\\{y\in\\{0,1\\}^{n}|E_{y}=E_{fs}\\}$ and we can define the graph
induced by those states Loc in $-H_{0}$. We call $G_{loc}$ this subgraph that
corresponds to the local minima of the optimization problem. An example of
$G_{loc}$ in the 5-cube is shown on Figure 1. We use MaxCut on a cycle to
generate this example, we give the details in the next section and in Appendix
B.1. To visualize the landscape of such a graph, we draw in Figure 2 a
schematic 2D plot of the objective function $C(x)$ which is also the energy
landscape of $H_{1}$. In the example of Figure 1, we see that the optimal
state $x_{opt}=|GS\rangle$ is entirely linked to $G_{loc}$ and there is no
component of $G_{loc}$ far from it, i.e. with a potential barrier in between.
This idea is conveyed in Fig 2 by the absence of green parts between the red
and blue sections.

Figure 1: A 5-cube with $G_{loc}$ highlighted with red nodes and thick black
edges. Lightblue node is the unique ground state and blue edges show the
connection between $G_{loc}$ and the ground state. Green nodes are all the
other possible states with higher energies. The labels, once converted in
binary, represent the state configuration. Figure 2: Schematic energy
landscape of $H_{1}$ corresponding to Figure 1. $G_{loc}$ has only one
component and is strongly connected to the ground state $x_{opt}$.

In the rest of the section, we detail the perturbation expansions and how we
can articulate them to derive a condition on the occurrence of the anti-
crossing during quantum annealing. More precisely, we will prove the following
theorem:

######  Theorem 3.1.

Under perturbative expansion validity, if $\lambda_{0}(\text{loc})$ is the
largest eigenvalue of the adjacency matrix of $G_{loc}$ and $H_{1}$ has a
unique ground state and a degenerated first eigenspace, we use a linear
interpolation between $H_{0}$ and $H_{1}$ as defined above, then by defining

$\displaystyle s_{lg}$ $\displaystyle=\frac{\lambda_{0}(\text{loc})}{\Delta
H_{1}+\lambda_{0}(\text{loc})}=\frac{1}{1+\frac{\Delta
H_{1}}{\lambda_{0}(\text{loc})}}$

and

$\alpha_{T}=\frac{\Delta H_{1}}{\langle H_{1}\rangle_{0}-E_{gs}}$

where $\Delta H_{1}=E_{fs}-E_{gs}$ and $\langle H_{1}\rangle_{0}$ is the mean
of $H_{1}$’s eigenvalues, we can say that an anti-crossing happens at $s_{lg}$
if $\lambda_{0}(\text{loc})>n\alpha_{T}$. No anti-crossing occurs if
$\lambda_{0}(\text{loc})<n\alpha_{T}$.

This forms a general condition on the occurrence of an anti-crossing during a
quantum process with the assumptions of the theorem. We see that the
$\alpha_{T}$ parameter depends only on the problem $H_{1}$ while
$\lambda_{0}(\text{loc})$ is mixing $H_{0}$ and $H_{1}$. We observe from this
result that the potential occurrence time of an AC around $s_{lg}$ is ruled by
the ratio $\frac{\Delta H_{1}}{\lambda_{0}(\text{loc})}$. In practice, this
result can help computer scientists to design appropriate schedules by slowing
the evolution around the AC. However, the $\lambda_{0}(\text{loc})$ parameter
can be complicated to compute. It encodes the centrality of $G_{loc}$ and can
be interpreted as the importance of the graph. To tackle this we use a result
from graph theory [13] that bounds the largest eigenvector of a graph by :
${\textbf{d}}_{\text{avg}}(\text{loc})\leq\lambda_{0}(\text{loc})\leq{\textbf{d}}_{\max}(\text{loc})$.
Where ${\textbf{d}}_{\text{avg}}(\text{loc})$ and
${\textbf{d}}_{\max}(\text{loc})$ denote the average and maximum degree of
$G_{loc}$ respectively. We can derive the following more practical corollary:

######  Corollary 3.2.

By introducing,

$\displaystyle s_{lg}^{+}$
$\displaystyle=\frac{{\textbf{d}}_{\text{avg}}(\text{loc})}{\Delta
H_{1}+{\textbf{d}}_{\text{avg}}(\text{loc})}$ $\displaystyle s_{lg}^{-}$
$\displaystyle=\frac{{\textbf{d}}_{\max}(\text{loc})}{\Delta
H_{1}+{\textbf{d}}_{\max}(\hbox{loc})}$

we can distinguish three regimes :

  1. -

AC occurs in the interval $[s_{lg}^{+},s_{lg}^{-}]$ if
${\textbf{d}}_{\text{avg}}(\text{loc})>n\alpha_{T}$;

  2. -

NO-AC occurs if ${\textbf{d}}_{\max}(\text{loc})<n\alpha_{T}$;

  3. -

UNDEFINED if
${\textbf{d}}_{\max}(\text{loc})>n\alpha_{T}>{\textbf{d}}_{\text{avg}}(\text{loc})$.

This corollary gives an interval where an AC may occur. Furthermore, it will
help anyone who wants to study the different regimes when applying to a
specific problem as we do with MaxCut in the next section. In any case, this
analytical result is derived from the perturbative theory and the validity of
the truncation used needs to be checked. We suggest a validation for MaxCut in
Appendix A. Now let us detail the proof of the theorem.

###  3.1 Initial perturbation

At the beginning of the evolution, we know that we start from the ground state
of $H_{0}$ with energy $E_{0}^{I}$, i.e.
$H_{0}|\psi_{0}\rangle=E_{0}^{I}|\psi_{0}\rangle$. We are interested in how it
changes while perturbing $H_{0}$ with some $H_{1}$. More formally, let us look
at the modified Hamiltonian $\tilde{H}(\varepsilon)=H_{0}+\varepsilon H_{1}$
which is obtained by dividing the original Hamiltonian by $(1-s)$ and setting
$\varepsilon=\frac{s}{1-s}$. If we call $E_{\text{deloc}}(\varepsilon)$,
’deloc’ for delocalized state, the ground state energy of
$\tilde{H}(\varepsilon)$, by perturbative analysis with non-degenerated
subspace, the first-order expansion is :

$\displaystyle E_{\text{deloc}}(\varepsilon)$
$\displaystyle=E_{0}^{(0)}+\varepsilon E_{0}^{(1)}$
$\displaystyle=\langle\psi_{0}|H_{0}|\psi_{0}\rangle+\varepsilon\langle\psi_{0}|H_{1}|\psi_{0}\rangle$
$\displaystyle=E_{0}^{I}+\varepsilon\langle H_{1}\rangle_{0}$

where $E_{0}^{I}=-n$ and the associated state $|\psi_{0}\rangle$ is a uniform
superposition among all bitstrings. Hence, $\langle H_{1}\rangle_{0}$
represents the mean of all possible values of the optimization problem,
encoded in $H_{1}$. Therefore, in the $s$ frame, we end up with :

$\displaystyle E_{\text{deloc}}(s)=-(1-s)n+s\langle H_{1}\rangle_{0}$ (1)

###  3.2 Final perturbation

At the end of the evolution, we know that the ideal case is if the state
overlaps largely with the final ground state. However, the occurrence of an
anti-crossing may lead to a significant overlap with the first excited state.
So we focus our interest on the energy’s behavior ending in $E_{gs}$ and
$E_{fs}$ while it is perturbed by $H_{0}$. More formally, let us look at the
modified Hamiltonian $\bar{H}(\lambda)=H_{1}+\lambda H_{0}$ which is obtained
by dividing the original Hamiltonian by $s$ and setting
$\lambda=\frac{1-s}{s}$.

We first focus on the behavior of the ground state. We know that
$H_{1}|GS\rangle=E_{gs}|GS\rangle$. If we call $E_{\text{glob}}(\lambda)$,
’glob’ for global minima, the ground state energy of $\bar{H}(\lambda)$, by
perturbative analysis with non-degenerated subspace, the first order expansion
is:

$\displaystyle E_{\text{glob}}(\lambda)$ $\displaystyle=E_{gs}^{(0)}+\lambda
E_{gs}^{(1)}$ $\displaystyle=\langle GS|H_{1}|GS\rangle+\lambda\langle
GS|H_{0}|GS\rangle$ $\displaystyle=E_{gs}$

Recall that $E_{gs}$ is the optimal value of the optimization problem we look
at and the associated eigenspace is non-degenerated. So $|GS\rangle$ is a
quantum state that encodes a classical bitstring optimal solution to the
problem. In other words, $|GS\rangle$ is a vector of the canonical basis of
the Hilbert space and then $\langle GS|H_{0}|GS\rangle$ is a diagonal element
of $H_{0}$ which is all 0. Therefore in the $s$ frame, we end up with:

$\displaystyle E_{\text{glob}}(s)=sE_{gs}^{T}$ (2)

Secondly, we focus on the evolution of the first excited state. However, we
supposed that this subspace is degenerated so we need to be more precise about
which state we want to study. Let $|FS,k\rangle$ denotes the $k^{th}$
eigenstate of the degenerate eigenspace of $H_{1}$, by definition
$H_{1}|FS,k\rangle=E_{fs}^{T}|FS,k\rangle$. If we keep the usual bitstring
basis among the degenerated subspace, the first order term $\langle
FS,k|H_{0}|FS,k\rangle$ will still be 0 and the degeneracy is not lifted. The
states $|FS,k\rangle$ can be ordered by continuity of the non-degenerate
instantaneous energy landscape of $H(s)$ and thus $\bar{H}(\lambda)$ also.
Therefore we focus on the energy evolution of the state $|FS,0\rangle$. If we
call $E_{\text{loc}}(\lambda)$ the first excited state energy of
$\bar{H}(\lambda)$, by perturbative analysis with non-degenerated subspace,
the first order expansion is :

$\displaystyle E_{\text{loc}}(\lambda)$ $\displaystyle=E_{fs,0}^{(0)}+\lambda
E_{fs,0}^{(1)}$ $\displaystyle=\langle FS,0|H_{1}|FS,0\rangle+\lambda\langle
FS,0|H_{0}|FS,0\rangle$ $\displaystyle=E_{fs}^{T}+\lambda\langle
FS,0|H_{0}|FS,0\rangle$

To lift the degeneracy at first-order, we need to find a “good” basis
$|FS,k\rangle$ for which $\forall k\geq 1,\langle
FS,0|H_{0}|FS,0\rangle<\langle FS,k|H_{0}|FS,k\rangle$. We take as basis
vectors $|FS,k\rangle$ of the degenerate eigenspace the eigenvectors of
$G_{loc}$’s adjacency matrix $A_{loc}$. With this notation,
$A_{loc}|FS,k\rangle=\lambda_{k}|FS,k\rangle$ where we ordered
$\lambda_{0}>\lambda_{1}\geq\lambda_{2}\geq...$ and finally $\langle
FS,k|H_{0}|FS,k\rangle=-\lambda_{k}$ by construction. This ensures to lift the
degeneracy if the largest eigenvalue of $A_{loc}$ is unique. This happens if
$G_{loc}$ has a unique major component which we suppose. Note that if
$G_{loc}$ is composed only of isolated nodes, intuitively, they become as
difficult as the ground state to find by QA unless there are exponentially of
them, we assume from now that this is not the case. Hence, $\lambda_{0}$ is
unique and in the $s$ frame, we end up with:

$\displaystyle E_{\text{loc}}(s)=sE_{fs}^{T}-(1-s)\lambda_{0}$ (3)

From [13], we can bound the largest eigenvector of a graph by :
${\textbf{d}}_{\text{avg}}(\text{loc})\leq\lambda_{0}\leq{\textbf{d}}_{\max}(\text{loc})$,
where ${\textbf{d}}_{\text{avg}}(\text{loc})$ and
${\textbf{d}}_{\max}(\text{loc})$ denote the average and maximum degree of
$G_{loc}$ respectively. Consequently, we can use the following more practical
bounds on $E_{\text{loc}}(s)$:

$\displaystyle E_{\text{loc}}(s)$ $\displaystyle\geq
sE_{fs}^{T}-(1-s){\textbf{d}}_{\max}(\text{loc})=E_{\text{loc}}^{-}(s)$ (4)
$\displaystyle E_{\text{loc}}(s)$ $\displaystyle\leq
sE_{fs}^{T}-(1-s){\textbf{d}}_{\text{avg}}(\text{loc})=E_{\text{loc}}^{+}(s)$
(5)

###  3.3 Energy crossing

Figure 3: Schematic behavior of the three energy expansions. (left) a case
with no AC and (right) case with AC.

We are set up to distinguish different regimes in which avoided crossing
occurs or not. The state starts in the delocalized situation, as
$|\psi_{0}\rangle$ is the uniform superposition, with energy
$E_{\text{deloc}}$. If it crosses $E_{\text{glob}}$ first, it then follows the
global minima trajectory to “easily” reach the final ground state. If it
crosses $E_{\text{loc}}$ first, it then follows the local minima trajectory
and at some point, it will cross $E_{\text{glob}}$ after and an anti-crossing
will occur at this instant. Hence, the two times of interest of the dynamic
are $s_{dg}$, defined such that
$E_{\text{deloc}}(s_{dg})=E_{\text{glob}}(s_{dg})$, and $s_{dl}$, defined such
that $E_{\text{deloc}}(s_{dl})=E_{\text{loc}}(s_{dl})$. If $s_{dl}<s_{dg}$,
then an anti-crossing occurs at a time $s_{lg}$ verifying that
$E_{\text{loc}}(s_{lg})=E_{\text{glob}}(s_{lg})$. Figure 3 shows the possible
behaviors of the energy expansions. In this plot, we considered that
$E_{gs}^{T}<E_{fs}^{T}<0$. The slope of the curve $E_{\text{loc}}$ depends in
addition on $\lambda_{0}$, the largest eigenvalue of $G_{loc}$. A larger
$\lambda_{0}$ moves the sign of the slope toward the positive value making
$E_{\text{loc}}$ crosses $E_{\text{deloc}}$ before $E_{\text{glob}}$ all
others things being equal. This situation (right) will create an AC during the
annealing. It is important to note that a large $\lambda_{0}$ means great
connectivity in the graph $G_{loc}$ (or at least in its major component). In
other words, it means that the local minima are wide in the mixing graph
$H_{0}$ which makes QA struggle to converge toward the global minima. We
understand from this observation that this construction only works if the
major component of $G_{loc}$ is not connected to the ground state.

We can derive the explicit expression for $s_{dg},s_{dl}$ and $s_{lg}$ as
follow:

$\displaystyle s_{dg}$ $\displaystyle=\frac{n}{n+\langle
H_{1}\rangle_{0}-E_{gs}^{T}}$ $\displaystyle s_{dl}$
$\displaystyle=\frac{n-\lambda_{0}}{n-\lambda_{0}+\langle
H_{1}\rangle_{0}-E_{fs}^{T}}$ $\displaystyle s_{lg}$
$\displaystyle=\frac{\lambda_{0}}{\Delta
E^{T}+\lambda_{0}}=\frac{1}{1+\frac{\Delta E^{T}}{\lambda_{0}}}$

We note

$\alpha_{T}=\frac{\Delta H_{1}}{\langle H_{1}\rangle_{0}-E_{gs}^{T}}$

where $\Delta H_{1}=E_{fs}^{T}-E_{gs}^{T}$, a parameter that depends only on
the problem $H_{1}$ we want to solve. And so AC occurs at $s_{lg}$ if
$s_{dl}<s_{dg}$ i.e. if $\lambda_{0}>n\alpha_{T}$. This concludes the proof of
our theorem.

The corollary immediately follows by using $E_{loc}^{-}(s)$ and
$E_{loc}^{+}(s)$. The undefined regime is then when
$s_{dg}\in[s_{dl}^{-},s_{dl}^{+}]$ because we cannot discriminate between
which curve the delocalized energy will cross first.

This result is quite general for many targets Hamiltonians, but we still need
two conditions: the ground state must be unique and the first excited subspace
is degenerated.

In this section, we apply the perturbative analysis to QA and show in the
assumption where the ground state of $H_{1}$ is unique and its first excited
subspace is degenerated, that anti-crossings may occur during annealing given
a condition to satisfy that depends on $G_{loc}$ and $H_{1}$. We also give a
corollary which relaxed the condition of the theorem to be more useful when
applying to a specific problem. In the next section, we show such an
application in the case of MaxCut on bipartite graphs.

##  4 Application to MaxCut

In this section, we apply the last theorem to the MaxCut problem. Given a
graph $G(V,E)$, the goal of MaxCut is to partition its node set $V$ into two
parts $L$ and $R$ in order to maximize the number of cut edges, i.e., of edges
with an endpoint in $L$ and the other in $R$. Such partitions are classically
encoded by a bitstring of size $n=|V|$, the $i^{th}$ bit being set to $0$ if
node $i\in L$, and to $1$ if $i\in R$. We define our target Hamiltonian as
$H_{1}=-\sum_{(ij)\in E}\frac{1-\sigma_{z}^{(i)}\sigma_{z}^{(j)}}{2}$. This
Hamiltonian (and the corresponding MaxCut cost function) has a trivial
symmetry: any solution can be turned into a solution with the same cost by
bit-flipping all its entries. Consequently, $H_{1}$ has a degenerated ground
state. We can break down this symmetry by forcing an arbitrary bit (say the
first one) to $0$ and updating $H_{1}$ accordingly.

To ensure that the two conditions of our theorem are met, we need to choose a
class of graphs such that the ground state is non-degenerated (after breaking
the trivial symmetry). Connected bipartite graphs obviously respect this
property and we focus on them in the rest of the section. We will in
particular show that the first excited subspace is degenerated. Also this
class allows us to explicitly determine the parameter and the graph . This
will help us to determine the existence (or not) of ACs while solving MaxCut
on these graphs with QA

###  4.1 d-regular bipartite graphs

We first restrict the bipartite graphs on being $d$-regular and we will show
that no AC appears during the evolution by using the result of the corollary:
${\textbf{d}}_{\max}(\text{loc})<n\alpha_{T}$. Leading to the following
theorem :

######  Theorem 4.1 (NO AC - d-regular bipartite graphs).

Quantum Annealing efficiently solves MaxCut on $d-$regular bipartite graphs.

First, we show the two following claims to give a value to $n\alpha_{T}$, then
we show the NO-AC conditions with lemma 4.2 if $d\notin\\{2,4\\}$. The latter
two cases are detailed in Appendix B where we directly use the theorem to
prove the desired result.

######  Claim 1.

For $d$-regular bipartite graphs we have, $n\alpha_{T}=\frac{4l}{d}$, where
$l\in[1,d]$ denotes the number of uncut edges in the first excited state, i.e.
$E_{fs}^{T}=E_{gs}^{T}+l$.

For bipartite graphs we have that $\langle H_{1}\rangle_{0}=-\frac{|E|}{2}$,
$E_{gs}^{T}=-|E|$ and $\Delta H_{1}=l\in[1,d]$. For regular graphs, we also
have that $|E|=\frac{dn}{2}$. So $n\alpha_{T}=\frac{4l}{d}$ and we need to
look at how ${\textbf{d}}_{\max}(\text{loc})$ and
${\textbf{d}}_{\text{avg}}(\text{loc})$ behave compare to $\frac{4l}{d}$.

######  Claim 2.

There exist graphs with ${\textbf{d}}_{\max}(\text{loc})>0$ only if $l=d$.
Therefore $n\alpha_{T}=4$.

Recall that $G_{loc}$ is the subgraph induced by solutions of energy
$E_{fs}^{T}$ in the hypercube $-H_{0}$. In full words, the vertices of
$G_{loc}$ are configurations (bitstrings) of energy $E_{fs}^{T}$ (so “second
best” solutions for MaxCut), and two vertices are adjacent if the
corresponding bitstrings differ in exactly one bit, i.e., each one is obtained
by bit flipping a single bit of the other. We denote by
${\textbf{d}}_{\max}(\text{loc})$ the maximum degree of $G_{loc}$. We know
that, in the input graph $G$, there exists a partition left/right of its
vertices such that all edges lie across the partition (by bipartiteness).
Looking at one configuration of the first excited subspace, it specifies
another bipartition, this time with all but $l$ edges lying across it. We are
interested in configurations that are not isolated in $G_{loc}$ because these
nodes as mentioned in Section 3 do not play a role in AC occurrence. In such a
configuration $x$, we want that by flipping one node (i.e. moving it to the
other side of the partition), the number of uncut edges stays the same, in
order to obtain a configuration $y$ that is also a vertex of $G_{loc}$. So
this specific node needs to have half of its edges that is uncut and the other
half that is cut in this particular configuration $x$ of the first excited
subspace. This automatically restricts $l$ to be both even and larger than
$d/2$.

Figure 4: Construction of a specific first excited configuration. The L/R
partition (left) is natural in MaxCut. The U/D partition (right) is relevant
if 1 is a minimal separator.

#### Case $l=d/2$:

Let us suppose $l=d/2$. We are in a situation similar to Figure 4 (left), and
see if we can create a bipartite graph from this. By supposing that $l=d/2$,
it means, in the configuration of one excited state, all other edges must go
from left (L) to right (R). This splits the configuration in the classical L/R
partition of a cut. Then we show the following claim that node 1 is a minimal
separator of the graph which creates another split up (U) and down (D) (Fig 4
\- right).

######  Claim 3.

Assume that $l=d/2$ and let us consider a configuration corresponding to a
non-isolated vertex of $G_{loc}$. Then there is a node of the input graph $G$,
say node 1, having $d/2$ neighbors on each side of the configuration.
Moreover, this node is a minimal separator of the graph (see Figure 4).

The configuration $x$ is such that all edges but $l=d/2$ are cut, and this
also holds after the bitflip of one of its bits. Assume w.l.o.g. that this is
the first bit, corresponding to node 1, and that 1 is on the left-hand side of
the configuration, i.e., $1\in L$. Since flipping node 1 from left to right
maintains the number of cut edges, it means that 1 has exactly $d/2$ neighbors
in set $L$ and $d/2$ in set $R$. Since $l=d/2$, it also means that the $l$
uncut edges are precisely the $d/2$ ones incident to node $1$, from $1$ to
vertices of $L$.

Let $N_{D}(1)$ denote the set of neighbors of $1$ in $L$, and $N_{U}(1)$
denote the set of neighbors of $1$ in $R$. We prove that $N_{D}(1)$ and
$N_{U}(1)$ are disconnected in graph $G-1$, obtained from the input graph $G$
by deleting vertex $1$. By contradiction, assume there is a path $P$ from
$a\in N_{U}(1)$ to $b\in N_{D}(1)$ in $G-1$. Path $P$ together with vertex $1$
form a cycle in graph $G$. By bipartiteness, this cycle is even, so at least
one edge of the cycle, other than $\\{1,b\\}$, is contained in L or R. This is
in contradiction with the assumption that $l=d/2$ and all of of these specific
$d/2$ edges are linked to the same node $1$. Therefore, $G-1$ is disconnected.
This proves claim 3.

This creates four quadrants UL, UR, DL and DR as follows: U is the subset of
nodes of $G$ formed by the union of connected components of $G-1$ intersecting
$N_{U}(1)$, and D is its complement. Then UL, UR, DL and DR are defined as the
respective intersections of U and D with L and R (UL = U $\cap$ L and
similar). The above considerations tell us that all edges of $G-1$ go either
from UL to UR or from DL to DR. Now, we call $n_{DL},n_{DR}$ the number of
nodes in part DL and DR (others than the labelled ones, i.e., the neighbors of
node 1). By counting the edges from DL to DR, observe that these variables
must satisfy the following equation:

$\frac{d}{2}(d-1)+dn_{DL}=dn_{DR}$

Because we know that $d$ is even, $n_{DL}$ and $n_{DR}$ are integers, the
above equation cannot be satisfied.

#### Case $l>d/2$:

$l$ must be strictly larger than $d/2$, i.e. $l\in[\frac{d}{2}+1,d]$. All
these $l$ uncut edges can be split between $r_{L}$ and $r_{R}$, the ones on
the left side and right side respectively and wlog we choose that already
$d/2$ of them are on the left side. So $r_{L}\in[\frac{d}{2},d]$,
$r_{R}\in[0,\frac{d}{2}]$ and $l=r_{L}+r_{R}$. Again we can count the number
of edges that lie across L and R and we end up with:

$dn_{L}-2r_{L}=dn_{R}-2r_{R}$

where $n_{L}=|L|$, $n_{R}=|R|$ and $n_{L}+n_{R}=n$ the total number of nodes.
In a $d-$regular bipartite graph, $n$ is necessarily even, so we have that

$r_{L}-r_{R}=2(\frac{n}{2}-n_{R})\frac{d}{2}=kd\quad\text{ for
}k\in\mathbb{Z}$

The potential values for $r_{L}$ and $r_{R}$ bring the interval for
$r_{L}-r_{R}$ to $[0,d]$. So only $k=0$ and $k=1$ are possible. If $k=0$, then
$r_{L}=r_{R}=d/2$ so $l=d$. If $k=1$, then $r_{R}=0$, $r_{L}=d$ so $l=d$. In
any case, the only possibility is to have $l=d$ which concludes the proof of
claim 2.

These two claims simplify the expression of the different AC occurrence
conditions, becoming:

  1. -

AC if ${\textbf{d}}_{\text{avg}}(\text{loc})>4$;

  2. -

NO-AC if ${\textbf{d}}_{\max}(\text{loc})<4$;

  3. -

UNDEFINED if
${\textbf{d}}_{\max}(\text{loc})>4>{\textbf{d}}_{\text{avg}}(\text{loc})$.

We are left with a last thing to show to assure that no AC occurs while
solving MaxCut on d-regular bipartite graphs with QA. To this purpose, we show
this final lemma:

######  Lemma 4.2.

If $d\notin\\{2,4\\}$ then ${\textbf{d}}_{\max}(\text{loc})<4$.

###### Proof.

Recall that odd values for $d$ are already disregarded as $d$ must be even.
Suppose it is possible to have $d_{\max}(\text{loc})\geq 4$ then it means that
we need at least 4 nodes in a configuration such as Figure 4, where half of
their edges are uncut. Let us call $F$ the set of these latter nodes, i.e.
$|F|=d_{\max}(\text{loc})$. It means that there are at least
$|F|*\frac{d}{2}\geq 2d$ outgoing uncut edges from the nodes in $F$. By
outgoing edge from a node, we mean the extremity of the edge that leaves the
node (each edge contributes to two outgoing edges, one for each of its nodes).
So here we count the number of edges that leave a node in $F$ which are uncut.
We are allowed to at most $d$ uncut edges to be a local minimum. So all of
these $2d$ outgoing uncut edges need to generate exactly $d$ edges. This
remark forces $d_{\max}(\text{loc})$ to be smaller than 4, so suppose
$d_{\max}(\text{loc})=4$. One node has only 3 possible neighbors for its $d/2$
uncut edges, so it is possible as long as $\frac{d}{2}\leq 3$, i.e., $d\leq
6$. For $d=6$, linking all of these edges creates a triangle which makes the
whole graph non-bipartite. ∎

#### Case $d=2$ and $d=4$.

In these two cases, $d_{\max}(\text{loc})=4$ and
$d_{\text{avg}}(\text{loc})<4$, so they fall in the UNDEFINED regime and
further studies are necessary. In Appendix B, we detail how we can still
classify them in the NO-AC regime by directly using the more technical result
from the theorem.

These above results allow us to conclude on the absence of anti-crossing
during an annealing process to solve MaxCut d-regular bipartite graph for
$d\notin\\{2,4\\}$ and show theorem 4.1. One can deduce from this that there
is no exponentially closing gap leading to a polynomial runtime to find the
optimal cut in regular bipartite graphs via QA. A natural question rises from
this conclusion: can we draw a similar conclusion for general bipartite
graphs? We discuss this in the next subsection.

###  4.2 General bipartite graphs

In this section, we are interested in the behavior of the energies if we look
at bipartite graphs in general. We construct a family of bipartite graphs that
respect the condition of occurrence of an anti-crossing, meaning that
exponentially closing gaps can arise even for MaxCut on bipartite graphs. Let
$G(E,V)$ denotes a bipartite graph. Similarly to the previous section,
$\langle H_{1}\rangle_{0}=-\frac{|E|}{2}$, $E_{gs}=-|E|$ and $\Delta
H_{1}=l\in[1,{\textbf{d}}_{\min}(G)]$. Claim 2 is still applicable with the
minimum degree ${\textbf{d}}_{\min}(G)$ of $G$. So $\Delta
H_{1}={\textbf{d}}_{\min}(G)$ and $n\alpha_{T}$ becomes
$4\frac{{\textbf{d}}_{\min}(G)}{{\textbf{d}}_{\text{avg}}(G)}$. The condition
for the different regimes can be written as:

  1. -

AC if
${\textbf{d}}_{\text{avg}}(\text{loc})>4\frac{{\textbf{d}}_{\min}(G)}{{\textbf{d}}_{\text{avg}}(G)}$;

  2. -

NO-AC if
${\textbf{d}}_{\max}(\text{loc})<4\frac{{\textbf{d}}_{\min}(G)}{{\textbf{d}}_{\text{avg}}(G)}$;

  3. -

UNDEFINED if
${\textbf{d}}_{\max}(\text{loc})>4\frac{{\textbf{d}}_{\min}(G)}{{\textbf{d}}_{\text{avg}}(G)}>{\textbf{d}}_{\text{avg}}(\text{loc})$.

The first point gives us the condition for a graph $G$ that produces an anti-
crossing under a QA evolution for the MaxCut problem. Firstly, looking only at
the right-hand side, the ratio
$\frac{{\textbf{d}}_{\min}(G)}{{\textbf{d}}_{\text{avg}}(G)}$ is small for
highly irregular graphs. From what we have seen in the previous subsection,
the average degree for $G_{loc}$ is certainly smaller than 4 so we need to
play with the degree of $G$. Even though we remove the regularity hypothesis,
we can still use some results from the above cases. Indeed, in that setting,
$G_{loc}$ arises from the bi-partition of a ${\textbf{d}}_{\min}(G)$-regular
induced subgraph of $G$. We look at graphs $G$ with a large average degree but
with also a small minimum degree and a large
${\textbf{d}}_{\text{avg}}(\text{loc})$. The cycle produces the densest
$G_{loc}$ but it is highly connected to the ground state and the average
degree of the cycle is not quite large. The idea is to attach two complete
bipartite graphs ($K_{rr},K_{ll}$) that will increase the average degree of
the graph by two parallel sequences of nodes of degree 2 ($P_{1},P_{2}$) that
will create the dense $G_{loc}$ and small ${\textbf{d}}_{\min}(G)$, equals to
2. Figure 5 provides an example of a such graph with $r=l=3$ and $P_{1},P_{2}$
are sequences of $k_{1}=k_{2}=2$ adjacent nodes of degree 2. $k_{1}$ and
$k_{2}$ need to be of the same parity to assure bipartiteness of the whole
graph. Three configurations of the same graph are shown, corresponding to the
ground state (left), and two configurations of the first excited subspace
(middle, right), that create the different components in $G_{loc}$ (Fig 6).

Figure 5: Configurations of $G$ in its ground state (left) and first excited
state. (middle) is a configuration far from GS, (right) a configuration
neighboring GS. Figure 6: $G_{loc}$ of graph $G$. Three components : (middle)
and (right) similarly: components corresponding to states in a configuration
close to the one on (Fig 5 \- right) and (left) component corresponding to
states in the configuration of (Fig 5 \- middle). The light dashed grey edges
and nodes show how these two components grow when $k_{i}>2$.

The largest component of $G_{loc}$ is a lattice of size $(k_{1}+1,k_{2}+1)$ if
$k_{i}$ represents the number of nodes in $P_{i}$. It is far away from the
ground state as we need to flip at least all the nodes of the $K_{r,r}$ part.
The two other components can be viewed as subgraphs of the large component so
they have smaller eigenvalues than the largest one of the lattice; they are
also strongly connected to the ground state. Figure 7 shows the details of the
relation between the nodes of $G_{loc}$ and graph configurations in a
left/right partition. The middle configuration of Figure 5 corresponds to the
middle node of the lattice in $G_{loc}$. Then moving each node in blue or
green produce another configuration with the same edge penalty.

Figure 7: Details of the large component of $G_{loc}$ and how each
configuration is related by bitflip. We intentionally omit the drawing of the
$K_{r,r}$ and $K_{l,l}$ which do not play a role in $G_{loc}$.

We directly have that ${\textbf{d}}_{\min}(G)=2$. Now, we need to derive the
average degree of $G$ and of the largest component of $G_{loc}$ (its maximum
degree being 4).

$\displaystyle{\textbf{d}}_{\text{avg}}(\text{loc})$
$\displaystyle=\frac{4*2+2(k_{1}-1+k_{2}-1)*3+(k_{1}-1)(k_{2}-1)*4}{(k_{1}+1)(k_{2}+1)}$
$\displaystyle=\frac{4k_{1}k_{2}+2(k_{1}+k_{2})}{(k_{1}+1)(k_{2}+1)}$
$\displaystyle=4\left(1-\frac{1+\frac{1}{2}(k_{1}+k_{2})}{(k_{1}+1)(k_{2}+1)}\right)$
$\displaystyle=4\left(1-\frac{1}{k+1}\right)\hskip 184.9429pt\text{ for
}k=k_{1}=k_{2}$ $\displaystyle{\textbf{d}}_{\text{avg}}(G)$
$\displaystyle=\frac{(k_{1}+k_{2})*2+2r*r+2l*l+4}{k_{1}+k_{2}+2r+2l}$
$\displaystyle=\frac{2k+r^{2}+l^{2}+2}{k+r+l}\hskip 178.3989pt\text{ for
}k=k_{1}=k_{2}$

Let’s solve the equation
${\textbf{d}}_{\text{avg}}(\text{loc})>4\frac{{\textbf{d}}_{\min}(G)}{{\textbf{d}}_{\text{avg}}(G)}$
with ${\textbf{d}}_{\min}(G)=2$.

$\displaystyle{\textbf{d}}_{\text{avg}}(\text{loc})$
$\displaystyle>4\frac{{\textbf{d}}_{\min}(G)}{{\textbf{d}}_{\text{avg}}(G)}$
$\displaystyle\Rightarrow 1-\frac{1}{k+1}$
$\displaystyle>\frac{2(k+r+l)}{2k+r^{2}+l^{2}+2}$
$\displaystyle\Rightarrow\frac{r^{2}+l^{2}+2-2r-2l}{2k+r^{2}+l^{2}+2}$
$\displaystyle>\frac{1}{k+1}$
$\displaystyle\Rightarrow(k+1)(r^{2}+l^{2}+2-2r-2l)$
$\displaystyle>2k+r^{2}+l^{2}+2$ $\displaystyle\Rightarrow
k(r^{2}+l^{2}-2r-2l)$ $\displaystyle>2r+2l$ $\displaystyle\Rightarrow k$
$\displaystyle>\frac{2(r+l)}{r(r-2)+l(l-2)}$ $\displaystyle\Rightarrow k$
$\displaystyle>\frac{2(r+3)}{r(r-2)+3}\hskip 88.2037pt\text{ for }l=3$

We have a limit at $r=3$ and $k=2$ for a graph of size 16. Then the smallest
graphs that satisfy the condition are for $r=3$ and $k=3$ or $r=4,l=3$ and
$k=2$ which bring the size of the smallest graphs satisfying AC condition to
18 nodes.

This above construction shows that there exist bipartite graphs that exhibit
an AC. The presence of an anti-crossing implies an exponentially closing gap
bringing the provable runtime to find the optimal cut exponentially large in
the size of the graph. This construction can be scaled up easily by growing
the parameters $k,r$ and $l$. In the next subsection, we numerically
investigate the presence of AC on graphs of this family to support this
theoretical result.

###  4.3 Numerical study: AC and other observations

In this section, we give some numerical evidence of the occurrence of the AC
in the particular family we constructed in Subsection 4.2. The goal is to
observe the behavior of the minimum gap and to confirm the exponentially
closing gap. We then discuss whether or not these gaps lead to a computational
inefficiency of QA and moderate the term AC by looking at the more
mathematical definition of [8].

#### Minimum gap study:

Let us first show that the value of the minimum gap supports the theoretical
results derived in Section 3 and Subsection 4.2. To compute this quantity for
large graphs, we use the SciPy library [14] and its optimized method,
scipy.sparse.linalg.eigs, for matrices with a sparse representation. Our
Hamiltonians have a sparse representation in the Pauli basis, enabling us to
compute the minimum gap for graphs with up to 28 nodes.

To satisfy the conditions required for our application, we fix one node of the
graph to lift the standard MaxCut symmetry. Specifically, we fix one node of
the $K_{l,l}$ part on the left (L) side of the partition. We consider the
family of graphs $G_{rk}$ with the same structure as in the previous section,
where we fix $l=3$ and assume $k_{1}=k_{2}=k$. Therefore, we can vary two
parameters (Figure 8 shows the schematic energy landscape of $H_{1}$ for
$G_{rk}$ :

  1. -

increasing $r$ increases the distance between $G_{loc}$ and the ground state
in the hypercube, as all the $K_{r,r}$ part needs to be flipped (fixing one
node in the $K_{l,l}$ part blocks the possibility to flip this part entirely),

  2. -

increasing $k$ creates a larger $G_{loc}$, resulting in a larger local minimum
that is not linked to the ground state, but also increases the two other parts
of $G_{loc}$ connected to it.

Figure 8: Schematic energy landscape of the MaxCut function on an instance
$G_{rk}$ and how $r$ and $k$ affect it.

We denote $\Delta_{rk}(s)$ as the difference between the two lowest
instantaneous eigenvalues of $H(s)$ associated with $G_{rk}$, i.e., the
spectral gap of the time-dependent Hamiltonian. We plot these gaps in Figure 9
(a) by varying $r$ and $k$. Specifically, we observe that increasing $r$ by 1
divides the gap by 2. To illustrate this, we also plot Figure 9 (b) the
minimum gap of $\Delta_{rk}$ for $k=2$ against $r$. We fit this curve with an
exponentially decreasing function of $r$. When $k$ is fixed, it is
straightforward to see that $r\simeq\frac{n}{2}$.

$\begin{array}[]{cc}\includegraphics[scale={0.41}]{delta_rk2.pdf}&\includegraphics[scale={0.5}]{delta_r2.pdf}\\\
(a)&(b)\end{array}$

Figure 9: (a) Evolution of the spectral gap $\Delta_{rk}(s)$ and (b) Minimum
gap of $\Delta_{r2}$ for $r$ going from 3 to 9. It fits an exponentially
decreasing tendency.

Figure 9 supports the main theorem in Section 3 and the construction in
Section 4. The distance to the ground state appears to play a major role in
the minimum gap compared to the size of $G_{loc}$. Remember that $G_{loc}$ has
three components and two of them are linked to the ground state while the
other one is a lattice far from the ground state. Increasing $k$ also
increases the width around the ground state, making it easier to reach than if
it were isolated while increasing $r$ has no impact on $G_{loc}$.

Typically, it is assumed that an exponentially closing gap implies the failure
of QA [6]. In the next paragraph, we investigate the probability of measuring
the ground state at the end of a QA evolution after a time $t_{\max}$ and
discuss about AC definition which opens a new question on the computational
efficiency of QA.

#### Discussions about AC and QA failure:

Now that we have established the exponentially small gaps for the graph
$G_{rk}$ when $r$ is increasing, we can wonder if it can be deduced that QA is
inefficient to solve those instances, as this is the usual deduction from
small gaps. In Figure 10, we observe the probability $p_{rk}$ of measuring the
ground state at the end of a quantum annealing (QA) evolution for different
instances of $G_{rk}$ as a function of $t_{\max}$. This plot was obtained
using the AnalogQPU of the Atos’ quantum software. Surprisingly, the
probability seems to reach the value around 0.5 faster than expected, meaning
in a time $t_{\max}$ that does not appear to depend too much on the size of
the graph. This observation is not a contradiction of the adiabatic theorem,
as it will certainly converge to 1 in an exponentially long runtime. It could
also be just a scale illusion: for much larger graphs, the probability might
stay at 0 for a longer time than observed here, but this is not what the point
below suggests. However, it raises questions about the effectiveness of QA in
practical applications even when exponentially small gaps are present.

Figure 10: Probability of measuring the ground state after a time $t_{\max}$
for instances with $k=2$ and $r\in[3,7]$.

The observed gaps in Figure 9 exhibit an exponentially closing behavior, which
is a signature of the AC phenomenon we are looking at. However, the
computational complexity does not seem to be affected, in the sense that a
constant probability to obtain the optimal solution is reached in a time that
does not seem to depend too much on the graph size. We can notice in Figure 9
(a) that the trend of the gaps appears to be softer compared to other observed
ACs [15], indicating a smoother transition. To address this observation, [8]
proposed a more formal definition of anti-crossings that involves a new set of
quantities. Let $g_{0}(s)=|\langle E_{0}(s)|GS\rangle|^{2}$ and
$g_{1}(s)=|\langle E_{1}(s)|GS\rangle|^{2}$ be the overlap squared of the
instantaneous eigenstate (zeroth and first respectively) of $H(s)$ with the
ground state $|GS\rangle$ of $H_{1}$. Typically, at anti-crossing point, these
curves undergo a harsh exchange of position. If $g_{0}(s)$ smoothly increases
toward 1, it is not an AC according to this definition. For the graph
$G_{rk}$, the conditions given in this formal definition do not seem to be
fully satisfied, as the plots in Figure 11 show. On the left, an example of
behavior of $g_{0}$ and $g_{1}$ when AC happens, the curves experience an
almost discontinuity at AC point, changing the position of $g_{0}$ and
$g_{1}$. On the middle and right plots, $g_{0}$ and $g_{1}$ for instances
$G_{32}$ and $G_{72}$ respectively. In the $G_{32}$ case, $g_{1}$ starts to
become bigger than $g_{0}$ but it produces only a little bump and $g_{0}$ has
a smooth growth toward 1. One could think that this phenomenon is due to the
small size of the instance, and that by considering larger instances but with
very small gaps, we would observe a “typical” AC behaviour. However, on the
$G_{72}$ case, where the size increases and the gap decreases, this bump
totally disappears and we can only attest a smooth growth of $g_{0}$. This
observation indicates the opposite of an AC behavior leading to an efficient
QA evolution to solve these instances. This raises the question of whether
every exponentially closing gap necessarily leads to a failure of QA, or if AC
is a particular event that creates an exponentially closing gap leading to a
complete leak of the probability distribution into higher energy levels.

Figure 11: Evolution of $g_{0}(s)$ in blue and $g_{1}(s)$ in red for graph
$G_{72}$ (right), $G_{32}$ (middle) and a typical behavior (left) during an AC
like in [8]

##  5 Conclusion

In conclusion, in this work, we prove a new theorem showing a condition on the
occurrence of anti-crossings during a quantum annealing process. The signature
of AC we consider is the presence of exponentially closing gaps. Using a
first-order perturbative analysis of the evolution at the beginning on the
initial ground energy of $H_{0}$ and at the end on the non-degenerated ground
energy and degenerated first eigenenergy of $H_{1}$, we manage to articulate
these expressions together to derive a general condition on the occurrence of
AC. In particular, if $\lambda_{0}(\text{loc})>n\alpha_{T}$, an AC occurs,
where $\lambda_{0}(\text{loc})$ is the principal eigenvalue of the graph
$G_{loc}$ which is the graph induced by the degenerated states of the first
eigenspace of $H_{1}$ in $H_{0}$. In other words, $G_{loc}$ is the restriction
of $H_{0}$ to the states that belong to the first excited space of $H_{1}$.
$\alpha_{T}$ is a parameter that depends only on the target Hamiltonian, i.e.
only on the problem we want to solve.

We then apply this theorem to the MaxCut problem and we show that for regular
bipartite graphs, the condition for AC to occur is never fulfilled meaning
that the gap stays “large” for these instances. This means that it is
efficient to solve MaxCut on regular bipartite graphs with quantum annealing.
As far as we know, it is the first proof of efficiency for this problem on any
class of graphs.

Eventually, by removing the regularity assumption, we manage to create highly
irregular bipartite graphs that satisfied the AC conditions. To support the
theoretical development, we numerically investigate the size of the gap while
increasing the size of the graph. We show that the minimum gap has an
exponentially decreasing fit. Surprisingly, while this usually implies the
inefficiency of the annealing process to solve those instances, we observe
that the final probability of measuring the ground state at the end of the
process seems to reach a constant value of 0.5 independently of the graph
size. This means that despite an exponentially closing gap, the computational
complexity to solve the instances is not affected. We further investigate the
AC phenomenon in these cases by using a more formal definition of AC and
conclude that our instances with small gaps do not meet this latter AC
description. This opens the question of whether the presence of an
exponentially closing gap necessarily entails inefficient annealing, or if the
true marker of inefficiency is the presence of an AC as defined in [8].

Overall, our study provides new insights into the efficiency of quantum
annealing for solving optimization problems, particularly the MaxCut problem,
and highlights the importance of considering the occurrence of ACs during the
annealing process.

## References

  * [1] Edward Farhi, Jeffrey Goldstone, Sam Gutmann, and Michael Sipser.  Quantum computation by adiabatic evolution.  arXiv preprint quant-ph/0001106, 2000.
  * [2] Tameem Albash and Daniel A Lidar.  Adiabatic quantum computation.  Reviews of Modern Physics, 90(1):015002, 2018.
  * [3] Edward Farhi, Jeffrey Goldstone, and Sam Gutmann.  A quantum approximate optimization algorithm.  arXiv preprint arXiv:1411.4028, 2014.
  * [4] Michael Wilkinson.  Statistics of multiple avoided crossings.  Journal of Physics A: Mathematical and General, 22(14):2795, 1989\.
  * [5] M. H. S. Amin and V. Choi.  First-order quantum phase transition in adiabatic quantum computation.  Phys. Rev. A, 80:062326, Dec 2009.
  * [6] Boris Altshuler, Hari Krovi, and Jérémie Roland.  Anderson localization makes adiabatic quantum optimization fail.  Proceedings of the National Academy of Sciences, 107(28):12446–12450, 2010.
  * [7] Vicky Choi.  The effects of the problem hamiltonian parameters on the minimum spectral gap in adiabatic quantum optimization.  Quantum Information Processing, 19(3):90, 2020.
  * [8] Arthur Braida and Simon Martiel.  Anti-crossings and spectral gap during quantum adiabatic evolution.  Quantum Information Processing, 20(8), aug 2021.
  * [9] Natasha Feinstein, Louis Fry-Bouriaux, Sougato Bose, and PA Warburton.  Effects of xx-catalysts on quantum annealing spectra with perturbative crossings.  arXiv preprint arXiv:2203.06779, 2022.
  * [10] Matthias Werner, Artur García-Sáez, and Marta P. Estarellas.  Bounding first-order quantum phase transitions in adiabatic quantum computing.  arXiv preprint arXiv:2301.13861, 1 2023.
  * [11] Francisco Barahona, Martin Grötschel, Michael Jünger, and Gerhard Reinelt.  An application of combinatorial optimization to statistical physics and circuit layout design.  Oper. Res., 36(3):493–513, jun 1988.
  * [12] Barton Zwiebach.  Chapter 1: Non-degenerate and degenerate perturbation theory.  In QUANTUM PHYSICS III —MIT Course. MIT OpenCourseWare, 2018.  MIT OpenCourseWare.
  * [13] Yueheng Zhang.  On the principal eigenvector of a graph.  arXiv preprint arXiv:2107.14421, 2021.
  * [14] Eric Jones, Travis Oliphant, Pearu Peterson, et al.  SciPy: Open source scientific tools for Python, 2001–.
  * [15] Victor Bapst and Guilhem Semerjian.  On quantum mean-field models and their quantum annealing.  Journal of Statistical Mechanics: Theory and Experiment, 2012(06):P06007, 2012.
  * [16] D.M. Cvetkovic, D.M. Cvetković, M. Doob, and H. Sachs.  Spectra of Graphs: Theory and Application.  Pure and applied mathematics : a series of monographs and textbooks. Academic Press, 1980.

##  Appendix A Validation of perturbative expansion

We discuss here the validation of this expansion at first order. We need to
look at the second order term and compare it to the first or 0th order term.

#### Delocalized state expansion:

The eigen basis of the initial Hamiltonian $H_{0}$ can be written as

$|E_{b}\rangle=\frac{1}{\sqrt{2^{n}}}\sum_{x\in\\{0,1\\}^{n}}(-1)^{b\cdot
x}|x\rangle$

where $b$ is an $n-$bitstring and $\cdot$ stands for the scalar product over
$\mathbb{F}_{2}^{n}$. There are $n+1$ differents eigen levels where the
$k^{th}$ eigenspace has degeneracy $\binom{n}{k}$ and correspond to
eigenstates with bitstring $b$ of hamming weight $|b|=k$ and eigen value
$E_{b}^{I}=-n+2|b|$ (see [16] for more details). With this notation, we can
write $|\psi_{0}\rangle$ as $|E_{00...00}\rangle$. We are interested in

$E_{0}^{(2)}=\sum_{b\neq 00...0}\frac{|\langle
E_{b}|H_{1}|\psi_{0}\rangle|^{2}}{E_{0}^{I}-E_{b}^{I}}$

For MaxCut problem on graph $G$, we know that $\langle
E_{b}|H_{1}|\psi_{0}\rangle=-1/2$ if and only if $G_{b}$ is exactly one edge.
$G_{b}$ is the graph induced by the node $i$ where $b_{i}=1$. Therefore
$E_{0}^{(2)}=-\frac{|E(G)|}{16}$. We have $E_{0}^{(1)}=\langle
H_{1}\rangle_{0}\simeq-\frac{|E(G)|}{2}$ so
$\frac{|E_{0}^{(2)}|}{|E_{0}^{(1)}|}=\frac{1}{8}<1$.

#### Ground state expansion:

The eigenbasis of the final Hamiltonian $H_{1}$ is the canonical basis of the
bitstring $|x\rangle$ with energy $E_{x}$, and we named $|GS\rangle$, the
bitstrings corresponding to the ground state with energy $E_{gs}$. It follows
that the second order term is

$E_{gs}^{(2)}=\sum_{x\in\\{0,1\\}^{n}}\frac{|\langle
x|H_{0}|GS\rangle|^{2}}{E_{gs}-E_{x}}$

where $|\langle x|H_{0}|GS\rangle|=1$ if and only if the bitstring $x$ is at
exactly one bitflip from the bitstring $GS$. We can rewrite it like

$E_{gs}^{(2)}=\sum_{x\underset{H_{0}}{\sim}GS}\frac{1}{E_{gs}-E_{x}}$

For MaxCut problem on $d-$regular bipartite graph, we can further simplify.
Indeed, from the ground state, flipping one bit gives an energy state
$|x\rangle$ of exactly $E_{x}=E_{gs}+d$. So we end up with
$E_{gs}^{(2)}=-\frac{n}{d}$. We have $E_{gs}^{(1)}=0$ and
$E_{gs}^{(0)}=E_{gs}=\frac{dn}{2}$ which leads to
$\frac{|E_{gs}^{(2)}|}{|E_{gs}^{(0)}|}=\frac{2}{d^{2}}<1$. For $d=4$ we have
the same value as for the delocalized state.

#### Local minima expansion:

We work in the same basis than gor the latter expansion and we look at

$E_{fs}^{(2)}=\sum_{x\notin V(G_{loc})}\frac{|\langle
x|H_{0}|FS,0\rangle|^{2}}{E_{fs}-E_{x}}\leq\sum_{x\notin
V(G_{loc})}\sum_{y\underset{H_{0}}{\sim}x}\frac{|\langle
y|FS,0\rangle|^{2}}{E_{fs}-E_{x}}$

The size of this double sum is the number of connection $G_{loc}$ has with the
whole hypercube, i.e. $|\partial G_{loc}|$. The term $|\langle
y|FS,0\rangle|^{2}$ is large when the degree of node $y$ in $G_{loc}$ is large
so with less occurrence in the above double sum. In average, when a graph is
regular its vector coordinate value of the largest eigenvalue is
$\frac{1}{\sqrt{|V(G_{loc})|}}$. By introducing the conductance of the
subgraph $G_{loc}$ as $\phi(\text{loc})=\frac{|\partial
G_{loc}|}{|V(G_{loc})|}$, we can upper bound the second order term with

$|E_{fs}^{(2)}|\leq\phi(\text{loc})\frac{1}{\min_{x}|E_{fs}-E_{x}|}$

We know that $|E_{fs}^{(1)}|=\lambda_{0}(\text{loc})\geq
d_{\text{avg}}(\text{loc})=n-\phi(\text{loc})$. So the ratio we need to check
is
$\frac{\phi(\text{loc})}{n-\phi(\text{loc})}\frac{1}{\min_{x}|E_{fs}-E_{x}|}$
which smaller if $G_{loc}$ is neighboring high energy states.

##  Appendix B Undefined cases of d-regular bipartite graphs

###  B.1 Case d=2

#### Cycle case (even):

Looking at the specific case of the even cycle, we see that it creates a large
$G_{loc}$, see Figure 12.

Figure 12: $G_{loc}$ of a cycle of size $n=6$

We can easily evaluate the average and maximum degree of this graph as :

$\displaystyle{\textbf{d}}_{\max}(\text{loc})$ $\displaystyle=4$
$\displaystyle{\textbf{d}}_{\text{avg}}(\text{loc})$
$\displaystyle=4\frac{n-2}{n}=4(1-\frac{2}{n})$

These values bring the cycle in the UNDEFINED regime. However, we can expect
that QA will easily work with a MaxCut on an even cycle because its $G_{loc}$
is highly connected to the ground state. Figure 1 shows how $G_{loc}$ (which
is the one in figure 12) is linked to te ground state (blue edges). More
precisely, there are $n-1$ connection with the ground state in a
$(n-1)$-regular graph. This means that there is no potential barrier to
overcome going from $G_{loc}$ to the GS.

Another justification is to directly look at the main theorem which says that
no AC occurs if $\lambda_{0}<4$, where $\lambda_{0}$ is the largest eigenvalue
of $G_{loc}$. We know that $\lambda_{0}={\textbf{d}}_{\max}(\text{loc})$ if
and only if $G_{loc}$ is ${\textbf{d}}_{\max}(\text{loc})$-regular, otherwise
$\lambda_{0}<{\textbf{d}}_{\max}(\text{loc})$. So we are in the no-AC regime.

###  B.2 Case d=4

By construction, in the case where $d=4$, there is one possible configuration
in a 4-regular graph that brings its $G_{loc}$ in the UNDEFINED regime. It can
be artificially scale up as follow :

Figure 13: (left) 4-regular bipartite graph in one of its first excited state
configuration and (right) $G_{loc}$ where we disregarded the isolated node.
Written in red, the number of red nodes ($k=3$). In blue, a part of the graph
that complete the graph in a 4-regular one.

We can easily derive the maximum and average degree of $G_{loc}$:

$\displaystyle{\textbf{d}}_{\max}(\text{loc})$ $\displaystyle=4$
$\displaystyle{\textbf{d}}_{\text{avg}}(\text{loc})$
$\displaystyle=\frac{8(k+1)}{3k+4}=2+\frac{2k}{3k+4}$

where $k$ is a parameter to construct the graph. $G_{loc}$ is not connected to
the ground state, so one can imagine that this will produce a potential
barrier that creates an AC. But as one can see, the average degree of
$G_{loc}$ only tends to $2+2/3<4$, which is far from the AC appearance
condition. A similar argument from the case $d=2$ can be applied here when
using directly the technical theorem with $\lambda_{0}$.


$\displaystyle\;=\;$ $\displaystyle\dim F^{d+1-i}H^{d}(X,L_{\chi^{-1}})$

where the last four equalities are due to proposition B.2. ∎

Note that part (1) of proposition B.2 in particular says
$(-1)^{d-p}\chi(X,\Omega_{X}^{p})\geqslant 0$ for all $p$, in line with the
result for subvarieties of abelian varieties given by generic vanishing [PS13,
cor. 1.4]. This allows to verify the numerical assumption (1.2) from the
introduction for odd-dimensional varieties and for surfaces with nef cotangent
bundle:

######  Lemma B.4.

Let $X$ be a smooth projective variety of dimension $d$ over a field of
characteristic zero, and assume
$h_{p}:=(-1)^{d-p}\chi(X,\Omega_{X}^{p})\geqslant 0$ for all $p$. Suppose
either that $d$ is odd or that $X$ is a surface with nef cotangent bundle.
Then

$2\chi(X\times X,\Omega^{d}_{X\times
X})\;\leqslant\;\chi_{\textup{top}}(X\times X).$

###### Proof.

Serre duality says $h_{p}=h_{d-p}$ for all $p$, so the Künneth decomposition
for differential forms gives

$\chi(X\times X,\Omega_{X\times
X}^{d})\;=\;\sum_{p=0}^{d}\chi(X,\Omega_{X}^{p})\chi(X,\Omega_{X}^{d-p})\;=\;\sum_{p=0}^{d}h_{p}h_{d-p}\;=\;\sum_{p=0}^{d}h_{p}^{2}.$

On the other hand, the Hodge decomposition gives
$\chi_{\textup{top}}(X)=h_{0}+\cdots+h_{d}$ and therefore

$\chi_{\textup{top}}(X\times
X)\;=\;\left(\chi_{\textup{top}}(X)\right)^{2}\;=\;\left(h_{0}+\cdots+h_{p}\right)^{2}$

It will thus be enough to show that the inequality
$Q(h_{0},\dots,h_{d})\leqslant 0$ holds for the quadratic form

$Q(X_{0},\dots,X_{d})=2(X_{0}^{2}+\cdots+X_{d}^{2})-\left(X_{0}+\cdots+X_{d}\right)^{2}.$

If $d$ is odd, then the desired inequality follows from the relations
$h_{i}=h_{d-i}\geqslant 0$ since in this case

$Q(h_{0},\dots,h_{d})=-8\sum_{0\leqslant i<j\leqslant d/2}h_{i}h_{j}\leqslant
0.$

If $d$ is even, then one gets

$Q(h_{0},\dots,h_{d})=h_{d/2}^{2}-4(h_{0}+\cdots+h_{d/2-1})h_{d/2}-8\sum_{0\leqslant
i<j\leqslant d/2-1}h_{i}h_{j}.$

In particular, for $d=2$ the desired inequality can be reformulated as
follows:

$\displaystyle Q(h_{0},h_{1},h_{2})\leqslant 0$
$\displaystyle\;\Longleftrightarrow\;$ $\displaystyle
h_{1}(h_{1}-4h_{0})\leqslant 0$ $\displaystyle\;\Longleftrightarrow\;$
$\displaystyle 4\chi(X,\mathcal{O}_{X})+\chi(X,\Omega_{X}^{1})\geqslant 0$
$\displaystyle\;\Longleftrightarrow\;$ $\displaystyle
6\chi(X,\mathcal{O}_{X})\geqslant c_{2}(X)$
$\displaystyle\;\Longleftrightarrow\;$ $\displaystyle c_{1}^{2}(X)\geqslant
c_{2}(X).$

Now $c_{1}(X)^{2}=c_{1}(\Omega_{X})^{2}$ and $c_{2}(X)=c_{2}(\Omega^{1}_{X})$.
Therefore if $X$ has nef contangent bundle, then $c_{1}(X)^{2}\geqslant
c_{2}(X)$ by nonnegativity of Schur polynomials of Chern classes of nef vector
bundles [Laz04, example 8.3.10]. ∎

## References

  * [And92] Y. André, _Mumford-Tate groups of mixed Hodge structures and the theorem of the fixed part_ , Compositio Math. 82 (1992), no. 1, 1–24.
  * [Art57] E. Artin, _Geometric algebra_ , Intersci. Tracts Pure Appl. Math., vol. 3, Interscience Publishers, New York, NY, 1957.
  * [Ber90] V. G. Berkovich, _Spectral theory and analytic geometry over non-Archimedean fields_ , Mathematical Surveys and Monographs, vol. 33, American Mathematical Society, Providence, RI, 1990.
  * [BMR20] M. Bate, B. Martin, and G. Roehrle, _Semisimplification for Subgroups of Reductive Algebraic Groups_ , arXiv, 2020, arXiv:2004.08105.
  * [BO78] P. Berthelot and A. Ogus, _Notes on crystalline cohomology_ , Princeton University Press, Princeton, NJ; University of Tokyo Press, Tokyo, 1978.
  * [BSS18] B. Bhatt, C. Schnell, and P. Scholze, _Vanishing theorems for perverse sheaves on abelian varieties, revisited_ , Sel. Math., New Ser. 24 (2018), no. 1, 63–84.
  * [BT65] A. Borel and J. Tits, _Groupes réductifs_ , Inst. Hautes Études Sci. Publ. Math. (1965), no. 27, 55–150.
  * [BT19] B. Bakker and J. Tsimerman, _The Ax-Schanuel conjecture for variations of Hodge structures_ , Invent. Math. 217 (2019), no. 1, 77–94.
  * [CMSP17] J. Carlson, S. Müller-Stach, and C. Peters, _Period mappings and period domains_ , 2nd edition ed., Camb. Stud. Adv. Math., vol. 168, Cambridge: Cambridge University Press, 2017.
  * [CTZ22] P. Corvaja, A. Turchet, and U. Zannier, _Around the Chevalley-Weil theorem_ , Enseign. Math. 68 (2022), no. 1-2, 217–235.
  * [Del70] P. Deligne, _Équations différentielles à points singuliers réguliers_ , Lecture Notes in Mathematics, Vol. 163, Springer-Verlag, Berlin-New York, 1970.
  * [Del71] by same author, _Théorie de Hodge. II_ , Inst. Hautes Études Sci. Publ. Math. (1971), no. 40, 5–57.
  * [Del74] by same author, _La conjecture de Weil. I_ , Inst. Hautes Études Sci. Publ. Math. (1974), no. 43, 273–307.
  * [Del85] by same author, _Preuve des conjectures de Tate et de Shafarevitch (d’après G. Faltings)_ , Astérisque (1985), no. 121-122, 25–41, Seminar Bourbaki, Vol. 1983/84.
  * [DMOS82] P. Deligne, J. S. Milne, A. Ogus, and K. Shih, _Hodge cycles, motives, and Shimura varieties_ , Lecture Notes in Mathematics, vol. 900, Springer-Verlag, Berlin-New York, 1982.
  * [Fal83] G. Faltings, _Endlichkeitssätze für abelsche Varietäten über Zahlkörpern_ , Invent. Math. 73 (1983), no. 3, 349–366.
  * [Fal89] by same author, _Crystalline cohomology and $p$-adic Galois-representations_, Algebraic analysis, geometry, and number theory (Baltimore, MD, 1988), Johns Hopkins Univ. Press, Baltimore, MD, 1989, pp. 25–80.
  * [GP11] P. Gille and P. Polo (eds.), _Schémas en groupes (SGA 3). Tome I. Propriétés générales des schémas en groupes_ , Documents Mathématiques (Paris), vol. 7, Société Mathématique de France, Paris, 2011, Séminaire de Géométrie Algébrique du Bois Marie 1962–64. A seminar directed by M. Demazure and A. Grothendieck with the collaboration of M. Artin, J.-E. Bertin, P. Gabriel, M. Raynaud and J-P. Serre, Revised and annotated edition of the 1970 French original.
  * [JKLM22] A. Javanpeykar, T. Krämer, C. Lehn, and M. Maculan, _The monodromy of families of subvarieties on abelian varieties_ , 2022.
  * [Kat73] N. M. Katz, _Travaux de Dwork_ , Exp. No. 409, pp. 167–200.
  * [Kat87] by same author, _On the calculation of some differential Galois groups_ , Invent. Math. 87 (1987), no. 1, 13–61.
  * [KW15] T. Krämer and R. Weissauer, _Vanishing theorems for constructible sheaves on abelian varieties_ , J. Algebraic Geom. 24 (2015), no. 3, 531–568.
  * [Laz04] R. Lazarsfeld, _Positivity in algebraic geometry. II_ , Ergebnisse der Mathematik und ihrer Grenzgebiete. 3. Folge. A Series of Modern Surveys in Mathematics, vol. 49, Springer-Verlag, Berlin, 2004, Positivity for vector bundles, and multiplier ideals.
  * [LS20] B. Lawrence and W. Sawin, _The Shafarevich conjecture for hypersurfaces in abelian varieties_ , arXiv, 2020, arXiv:2004.09046.
  * [LV20] B. Lawrence and A. Venkatesh, _Diophantine problems and $p$-adic period mappings_, Invent. Math. 221 (2020), no. 3, 893–999.
  * [Mar03] B. M. S. Martin, _Reductive subgroups of reductive groups in nonzero characteristic_ , J. Algebra 262 (2003), no. 2, 265–286.
  * [Mil17] J. S. Milne, _Algebraic groups_ , Cambridge Studies in Advanced Mathematics, vol. 170, Cambridge University Press, Cambridge, 2017, The theory of group schemes of finite type over a field.
  * [MO13] user76758, _In any Lie group with finitely many connected components, does there exist a finite subgroup which meets every component?_ , MathOverflow, 2013, mathoverflow.net/questions/150949/.
  * [PS13] M. Popa and C. Schnell, _Generic vanishing theory via mixed Hodge modules_ , Forum Math. Sigma 1 (2013), Paper No. e1, 60.
  * [Ric67] R. W. Richardson, Jr., _Conjugacy classes in Lie algebras and algebraic groups_ , Ann. of Math. (2) 86 (1967), 1–15.
  * [Rou81] G. Rousseau, _Instabilité dans les espaces vectoriels_ , Algebraic surfaces (Orsay, 1976–78), Lecture Notes in Math., vol. 868, Springer, Berlin-New York, 1981, pp. 263–276.
  * [Sch15] C. Schnell, _Holonomic $\mathcal{D}$-modules on abelian varieties_, Publ. Math., Inst. Hautes Étud. Sci. 121 (2015), 1–55.
  * [Ser94] J.-P. Serre, _Cohomologie galoisienne_ , fifth ed., Lecture Notes in Mathematics, vol. 5, Springer-Verlag, Berlin, 1994.
  * [SR72] N. Saavedra Rivano, _Catégories Tannakiennes_ , Lecture Notes in Mathematics, Vol. 265, Springer-Verlag, Berlin-New York, 1972.
  * [Sta22] The Stacks Project Authors, _The Stacks Project_ , https://stacks.math.columbia.edu, 2022.
  * [Vie95] E. Viehweg, _Quasi-projective moduli for polarized manifolds_ , Ergeb. Math. Grenzgeb., 3. Folge, vol. 30, Berlin: Springer-Verlag, 1995.
  * [Vin96] E. B. Vinberg, _On invariants of a set of matrices_ , J. Lie Theory 6 (1996), no. 2, 249–269.