Asymptotic minimum-gap scaling, avoided-crossing structure, and stoquasticity limits of the quantum adiabatic algorithm on random 3-regular Max-Cut instances

The quantum adiabatic algorithm (QAA) applied to random instances of Max-Cut on 3-regular graphs, with the standard stoquastic transverse-field interpolation, was shown by Farhi, Gosset, Hen, Sandvik, Shor, Young, and Zamponi (Phys. Rev. A 86, 052334, 2012) to run into very small spectral gaps not at the second-order quantum phase transition (near s = 0.36, where the gap decreases only polynomially) but deep in the spin-glass phase at larger s, with finite-size fits favoring an exponentially small median gap although a stretched-exponential fit was also satisfactory. That work left open the precise large-N asymptotics of the typical (median and higher-quantile) minimum gap; the existence and severity of additional avoided crossings for s beyond the range 0.3 ≤ s ≤ 0.5 accessible to its quantum Monte Carlo (QMC) simulations; the accuracy of the one-step replica-symmetry-breaking (1RSB) quantum cavity approximation (the first level of the replica-symmetry-breaking hierarchy used to describe fragmented low-temperature Gibbs measures) with Parisi parameter m = 0 relative to the true thermodynamic limit; whether stoquastic interpolating Hamiltonians are inherently less powerful than general (nonstoquastic) or non-monotonic interpolation paths; and the effect of the QMC instance-selection restrictions on these conclusions. These questions remain open in the literature.

Background

The quantum adiabatic algorithm (QAA) attempts to solve a combinatorial optimization problem by preparing the ground state of a simple driver Hamiltonian $H_B$ (here a transverse magnetic field $-\sum_i\sigma^x_i$) and slowly deforming the Hamiltonian to the classical problem Hamiltonian $H_P$ whose ground state encodes the solution, following the interpolating path $H(s)=(1-s)H_B+sH_P$ with $0\le s\le 1$ (Farhi, Gosset, Hen, Sandvik, Shor, Young, and Zamponi, Phys. Rev. A 86, 052334 (2012)). By the quantum adiabatic theorem, the running time required to stay in the instantaneous ground state scales as the inverse square of the minimum eigenvalue gap $\Delta_{\min}$ between the ground state and the first excited state along the path, so the size dependence of $\Delta_{\min}$ determines the algorithm's complexity. Max-Cut is the NP-hard problem of partitioning the vertices of a graph into two sets so as to maximize the number of edges connecting the sets; on a random 3-regular graph (every vertex has degree 3) it maps to an antiferromagnetic Ising spin glass, i.e. an Ising model with random frustrated interactions that cannot all be minimized simultaneously, producing a rugged energy landscape with many competing low-energy states; the number of clauses is $M=3N/2$ for $N$ spins. Its clause structure is similar to 3-XORSAT (linear equations over three bits, also defined on 3-regular hypergraphs, i.e. 3-uniform hypergraphs in which every variable appears in exactly three clauses), for which Jörg, Krzakala, Semerjian, and Zamponi (Phys. Rev. Lett. 104, 207206 (2010)) had shown that the QAA fails through a first-order quantum phase transition with an exponentially small gap.

A Hamiltonian is called stoquastic when all its off-diagonal matrix elements in the computational (product) basis are real and non-positive; such Hamiltonians can be simulated by sign-problem-free quantum Monte Carlo (QMC), because their ground-state amplitudes in that basis can be chosen non-negative, whereas general nonstoquastic Hamiltonians generically suffer the QMC sign problem (severe cancellations making Monte Carlo sampling exponentially inefficient). Stoquasticity is therefore what made the source paper's numerics possible, and it motivated its question of whether this class of easily-simulable interpolations is also computationally weaker.

