Abstract:
Quantum Computing is one of the most exciting and potentially societychanging elds in contemporary science and engineering research. While the potential power of quantum computers has been known since 1981, scepticism in their long-term practical capabilities has been rife due to limited success in physically building scalable quantum computers. Recent breakthroughs have increased hope however; chief among these was the development of a series of quantum computers by D-Wave Systems | a Canadian specialist quantum computing company. To solve a problem on a D-Wave device, it must be formulated in QUBO or Ising model form. The key determinants of a formulation's e cacy are the number of variables it uses, and its density. The smaller these are the better. In this thesis, we signi cantly improve the QUBO formulations for ve NPhard graph problems in this regard. For four of these problems featuring a graph with jV j vertices, O(jV j2)-variable and O(jV j3)-density formulations are given in place of preceding formulations which at-best used O(jV j3) variables and O(jV j4) density. We improve one other problem's formulation so it uses O(jV j3) variables and O(jV j5) density; its previous-best used O(jV j3 log(jV j)2)) variables and O(jV j6 log(jV j)4) density.
