Hamerly Ryan, Inagaki Takahiro, McMahon Peter L, Venturelli Davide, Marandi Alireza, Onodera Tatsuhiro, Ng Edwin, Langrock Carsten, Inaba Kensuke, Honjo Toshimori, Enbutsu Koji, Umeki Takeshi, Kasahara Ryoichi, Utsunomiya Shoko, Kako Satoshi, Kawarabayashi Ken-Ichi, Byer Robert L, Fejer Martin M, Mabuchi Hideo, Englund Dirk, Rieffel Eleanor, Takesue Hiroki, Yamamoto Yoshihisa
Research Laboratory of Electronics, Massachusetts Institute of Technology, 50 Vassar Street, Cambridge, MA 02139, USA.
National Institute of Informatics, Hitotsubashi 2-1-2, Chiyoda-ku, Tokyo 101-8403, Japan.
Sci Adv. 2019 May 24;5(5):eaau0823. doi: 10.1126/sciadv.aau0823. eCollection 2019 May.
Physical annealing systems provide heuristic approaches to solving combinatorial optimization problems. Here, we benchmark two types of annealing machines-a quantum annealer built by D-Wave Systems and measurement-feedback coherent Ising machines (CIMs) based on optical parametric oscillators-on two problem classes, the Sherrington-Kirkpatrick (SK) model and MAX-CUT. The D-Wave quantum annealer outperforms the CIMs on MAX-CUT on cubic graphs. On denser problems, however, we observe an exponential penalty for the quantum annealer [exp(-α )] relative to CIMs [exp(-α )] for fixed anneal times, both on the SK model and on 50% edge density MAX-CUT. This leads to a several orders of magnitude time-to-solution difference for instances with over 50 vertices. An optimal-annealing time analysis is also consistent with a substantial projected performance difference. The difference in performance between the sparsely connected D-Wave machine and the fully-connected CIMs provides strong experimental support for efforts to increase the connectivity of quantum annealers.
物理退火系统提供了解决组合优化问题的启发式方法。在此，我们在两类问题——谢林顿-柯克帕特里克（SK）模型和最大割问题上，对两种类型的退火机器进行基准测试，一种是由D-Wave系统公司制造的量子退火器，另一种是基于光学参量振荡器的测量反馈相干伊辛机（CIM）。在立方图上的最大割问题中，D-Wave量子退火器的表现优于CIM。然而，在密度更大的问题上，我们观察到，对于固定的退火时间，无论是在SK模型还是在50%边密度的最大割问题上，量子退火器相对于CIM都存在指数级惩罚[exp(-α)]。这导致对于超过50个顶点的实例，求解时间相差几个数量级。最优退火时间分析也与预期的显著性能差异一致。稀疏连接的D-Wave机器与全连接的CIM之间的性能差异，为增加量子退火器连接性的努力提供了有力的实验支持。
