Asymptotic scaling of the minimum spectral gap of the quantum-walk-inspired adiabatic algorithm for graph isomorphism

Tamascelli and Zanetti (2014) encoded the graph isomorphism problem as the satisfiability of a 2-SAT formula over an n×n grid of qubits whose dynamics is restricted, by the structure of the initial Hamiltonian, to the space of functions from vertices to vertices; the final Hamiltonian is 2-local and stoquastic, and frustration-free exactly when the two input graphs are isomorphic. The efficiency of the resulting adiabatic algorithm is controlled by the minimum spectral gap of the linear interpolation between the two Hamiltonians, for which only positivity on finite instances (via Perron–Frobenius) is known. Whether this gap is bounded below by an inverse polynomial in n or can become exponentially small — equivalently, whether the annealing time is polynomial, sub-exponential, or exponential — remains unresolved, and the existing empirical evidence (exact diagonalization up to n≈7; quantum Monte Carlo emulation of coherent dynamics up to n=12–17, fitting $O(2^{\sqrt{n}\log n})$ ) is unfaithful or too small to settle it. Determining this scaling, analytically or by faithful large-scale simulation/experiment, is the open problem.

Background

The graph isomorphism problem (GI) asks whether two graphs $G_1=(V,E_1)$ and $G_2=(V,E_2)$ on the same vertex set coincide up to a relabeling of vertices, i.e. whether some permutation $\pi$ maps $G_1$ onto $G_2$ . GI is in NP but believed to be neither NP-complete nor in P, and the best general classical algorithm (Babai, STOC 2016) runs in quasipolynomial time $\exp(O(\log^c n))$ . Adiabatic quantum computation (AQC), introduced by Farhi, Goldstone, Gutmann, Lapan, Lundgren, and Preda (Science 292, 472, 2001), solves a problem by preparing the easily prepared ground state of an initial Hamiltonian $H_I$ and slowly evolving to a final Hamiltonian $H_f$ whose ground state encodes the answer, under the linear schedule $H(s)=(1-s)H_I+sH_f$ , $0\le s\le 1$ . The adiabatic theorem guarantees the evolution stays near the instantaneous ground state provided the total time $T$ is large compared with $\epsilon/g_{\min}^2$ , where $g_{\min}$ is the minimum over $s$ of the gap between the ground level of $H(s)$ and the first distinct excited level above it (the ground-level gap, defined precisely in the Problem Statement) and $\epsilon$ bounds the matrix element of $dH/ds$ between those states; $\epsilon$ is typically polynomial in the system size, so the scaling of $g_{\min}$ decides whether the algorithm is efficient. Prior quantum approaches to GI fall into two classes. Witness-based schemes compare single- or multi-particle continuous-time quantum walks (coherent evolution of a particle hopping along graph edges, e.g. Gamble, Friesen, Zhou, Joynt, and Coppersmith, Phys. Rev. A 81, 052313, 2010) or adiabatically evolved observables (Hen and Young, Phys. Rev. A 86, 042310, 2012; Gaitan and Clark, Phys. Rev. A 89, 022342, 2014; Vinci, Markström, Boixo, Roy, Spedalieri, Warburton, and Severini, arXiv:1307.1114) on the two graphs, but are not guaranteed to distinguish all non-isomorphic pairs. Tamascelli and Zanetti (J. Phys. A 47, 325302, 2014) instead search directly for the isomorphism: each of the $n^2$ Boolean variables $x_{i,j}$ ('vertex $i$ of $G_1$ maps to vertex $j$ of $G_2$ ') is a qubit, arranged in an $n\times n$ grid; the cost function penalizing non-isomorphism-inducing assignments and row/column degeneracy reduces, within the subspace carrying exactly one excitation per row, to a 2-SAT formula, encoded as a 2-local diagonal penalty Hamiltonian $H_f$ . The initial Hamiltonian $H_I$ is a sum of nearest-neighbor XY exchange terms along each row (the XY exchange is the two-qubit interaction that swaps a single excitation between neighboring qubits and so conserves the excitation count; each row therefore performs an independent continuous-time quantum walk on a line); it preserves the one-excitation-per-row sector, so the dynamics explores only the $n^n$ -dimensional space of functions from $\{1,\dots,n\}$ to itself rather than all $2^{n^2}$ configurations. $H_f$ is stoquastic (off-diagonal matrix elements non-positive in the computational basis, so the ground state has non-negative amplitudes by Perron–Frobenius) and frustration-free (admitting a configuration violating no clause, equivalently a zero-energy ground state) exactly when $G_1\cong G_2$ ; the relevance of these properties to classical simulability is tied to results such as Bravyi and Terhal's study of stoquastic frustration-free Hamiltonians (SIAM J. Comput. 39, 1462, 2009). The authors prove only $g_{\min}>0$ for every finite instance (Perron–Frobenius), compute the gap by exact diagonalization only up to $n\le 6$ – $7$ vertices, and estimate annealing times for larger instances (random graphs to $n=12$ , and strongly regular graphs — graphs in which the number of common neighbors of any two distinct vertices depends only on whether they are adjacent, a class that provides hard GI instances — to $n=17$ ) using world-line quantum Monte Carlo (QMC) — a method not guaranteed to emulate the coherent adiabatic dynamics. The measured times fit $O(2^{\sqrt{n}\log n})$ , the same scaling class as the then-best classical algorithms, and small-gap failures of adiabatic optimization on other problems are known to occur (Altshuler, Krovi, and Roland, PNAS 107, 12446, 2010: Anderson localization of the ground state produces exponentially small gaps), so no efficiency conclusion can be drawn.

