In this thesis, we investigate the solving of NP-hard optimization problems using quantum annealers. We start by describing how the field of quantum computing began to develop and where it stands today. We list some of the commercial quantum service providers, with more attention given to D-Wave Systems, as computation on their quantum annealers is the focus of this thesis. This is followed by a chapter on the operation process of D-Wave quantum annealers and the physical principles underlying their operation. The aim is to establish an intuition for how a quantum annealer works in the first place. This is followed by a chapter on transforming optimization problems into a form suitable for quantum annealers.
With this knowledge, we will then address the maximum independent set problem (sometimes called maximum stable set problem). We will define the problem and convert it into a suitable form for use on a quantum annealer. In doing so, we will demonstrate which other forms are equally valid but less suitable. We will then solve the maximum independent set problem on some classical graphs. Additionally, we will explain how to process the results to extract the best possible solution. We will proceed to reduce the size of the input data to facilitate the computation of this problem. This will be achieved by splitting the problem into several smaller sub-problems and removing input data that does not affect the final solution. This will enable us to compute the problem on some instances of the problem that were previously too large to handle on the quantum annealer. Finally, we will derive an algorithm that allows us to determine a (not necessarily tight) upper bound and present some ideas for further exploration and improvement.
|
