Solving the Graph Isomorphism Problem with a Quantum Annealer

Abstract

We propose a novel method using a quantum annealer -- an analog quantum computer based on the principles of quantum adiabatic evolution -- to solve the Graph Isomorphism problem, in which one has to determine whether two graphs are isomorphic (i.e., can be transformed into each other simply by a relabeling of the vertices). We demonstrate the capabilities of the method by analyzing several types of graph families, focusing on graphs with particularly high symmetry called strongly regular graphs (SRG's). We also show that our method is applicable, within certain limitations, to currently available quantum hardware such as "D-Wave One".

9 pages, 6 figures. arXiv admin note: text overlap with arXiv:1002.3003 by other authors

References in corpus (6)

• Size dependence of the minimum excitation gap in the Quantum Adiabatic Algorithm
• Optimized quantum random-walk search algorithms
• Classical approach to the graph isomorphism problem using quantum walks
• Continuous-time Quantum Walks on a Cycle Graph
• Quantum searches on highly symmetric graphs
• Non-interacting multi-particle quantum random walks applied to the graph isomorphism problem for strongly regular graphs

Cited by in corpus (19)

• Ising formulations of many NP problems
• Adiabatic Quantum Computing
• Group-Invariant Quantum Machine Learning
• Circuit design for multi-body interactions in superconducting quantum annealing system with applications to a scalable architecture
• Driver Hamiltonians for constrained optimization in quantum annealing
• Experimental quantum annealing: case study involving the graph isomorphism problem
• Maximum-Entropy Inference with a Programmable Annealer
• Graph isomorphism and adiabatic quantum computing
• Resource Efficient Gadgets for Compiling Adiabatic Quantum Optimization Problems
• A quantum-walk-inspired adiabatic algorithm for graph isomorphism
• Controlled Online Optimization Learning (COOL): Finding the ground state of spin Hamiltonians with reinforcement learning
• Hearing the Shape of the Ising Model with a Programmable Superconducting-Flux Annealer
• Adiabatic Quantum Optimization for Associative Memory Recall
• Adiabatic quantum optimization in presence of discrete noise: Reducing the problem dimensionality
• What do QAOA energies reveal about graphs?
• Fluctuation guided search in quantum annealing
• Performance Models for Split-execution Computing Systems
• Discriminating Non-Isomorphic Graphs with an Experimental Quantum Annealer
• The quantum algorithm for graph isomorphism problem