  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\"odinger 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.

Quantum Physics;Data Structures and Algorithms