用于二次无约束二进制优化的量子启发式启发式求解器的基准测试。

Benchmark of quantum-inspired heuristic solvers for quadratic unconstrained binary optimization.

作者信息

Oshiyama Hiroki, Ohzeki Masayuki

机构信息

Graduate School of Information Sciences, Tohoku University, Sendai, 980-8579, Japan.

Institute of Innovative Research, Tokyo Institute of Technology, Yokohama, 226-8503, Japan.

出版信息

Sci Rep. 2022 Feb 9;12(1):2146. doi: 10.1038/s41598-022-06070-5.

DOI:10.1038/s41598-022-06070-5

PMID:35140264

原文链接:https://pmc.ncbi.nlm.nih.gov/articles/PMC8828756/

Abstract

Recently, inspired by quantum annealing, many solvers specialized for unconstrained binary quadratic programming problems have been developed. For further improvement and application of these solvers, it is important to clarify the differences in their performance for various types of problems. In this study, the performance of four quadratic unconstrained binary optimization problem solvers, namely D-Wave Hybrid Solver Service (HSS), Toshiba Simulated Bifurcation Machine (SBM), Fujitsu Digital Annealer (DA), and simulated annealing on a personal computer, was benchmarked. The problems used for benchmarking were instances of real problems in MQLib, instances of the SAT-UNSAT phase transition point of random not-all-equal 3-SAT (NAE 3-SAT), and the Ising spin glass Sherrington-Kirkpatrick (SK) model. Concerning MQLib instances, the HSS performance ranked first; for NAE 3-SAT, DA performance ranked first; and regarding the SK model, SBM performance ranked first. These results may help understand the strengths and weaknesses of these solvers.

摘要

最近，受量子退火启发，许多专门用于无约束二元二次规划问题的求解器被开发出来。为了进一步改进和应用这些求解器，明确它们在各种类型问题上的性能差异很重要。在本研究中，对四种二次无约束二元优化问题求解器的性能进行了基准测试，这四种求解器分别是D-Wave混合求解器服务（HSS）、东芝模拟分岔机（SBM）、富士通数字退火器（DA）以及在个人计算机上运行的模拟退火。用于基准测试的问题包括MQLib中实际问题的实例、随机异或非全相等3-SAT（NAE 3-SAT）的SAT-UNSAT相变点实例以及伊辛自旋玻璃谢林顿-柯克帕特里克（SK）模型。关于MQLib实例，HSS性能排名第一；对于NAE 3-SAT，DA性能排名第一；而对于SK模型，SBM性能排名第一。这些结果可能有助于了解这些求解器的优缺点。