Computational complexity of three-dimensional Ising spin glass: Lessons from D-wave annealer
Physical Review Research · 28.07.2025 · 7 (3)
DOI: 10.1103/3bkn-v5rd ↗Kurz gefasst
Fachartikel in der Zeitschrift Physical Review Research, online erschienen am 28.07.2025. Verfasst von Hao Zhang und 1 weiteren Autor:innen. Die Arbeit wurde bisher 8-mal zitiert (Crossref) und nennt 80 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: National Science Foundation.
Abstract (Originalsprache)
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 ≤ 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 / β with β ≈ 10 3 . Based on statistical analysis of low-energy states, we argue that with an improvement of annealing protocols and device noise reduction, β can be increased even further. This suggests that, for N < β 3 , annealing devices provide most efficient way to find an exact ground state.
Förderung
- National Science Foundation
Zitieren
APA
Zhang, H., & Kamenev, A. (2025). Computational complexity of three-dimensional Ising spin glass: Lessons from D-wave annealer. Physical Review Research, 7(3). https://doi.org/10.1103/3bkn-v5rd
Vancouver
Zhang H, Kamenev A. Computational complexity of three-dimensional Ising spin glass: Lessons from D-wave annealer. Physical Review Research. 2025;7(3). doi:10.1103/3bkn-v5rd
BibTeX
@article{Zhang2025,
author = {Zhang, Hao and Kamenev, Alex},
title = {Computational complexity of three-dimensional Ising spin glass: Lessons from D-wave annealer},
journal = {Physical Review Research},
year = {2025},
volume = {7},
number = {3},
doi = {10.1103/3bkn-v5rd}
}
EUVIMED