SQBM+の技術
組合せ最適化ソルバー
Simulated Bifurcation Machine / シミュレーテッド分岐マシンとは
量子分岐マシン研究から生まれた、大規模な組合せ最適化問題を高速に解く、いま動く、実用的なイジングマシンです。
※ Simulated Bifurcation Machine = SBM
Software
特殊なハードウエアは不要。
GPUやFPGAで動作。
クラウドでも提供。
Large-scale
最大1,000万変数をサポート。
相互作用のグラフ表現に制約なし*1。
ハードウェアのスケールアップやクラスタリングによる性能向上も可能。
Fast
1万変数のイジング問題で、既存の代表的な解法であるシミュレーティドアニーリングの100 倍高速*2。
*1：ただし相互作用を表す非ゼロ係数は10億個まで
*2：当社環境における比較
組合せ最適化問題とは
組合せ最適化問題は、多数の選択肢がある中で、最も良い組み合わせを選ぶ問題です。問題のサイズ（組合せの総数）が大きくなると、全ての組み合わせを１つ１つ検証して良い解（良い組み合わせ）を見つけることが困難になり、従来の計算機技術で解を導き出すのは困難です。
組合せ最適化問題の例
物流最適化
走行距離が最短となるような輸送経路を探す。
渋滞緩和
渋滞が最も発生しないように各自動車の走行経路を決める。
金融ポートフォリオ最適化
リスクが低く収益性が高い「株の銘柄の組合せ」を探す。
創薬のための分子設計
所望の効能が高くなるよう薬を構成する分子の組合せを求める。
問題の規模が小さいとき
組み合わせを1つ1つ検証して答えを
出すことができる！
問題の規模が大きいとき
全ての組み合わせを１つ１つ検証するのは現実的に不可能。経験、勘、試行錯誤に頼ることになる。
自然現象を利用した解法、イジングマシン
組合せ最適化問題を磁性体の模型でモデル化し（イジングモデル）、イジングマシンでシミュレーションすると、最適解が得られます。
シミュレーテッド分岐アルゴリズムとは
当社における量子計算機「量子分岐マシン」の研究の過程で発見した、量子に由来する組合せ最適化アルゴリズムです。
シミュレーテッド分岐アルゴリズムの原理
分岐現象・断熱過程・エルゴード過程（カオス）といった古典力学の興味深い現象を組合せ最適化に初めて応用しました。当社独自の量子計算機「量子分岐マシン」から理論的に導かれたSBMの原理は、数理物理学における未知の定理の存在をも示唆する、真に量子に由来する発見です。
分岐現象
系のパラメータの変化に伴い、安定運動状態が1つから複数に変化する。
連続変数を離散変数に変換する
断熱過程
系のパラメータがゆっくりと変化するとき、エネルギーの低い状態に留まり続ける。
ポテンシャルの底を追いかける
エルゴード過程
エネルギー的に許される状態を満遍なく動き回り、ポテンシャルエネルギーの低い状態に長く滞在する。
より深い底を見つける
Simulated Bifurcation Machineが2000変数・全結合問題の解を求める際の2000粒子の運動の様子
どちらの図においても、赤はxが正、青はxが負であることを示している。
※ 再生ボタンをクリックすると、YouTubeに掲載している動画が再生されます。
※ YouTubeは弊社とは別企業のサービスであり、各サービスの利用規約に則りご利用ください。
SQBM+が高速な理由
逐次更新であるシミュレーテッドアニーリング（SA）と異なり、微分方程式を解く本技術は並列更新が可能であり、既存の並列計算機で高速化が可能です。並列化というコンピューティングの技術トレンドとの親和性が高いアルゴリズムです。
H. Goto (2016). Bifurcation-based adiabatic quantum computation with a nonlinear oscillator network, Scientific Reports, 6, 21686
SQBM+の速度・精度・規模を大幅に向上させる２つの新アルゴリズム
短時間で良解を見つける高速アルゴリズム「弾道的シミュレーテッド分岐アルゴリズム（bSB）
従来のaSBで生じるエラーを低減する工夫により、シミュレーテッド分岐マシンの高速化と高精度化を実現しました。これをFPGAで高速実装することで、2,000変数問題の良解を従来のシミュレーテッド分岐マシンに比べて約10倍高速に得ることができます（図1）
他のマシンを凌ぐ計算速度でより高精度な解を見つける高精度アルゴリズム「離散的シミュレーテッド分岐アルゴリズム（dSB）
疑似量子トンネル効果によって古典力学の限界を打破してさらなる高精度化を実現し、同じ2,000変数問題の最適解（厳密解の推定値）を得ることができます。これをFPGAで高速実装した2,048変数対応シミュレーテッド分岐マシンは、最適解を得るのにかかる計算時間で量子アニーラやコヒーレントイジングマシンなど他のマシンを凌駕する高速性を達成しました。また、16台のGPUからなるGPUクラスタを用いることで100万変数という世界最大規模のマシンを実現し、約30分で最適解にほぼ到達できました（図2）
これは、最適化問題を解くための一般的な手法であるシミュレーテッドアニーリングを通常の計算機（CPU）上で実行した場合およそ1年2か月かかる計算を30分という現実的な時間に短縮したこと（約2万倍の高速化）を意味します。
実社会の問題に適用する際は、即時に良解が必要な場合はbSB、時間をかけてでも極めて精度の高い解が必要な場合はdSB等といった用途に応じた使い分けが想定されます。
SQBM+は、この２つのアルゴリズムを自動的に使い分ける機能（パラメータ自動調整機能）を実装しています。
H. Goto et al., Science Advances Vol. 7, no. 6, eabe7953 (2021)
パラメータ自動調整機能
高速に高精度な解を得るには、最適化問題に応じて、計算の性質を制御する固有パラメーターを調整する必要がありますが、その調整方法には一定の規則がありません。良いパラメーターを探すために何度も計算を繰り返す試行錯誤が発生すると、SQBM+の高速・高精度な特長を損なってしまいます。
SQBM+では、パラメーターの最適な値を自動で調整して最良解を返すインタフェースを実現しています。ベイズ最適化手法を活用し、SQBM+サービス内部で複数回の最適化計算を行いながら、より良いパラメーターを自動探索します。これによって、解くべき最適化問題の入力データだけをSQBM+に投入することで、パラメーター調整の試行錯誤なしに最良解が得られます。
右図は、SBアルゴリズムにおける時間ステップ幅を表すパラメーターdtを例にその自動調整の様子を表したものです。dtの値によって解の精度は大きく変化します。
従来はdtの値の試行錯誤によって最良解を探しあてる必要がありましたが、パラメーター自動調整機能を使うことで、試行錯誤なしに1回の試行だけで、最良解を返せたことを示しています。
実問題へのSQBM+適用のイメージ
実問題を組合せ最適化問題に落とした後、「イジングモデル」という特定形式に変換する作業が必要です。
※ 本ページに掲載している数式はSBMの原理を説明するために使用しており、SBM PoC版の数式とは異なる場合があります。
技術解説
第1回： シミュレーテッド分岐アルゴリズムによるイジングマシン
量子コンピューターには、大きく分けて「ゲート方式」と「イジングマシン方式」があります。それぞれの方式と、当社の量子インスパイア―ド最適化技術の構造について解説します。