Problem Statement

Determine the asymptotic scaling with the number of vertices $n$ of the minimum spectral gap $g_{\min}=\min_{0\le s\le 1}\big(e_1(s)-e_0(s)\big)$ , where $e_0(s)$ is the ground-state energy of the interpolating Hamiltonian $H(s)=(1-s)H_I+sH_f$ of Tamascelli and Zanetti and $e_1(s)$ is the lowest energy level strictly above $e_0(s)$ , so that $g_{\min}$ is the gap between the ground level and the first distinct excited level (the final ground space of $H_f$ is degenerate for non-rigid isomorphic inputs — its zero-energy configurations are the $|\mathrm{Aut}(G_1)|$ isomorphisms — so the literal two-lowest-eigenvalue reading would vanish identically, while the ground-level gap is the quantity that controls the adiabatic runtime), where $H_I$ is the sum of nearest-neighbor XY exchange terms along the rows of the $n\times n$ qubit grid (restricted to the sector with exactly one excitation per row) and $H_f$ is the 2-local diagonal clause-penalty Hamiltonian of Section III of the source, encoding a GI instance $(G_1,G_2)$ as a 2-SAT formula (the source's Eq. (9)). Equivalently: decide whether the adiabatic runtime $T\propto 1/g_{\min}^2$ for this algorithm is polynomial, sub-exponential, or exponential in $n$ . A complete answer takes one of the forms: (a) a rigorous proof that $g_{\min}$ is bounded below by an inverse polynomial in $n$ for all instances (or for the class of isomorphic instances $G_2=\pi(G_1)$ , whose frustration-free $H_f$ is the case the algorithm is designed to solve), establishing a polynomial-time adiabatic algorithm for GI along this route in the corresponding scope (all instances, or the isomorphic class); or (b) a rigorous construction of a family of GI instances whose interpolating Hamiltonians have $g_{\min}$ exponentially small in $n$ (with the near-degeneracy of the low-lying energy levels of the constructed family verified), showing the algorithm is not efficient on those instances; or (c) a determination that $g_{\min}$ lies in an intermediate class — neither bounded below by an inverse polynomial in $n$ nor exponentially small — with its scope (all instances, the isomorphic class named in (a), or a named family) and its standard (rigorous proof, or the faithful simulation/experiment of the sentence below) stated explicitly. Because the question is about the coherent quantum dynamics, an empirical contribution resolves the same objective only if it faithfully emulates that dynamics — e.g. exact or certified diagonalization/simulation at substantially larger $n$ than the source's $n\le 7$ , or a quantum-hardware implementation — and thereby pins down the annealing-time scaling that the source's unfaithful quantum Monte Carlo emulation could only suggest. The source's subsidiary heuristics — the random-relabeling 'Permutation Trick' and the conjecture that frustration-free instances are systematically easier — remain open side issues connected to the same objective but are not themselves required deliverables.

References

Dario Tamascelli and Luca Zanetti, 'A quantum-walk-inspired adiabatic algorithm for solving graph isomorphism problems', J. Phys. A: Math. Theor. 47, 325302 (2014). DOI: 10.1088/1751-8113/47/32/325302; arXiv:1401.1278; https://arxiv.org/abs/1401.1278
László Babai, 'Graph isomorphism in quasipolynomial time [extended abstract]', in Proceedings of the 48th Annual ACM Symposium on Theory of Computing (STOC 2016), pp. 684–697. DOI: 10.1145/2897518.2897542; https://doi.org/10.1145/2897518.2897542
Edward Farhi, Jeffrey Goldstone, Sam Gutmann, Joshua Lapan, Andrew Lundgren, and Daniel Preda, 'A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem', Science 292, 472 (2001). DOI: 10.1126/science.1057726; https://doi.org/10.1126/science.1057726
John King Gamble, Mark Friesen, Dong Zhou, Robert Joynt, and S. N. Coppersmith, 'Two-particle quantum walks applied to the graph isomorphism problem', Phys. Rev. A 81, 052313 (2010). DOI: 10.1103/PhysRevA.81.052313; https://doi.org/10.1103/PhysRevA.81.052313
Itay Hen and A. P. Young, 'Solving the graph-isomorphism problem with a quantum annealer', Phys. Rev. A 86, 042310 (2012). DOI: 10.1103/PhysRevA.86.042310; https://doi.org/10.1103/PhysRevA.86.042310
Walter Vinci, Klas Markström, Sergio Boixo, Aidan Roy, Federico M. Spedalieri, Paul A. Warburton, and Simone Severini, 'Hearing the Shape of the Ising Model with a Programmable Superconducting-Flux Annealer' (2013). arXiv:1307.1114; https://arxiv.org/abs/1307.1114
Frank Gaitan and Lane Clark, 'Graph isomorphism and adiabatic quantum computing', Phys. Rev. A 89, 022342 (2014). DOI: 10.1103/PhysRevA.89.022342; https://doi.org/10.1103/PhysRevA.89.022342
Boris Altshuler, Hari Krovi, and Jérémie Roland, 'Anderson localization makes adiabatic quantum optimization fail', Proc. Natl. Acad. Sci. USA 107, 12446 (2010). DOI: 10.1073/pnas.1002116107; https://doi.org/10.1073/pnas.1002116107
Sergey Bravyi and Barbara Terhal, 'Complexity of Stoquastic Frustration-Free Hamiltonians', SIAM J. Comput. 39, 1462 (2009). DOI: 10.1137/08072689X; https://doi.org/10.1137/08072689X
Kenneth M. Zick, Omar Shehab, and Matthew French, 'Experimental quantum annealing: case study involving the graph isomorphism problem', Sci. Rep. 5, 11168 (2015). DOI: 10.1038/srep11168; https://doi.org/10.1038/srep11168
Yukun Wang, Yingtong Shen, Lu Cao, Wenmin Han, Zhichao Zhang, and Linchun Wan, 'RBM-based simulated quantum annealing for graph isomorphism problems', Phys. Lett. A 587, 131719 (2026). DOI: 10.1016/j.physleta.2026.131719; arXiv:2503.07749; https://doi.org/10.1016/j.physleta.2026.131719