In the source paper, QMC (path-integral Monte Carlo, which samples the quantum model as a classical system in an extra imaginary-time dimension, combined with parallel tempering, an enhanced-sampling method that swaps configurations between simulations at different effective temperatures to overcome energy barriers, projected onto the symmetry-even subspace, for $N$ up to 160 and roughly 50 instances per size) found for random 3-regular Max-Cut a second-order (continuous) quantum phase transition at $s_c\simeq 0.36$ with gaps decreasing only polynomially with $N$, but also very small gaps at $s>s_c$ in the spin-glass phase. Fits to the global minimum gap over the studied interval preferred an exponentially decreasing median gap over a polynomial one, while a stretched-exponential fit (of the form $\exp(-aN^b)$ with $0<b<1$) was also satisfactory, so the asymptotic behavior was left undecided; the gap distribution showed heavy-tailed instance-to-instance fluctuations, and deep minima became more prevalent with increasing $N$. The QMC study was restricted to $0.3\le s\le 0.5$ (equilibration of QMC becomes exponentially hard as $s\to 1$) and, for technical convenience, to instances whose problem Hamiltonian has exactly two minimal-energy states (the minimum allowed by the global spin-flip symmetry) and a fixed ground-state energy ($N/8$ in the paper's units), an exponentially rare subset of the full random ensemble. In parallel, the quantum cavity method (a message-passing technique, exact on the Bethe lattice — the infinite graph that is locally a tree, which large random 3-regular graphs approximate locally — that treats the transverse-field model in imaginary time, and exact for locally treelike graphs if correlation decay assumptions hold) was applied to the full random ensemble: for 3-regular 3-XORSAT the replica-symmetric (RS) cavity works, while for 3-regular Max-Cut the one-step replica-symmetry-breaking (1RSB) approximation was used with fixed Parisi parameter $m=0$ (the zero-temperature limit of the RSB construction, which accounts for the equilibrium Gibbs measure fragmenting into many pure states, i.e. mutually non-communicating low-energy components) and finite population sizes $N_D$, $N_R$; the authors noted that for the classical 3-regular spin glass neither RS nor 1RSB is exact and full (infinite-step) RSB is widely believed to be needed, leaving the accuracy of 1RSB($m=0$) for the quantum problem unresolved. The small gaps at $s>s_c$ may be associated with perturbative crossings, i.e. level crossings between the ground state and low-energy localized configurations that occur at weak transverse field, a mechanism described by Altshuler, Krovi, and Roland (Proc. Natl. Acad. Sci. 107, 12446 (2010); the arXiv preprint carries the variant title 'Anderson localization casts clouds over adiabatic quantum optimization') as an Anderson-localization-type failure of adiabatic quantum optimization (Anderson localization is the freezing of a quantum particle's wavefunction by strong disorder; here the low-energy perturbations localize on a few spins instead of spreading). The review of Bapst, Foini, Krzakala, Semerjian, and Zamponi (Phys. Rep. 2013) summarizes this statistical-mechanics perspective on the QAA, including the continuum of avoided crossings expected in the weakly quantum spin-glass phase.

Problem Statement

The common objective is to establish, with quantitative and methodologically controlled evidence, the true asymptotic performance of the quantum adiabatic algorithm on the random 3-regular Max-Cut ensemble with the standard stoquastic transverse-field interpolation, and to determine whether its identified small-gap failure mechanism is intrinsic or can be avoided by other interpolation paths. Specifically, the unresolved questions are: (1) the precise large-$N$ scaling of the typical (median and higher-quantile) global minimum gap of $H(s)=(1-s)H_B+sH_P$ over the full path $0\le s\le 1$ — whether it is exponential, stretched-exponential, or a crossover form — given that finite-size fits up to $N\approx 160$ prefer exponential over polynomial but admit stretched-exponential fits, that the critical-region minima near $s_c\simeq 0.36$ scale only polynomially, and that the gap distribution is heavy-tailed with deep minima becoming more prevalent as $N$ grows; (2) whether additional avoided crossings exist generically at $s>0.5$ (the region inaccessible to the original quantum Monte Carlo equilibration), and whether they further reduce the typical gap; (3) whether the 1RSB quantum cavity computation with fixed Parisi parameter $m=0$ is exact for the thermodynamic limit of this quantum model, or whether further replica-symmetry-breaking steps (full RSB) are required, including a systematic assessment of the dependence on $m$ and on the population sizes; (4) whether stoquastic interpolating Hamiltonians are inherently less powerful than general nonstoquastic (or non-monotonic) interpolation paths for these ensembles, i.e. whether an alternative path can avoid the small-gap bottlenecks; and (5) how the quantum Monte Carlo instance-selection restrictions (exponentially rare instances with exactly two ground states and fixed ground-state energy) affect the median-gap scaling and the comparison between finite-$N$ quantum Monte Carlo results and thermodynamic cavity predictions. A complete answer would settle the asymptotic running time of the QAA on this ensemble, identify the location and mechanism of the controlling avoided crossings, validate (or correct) the cavity description of the quantum spin-glass phase, resolve whether escaping stoquasticity is or is not a route to efficient adiabatic optimization here, and establish how the QMC instance-selection restrictions affect the median-gap scaling and the comparison between finite-$N$ quantum Monte Carlo results and thermodynamic cavity predictions. These five questions are independent: resolving any one of them constitutes a partial resolution of the task, while the complete answer above requires all five.

References

