Computational complexity of three-dimensional Ising spin glass: Lessons from D-Wave annealer

Alex Kamenev; Hao Zhang

REVIEW 3 major objections 4 minor 1 cited by

Computational complexity of three-dimensional Ising spin glass: Lessons from D-Wave annealer

T0 review · 3 major / 4 minor · reviewed 2026-08-10 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read A quantum annealer finds exact 3D spin-glass ground states at efficiency $2^{N/\beta}$, with $\beta\approx 10^3$.

desk verdict A useful empirical scaling result is over-sold as certified ground-state finding; the exactness claim is circular and the largest-N case does not converge, but the basin-count data and 'very low energies' scaling are worth publishing with more modest language. read the letter →

arxiv 2501.01107 v3 pith:SO55QTKB submitted 2025-01-02 cond-mat.dis-nn quant-ph

Hao Zhang , Alex Kamenev This is my paper · ORCID

classification cond-mat.dis-nnquant-ph

keywords Isingspinglass3DEdwards-AndersonmodelquantumannealingNP-hardoptimizationground-statesearchbasincountingcyclicdigitalcooling

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper reports experiments on a quantum annealing device for three-dimensional Edwards-Anderson spin glasses with up to 5,627 spins. The authors' claim is that, for typical random instances and in a probabilistic sense, they find the true ground state, and that the computational effort scales as $2^{N/\beta}$ with $\beta\approx 10^3$, where $N$ is the number of spins. The efficiency comes from a fitted law for the number of low-energy basins, together with a classical digital-cooling step that drives a large ensemble of annealer outputs down to a common ancestor state. If the claim holds, annealing hardware is the most efficient known way to solve this NP-hard problem for all sizes below roughly $\beta^3\approx 10^9$ spins, and the authors argue that $\beta$ can be pushed still higher with better protocols and quieter devices.

What carries the argument

The load-bearing object is the fitted basin-counting formula, Eq. (6): $m(\delta,d)=C_0\,e^{\delta/(2\delta_0)}(N/2d)^{\alpha}$, with $\alpha\approx 2.6$, $\delta_0\approx 1.6$, and $C_0\approx 0.08$. It says that the number of basins seen at excess energy $\delta$ and Hamming-distance threshold $d$ is exponential in $\delta$ and power-law in $N/(2d)$, and that at $\delta\sim O(1)$ the formula yields roughly one basin, the one containing the ground state. The second mechanism is digital cooling: pairwise comparison of low-energy states, decomposition of their differing spins into connected clusters via nonzero couplings, and iterative flipping of the clusters that produce the largest energy decrease, until a common ancestor appears. Together these two pieces convert a sample of annealer outputs into a claimed exact ground state and turn the exponential basin count into the complexity estimate $2^{N/\beta}$.

What would settle it

Run the full cyclic-annealing plus digital-cooling pipeline on a 3D spin-glass instance whose exact ground state is independently known, for example a small instance solved by an exact branch-and-cut code, and check whether the common ancestor equals that known state; a mismatch, or a second non-collapsing basin, would falsify the claim.

Watch

Extended reading notes

Core claim

The central discovery is that the low-energy landscape of the 3D Edwards-Anderson model is organized so that the number of distant basins grows exponentially with the excess energy $\delta$ as $m\propto\exp(\delta/2\delta_0)$, with $\delta_0\approx 1.6$, while at the very lowest energies only a single distant basin remains. On this basis, the authors claim that a sufficiently large ensemble of low-energy states, generated by cyclic annealing at an effective inverse temperature above $10^3$, can be digitally cooled to the true ground state: one identifies connected clusters of flipped spins between pairs of states, flips the clusters that lower the energy, and iterates until independent groups of states collapse to the same common ancestor. They take that ancestor to be the exact ground state, with the error probability decreasing exponentially in the number of independent groups. The measured complexity is $m\sim 2^{N/\beta}$ with $\beta\approx 2.2\,\beta_{\mathrm{eff}}\approx 10^3$, which they present as an order-of-magnitude improvement over exact branch-and-cut solvers and as more efficient than the proven subexponential $2^{N^{2/3}}$ algorithm for every $N<\beta^3$. They conjecture that no fundamental limit prevents a further increase of $\beta$.

Load-bearing premise

The entire certification of the ground state rests on the fitted basin-counting formula holding down to the lowest energies and on the annealer not having missed a whole basin, so that the repeated common ancestor really is the unique ground state.

Editorial extensions

If this is right

For $N$ below about $\beta^3\approx 10^9$, the annealing-plus-cooling pipeline would be the fastest known way to find exact ground states of typical 3D Edwards-Anderson instances.
The empirical relation $\beta_{\mathrm{eff}}\approx 560(\tau/20\,\mu\mathrm{s})^{0.16}$ implies that longer annealing cycles raise efficiency, so improving hardware and protocols could enlarge the tractable size range.
The basin-counting formula predicts a definite number of basins for any given $\delta$ and $d$, which can be checked on other annealing architectures and other short-range spin-glass models.
The authors argue that large $\beta$ is tied to spatial locality: short-range models support independent excitation clusters, while all-to-all models such as Sherrington-Kirkpatrick remain stuck at small $\beta$.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

