# Graph isomorphism and adiabatic quantum computing

arXiv: https://arxiv.org/abs/1304.5773 · HTML: https://mlsanity.com/paper/1304.5773/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 21 Apr 2013.

## Built on by (most cited first, 7 of 7)

- [Group-Invariant Quantum Machine Learning](https://mlsanity.com/paper/2205.02261/) (2022)
- [Quantum Permutation Synchronization](https://mlsanity.com/paper/2101.07755/) (2021)
- [Adiabatic Quantum Graph Matching with Permutation Matrix Constraints](https://mlsanity.com/paper/2107.04032/) (2021)
- [Agent-Q: Fine-Tuning Large Language Models for Quantum Circuit Generation and Optimization](https://mlsanity.com/paper/2504.11109/) (2025)
- [QUASAR: Quantum Assembly Code Generation Using Tool-Augmented LLMs via Agentic RL](https://mlsanity.com/paper/2510.00967/) (2025)
- [QuAnt: Quantum Annealing with Learnt Couplings](https://mlsanity.com/paper/2210.08114/) (2022)
- [Learning structural balance of graphs from quantum spectral features](https://mlsanity.com/paper/2609.11736/) (2026)

## Abstract (arXiv)

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.