Abstract:
We study two types of problems in this thesis, graph covering problems including the Dominating Set and Edge Cover which are classic combinatorial problems and the Graph Isomorphism Problem with several of its variations. For each of the problems, we provide efficient quadratic unconstrained binary optimization (QUBO) formulations suitable for adiabatic quantum computers, which are viewed as a real-world enhanced model of simulated annealing. The number of qubits (dimension of QUBO matrices) required to solve the graph covering problems are O(n + n lg n) and O(m + n lg n) respectively, where n is the number of vertices and m is the number of edges. We also extend our formulations for the Minimum Vertex- Weighted Dominating Set problem and Minimum Edge-Weighted Edge Cover problem. For the Graph Isomorphism Problem, we provide two QUBO formulation through two approaches both requiring O(n2) variables. We also provide several different formulations for two extensions of the Graph Isomorphism Problems each requiring a different number of variables ranging from O(n1n2) to O((n1 + 1)n2). We also provide some experimental results using a D-Wave 2X quantum computer with 1098 active qubit-coupled processors on the problems studied here for a selection of known common graphs.
