Discriminating nonisomorphic graphs with an experimental quantum annealer
Zoe Gonzalez Izquierdo, Ruilin Zhou, Klas Markström, Itay Hen · Physical Review A · 2020
We demonstrate experimentally the ability of a quantum annealer to distinguish between sets of nonisomorphic graphs that share the same classical Ising spectrum. Utilizing the pause-and-quench features recently introduced into D-Wave quantum annealing processors, which allow the user to probe the quantum Hamiltonian realized in the middle of an anneal, we show that obtaining thermal averages of diagonal observables of ``classically indistinguishable'' nonisomorphic graphs encoded into transverse-field Ising Hamiltonians enable their discrimination. We discuss the significance of our results in the context of the graph isomorphism problem.