量子計算から生まれた組合せ最適化アルゴリズム――古典力学の断熱変化とエルゴード性を利用して解を探索する

DOI Web Site

書誌事項

タイトル別名
  • Simulated Bifurcation Algorithm Inspired by Adiabatic Quantum Computation
  • リョウシ ケイサン カラ ウマレタ クミアワセ サイテキカ アルゴリズム : コテン リキガク ノ ダンネツ ヘンカ ト エルゴードセイ オ リヨウ シテ カイ オ タンサク スル

この論文をさがす

抄録

<p>カナダのベンチャー企業D-Wave Systemsが量子アニーリング（断熱量子計算）に基づく量子コンピュータ「量子アニーラ」を商用化したことをきっかけに，組合せ最適化問題に特化した計算機がドメイン指向コンピューティングの新たなターゲットとして注目されている．量子アニーラはイジングモデルの基底状態を求める問題（イジング問題）を解くイジングマシンの一種である．イジングマシンの他の方式としては，光パラメトリック発振器を用いるコヒーレントイジングマシン（CIM）やシミュレーテッドアニーリング（SA）をベースにしたデジタル回路などがある．</p><p>こうした背景の下，筆者は2016年，カー効果を有するパラメトリック発振器（KPO）の量子分岐現象を利用するイジングマシン「量子分岐マシン（QbM）」を提案した．QbMは量子断熱定理に基づいてイジング問題を解けるだけでなく，ゲート方式のユニバーサル量子計算も行える新しい量子コンピュータである．</p><p>QbMの量子性を議論するために，QbMの古典力学版である「古典分岐マシン（CbM）」も同時に導入した．数値実験により，CbMもイジング問題を解けることがわかったが，これは興味深い結果である．なぜなら，QbMの原理である量子断熱定理は一般の量子系に関して成り立つが，古典力学にはこのような一般的に成り立つ断熱定理は知られていないからである．つまり，CbMは未知の古典断熱定理の存在を示唆すると同時に，古典断熱変化に基づく組合せ最適化の最初の例であり，真に量子にインスパイアされた発見と言える．</p><p>QbMとCbMの発見から1年ほど経った後，CIMが2000スピン・全結合という大規模なイジング問題をデジタル計算機に比べて圧倒的な速さで解いた，というインパクトの大きい結果が発表された．QbMではまだ大規模な問題を扱えないが，CbMであればシミュレーションによって大規模問題を扱えることに気が付き，CbMの研究を開始した．そして，CbMの運動方程式を高速シミュレーションに適した形に改変することで，高い並列性を有する組合せ最適化アルゴリズム「シミュレーテッド分岐（SB）アルゴリズム」を発見した．SAは代表的なヒューリスティクスの1つであるが，並列計算には向かない．SBは並列計算向きの新たなヒューリスティクスと言える．</p><p>SBの高い並列性をフルに活かし，そのポテンシャルを示すために，SBを既存のデジタル計算機で超並列実装し，CIMが解いた2000スピン・全結合問題を解き，CIMよりも約10倍高速という結果を得た．これは，社会実装しやすい既存のデジタル計算機を用いて高速かつ大規模な組合せ最適化を実現できる可能性を示している．</p><p>一方で，すでに触れたように，SBの原理は自明ではない．エネルギー極小点を追随するという古典断熱定理が一般に成り立つと仮定すればある程度説明できるが，数値実験で得られた高い性能を説明するには何か別の動作原理が必要と思われた．</p><p>そこで，2スピン・強磁性結合という最も単純なイジング問題の場合を詳しく調べたところ，断熱変化だけでなく，位相空間内のエネルギー的に許される領域をまんべんなく訪れるというエルゴード性が解探索に有効に働いていることを示唆する結果が得られた．つまり，SBは古典力学における断熱変化とエルゴード性に基づくと考えられる．より数学的に厳密なSBの原理説明は未解決問題であり，今後の課題である．</p><p>このように，量子計算から生まれたSBは，実用的な組合せ最適化マシンへの新たな道を開くとともに，理論物理学や数理工学などを横断する学際的な研究領域を生み出すと期待される．</p>

収録刊行物

  • 日本物理学会誌

    日本物理学会誌 75 (2), 83-89, 2020-02-05

    一般社団法人 日本物理学会

キーワード

詳細情報 詳細情報について

問題の指摘

ページトップへ