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 no less than <a:math xmlns:a="http://www.w3.org/1998/Math/MathML"><a:msup><a:mn>2</a:mn><a:msup><a:mi>N</a:mi><a:mrow><a:mn>2</a:mn><a:mo>/</a:mo><a:mn>3</a:mn></a:mrow></a:msup></a:msup></a:math>, where <b:math xmlns:b="http://www.w3.org/1998/Math/MathML"><b:mi>N</b:mi></b:math> is the total number of spins. Here, we report results of extensive experimentation with D-Wave 3D annealer with <c:math xmlns:c="http://www.w3.org/1998/Math/MathML"><c:mrow><c:mi>N</c:mi><c:mo>≤</c:mo><c:mn>5627</c:mn></c:mrow></c:math>. We found exact ground states (in a probabilistic sense) for typical realizations of 3D spin glasses with the efficiency, which scales as <d:math xmlns:d="http://www.w3.org/1998/Math/MathML"><d:msup><d:mn>2</d:mn><d:mrow><d:mi>N</d:mi><d:mo>/</d:mo><d:mi>β</d:mi></d:mrow></d:msup></d:math> with <e:math xmlns:e="http://www.w3.org/1998/Math/MathML"><e:mrow><e:mi>β</e:mi><e:mo>≈</e:mo><e:msup><e:mn>10</e:mn><e:mn>3</e:mn></e:msup></e:mrow></e:math>. Based on statistical analysis of low-energy states, we argue that with an improvement of annealing protocols and device noise reduction, <f:math xmlns:f="http://www.w3.org/1998/Math/MathML"><f:mi>β</f:mi></f:math> can be increased even further. This suggests that, for <g:math xmlns:g="http://www.w3.org/1998/Math/MathML"><g:mrow><g:mi>N</g:mi><g:mo>&lt;</g:mo><g:msup><g:mi>β</g:mi><g:mn>3</g:mn></g:msup></g:mrow></g:math>, annealing devices provide most efficient way to find an exact ground state.