标题： 三维伊辛自旋玻璃的计算复杂性：来自D-Wave退火器的启示 显示英文标题

标题： Computational complexity of three-dimensional Ising spin glass: Lessons from D-Wave annealer

摘要： 找到三维（3D）伊辛自旋玻璃的精确基态已被证明是一个NP难问题（即，至少与任何非确定性多项式时间（NP）类中的问题一样困难）。 在指数时间假设有效的情况下，其计算复杂性已被证明不少于$2^{N^{2/3}}$，其中$N$是自旋的总数。 在这里，我们报告了对具有$N\le 5627$的D-Wave 3D退火器进行的大规模实验结果。 我们发现对于典型的三维自旋玻璃实现，在效率方面可以以$2^{N/ \beta}$的方式缩放，其中$\beta\approx 10^3$。 基于对低能态的统计分析，我们认为随着退火协议的改进和设备噪声的减少，$\beta$可以进一步提高。 这表明，对于$N<\beta^3$，退火设备是寻找精确基态最有效的方法。 显示英文摘要

摘要： 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\le 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/ \beta}$ with $\beta\approx 10^3$. Based on statistical analysis of low-energy states, we argue that with an improvement of annealing protocols and device noise reduction, $\beta$ can be increased even further. This suggests that, for $N<\beta^3$, annealing devices provide most efficient way to find an exact ground state.