A direct falsification test would compare the $N=5{,}627$ common ancestor against an independent exact solver on the same instance; the paper itself notes that for this size the two surviving ancestor candidates are very close and the confidence is much lower.
If the basin-counting law is generic, the same digital-cooling postprocessor should convert any low-energy sampler with comparably low effective temperature, classical or quantum, into a ground-state finder; the authors hint at this but do not test it.
The crossover $N\approx\beta^3$ means efficiency gains compound: a tenfold increase in $\beta$ enlarges the solvable size by a factor of one thousand, so reducing the effective temperature matters more than linear speedups.
The claim is stated for typical random couplings; planted or adversarial instances would clarify whether the efficiency extends beyond the typical-case setting that the paper studies.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

First impression: this paper has a genuinely interesting empirical result buried under an over-claimed headline. The data on low-energy basins in the 3D EA model, the basin-count formula Eq. (6), and the measured beta_eff ~ 10^3 on a D-Wave Advantage (with data on Zenodo) are new and worth knowing about. The digital cooling / common-ancestor method is a natural extension of cluster-flipping postprocessing, but the systematic scaling with N and the fit to Eq. (6) are a useful addition. The paper also deserves credit for stating clearly that for N=5627 the second-generation ancestors do not converge, and for calling out their own confidence level.

The soft spot is the exactness claim. The abstract says "exact ground states (in a probabilistic sense)" with beta ~ 10^3, but the ground-state energy E0 used to define delta is the output of the very same digital cooling pipeline whose reliability is then justified using the fitted basin-count formula. That's circular in a quantitative way: if the true E0 is lower, delta is underestimated and beta_eff is overestimated. The N=958 case looks great—25 groups all collapse to the same ancestor—but that is a self-consistency check, not a certificate; a deterministic bias in the annealer or the postprocessing could produce a common wrong ancestor. And the largest case, N=5627, is exactly where the convergence fails. The authors say they "believe" the first ancestor is the true ground state; that is not the same as having found it.

So the paper's central claim, as stated in the abstract, is not well-supported. That said, the more modest claim—that their protocol produces very low residual energies scaling as N/beta_eff, and that the basin count follows Eq. (6)—does not depend on E0 being exactly right, as long as the candidate E0 is close. The practical value of the annealer for finding near-ground states stands on its own.

My recommendation for peer review: send it out. The empirical work is substantial, the methods are described in enough detail to reproduce, and the scaling question is important enough to deserve careful referee time. But the authors should be pushed to either benchmark against an independent exact solver (e.g., branch-and-cut on smaller sizes) or to soften the language from "exact ground states" to "very low-energy states" and reframe the complexity estimate as conditional on the candidate E0. Rejecting the paper entirely would throw out the useful empirical core; accepting the headline as-is would enshrine an unverified claim. A revision with a more honest framing and an explicit discussion of the circularity would be publishable.

Referee Report

3 major / 4 minor

Summary. The paper reports experiments on the D-Wave Advantage 3D annealer for Edwards-Anderson spin glasses up to N=5627. The authors use a cyclic annealing protocol to generate low-energy states and a 'digital cooling' ancestry search to identify a common ancestor state, which they claim is the exact ground state (in a probabilistic sense) for typical realizations. They fit an empirical basin-count formula m(δ,d)=C0 exp(δ/(2δ0)) (N/2d)^α, observe that the average residual energy scales as δ≈N/βeff with βeff in excess of 10^3, and conclude that the computational complexity of finding exact ground states on this hardware scales as 2^{N/β} with β≈10^3. The paper also sketches a subexponential 2^{O(N^{2/3})} divide-and-conquer algorithm for comparison and argues that annealing devices are the most efficient known method for N<β^3.

Significance. If the central claim were established, this would be a striking result: an analog annealer finding exact ground states of 3D spin glasses at sizes up to 5,627 spins with an effective exponent β≈10^3, far exceeding the reported β≈10^2 for exact branch-and-cut algorithms. The empirical observation of exponential basin proliferation is interesting in its own right, and the authors are transparent about their protocol and data availability. However, the exactness certification is not independent: the ground-state energy E0 used in the analysis is the output of the very same digital-cooling pipeline that the paper seeks to validate, and for the largest system the pipeline does not converge to a unique ancestor. The headline claim is therefore unsupported in its current form.

major comments (3)

[Sec. IV, Fig. 6(b), and Abstract] For N=5627 the digital-cooling ancestry search produces two non-identical common ancestors, with energies −8961.40 and −8961.11, differing by a 67-spin cluster; the authors state, 'We believe the first one is the true ground state, though the confidence level of this assertion is much less than for N=958.' The abstract nevertheless claims exact ground states (in a probabilistic sense) for N≤5627. Since the energy assigned as E0 for this largest size is one of these unverified candidates, and that E0 enters Eq. (6) and the linear fit in Fig. 6(c), the reported βeff and hence β≈10^3 are not certified for the headline system size. An independent exact or rigorous solver (e.g., branch-and-cut) is needed for at least some instances, or the claim of exactness for N=5627 must be withdrawn.
[Eq. (6) and Secs. II–III] The basin-count formula m(δ,d)=C0 exp(δ/(2δ0)) (N/2d)^α is fitted using δ=E−E0 and δ0=|E0|/N, where E0 is the candidate ground state produced by the same digital-cooling algorithm whose exactness the paper argues. This is a quantitative circularity: if the true ground state is lower than the candidate, then δ is underestimated and δ0 is overestimated, so the fitted exponential slope is biased. The data collapse in Fig. 2(c) and the 'single basin at low energy' conclusion of Sec. II are thus not independent evidence that the common ancestor is the true ground state; they are rearrangements of the assumed E0. The paper should validate Eq. (6) on small instances where E0 is independently known from exact algorithms.
[Sec. III, paragraph on common-ancestor convergence] The statement 'Given a sufficiently large initial set, the common ancestor state must be the ground state' rests on the empirical basin-count formula (6) and on the assumption that the annealer samples all low-energy basins at the sampled energy. The N=958 evidence that 25 independent groups converge to the same ancestor is suggestive, but it is a self-consistency check rather than a certificate: a deterministic bias in the cyclic protocol, which repeatedly biases toward a reference state, could in principle drive all groups to the same non-ground-state ancestor. The authors should either provide a rigorous argument for convergence or benchmark the ancestor against an external exact solver.

