EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

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

Hao Zhang, Alex Kamenev

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →