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

标题： On Computational Complexity of 3D Ising Spin Glass: Lessons from D-Wave Annealer

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

摘要： Finding an exact ground state of a 3D Ising spin glass is proven to be an NP-hard problem. 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\leq 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 a most efficient way to find the ground state.