minor comments (4)

[Sec. I, paragraph on NP-hardness] The statement that NP-hardness means 'no known algorithm (classical or quantum) can find or verify an answer in a polynomial time' is imprecise; NP-hardness alone does not imply that verification is hard for every instance class, and the verification complexity of optimality for spin glasses is a separate question.
[Throughout] There are several typographical errors, including 'D-Wave' vs 'D-wave' in the title/abstract, 'Y et' in Sec. II, and the phrase 'to compare the initial (blue) states were centered' in Sec. IV, which should be corrected.
[Sec. V] The recursive algorithm is described with notation '24N^{2/3}' that is easy to misread; the intended meaning is 2^{4N^{2/3}}, and the text should be typeset to avoid this ambiguity.
[Sec. IV, Fig. 6(c)] The linear fit δ/(2δ0)=0.00105N−0.733 is reported without error bars or a goodness-of-fit measure; given the central role of this fit in determining βeff, the authors should provide at least standard errors and the number of instances used.

Circularity Check

2 steps flagged · score 6.0 of 10

Ground-state certification is circular: E0 is set by the digital-cooling common ancestor, then fed into Eq. (6) which is used to prove that ancestor is exact; the 2^{N/β} scaling is the same fit rearranged, and no exact-solver check breaks the loop.

self definitional [Sec. III 'Digital cooling technique', Sec. II Eq. (6), Sec. IV 'Finding ground states of large spin glasses']
"Given a sufficiently large initial set, the common ancestor state must be the ground state. ... Here, δ = E − E0, where E is the center of the energy window and E0 is the ground-state energy (a way we determine E0 is discussed below), δ0 =| E0|/N ≈ 1.6, and C0 ≈ 0.08. ... The digital cooling algorithm was run for each system size. Except for the largest case of N = 5627, it rapidly converges to an exactly same common ancestor. Its energy was taken as E0."

Eq. (6) is the quantitative basis for the assertion that the common ancestor must be the ground state: at δ ∼ O(1) there is typically a single basin. But the δ and δ0 entering Eq. (6) are defined from E0, and E0 was itself set equal to the energy of the digital-cooling common ancestor. The object being certified (E0 is exact) is an input to the formula used to certify it. No independent exact solver is applied, so a systematic error in E0 would be absorbed into the fitted δ0 and C0 rather than detected.
fitted input called prediction [Sec. I 'Introduction' (after Eq. (3)), Sec. IV Fig. 6(c) caption, Sec. V]
"Both the average residual energy δ/2δ0 and the standard deviation σ scale approximately linearly with the system size N ... The linear fit (red) δ/(2δ0) = 0.00105N − 0.733. ... The computational effort involved in this procedure scales as ∼m(δ,N) ∝ e^{N/(2δ0βeff)} ... This leads to β = (2δ0 log 2)βeff ≈ 2.2βeff. Based on the data obtained with the D-Wave Advantage annealer, we observed an exponential scaling, 2^{N/β}"

The reported β is not an independent prediction: it is obtained by inserting the fitted linear residual-energy law (δ ≈ N/βeff, Eq. (3)) into the fitted exponential basin-count formula (Eq. (6)), giving β = (2δ0 log 2)βeff. Thus the headline 2^{N/β} is a rearrangement of the same measured slopes. Moreover, βeff and δ0 both depend on the assumed E0; if E0 is above the true ground state, δ is underestimated, βeff is overestimated, and β is inflated. No exact-solver benchmark is reported against which the fitted scaling could be falsified.

full rationale

The paper contains real empirical work: basin dendrograms, energy histograms, and the N=958 convergence of 25 independently processed groups to the same common ancestor are substantive internal-consistency checks. The circularity is located in the certification step. In Sec. IV, E0 is explicitly taken as the energy of the digital-cooling common ancestor; in Sec. II, that same E0 defines δ and δ0 in the fitted basin-counting law Eq. (6). The paper then uses Eq. (6) to argue that near δ∼O(1) there is a single basin and hence the common ancestor is the true ground state. That reduces to a self-consistency check: the formula that 'proves' E0 is exact was fitted using that same E0. For N=5627 the paper admits the two second-generation ancestors differ by a 67-spin cluster and that confidence is much lower; no independent exact solver is used anywhere. The complexity exponent 2^{N/β} follows by inserting the fitted residual-energy law (3) into the fitted basin law (6), so β≈10^3 is a derived fit rather than a validated prediction. The self-citations to Refs. [73,74] are methodological (the cyclic protocol is reproduced in the Appendix), so I do not count them as circular. The central claim is therefore partially circular: the ground-state certificate and the β value both reduce to the same unverified E0, giving a score of 6.

