How computationally hard is 3D spin glass? A quantum optimization study.

We study 3D spin glass optimization problems with the D-wave quantum annealing device. We found that the combination of previously introduced [1] cyclic annealing algorithm and the cluster flipping (classical) post-processing is capable of reaching allegedly *exact* ground states of 3D Ising spin glasses as big as N=5627. This may seem to contradict the 40 years old proof [2] of NP-hardness of the problem. Detailed analysis of the data for systems sizes 678 ≤ N ≤ 5627 shows that the required computational effort does scales exponentially with the system size as exp(N/N_0) with N_0 around 10^3 ! We conjecture that, with an improvement of hardware, annealing strategies and post-processing algorithms, N_0 can be increased even further. This raises questions regarding the existence of fundamental limitations on the value of N_0.

[1] Wang, H., Yeh, H.C. and Kamenev, A., 2022. Many-body localization enables iterative quantum optimization. Nature communications, 13(1), p.5503; Zhang, H., Boothby, K. and Kamenev, A., 2024. Cyclic Quantum Annealing: Searching for Deep Low-Energy States in 5000-Qubit Spin Glass. arXiv preprint arXiv:2403.01034.

[2] Barahona, F., 1982. On the computational complexity of Ising spin glass models. Journal of Physics A: Mathematical and General, 15(10), p.3241.