Testing graph isomorphism using simple quantum circuits
Abstract
The graph isomorphism problem asks whether two graphs are equivalent up to a permutation of their vertices. Its precise computational complexity remains unresolved, and it is still unknown whether a polynomial-time algorithm exists. We investigate whether simple graph-dependent Instantaneous Quantum Polynomial-time (IQP) and Quantum Approximate Optimisation Algorithm (QAOA) circuits can distinguish non-isomorphic graphs. We first show that suitable IQP and QAOA constructions allow the underlying graph to be reconstructed using a polynomial number of samples. Building on previous work using the QAOA energy, we show that Hamming weight distributions can distinguish graph pairs at circuit depths for which the numerically computed energy gap is zero. We then apply graph invariants to the matrix of ZZ correlators on the output distribution. For the specific case of the graph spectrum, at QAOA depth p=2, this invariant numerically distinguishes all 10,486 cospectral regular graph pairs tested on up to 18 vertices. For IQP circuits, we introduce a finer invariant based on probability multiplicities within Hamming weight sectors, which distinguishes every non-isomorphic graph pair tested numerically. Finally, we derive exact graph-theoretic characterisations of the IQP output distribution at θ=π/2 and θ=π/4. These results show that simple graph-dependent quantum circuits encode substantial structural information, while leaving open whether this information can be extracted efficiently for general graph isomorphism.
Related
- Near-optimal quantum query lower bounds on bipartiteness and expansion testing in the bounded-degree graph model
- Quantum state isomorphism problems for groups
- Random quantum circuits, chaos and quantum thermalization
- Quantum Hierarchical Reinforcement Learning via Variational Quantum Circuits
- A New Method For Manipulating Circuits, Application To Quantum Adders
BibTeX
@misc{beasley2026testing,
title = {{Testing graph isomorphism using simple quantum circuits}},
author = {Samuel Beasley and Ashley Montanaro},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.19962},
eprint = {2610.19962},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.19962},
}
RIS
TY - UNPB
TI - Testing graph isomorphism using simple quantum circuits
AU - Samuel Beasley
AU - Ashley Montanaro
PY - 2026
DA - 2026/10/14
PB - arXiv
DO - 10.48550/arxiv.2610.19962
UR - https://arxiv.org/abs/2610.19962
AB - The graph isomorphism problem asks whether two graphs are equivalent up to a permutation of their vertices. Its precise computational complexity remains unresolved, and it is still unknown whether a polynomial-time algorithm exists. We investigate whether simple graph-dependent Instantaneous Quantum Polynomial-time (IQP) and Quantum Approximate Optimisation Algorithm (QAOA) circuits can distinguish non-isomorphic graphs. We first show that suitable IQP and QAOA constructions allow the underlying graph to be reconstructed using a polynomial number of samples. Building on previous work using the QAOA energy, we show that Hamming weight distributions can distinguish graph pairs at circuit depths for which the numerically computed energy gap is zero. We then apply graph invariants to the matrix of ZZ correlators on the output distribution. For the specific case of the graph spectrum, at QAOA depth p=2, this invariant numerically distinguishes all 10,486 cospectral regular graph pairs tested on up to 18 vertices. For IQP circuits, we introduce a finer invariant based on probability multiplicities within Hamming weight sectors, which distinguishes every non-isomorphic graph pair tested numerically. Finally, we derive exact graph-theoretic characterisations of the IQP output distribution at θ=π/2 and θ=π/4. These results show that simple graph-dependent quantum circuits encode substantial structural information, while leaving open whether this information can be extracted efficiently for general graph isomorphism.
ER -