Assumptions & free parameters 5 free parameters · 4 assumptions · 0 invented entities

The central complexity claim is assembled from several fitted parameters and from the assumption that the algorithm's own output is the true ground state. The latter assumption is not checked against an external exact solver, which creates a circular verification loop.

free parameters (5)

delta0 = ≈1.6
Ground-state energy per spin for the box distribution and D-Wave Advantage. Used in Eq. (6) to define delta and in beta = 2 delta0 log 2 beta_eff. Determined from the algorithm's own ground-state candidate, not from an independent exact solver.
alpha = ≈2.6
Exponent in the basin count power law Eq. (5). Fitted to dendrogram data for N=958.
C0 = ≈0.08
Prefactor in Eq. (6). Fitted to basin counts across energy windows.
beta_eff prefactor = 560 (tau/20us)^0.16
Eq. (4): inverse average residual energy per spin as a function of annealing time. Both prefactor and exponent are empirical fits. beta_eff is the quantity that sets the claimed complexity.
power-law exponent 0.16 = 0.16
Exponent in Eq. (4). Fitted on log-log plot without reported error bars.

assumptions (4)

domain assumption Exponential Time Hypothesis (ETH)
Assumed when citing the 2^{N^{2/3}} lower bound from Ref. [55] for the comparison in Sec. V. Not needed for the experimental scaling, but used to frame 'most efficient'.
domain assumption D-Wave Pegasus graph faithfully represents a 3D cubic-lattice EA model
Sec. II: 'This architecture is a 3D cubic lattice (M-1)x(M-1)x12, with two spins per unit cell.' The hardware graph is not a full 3D lattice; the mapping assumes the embedded problem is equivalent to the EA model with nearest-neighbor random couplings.
domain assumption The annealer samples all low-energy basins without strong bias
The basin counting formula (6) is used to argue that convergence of independent groups implies the ground state. This assumes the sample of states is representative of the true basin structure at each energy.
ad hoc to paper Each basin has a unique lowest-energy ancestor, and clusters can be independently flipped
Sec. III: 'each basin in the spin glass landscape has an ancestor, a state with lowest energy, from which all other states are generated.' This is the structural assumption that makes digital cooling work and is not proven for 3D EA.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Computational complexity of three-dimensional Ising spin glass: Lessons from D-Wave annealer." pith.science (2026). https://pith.science/paper/SO55QTKB

@misc{pith2026250101107,
  author       = {Pith},
  title        = {Pith review of: Computational complexity of three-dimensional Ising spin glass: Lessons from D-Wave annealer},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/SO55QTKB}},
  note         = {Machine review of arXiv:2501.01107}
}

abstract

Finding an exact ground state of a three-dimensional (3D) Ising spin glass is proven to be an NP-hard problem (i.e., at least as hard as any problem in the nondeterministic polynomial-time (NP) class). Given validity of the exponential time hypothesis, its computational complexity was proven to be no less than $2^{N^{2/3}}$, where $N$ is the total number of spins. Here, we report results of extensive experimentation with D-Wave 3D annealer with $N\le 5627$. We found exact ground states (in a probabilistic sense) for typical realizations of 3D spin glasses with the efficiency, which scales as $2^{N/ \beta}$ with $\beta\approx 10^3$. Based on statistical analysis of low-energy states, we argue that with an improvement of annealing protocols and device noise reduction, $\beta$ can be increased even further. This suggests that, for $N<\beta^3$, annealing devices provide most efficient way to find an exact ground state.

Figures

Figures reproduced from arXiv: 2501.01107 by the authors.

