2025/01/02 by Hao Zhang, Zhang, Hao, Alex Kamenev +1 · 3 citations
Physics and Astronomy · Mathematics · Computer Science · #Theoretical and Computational Physics #Random Matrices and Applications #Neural Networks and Applications
paper · pdf · doi:10.48550/arxiv.2501.01107
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^N2/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 2N/ β with β≈ 103. 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.