Adiabatic Quantum Computing for Optimization Problems with a Case Study on the Maximum Independent Set Problem

With the increasing attention and investments drawn to the Quantum Computing field, a number of different technologies and multiple algorithms have emerged in an effort to study the capabilities of this innovative computing paradigm. The thesis covers the study of the Quantum Computing formalism, the peculiarities characterizing different technologies and the potential use cases that are expected to benefit from applying Quantum Computing techniques, specifically in Combinatorial Optimization. The difference between the two main approaches of quantum computing, Digital Quantum Computing and Analog Hamiltonian Simulation, was studied. While the former performs computation with Quantum Gates and Circuits, the latter simulates complex quantum systems by replicating their Hamiltonian dynamics described by the Schrödinger equation. Among the methodologies of Analog Hamiltonian Simulation, Adiabatic Quantum Computing solves optimization problems by evolving a quantum system's Hamiltonian from its initial state to its final state, following the Adiabatic Theorem, wherein if the Hamiltonian changes slowly enough, a quantum system remains in its instantaneous ground state. In this work, this approach was directly applied to solve a specific combinatorial optimization problem, the Maximum Independent Set (MIS) problem, using two quantum annealers. The first, D-Wave, utilizes superconducting qubits, while the second, QuEra, is an emerging technology that exploits neutral atoms as computational units. This cutting-edge technology was studied in detail. In this regard, the neutral atom was defined and its possible states were analyzed, specifically identifying the Rydberg atom. The constituent components of QuEra’s hardware were examined, as well as the techniques used for preparing atomic states and their dynamic evolution over time. Subsequently, the MIS problem was defined, and through examples, various real-world applications were described, underlining that a graph can have multiple MISs and, for this reason, the solution to the MIS problem may not be unique. Finally, the context of the MIS problem applied in this work was outlined, focusing on identifying the companies with the highest financial risk within a pool, located at the vertices of a graph whose edges are defined based on the covariance values between the companies. The solution to this problem is represented by the Minimum Vertex Cover of the reference graph, which is the complementary set of vertices of the Maximum Independent Set. It is important to note that, at the time of writing, it was not possible to solve the problem using QuEra's QPU. Instead, a local Analog Hamiltonian Simulator was used, which operates with only about ten atoms and thus limiting the problem size. The parameters of the problem defining the reference Unit Disk Graph were then defined, followed by focusing on all the steps that allowed the implementation of the algorithm. The solutions were saved, followed by post-processing and analysis of the results. This problem was then solved using D-Wave's QPU, enabling a comparison between results obtained from two technologies based on the same resolution principle but using different approaches. After evaluating the quality of the results, companies common to all solutions were identified, highlighting the need to conduct market analysis on non-included companies to determine the most advantageous financial solution.