1. E. Farhi, D. Gosset, I. Hen, A. W. Sandvik, P. Shor, A. P. Young, and F. Zamponi, "Performance of the quantum adiabatic algorithm on random instances of two optimization problems on regular hypergraphs", Phys. Rev. A 86, 052334 (2012). DOI: 10.1103/PhysRevA.86.052334; arXiv:1208.3757; https://arxiv.org/abs/1208.3757 (originating paper)
2. T. Jörg, F. Krzakala, G. Semerjian, and F. Zamponi, "First-Order Transitions and the Performance of Quantum Algorithms in Random Optimization Problems", Phys. Rev. Lett. 104, 207206 (2010). DOI: 10.1103/PhysRevLett.104.207206; arXiv:0911.3438; https://arxiv.org/abs/0911.3438
3. B. Altshuler, H. Krovi, and J. Roland, "Anderson localization makes adiabatic quantum optimization fail", Proc. Natl. Acad. Sci. USA 107, 12446 (2010). DOI: 10.1073/pnas.1002116107; arXiv:0912.0746; https://arxiv.org/abs/0912.0746 (arXiv preprint title variant: "Anderson localization casts clouds over adiabatic quantum optimization")
4. V. Bapst, L. Foini, F. Krzakala, G. Semerjian, and F. Zamponi, "The quantum adiabatic algorithm applied to random optimization problems: The quantum spin glass perspective", Physics Reports 485 (2013). DOI: 10.1016/j.physrep.2012.10.002; arXiv:1210.0811; https://arxiv.org/abs/1210.0811
5. I. Hen and A. P. Young, "Performance of the quantum adiabatic algorithm on constraint satisfaction and spin glass problems", Eur. Phys. J. Spec. Top. 224, 63 (2015). DOI: 10.1140/epjst/e2015-02343-3; https://link.springer.com/article/10.1140/epjst/e2015-02343-3
6. S. Knysh, "Zero-temperature quantum annealing bottlenecks in the spin-glass phase", Nature Communications 7, 12370 (2016). DOI: 10.1038/ncomms12370; https://www.nature.com/articles/ncomms12370
7. G. Mossi, T. Parolini, S. Pilati, and A. Scardicchio, "On the quantum spin glass transition on the Bethe lattice", J. Stat. Mech. 2017, 013102 (2017). DOI: 10.1088/1742-5468/aa5286; arXiv:1606.06462; https://arxiv.org/abs/1606.06462
8. H. Nishimori and K. Takada, "Exponential Enhancement of the Efficiency of Quantum Annealing by Non-Stoquastic Hamiltonians", Frontiers in ICT 4, 2 (2017). DOI: 10.3389/fict.2017.00002; arXiv:1609.03785; https://arxiv.org/abs/1609.03785 (arXiv preprint title variant: "...by Non-Stochastic Hamiltonians")
9. G. Mazzola and M. Troyer, "Quantum Monte Carlo annealing with multi-spin dynamics", J. Stat. Mech. 2017, 053105 (2017). DOI: 10.1088/1742-5468/aa6de1; arXiv:1701.08775; https://arxiv.org/abs/1701.08775
10. V. Choi, "The effects of the problem Hamiltonian parameters on the minimum spectral gap in adiabatic quantum optimization", Quantum Information Processing 19 (2020). DOI: 10.1007/s11128-020-2582-1; arXiv:1910.02985; https://arxiv.org/abs/1910.02985
11. E. Crosson, T. Albash, I. Hen, and A. P. Young, "De-Signing Hamiltonians for Quantum Adiabatic Optimization", Quantum 4, 334 (2020). DOI: 10.22331/q-2020-09-24-334; arXiv:2004.07681; https://arxiv.org/abs/2004.07681
12. M. Dadgar and C. L. Baldwin, "The anomalously slow dynamics of inhomogeneous quantum annealing", Phys. Rev. A 111, 062601 (2025). DOI: 10.1103/PhysRevA.111.062601; arXiv:2502.03535; https://arxiv.org/abs/2502.03535
13. E. Granet and H. Dreyer, "Benchmarking a heuristic Floquet adiabatic algorithm for the Max-Cut problem", Scientific Reports 15, 31983 (2025). DOI: 10.1038/s41598-025-13923-2; arXiv:2404.16001; https://arxiv.org/abs/2404.16001
14. A. Karakashian and I. Hen, "Dismantling the Stoquastic Dichotomy" (2026). arXiv:2607.18596; https://arxiv.org/abs/2607.18596
15. M. Kowalsky, T. Albash, I. Hen, and D. A. Lidar, "3-Regular 3-XORSAT Planted Solutions Benchmark of Classical and Quantum Heuristic Optimizers", Quantum Science and Technology 7, 025008 (2022). DOI: 10.1088/2058-9565/ac4d1b; arXiv:2103.08464; https://arxiv.org/abs/2103.08464
16. P. Patil, S. Kourtis, C. Chamon, E. R. Mucciolo, and A. E. Ruckenstein, "Obstacles to quantum annealing in a planar embedding of XORSAT", Phys. Rev. B 100, 054435 (2019). DOI: 10.1103/PhysRevB.100.054435; arXiv:1904.01860; https://arxiv.org/abs/1904.01860
17. M. Goh and T. Müller, "The Overlap Gap Property: Separating Quantum and Quantum-Inspired Approximate Optimization Algorithms" (2026). arXiv:2609.35131; https://arxiv.org/abs/2609.35131