arXiv:2610.19962
Testing graph isomorphism using simple quantum circuits
Samuel Beasley, Ashley Montanaro
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.
AI Summary
The paper asks whether graph-dependent IQP and QAOA output distributions provide graph-isomorphism tests beyond the QAOA energy. It studies Hamming-weight distributions, spectra of two-qubit $ZZ$ correlation matrices, and multiplicities of individual outcome probabilities within Hamming-weight sectors. Small-angle perturbative arguments show that labelled adjacency information can be reconstructed with polynomially many samples: $n^{13}$ for an explicit IQP construction and $\widetilde O(n^8)$ for depth-one QAOA. This establishes information retention, not an efficient isomorphism algorithm. Statevector simulations find that Hamming-weight distributions distinguish circular/Möbius ladder pairs on 16 and 20 vertices already at $p=1$, whereas computed energy gaps become nonzero only at $p=4$ and $p=5$, respectively. At $p=2$, the $ZZ$ correlation spectrum numerically distinguishes all 10,486 tested cospectral regular graph pairs, on up to 18 vertices. A concentration argument gives a sufficient sample bound $O(n^2\log n/\delta^2)$ to estimate an average spectral gap $\delta$ to fixed relative accuracy. For IQP, Hamming-weight distributions fail on some seven-vertex pairs, while probability multiplicities distinguish every tested non-isomorphic pair. Exact characterisations give degree-parity output at $\theta=\pi/2$ and uniform affine-subspace support determined by the binary degree-parity Laplacian at $\theta=\pi/4$. Completeness and efficient distinguishability remain conjectural: depth, parameter selection, and potentially vanishing statistical gaps are unresolved. Probability multiplicities may require exponentially many outcomes and are numerically fragile. Simulations use exact floating-point equality without tolerances, so reported distinctions and zeros are not analytic certificates. No hardware experiments are reported.
We have used LLMs for finding relevant references, feedback on our text, to help improve the clarity of the exposition, to check correctness of results, as well as for some coding tasks.
Central claim may not hold: The claim that all 10,486 tested pairs have distinguishable ZZ correlation spectra lacks numerical validation because any nonzero floating-point eigenvalue difference counts as a distinction without a bound separating it from round-off. The IQP all-pairs distinguishability result relies on exact equality of floating-point probabilities, which can produce spurious differences in probability multiplicities without an error-controlled check.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
- Comments
- 35 pages, 11 figures