Abstract

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 …

Date

2020

Authors

Zoe Gonzalez Izquierdo, Itay Hen, Ruilin Zhou

Journal

Bulletin of the American Physical Society

Volume

65

Publisher

American Physical Society