Yaacoby Ran, Schaar Nathan, Kellerhals Leon, Raz Oren, Hermelin Danny, Pugatch Rami
Department of Complex Systems, Weizmann Institute of Science, Rehovot 7610001, Israel.
Technische Universität Berlin, Chair of Algorithmics and Computational Complexity, Berlin 10623, Germany.
Phys Rev E. 2022 Mar;105(3-2):035305. doi: 10.1103/PhysRevE.105.035305.
Finding the ground state of an Ising spin glass on general graphs belongs to the class of NP-hard problems, widely believed to have no efficient polynomial-time algorithms to solve them. An approach developed in computer science for dealing with such problems is to devise approximation algorithms; these are algorithms, whose run time scales polynomially with the input size, that provide solutions with provable guarantees on their quality in terms of the optimal unknown solution. Recently, several algorithms for the Ising spin-glass problem on a bounded degree graph that provide different approximation guarantees were introduced. D-Wave, a Canadian-based company, has constructed a physical realization of a quantum annealer and has enabled researchers and practitioners to access it via their cloud service. D-Wave is particularly suited for computing an approximation for the ground state of an Ising spin glass on its Chimera and Pegasus graphs-both with a bounded degree. To assess the quality of D-Wave's solution, it is natural to compare it to classical approximation algorithms specifically designed to solve the same problem. In this work, we compare the performance of a recently developed approximation algorithm to solve the Ising spin-glass problem on graphs of bounded degree against the performance of the D-Wave computer. We also compared the performance of D-Wave's computer in the Chimera architecture against the performance of a heuristic tailored specifically to handle the Chimera graph. We found that the D-Wave computer was able to find better approximations for all the random instances of the problem we studied-Gaussian weights, uniform weights, and discrete binary weights. Furthermore, the convergence times of D-Wave's computer were also significantly better. These results indicate the merit of D-Wave's computer under certain specific instances. More broadly, our method is relevant to a wider class of performance comparison studies, and we suggest that it is important to compare the performance of quantum computers not only against exact classical algorithms with exponential run-time scaling, but also against approximation algorithms with polynomial run-time scaling and a provable guarantee of performance.
在一般图上寻找伊辛自旋玻璃的基态属于NP难问题类别，人们普遍认为不存在有效的多项式时间算法来解决这类问题。计算机科学中开发的一种处理此类问题的方法是设计近似算法；这些算法的运行时间与输入大小成多项式比例，并且能为所提供的解决方案在质量上相对于未知最优解给出可证明的保证。最近，针对有界度图上的伊辛自旋玻璃问题引入了几种提供不同近似保证的算法。总部位于加拿大的D-Wave公司构建了量子退火器的物理实现，并通过其云服务使研究人员和从业者能够使用它。D-Wave特别适合在其具有有界度的嵌合体图和珀加索斯图上计算伊辛自旋玻璃基态的近似值。为了评估D-Wave解决方案的质量，将其与专门设计用于解决同一问题的经典近似算法进行比较是很自然的。在这项工作中，我们将一种最近开发的用于解决有界度图上伊辛自旋玻璃问题的近似算法的性能与D-Wave计算机的性能进行了比较。我们还将D-Wave计算机在嵌合体架构中的性能与专门针对处理嵌合体图量身定制的启发式算法的性能进行了比较。我们发现，对于我们研究的该问题的所有随机实例——高斯权重、均匀权重和离散二进制权重，D-Wave计算机都能够找到更好的近似值。此外，D-Wave计算机的收敛时间也明显更好。这些结果表明了D-Wave计算机在某些特定实例下的优势。更广泛地说，我们的方法适用于更广泛的性能比较研究类别，并且我们认为不仅将量子计算机的性能与运行时间呈指数比例缩放的精确经典算法进行比较，而且与运行时间呈多项式比例缩放且具有可证明性能保证的近似算法进行比较很重要。
