Graph isomorphism and adiabatic quantum computing

Abstract

In the Graph Isomorphism problem two N-vertex graphs G and G' are given and the task is to determine whether there exists a permutation of the vertices of G that preserves adjacency and transforms G into G'. If yes, then G and G' are said to be isomorphic; otherwise they are non-isomorphic. The GI problem is an important problem in computer science and is thought to be of comparable difficulty to integer factorization. In this paper we present a quantum algorithm that solves arbitrary instances of GI and can also determine all automorphisms of a given graph. We show how the GI problem can be converted to a combinatorial optimization problem that can be solved using adiabatic quantum evolution. We numerically simulate the algorithm's quantum dynamics and show that it correctly: (i) distinguishes non-isomorphic graphs; (ii) recognizes isomorphic graphs; and (iii) finds all automorphisms of a given graph G. We then discuss the GI quantum algorithm's experimental implementation, and close by showing how it can be leveraged to give a quantum algorithm that solves arbitrary instances of the NP-Complete Sub-Graph Isomorphism problem.

22 pages; 18 figures; and 6 tables; version to appear in Physical Review A

References in corpus (4)

• Ground State Spin Logic
• Non-interacting multi-particle quantum random walks applied to the graph isomorphism problem for strongly regular graphs
• Resource Efficient Gadgets for Compiling Adiabatic Quantum Optimization Problems
• Solving the Graph Isomorphism Problem with a Quantum Annealer

Cited by in corpus (26)

• Adiabatic Quantum Computing
• Quantum information processing with superconducting circuits: a review
• Group-Invariant Quantum Machine Learning
• Quantum Annealing for Constrained Optimization
• Bayesian Network Structure Learning Using Quantum Annealing
• Driver Hamiltonians for constrained optimization in quantum annealing
• Experimental quantum annealing: case study involving the graph isomorphism problem
• Graph isomorphism and Gaussian boson sampling
• Constrained quantum annealing of graph coloring
• An Integrated Programming and Development Environment for Adiabatic Quantum Optimization
• Adiabatic Quantum Optimization for Associative Memory Recall
• Theorem on the existence of a nonzero energy gap in adiabatic quantum computation
• Collective dynamics of phase-repulsive oscillators solves graph coloring problem
• Agent-Q: Fine-Tuning Large Language Models for Quantum Circuit Generation and Optimization
• Localization in the constrained quantum annealing of graph coloring
• On quantum invariants and the graph isomorphism problem
• Optimization on Large Interconnected Graphs and Networks Using Adiabatic Quantum Computation
• Performance Models for Split-execution Computing Systems
• Discriminating Non-Isomorphic Graphs with an Experimental Quantum Annealer
• The quantum algorithm for graph isomorphism problem
• Tensor Decompositions and Adiabatic Quantum Computing for Discovering Practical Matrix Multiplication Algorithms
• Simon's Period Finding on a Quantum Annealer
• Bayesian Networks based Hybrid Quantum-Classical Machine Learning Approach to Elucidate Gene Regulatory Pathways
• Adiabatic Quantum Graph Matching with Permutation Matrix Constraints
• An Adiabatic Quantum Algorithm for Determining Gracefulness of A Graph
• Effects of Graph Network Connections on The Efficiency of Quantum Annealing