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

[Kashalpha]

一言でいうと

QUBOのヒューリスティックなソルバーであるD-Wave Hybrid Solver Service(HSS)、Simulated Bifurcation Machine(SBM)、Digital
Annealer(DA)、シミュレーテッド・アニーリング(SA)のベンチマーク論文。

論文リンク

https://arxiv.org/abs/2104.14096

概要

• SAはD-WaveのnealをIntel(R) Core(TM) i9-9900Kで実行
• ベンチマーク問題にはMQLib、8192変数のrandom NAE 3-SAT、8192変数のSK modelを利用
• 計算にかける時間は5分に設定
• 通信時間等はカウントしていない
• MQLibの45個の問題のうち、最も良い答えを見つけた回数は、HSSが22回、SBMが16回、DAが20回、SAが7回
• MQLibのLarge sizeの問題ではDAが強い
• random NAE 3-SATで、アニーリング時間が短時間の場合にはSBMとSAが良く、長い場合にはDAが良い
• SK modelで、アニーリング時間が短時間の場合も長時間の場合もSBMが良い。

先行研究

コメント