Computational complexity of three-dimensional Ising spin glass: Lessons from D-wave annealer
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 n...
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
American Physical Society
2025-07-01
|
| Series: | Physical Review Research |
| Online Access: | http://doi.org/10.1103/3bkn-v5rd |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1839611361463631872 |
|---|---|
| author | Hao Zhang Alex Kamenev |
| author_facet | Hao Zhang Alex Kamenev |
| author_sort | Hao Zhang |
| collection | DOAJ |
| description | 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. |
| format | Article |
| id | doaj-art-71eb185e86404adfafef73da3cf4f6b2 |
| institution | Matheson Library |
| issn | 2643-1564 |
| language | English |
| publishDate | 2025-07-01 |
| publisher | American Physical Society |
| record_format | Article |
| series | Physical Review Research |
| spelling | doaj-art-71eb185e86404adfafef73da3cf4f6b22025-07-28T17:12:15ZengAmerican Physical SocietyPhysical Review Research2643-15642025-07-017303309810.1103/3bkn-v5rdComputational complexity of three-dimensional Ising spin glass: Lessons from D-wave annealerHao ZhangAlex KamenevFinding 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.http://doi.org/10.1103/3bkn-v5rd |
| spellingShingle | Hao Zhang Alex Kamenev Computational complexity of three-dimensional Ising spin glass: Lessons from D-wave annealer Physical Review Research |
| title | Computational complexity of three-dimensional Ising spin glass: Lessons from D-wave annealer |
| title_full | Computational complexity of three-dimensional Ising spin glass: Lessons from D-wave annealer |
| title_fullStr | Computational complexity of three-dimensional Ising spin glass: Lessons from D-wave annealer |
| title_full_unstemmed | Computational complexity of three-dimensional Ising spin glass: Lessons from D-wave annealer |
| title_short | Computational complexity of three-dimensional Ising spin glass: Lessons from D-wave annealer |
| title_sort | computational complexity of three dimensional ising spin glass lessons from d wave annealer |
| url | http://doi.org/10.1103/3bkn-v5rd |
| work_keys_str_mv | AT haozhang computationalcomplexityofthreedimensionalisingspinglasslessonsfromdwaveannealer AT alexkamenev computationalcomplexityofthreedimensionalisingspinglasslessonsfromdwaveannealer |