The adiabatic theorem is a powerful result concerning the evolution of quantum mechanical systems. Intuitively, it states the following: suppose we want to study the evolution of a quantum mechanical system governed by a given Hamiltonian
H (Def. 6.1), and the initial state of the system is the eigenstate of
H corresponding to its lowest eigenvalue. The laws of quantum physics tell us that the evolution of the system over time follows the Schrüdinger equation, Eq. (6.1). Suppose now that the Hamiltonian is not fixed, but rather, it changes very slowly over time, so that the evolution of the system is described by the differential equation
idtd∣ψ(t)⟩=H(t)∣ψ(t)⟩, and
H(t) is slowly changing. If, for any value of the time parameter
t, there is always a gap between the lowest eigenvalue of
H(t) and all other eigenvalues, then the adiabatic theorem asserts that the state of the system always remains in an eigenstate with the lowest eigenvalue throughout the evolution. One specific case of interest in this chapter occurs when the time-dependent Hamiltonian
H(t) varies from an initial (time-independent) Hamiltonian
HI to a final Hamiltonian
HF. If the change happens slowly, and the initial state of the system is an eigenstate of
HI with minimum eigenvalue, the adiabatic theorem asserts that the evolution eventually leads to the eigenstate with minimum eigenvalue of the final Hamiltonian
HF. This result can be used for optimization: imagine that the initial Hamiltonian encodes an easy problem for which we can construct the eigenstate with minimum eigenvalue, and the final Hamiltonian encodes a difficult optimization problem whose solution is given by the eigenstate with minimum eigenvalue. By the adiabatic theorem, evolving the eigenstate of the initial Hamiltonian while slowly changing the Hamiltonian into the final one leads to the solution of the difficult optimization problem. Of course we need to know how slowly
HI should be changed into
HF. The adiabatic theorem is at the heart of the quantum approximate optimization algorithm (QAOA), a framework that has been widely used to implement optimization algorithms on existing quantum hardware, because it has low requirements of quantum resources–although it does not guarantee improvements over classical algorithms in general. In this chapter we first discuss the adiabatic theorem, and then give an overview of QAOA.
In adiabatic quantum computing the aim is to track an eigenstate as the Hamiltonian changes. In the usual setup this is achieved using the natural time-dependent Hamiltonian evolution of the system and the main technical tool is the adiabatic theorem. We propose several alternative processes that achieve the same goal, but can easily be implemented on a gate-based quantum computer without the overhead of simulating time-dependent Hamiltonian evolution. We give a general framework for deriving `adiabatic' theorems for these processes.
As an application, we give various algorithms for solving the Quantum Linear Systems Problem (QLSP) with optimal scaling in the condition number. One of these algorithms was previously developed in [Cunningham, Roland 2024] and another can be seen as a randomised version of the discrete adiabatic algorithm of [Costa et al. 2022].
We also describe versions of Trotterisation in our framework, which allows several results from [An et al. 2025] to be reproduced in a randomised setting. In particular, bounds on the Trotter error in terms of the fidelity are obtained that are asymptotically better than the standard bounds.
Abstract In this chapter, we finally have our first look at quantum computing. In particular, we consider adiabatic quantum computing which is a paradigm tailored to the general problem of bipolar QUBO solving. Given our study up to this point, its basic principles will be easy to understand since Hopfield nets for problem solving and adiabatic quantum computing are closely related concepts. Indeed, we already know about tensor products, Hopfield energies and their representation in terms of Hamiltonians, annealing, the axioms of quantum mechanics, the Schrödinger equation, and quantum superposition. All these concepts will now be jointly put to use and brought together with yet another quantum mechanical principle, namely the adiabatic theorem. Based on two examples of simple QUBO problems, we demonstrate how adiabatic quantum computers can explore their exponentially large search spaces in parallel and thus achieve quadratic speedup over classical exhaustive search procedures.
QUBO problems are NP-hard and have wide applications in optimization, including finance, logistics, machine learning, and combinatorial problems. However, classical algorithms employed for solving them can often get stuck in local minima. This paper presents an Adiabatic Quantum Computing (AQC) approach towards finding an optimal solution for QUBO problems. The QUBO problem has been first encoded into Hamiltonians. The adiabatic theorem has been used to achieve success of an AQC solution with a rate which is found to be dependent on relative gap between the ground state and first exited state of the Hamiltonian.
This paper investigates the application of quantum annealing for solving complex combinatorial optimization problems. The core claim is that quantum annealing leverages its global search capabilities to efficiently address such problems. The proposed mechanism involves formulating the combinatorial optimization problem as a quantum annealing problem and utilizing the simulated annealing process within quantum annealing to conduct a search for the optimal solution. This research explores the potential of quantum annealing in practical applications, acknowledging that its application in combinatorial optimization is still in its exploratory phase. The algorithm is designed to minimize the energy of a system described by a Hamiltonian, which evolves over time according to the time-dependent Schrödinger equation. The core of the algorithm lies in mapping the problem's constraints and objective function into this Hamiltonian. The search process is governed by quantum fluctuations, represented by the operator
H^, which encourages transitions to lower energy states, effectively navigating the solution space. The effectiveness of the algorithm is evaluated based on the quality of the solution found and the computational resources required. This work provides a foundational exploration of quantum annealing's potential within the field of combinatorial optimization.
Quantum physics has the potential to revolutionize computer science by building what is called a quantum computer. Quantum computers can perform tasks that are impossible with Turing-machine based classical computers (e.g., generating random sequences of bits) and can outperform classical computers (to different degrees) in a variety of classical computation problems. Several different models of quantum computing exist. Based on the Adiabatic Theorem in physics, Adiabatic Quantum Computing is a novel computing framework that is drastically different from the more traditional quantum logic gate model. Traditionally, quantum computing has only been tested on devices with a very small number of qubits, severely limiting their uses in practice. In recent years however, advances in engineering and physics have allowed the construction for (relatively) large machines called quantum annealers that do what is known as a specific type of adiabatic quantum computation called quantum annealing. Solving classical computation problems with the quantum annealing framework is not an easy task and there are many obstacles to overcome if we want to achieve any kind of speedups over classical algorithms. In this thesis, we present quantum annealing solutions to several classical problems including the Hamiltonian Cycle Problem, Mixed Dominating Set Problem, Graph Isomorphism Problem, Densest k-Subgraph Problem and the Maximum Weighted Independent Set Problem. Experimental results of these quantum solutions on DWave quantum annealers are also reported. We also look at some of the bottlenecks in the quantum annealing framework and propose several novel approach to mitigate their effects on the efficiency of the quantum solutions.