Abstract:
The commercial D-Waves quantum annealer has given rise to plenty of interests due to the reported quantum speedup against classical annealing. In order to make use of this new technology, a problem must be formulated into a form of quadratic unconstrained binary optimization (QUBO) or Ising model. This thesis reports on case studies using a D-Wave quantum annealer to solve several optimization problems and providing results validation using classical exact approaches. In our thesis, we briefly introduce several classical techniques designed for QUBO problems and implement two exact approaches. With the proper tools, a D-Wave 2X computer consisted of 1098 active qubits is then evaluated for the Degree-Constrained Minimum Spanning Tree and the Steiner Tree problems, establishing their QUBO formulations are suitable for adiabatic quantum computers. Motivated by the remarkable performance, two more optimization problems are studied—the Bounded-Depth Steiner Tree problem and the Chromatic Sum problem. We propose a new formulation for each problem. The numbers of qubits (dimension of QUBO matrices) required by our formulations are O(|V|3) and O(|V|2) respectively, where |V| represents the number of vertices.