Browse Teach Curate

Empirical Complexity of the 3D Ising Spin Glass on a D-Wave Annealer

Shows experimentally that a D-Wave quantum annealer (N up to 5627) finds exact ground states of the NP-hard 3D Edwards-Anderson spin glass with success efficiency scaling as 2^(N/beta), beta about 10^3, far below the worst-case 2^(N^(2/3)) bound, and argues that for N<beta^3 annealers are the most efficient known route to exact ground states.

Data Text

PHYSICAL REVIEW RESEARCH 7, 033098 (2025) Computational complexity of three-dimensional Ising spin

This paper empirically probes the practical hardness of finding exact ground states of the NP-hard 3D Ising spin glass (Edwards-Anderson model) using a D-Wave quantum annealer with up to N=5627 spins…