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

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

摘要： 找到三维伊辛自旋玻璃的精确基态已被证明是一个NP难问题。 人们普遍认为，这一陈述意味着所需的计算努力（经典或量子）会随着自旋数量$N$呈指数级增长（$\sim 2^{N/\beta}$）。 然而，这里的因子$\beta$是什么，以及是否存在该因子可能达到的最大值的根本限制？ 在此，我们报告了对D-Wave三维退火器进行的大规模实验结果，其中包含$N\leq 5627$。 我们发现对于典型的三维自旋玻璃实现，在效率方面，由$\beta\approx 10^{3}$表征的精确基态（在概率意义上）。 我们认为，通过进一步改进退火协议、后处理算法和设备噪声减少，$\beta$可以进一步提高。 我们基于低能态的统计分析，对此观察提供了理论论证。 显示英文摘要

摘要： Finding an exact ground state of a 3D Ising spin glass is proven to be an NP-hard problem. There is a widespread belief that this statement implies an exponential scaling, $\sim 2^{N/\beta}$, of necessary computational efforts (classical or quantum), with the number of spins, $N$. Yet, what is a factor $\beta$ here and are there any fundamental limits on how large it can be? 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, characterized by $\beta\approx 10^{3}$. We argue that with a further improvement of annealing protocols, post-processing algorithms and device noise reduction, $\beta$ can be increased even further. We provide a theoretical argumentation for this observation based on statistical analysis of low energy states.