Solving the Graph Isomorphism Problem on a Quantum Annealer*

The Graph Isomorphism (GI) problem—the task of deciding whether two graphs are isomorphic—has garnered considerable interest both for its wide range of applications in industry and for its particular computational complexity. One possible approach is measuring certain graph invariants—quantities that remain unchanged under vertex relabeling. While a complete graph invariant that would unequivocally distinguish non-isomorphic graphs is yet unknown, the energy spectrum of the quantum Ising Hamiltonian is a possible candidate. This is the Hamiltonian implemented by commercially available quantum annealers, making quantum annealing a natural tool for solving certain hard instances of the GI problem. Following the lead of previous work, we use a D-Wave quantum annealer to distinguish between pairs of graphs with the same classical Ising spectrum by gathering statistics on the energy and other observables. We show that introducing a pause at intermediate points in the anneal yields clearly different results for graphs that had previously been undistinguishable using standard annealing schedules.