arXiv:2501.01107 · Physical Review Research
Computational complexity of three-dimensional Ising spin glass: Lessons from D-wave annealer
Hao Zhang, Alex Kamenev
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 ≤ 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.