**Figure 1.** FIG. 1. (a) A dendrogram illustrating the hierarchical clustering of basins, based on a set of 21 000 low-energy states within a small energy [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗

**Figure 2.** FIG. 2. (a) Number of observed basins (with threshold [PITH_FULL_IMAGE:figures/full_fig_p003_2.png] view at source ↗

**Figure 3.** FIG. 3. Schematic illustration for proliferation of distant basins. [PITH_FULL_IMAGE:figures/full_fig_p003_3.png] view at source ↗

Figures from the paper (3 more)

**Figure 4.** Figure 4: FIG. 4. Examples of connected clusters with small surface en [PITH_FULL_IMAGE:figures/full_fig_p004_4.png]

**Figure 6.** Figure 6: FIG. 6. (a) For [PITH_FULL_IMAGE:figures/full_fig_p005_6.png]

**Figure 7.** Figure 7: FIG. 7. Schematic phase diagram. Schematic representation of [PITH_FULL_IMAGE:figures/full_fig_p007_7.png]

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

Quantum Algorithm Software for Condensed Matter Physics
cond-mat.str-el 2025-06 reject novelty 2.0 of 10

A review of quantum algorithm software that advertises a benchmark suite, yet the body contains no benchmarks, data, or code.

Reference graph

Works this paper leans on

87 extracted references · 73 canonical work pages · cited by 1 Pith paper

[1]

The data presented in this section were generated using standard forward annealing protocol

× 12, with two spins per unit cell. The data presented in this section were generated using standard forward annealing protocol. In spin glasses, a basin represents a set of states with similar energies and Hamming distances between any two of them below a certain threshold, denoted by d. To visualize and organize the basins, we used dendrograms [see Fig....

2025
[2]

Encyclopedia of Optimization , edited by C. A. Floudas and P . M. Pardalos (Springer, New Y ork, 2008), 2nd ed

2008
[3]

quantum-inspired

As the energy increases, basins (in cyan) proliferate. Dashed lines illustrate the number of basins at each energy level E = E0 + δ. 033098-3 HAO ZHANG AND ALEX KAMENEV PHYSICAL REVIEW RESEARCH 7, 033098 (2025) FIG. 4. Examples of connected clusters with small surface en- ergy between two low-energy states with a total Hamming distance of about 450. Six l...

2025
[4]

Mézard and A

M. Mézard and A. Montanari, Information, Physics, and Com- putation, Oxford Graduate Texts (Oxford University Press, Oxford, 2009)

2009
[5]

A. D. King, C. D. Batista, J. Raymond, T. Lanting, I. Ozﬁdan, G. Poulin-Lamarre, H. Zhang, and M. H. Amin, Quantum annealing simulation of out-of-equilibrium magne- tization in a spin-chain compound, PRX Quantum 2, 030317 (2021)

work page 2021
[6]

Lucas, Ising formulations of many NP problems, Front

A. Lucas, Ising formulations of many NP problems, Front. Phys. 2, 5 (2014)

2014
[7]

A. Mott, J. Job, J.-R. Vlimant, D. Lidar, and M. Spiropulu, Solving a Higgs optimization problem with quantum annealing for machine learning, Nature (London) 550, 375 (2017)

2017
[8]

Mezard, G

M. Mezard, G. Parisi, and M. A. Virasoro, Spin Glass Theory and Beyond: An Introduction to the Replica Method and Its Applications (World Scientiﬁc Publishing Company, Teaneck, NJ, USA, 1987)

work page 1987

Show all 87 references

[9]

Abel and M

S. Abel and M. Spannowsky, Quantum-ﬁeld-theoretic simula- tion platform for observing the fate of the false vacuum, PRX Quantum 2, 010349 (2021)

2021
[10]

Mohseni, P

N. Mohseni, P . L. McMahon, and T. Byrnes, Ising machines as hardware solvers of combinatorial optimization problems, Nat. Rev. Phys. 4, 363 (2022)

2022
[11]

Jiang, K

S. Jiang, K. A. Britt, A. J. McCaskey, T. S. Humble, and S. Kais, Quantum annealing for prime factorization, Sci. Rep. 8, 17667 (2018)

2018
[12]

Perdomo-Ortiz, N

A. Perdomo-Ortiz, N. Dickson, M. Drew-Brook, G. Rose, and A. Aspuru-Guzik, Finding low-energy conformations of lat- tice protein models by quantum annealing, Sci. Rep. 2, 571 (2012)

2012
[13]

Dridi and H

R. Dridi and H. Alghassi, Prime factorization using quantum annealing and computational algebraic geometry, Sci. Rep. 7, 43048 (2017)

2017
[14]

S. F. Edwards and P . W. Anderson, Theory of spin glasses, J .P h y s .F :M e t .P h y s .5, 965 (1975)

1975
[15]

J. C. Criado and M. Spannowsky, Qade: Solving differential equations on quantum annealers, Quantum Science Techno. 8, 015021 (2022)

2022
[16]

Phillipson and H

F. Phillipson and H. S. Bhatia, Portfolio optimisation using the D-Wave quantum annealer, in Computational Science— ICCS 2021 , edited by M. Paszynski, D. Kranzlmüller, V . V . Krzhizhanovskaya, J. J. Dongarra, and P . M. A. Sloot (Springer International Publishing, Cham, 2021...

2021
[17]

A. P . Y oung, Spin glasses: A computational challenge for the 21st century, Comput. Phys. Commun. 146, 107 (2002)

2002
[18]

Sherrington and S

D. Sherrington and S. Kirkpatrick, Solvable model of a spin- glass, P h y s .R e v .L e t t .35, 1792 (1975)

1975
[19]

Binder and A

K. Binder and A. P . Y oung, Spin glasses: Experimental facts, theoretical concepts, and open questions, Rev. Mod. Phys. 58, 801 (1986). 033098-7 HAO ZHANG AND ALEX KAMENEV PHYSICAL REVIEW RESEARCH 7, 033098 (2025)

1986
[20]

Istrail, Statistical mechanics, three-dimensionality and NP- completeness: I

S. Istrail, Statistical mechanics, three-dimensionality and NP- completeness: I. Universality of intracatability for the partition function of the Ising model across non-planar surfaces (ex- tended abstract), in Proceedings of the 32nd Annual ACM Symposium on Theory of Computi...

2000
[21]

Boettcher, Physics of the Edwards–Anderson spin glass in dimensions d = 3, ...,8 from heuristic ground state optimization, Front

S. Boettcher, Physics of the Edwards–Anderson spin glass in dimensions d = 3, ...,8 from heuristic ground state optimization, Front. Phys. 12, 1466987 (2024)

2024
[22]

Barahona, On the computational complexity of Ising spin glass models, J

F. Barahona, On the computational complexity of Ising spin glass models, J. Phys. A: Math. Gen. 15, 3241 (1982)

1982
[23]

Arora and B

S. Arora and B. Barak, Computational Complexity: A Modern Approach, 1st ed. (Cambridge University Press, New Y ork, 2007)

2007
[24]

A. K. Hartmann, Ground states of two-dimensional Ising spin glasses: Fast algorithms, recent developments and a ferromagnet-spin glass mixture, J. Stat. Phys. 144, 519 (2011)

2011
[25]

M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness , 1st ed. (W. H. Freeman, New Y ork, 1979)

1979
[26]

Kirkpatrick, C

S. Kirkpatrick, C. D. Gelatt, and M. P . V ecchi, Optimization by simulated annealing, Science 220, 671 (1983)

1983
[27]

W. K. Hastings, Monte Carlo sampling methods using Markov chains and their applications, Biometrika 57, 97 (1970)

1970
[28]

R. P . Feynman, Simulating physics with computers, Int. J. Theor. Phys. 21, 467 (1982)

1982
[29]

Kadowaki and H

T. Kadowaki and H. Nishimori, Quantum annealing in the trans- verse Ising model, Phys. Rev. E 58, 5355 (1998)

1998
[30]

A. B. Finnila, M. A. Gomez, C. Sebenik, C. Stenson, and J. D. Doll, Quantum annealing: A new method for minimizing multidimensional functions, Chem. Phys. Lett. 219, 343 (1994)

1994
[31]

Hukushima and K

K. Hukushima and K. Nemoto, Exchange Monte Carlo method and application to spin glass simulations, J. Phys. Soc. Jpn. 65, 1604 (1996)

1996
[32]

Farhi, J

E. Farhi, J. Goldstone, S. Gutmann, and M. Sipser, Quantum computation by adiabatic evolution, arXiv:quant-ph/0001106

arXiv
[33]

Brooke, D

J. Brooke, D. Bitko, T. F. Rosenbaum, and G. Aeppli, Quantum annealing of a disordered magnet, Science 284, 779 (1999)

1999
[34]

Houdayer and O

J. Houdayer and O. C. Martin, Renormalization for discrete optimization, P h y s .R e v .L e t t .83, 1030 (1999)

1999
[35]

D. J. Earl and M. W. Deem, Parallel tempering: Theory, applica- tions, and new perspectives, Phys. Chem. Chem. Phys. 7, 3910 (2005)

2005
[36]

Farhi, J

E. Farhi, J. Goldstone, S. Gutmann, J. Lapan, A. Lundgren, and D. Preda, A quantum adiabatic evolution algorithm applied to random instances of an NP-complete problem, Science 292, 472 (2001)

2001
[37]

G. E. Santoro, R. Martoñák, E. Tosatti, and R. Car, Theory of quantum annealing of an Ising spin glass, Science 295, 2427 (2002)

2002
[38]

Morita and H

S. Morita and H. Nishimori, Mathematical foundation of quan- tum annealing, J. Math. Phys. 49, 125210 (2008)

2008
[39]

G. E. Santoro and E. Tosatti, Topical review: Optimization us- ing quantum mechanics: Quantum annealing through adiabatic evolution, J. Phys. A: Math. Gen. 39, R393 (2006)

2006
[40]

Das and B

A. Das and B. K. Chakrabarti, Colloquium: Quantum annealing and analog quantum computation, Rev. Mod. Phys. 80, 1061 (2008)

2008
[41]

J. E. Dorband, A method of ﬁnding a lower energy solutionto a QUBO/Ising objective function, arXiv:1801.04849

arXiv
[42]

Farhi, J

E. Farhi, J. Goldstone, and S. Gutmann, A quantum approxi- mate optimization algorithm, arXiv:1411.4028

arXiv
[43]

Z. Zhu, A. J. Ochoa, and H. G. Katzgraber, Efﬁcient cluster algorithm for spin glasses in any space dimension, Phys. Rev. Lett. 115, 077201 (2015)

2015
[44]

C. Fan, M. Shen, Z. Nussinov, Z. Liu, Y . Sun, and Y .-Y . Liu, Searching for spin glass ground states through deep reinforce- ment learning, Nat. Commun. 14, 725 (2023)

2023
[45]

A. J. Ochoa, D. C. Jacob, S. Mandrà, and H. G. Katzgraber, Feeding the multitude: A polynomial-time algorithmto improve samplingding, P h y s .R e v .E99, 043306 (2019)

2019
[46]

Zhou, S.-T

L. Zhou, S.-T. Wang, S. Choi, H. Pichler, and M. D. Lukin, Quantum approximate optimization algorithm: Performance, mechanism, and implementation on near-term devices, Phys. Rev. X 10, 021067 (2020)

2020
[47]

M. W. Johnson et al. , Quantum annealing with manufactured spins, Nature (London) 473, 194 (2011)

2011
[48]

Misra-Spieldenner, T

A. Misra-Spieldenner, T. Bode, P . K. Schuhmacher, T. Stollenwerk, D. Bagrets, and F. K. Wilhelm, Mean-ﬁeld ap- proximate optimization algorithm, PRX Quantum 4, 030335 (2023)

2023
[49]

Munoz-Bauza and D

H. Munoz-Bauza and D. Lidar, Scaling advantage in approx- imate optimization with quantum annealing, P h y s .R e v .L e t t . 134, 160601 (2025)

2025
[50]

Y amashiro, M

Y . Y amashiro, M. Ohkuwa, H. Nishimori, and D. A. Lidar, Dynamics of reverse annealing for the fully connected p-spin model, P h y s .R e v .A100, 052321, (2019)

2019
[51]

N. G. Dickson et al., Thermally assisted quantum annealing of a 16-qubit problem, Nat. Commun. 4, 1903 (2013)

2013
[52]

Ohkuwa, H

M. Ohkuwa, H. Nishimori, and D. A. Lidar, Reverse annealing for the fully connected p-spin model, Phys. Rev. A 98, 022314, (2018)

2018
[53]

A. D. King et al. , Quantum critical dynamics in a 5000-qubit programmable spin glass, Nature (London) 617, 61 (2023)

2023
[54]

C. Cao, J. Xue, N. Shannon, and R. Joynt, Speedup of the quan- tum adiabatic algorithm using delocalization catalysis, Phys. Rev. Res. 3, 013092 (2021)

2021
[55]

A. D. King et al. , Coherent quantum annealing in a pro- grammable 2,000 qubit Ising chain, Nat. Phys. 18, 1324 (2022)

2022
[56]

Impagliazzo and R

R. Impagliazzo and R. Paturi, Complexity of k-sat, in Proceed- ings of the 14th Annual IEEE Conference on Computational Complexity (formerly, Structure in Complexity Theory Confer- ence) (Cat.No. 99CB36317) (IEEE, Atlanta, GA, USA, 1999), pp. 237–240

1999
[57]

Bernaschi, I

M. Bernaschi, I. González-Adalid Pemartín, V . Martín-Mayor, and G. Parisi, The quantum transition of the two-dimensional I s i n gs p i ng l a s s ,Nature (London) 631, 749 (2024)

2024
[58]

Zhang, Computational complexity of spin-glass three- dimensional (3D) Ising model, J

Z. Zhang, Computational complexity of spin-glass three- dimensional (3D) Ising model, J. Mater. Sci. Technol. 44, 116 (2020)

2020
[59]

W. L. McMillan, Scaling theory of Ising spin glasses, J. Phys. C 17, 3179 (1984)

1984
[60]

Palassini, F

M. Palassini, F. Liers, M. Juenger, and A. P . Y oung, Low-energy excitations in spin glasses from exact ground states, Phys. Rev. B 68, 064413 (2003)

2003
[61]

Montanaro, Quantum speedup of branch-and-bound algo- rithms, P h y s .R e v .R e s .2, 013056 (2020)

A. Montanaro, Quantum speedup of branch-and-bound algo- rithms, P h y s .R e v .R e s .2, 013056 (2020). 033098-8 COMPUTA TIONAL COMPLEXITY OF THREE-DIMENSIONAL … PHYSICAL REVIEW RESEARCH 7, 033098 (2025)

2020
[62]

Palassini and A

M. Palassini and A. P . Y oung, Nature of the spin glass state, Phys. Rev. Lett. 85, 3017 (2000)

2000
[63]

D. S. Fisher and D. A. Huse, Ordered phase of short-range Ising spin-glasses, P h y s .R e v .L e t t .56, 1601 (1986)

1986
[64]

M. A. Moore, H. Bokil, and B. Drossel, Evidence for the droplet picture of spin glasses, Phys. Rev. Lett. 81, 4252 (1998)

1998
[65]

Marinari and G

E. Marinari and G. Parisi, Effects of a bulk perturbation on the ground state of 3D Ising spin glasses, P h y s .R e v .L e t t .86, 3887 (2001)

2001
[66]

Marinari and G

E. Marinari and G. Parisi, Effects of changing the boundary conditions on the ground state of Ising spin glasses, Phys. Rev. B 62, 11677 (2000) ()

2000
[67]

Franz and G

S. Franz and G. Parisi, Non trivial overlap distributions at zero temperature, Eur. Phys. J. B 18, 485 (2000)

2000
[68]

Parisi and T

G. Parisi and T. Temesvári, Replica symmetry breaking in and around six dimensions, Nucl. Phys. B 858, 293 (2012)

2012
[69]

C. M. Newman and D. L. Stein, Finite-dimensional spin glasses: States, excitations, and interfaces, Ann. Henri Poincaré 4, 497 (2003)

2003
[70]

Collaboration et al., Nature of the spin-glass phase at experi- mental length scales, J

J. Collaboration et al., Nature of the spin-glass phase at experi- mental length scales, J. Stat. Mech. (2010) P06026

2010
[71]

Houdayer, F

J. Houdayer, F. Krzakala, and O. Martin, Large-scale low- energy excitations in 3-d spin glasses, Eur. Phys. J. B 18, 467 (2000)

2000
[72]

M. A. Moore, Droplet-scaling versus replica symmetry break- ing debate in spin glasses revisited, Phys. Rev. E 103, 062111 (2021)

2021
[73]

M. Shen, G. Ortiz, Y .-Y . Liu, M. Weigel, and Z. Nussinov, Universal fragility of spin glass ground states under single bond changes, P h y s .R e v .L e t t .132, 247101 (2024)

2024
[74]

Zhang, K

H. Zhang, K. Boothby, and A. Kamenev, Cyclic quantum an- nealing: Searching for deep low-energy states in 5000-qubit spin glass, Sci. Rep. 14, 30784, (2024)

2024
[75]

Krzakala and O

F. Krzakala and O. C. Martin, Spin and link overlaps in three- dimensional spin glasses, P h y s .R e v .L e t t .85, 3013 (2000)

2000
[76]

Wang, H.-C

H. Wang, H.-C. Y eh, and A. Kamenev, Many-body localiza- tion enables iterative quantum optimization, Nat. Commun. 13, 5503 (2022)

2022
[77]

For example, the cyclic annealing achieves a lower effective temperature than the forward annealing [ 74]
[78]

Indeed, an evolution is nonergodic and is getting stuck in a local minimum

One may worry about using the notion of temperature for the intrinsically nonequilibrium glassy system. Indeed, an evolution is nonergodic and is getting stuck in a local minimum. We use the cyclic annealing with random initial conditions to generate a large ensemble of such l...
[79]

While the adiabatic quantum annealing is, in principle, capa- ble of reaching an exact ground state (also in probabilistic sense), its efﬁciency is fundamentally limited to β ≈ 1, due to exponentially small energy gaps along the anneal- ing path and nonadiabatic Landau-Zener t...
[80]

Hereafter, we use the reduced Hamming distance, deﬁned as d = min( ˜d, N − ˜d ), where ˜d is the original deﬁnition of Ham- ming distance, since ﬂipping all spins yields an equivalent state with identical energy
[81]

Boothby, P

K. Boothby, P . Bunyk, J. Raymond, and A. Roy, Next- generation topology of D-Wave quantum processors, arXiv:2003.00133

2003 arXiv
[82]

Virtanen et al

P . Virtanen et al. , SciPy 1.0: Fundamental algorithms for scientiﬁc computing in Python, Nat. Methods 17, 261 (2020)

2020
[83]

Zhang and A

H. Zhang and A. Kamenev, 3D Ising Spin Glass Solutions, Zenodo (2024), https://zenodo.org/records/14578166

2024
[84]

We are indebted to Michael Winer for discussion of this issue
[85]

Schlömer and S

H. Schlömer and S. Sachdev, Quantum annealing with chaotic driver Hamiltonians, Ann. Phys. 479, 170042 (2025)

2025
[87]

Rajak, S

A. Rajak, S. Suzuki, A. Dutta, and B. K. Chakrabarti, Quan- tum annealing: An overview, Philos. Trans. R. Soc. A 381, 20210417 (2023). 033098-9

2023
[500]

Y et, the cyclic annealing is capable of “cooling” the system down to a very low effective temperature of 10 −3

The annealing is always performed in the nonadiabatic regime [76]. Y et, the cyclic annealing is capable of “cooling” the system down to a very low effective temperature of 10 −3. We expect that the temperature, decreasing with the increasing annealing time, saturates at a suf...

Pith tools

Reviewed August 10, 2026 · model on record in the stance chip above.

[1] [1]

The data presented in this section were generated using standard forward annealing protocol

× 12, with two spins per unit cell. The data presented in this section were generated using standard forward annealing protocol. In spin glasses, a basin represents a set of states with similar energies and Hamming distances between any two of them below a certain threshold, denoted by d. To visualize and organize the basins, we used dendrograms [see Fig....

2025

[2] [2]

Encyclopedia of Optimization , edited by C. A. Floudas and P . M. Pardalos (Springer, New Y ork, 2008), 2nd ed

2008

[3] [3]

quantum-inspired

As the energy increases, basins (in cyan) proliferate. Dashed lines illustrate the number of basins at each energy level E = E0 + δ. 033098-3 HAO ZHANG AND ALEX KAMENEV PHYSICAL REVIEW RESEARCH 7, 033098 (2025) FIG. 4. Examples of connected clusters with small surface en- ergy between two low-energy states with a total Hamming distance of about 450. Six l...

2025

[4] [4]

Mézard and A

M. Mézard and A. Montanari, Information, Physics, and Com- putation, Oxford Graduate Texts (Oxford University Press, Oxford, 2009)

2009

[5] [5]

A. D. King, C. D. Batista, J. Raymond, T. Lanting, I. Ozﬁdan, G. Poulin-Lamarre, H. Zhang, and M. H. Amin, Quantum annealing simulation of out-of-equilibrium magne- tization in a spin-chain compound, PRX Quantum 2, 030317 (2021)

work page 2021

[6] [6]

Lucas, Ising formulations of many NP problems, Front

A. Lucas, Ising formulations of many NP problems, Front. Phys. 2, 5 (2014)

2014

[7] [7]

A. Mott, J. Job, J.-R. Vlimant, D. Lidar, and M. Spiropulu, Solving a Higgs optimization problem with quantum annealing for machine learning, Nature (London) 550, 375 (2017)

2017

[8] [8]

Mezard, G

M. Mezard, G. Parisi, and M. A. Virasoro, Spin Glass Theory and Beyond: An Introduction to the Replica Method and Its Applications (World Scientiﬁc Publishing Company, Teaneck, NJ, USA, 1987)

work page 1987