3-Regular 3-XORSAT Planted Solutions Benchmark of Classical and Quantum Heuristic Optimizers

[Kashalpha]

一言でいうと

線形方程式系をマッピングした組合せ最適化問題をベンチマーク問題として、6つのQUBOソルバー、SATonGPU algorithm、Digital Annealer(DA)、Simulated Bifurcation Machine (SBM)、single CPUでのparallel tempering(PT)、Virtual MemComputing Machine(MEM)、D-Wave Advantage(DWA)の計算時間のスケーリングを比較した。
D-Waveのマシンを除いて、スケーリングの指数はほぼ同じ。

論文リンク

https://arxiv.org/abs/2103.08464

概要

• ベンチマーク問題は、2値変数からなるn/2本の線形方程式系を3次のbinary optimizationに焼き直したもので、もとの方程式は多項式時間で解が分かる
• QUBOに変形するのに追加でn/2のbitが必要なので、最終的なQUBOはn変数
• 評価指標はtime-to-solution(TTS)で、nが大きい領域でのn依存性（TTS ~ 10^{an+b}）を調査
• ベンチマーク結果のscaling exponentの値で、ソルバーは3グループに分けることができる
  • scaling exponentが0.017~0.019程度：SATonGPU、DAU
  • scaling exponentが0.021~0.025程度：SBM、PT 、MEM
  • scaling exponentが0.08程度：DWA
• DAが最も良く、DWAが一番ダメ
• DWAのscaling exponentは断熱定理から期待される結果よりも大きい->ノイズやコントロールエラーが原因（?）

先行研究

コメント

• scaling exponentを計算するときに使っている問題のサイズがアルゴリズムによって違うので少し微妙