SBMの技術

※ Simulated Bifurcation Machine = SBM

組合せ最適化問題とは


組合せ最適化問題は、多数の選択肢がある中で、最も良い組み合わせを選ぶ問題です。問題のサイズ(組合せの総数)が大きくなると、全ての組み合わせを1つ1つ検証して良い解(良い組み合わせ)を見つけることが困難になり、従来の計算機技術で解を導き出すのは困難です。

組合せ最適化問題の例

物流最適化
走行距離が最短となるような輸送経路を探す。

渋滞緩和
渋滞が最も発生しないように各自動車の走行経路を決める。

金融ポートフォリオ最適化
リスクが低く収益性が高い「株の銘柄の組合せ」を探す。

創薬のための分子設計
所望の効能が高くなるよう薬を構成する分子の組合せを求める。

問題の規模が小さいとき

組み合わせを1つ1つ検証して答えを
出すことができる!

問題の規模が大きいとき

全ての組み合わせを1つ1つ検証するのは現実的に不可能。経験、勘、試行錯誤に頼ることになる。

自然現象を利用した解法、イジングマシン


組合せ最適化問題を磁性体の模型でモデル化し(イジングモデル)、イジングマシンでシミュレーションすると、最適解が得られます。

SBMとは


当社における量子計算機「量子分岐マシン」の研究の過程で発見した、量子に由来する組合せ最適化アルゴリズムです。

SBMの原理


分岐現象・断熱過程・エルゴード過程(カオス)といった古典力学の興味深い現象を組合せ最適化に初めて応用しました。当社独自の量子計算機「量子分岐マシン」から理論的に導かれたSBMの原理は、数理物理学における未知の定理の存在をも示唆する、真に量子に由来する発見です。

分岐現象

系のパラメータの変化に伴い、安定運動状態が1つから複数に変化する。

連続変数を離散変数に変換する

断熱過程

系のパラメータがゆっくりと変化するとき、エネルギーの低い状態に留まり続ける。

ポテンシャルの底を追いかける

エルゴード過程

エネルギー的に許される状態を満遍なく動き回り、ポテンシャルエネルギーの低い状態に長く滞在する。

より深い底を見つける

Simulated Bifurcation Machineが2000変数・全結合問題の解を求める際の2000粒子の運動の様子

左図:2000粒子の位置xの時間変化(横軸が時刻、縦軸が位置x)。
右図:2000粒子の位相空間(xy平面)内での動き。(横軸が位置x、縦軸が運動量y)

どちらの図においても、赤はxが正、青はxが負であることを示している。

※ 再生ボタンをクリックすると、YouTubeに掲載している動画が再生されます。
※ YouTubeは弊社とは別企業のサービスであり、各サービスの利用規約に則りご利用ください。

SBMが高速な理由


逐次更新であるシミュレーテッドアニーリング(SA)と異なり、微分方程式を解く本技術は並列更新が可能であり、既存の並列計算機で高速化が可能です。並列化というコンピューティングの技術トレンドとの親和性が高いアルゴリズムです。

H. Goto (2016). Bifurcation-based adiabatic quantum computation with a nonlinear oscillator network, Scientific Reports, 6, 21686

実問題へのSBM適用のイメージ


実問題を組合せ最適化問題に落とした後、「イジングモデル」という特定形式に変換する作業が必要です。

※ 本ページに掲載している数式はSBMの原理を説明するために使用しており、SBM PoC版の数式とは異なる場合があります。