2021/09/30

～世界最大級の光計算機による大規模組合せ最適化問題の高速な解探索を実証～

＞ニュースリリース

＞量子光制御研究グループ

研究の背景と経緯

現代コンピュータ技術を支えるCMOS電子回路の微細化技術が限界に近づき、デジタルコンピュータの性能が指数関数的に向上するというMooreの法則の終焉が現実のものとなってきた現在、物理現象を用いてデジタルコンピュータが苦手とする特定の問題を効率よく解く計算機の研究が盛んに行われています。特に、システムやネットワークの最適化に関連する組合せ最適化問題を、相互作用するスピン(^※1)群の理論モデル(イジングモデル)の最低エネルギーを求める問題に変換し、これをスピンの挙動を模擬する物理システムを用いた実験で解く「イジング型計算機」が注目されています。スピンを模擬する物理システムとして捕捉イオン、単電子素子、ナノメカニカル素子などを利用したイジング型計算機が実証されており、特に超伝導素子を用いた量子アニーリング装置では、既に数千のスピンからなるイジング問題の解探索が可能となっています。また、このようなイジング型計算機の概念を、デジタル計算機上で実装した計算機も発表されています。
縮退光パラメトリック発振器(degenerate optical parametric oscillator: DOPO)と呼ばれる、位相基準に対し0またはπの位相のみで発振する特殊な光発振器を用いてスピンを模擬する「コヒーレントイジングマシン(Coherent Ising machine: CIM)」は、常温で動作可能という特長を持つイジング型計算機です。NTT、NII、阪大、東大、スタンフォード大からなる共同研究チームは、1 kmの光ファイバリング中で1ナノ秒の時間間隔で2048個のDOPOパルスを発生し、測定・フィードバックと呼ばれる光・電気ハイブリッド手法で2048パルスの全結合を実現するCIMを2016年に発表しました。このCIM装置を用いて、2000要素の組合せ最適化問題の一問題を解き、CPU上で実装された焼きなまし法(Simulated annealing: SA)(^※2)よりも高速に同じ精度の解が得られることを確認しましたが、高速化の度合いは数十倍程度に限られていました。
本研究では、CIMの光システムと測定・フィードバック回路の飛躍的大規模化を行い、100,512個のDOPOの全結合を可能とするCIMを構築しました。これにより、最大10万スピン、100億結合のイジングモデルを実装可能な、物理システムに基づく世界最大級のイジング型計算機を実現しました。この10万スピンCIMを用いて10万要素の全結合グラフの最大カット問題(^※3)の解探索を行ったところ、CPU上に実装した標準的なSAよりも約1000倍の速さで同じ精度の解を得ました。また、DOPOを発振閾値付近で動作させた際には、SAと比較して、高い解精度を維持しつつ様々なスピン状態を幅広く取ることができることを確認しました。

研究の内容

本研究で実現した10万スピンCIM(図１)においては、5 kmの光ファイバリング中に配置された位相感応増幅器(Phase sensitive amplifier: PSA)を200 ピコ秒の時間間隔でオン・オフします。PSAは入力した光の0位相成分とπ位相成分を最も効率よく増幅するため、動作開始時にPSAから出力された微弱なノイズ光パルスがリングを周回しPSAを多数回通過するうちに、0位相またはπ位相で発振します(DOPOパルス)。5 kmの光ファイバ中の光パルスの伝搬時間は約25 マイクロ秒であるため、時間的に一列に並んだ12万個以上のDOPOパルスが得られます。このうち100,512パルスに対して、動作開始時から、PSAを通過するごとに全パルスのエネルギーの一部を分岐しその位相、振幅を測定、結果を高速行列演算回路に入力します。本行列演算回路には、あらかじめ解きたいイジング問題に相当する100,512行100,512列の行列が格納されており、測定結果(100,512要素のベクトル)と積算することで、各DOPOパルスへのフィードバック信号を得ます。その信号を用いて、DOPOパルスと同一の波長をもつ光パルスを変調し、リング中の各DOPOパルスに入力することで、DOPOパルス間の結合を実現します。光と電子回路のハイブリッド方式を用いることで、10万を超えるDOPOパルス間の全ての結合(最大10,102,662,144通り)が可能です。この「位相感応増幅-測定・フィードバック」動作をDOPOパルスがリング中を数十周～数百周する間繰り返すことで、DOPOパルス群の位相は全体として最も安定となる組合せをとります。DOPOパルス位相の0/πをスピンの+1/-1状態に対応させることで、与えられたイジング問題の近似解を得ることができます。

計算時間の評価

1. 10万ノード全結合グラフの最大カット問題の解探索を行い、基準スコア(貪欲法(^※4)で得られた近似解のカット値)に到達する時間で計算時間を評価。
2. 基準スコア到達時間は、CPU上で実装したSAでは0.7秒であったのに対し、CIMでは600 マイクロ秒となり、約1000倍高速であった(図2)

解精度の評価

1. 計算時間22ミリ秒 (光ファイバリング890周に相当)において10万ノード全結合グラフの最大カット問題における解精度を評価。結果を計算時間0.5秒、1秒のSAと比較。
2. CIMは高い解精度と広い解分布を両立する、SAでは得ることが困難な特徴的な解分布を得た(図3(a))。特に、ポンプ光振幅を低めに設定し、DOPO発振閾値近傍となるように動作させた場合(図3(b)、動作条件2)、非常に高いスコアを得るとともに、顕著な解分布の広がりを観測した。
3. 上記の特徴的解分布は、10万個のDOPOパルス群の集団的な相転移において、PSAから出力される自然放出ノイズやDOPO振幅測定の反作用に伴うノイズによってDOPO振幅の揺らぎが増強されたことにより生じたと考えられる。

技術のポイント

1. 10万個のDOPOパルス群の発生と安定化
   実験系の詳細を図4に示します。長さ5 kmの光ファイバリング中に、周期分極反転ニオブ酸リチウム(Periodically Poled Lithium Niobate: PPLN)導波路(^※5)を挿入します。ここで、光ファイバリングを構成する5 km光ファイバは、温度変化によるファイバ伸縮を抑制するため、ペルチエ素子により内部温度が±0.05℃の精度で制御された温度制御ボックスに格納されています。また、光ファイバリングの位相はピエゾ素子を用いたフィードバック制御により安定化されています。さらにリングを構成する光ファイバとしてゼロ分散波長を1.5 m近辺にもつ偏波保持光ファイバを用いることで、偏波回転を抑えた安定な光パルス伝搬を実現しています。PPLN導波路に、波長約780 nm、繰り返し周波数5 GHzのポンプパルス列を入力すると、ポンプ波長の2倍にあたる約1560 nmの波長において、ポンプ光の位相に対して0またはπの位相成分だけが増幅される(位相感応増幅)ため、位相0またはπのいずれかのみで発振するDOPOパルスを200ピコ秒の間隔(5 GHzの繰り返し)で発生することができます。 　長さ1 kmの光ファイバリングを用い、1 GHzの繰り返し周波数でDOPOパルスを発生していた従来のCIMに比べ、今回の5 km共振器では、長尺化による損失の増大と、繰り返し周波数の増大に伴うポンプパルスのピーク強度低下のため、PPLN導波路の効率向上が必要です。本研究では、高分解能フォトリソグラフィとドライエッチングの適用により、PPLN導波路の屈折率ゆらぎを低減し効率を向上しました。さらに、光ファイバと導波路の結合効率も改善することで、位相感応増幅の効率を従来の3倍程度まで増大しました。
2. 大規模行列演算システムの実現
   本CIMにおける測定・フィードバックでは、5 kmファイバリングをDOPOパルスが１周する25マイクロ秒毎に100,512 行 100,512列の行列と100,512要素のベクトルとの積演算を完了する必要があり、その実現のためには演算速度約1000テラops(^※6)、行列読出しのためのメモリ帯域約100テラ Byte/sが必要とされます。これらを実現するために、行列計算を並列実行する専用システムを開発しました。これにより、100,512個のDOPOパルスの全結合が可能となりました。

今後の展開

高精度かつ多様な解の探索が可能であるというCIMの特徴を生かし、創薬の候補物質探索や機械学習などのサンプリング問題への適用に向けた基礎研究を進めます。また、大規模な組合せ最適化問題の高速な解探索が行えるという特長を生かし、NTTで研究開発を進めるCIMに基づく計算システム「LASOLV」の応用を開拓します。

論文情報

論文タイトル：100,000-spin coherent Ising machine
著者： Toshimori Honjo, Tomohiro Sonobe, Kensuke Inaba, Takahiro Inagaki, Takuya Ikuta, Yasuhiro Yamada, Takushi Kazama, Koji Enbutsu, Takeshi Umeki, Ryoichi Kasahara, Ken-ichi Kawarabayashi, Hiroki Takesue
雑誌名：「Science Advances」（9月29日(米国東部標準時)付）

用語解説

※1 ... スピン

＋１または-1の二値の値をとる変数のこと。「スピン」の語源は、電子の量子力学的な内部自由度を表すために導入された「仮想的な自転自由度」に由来する。

※2 ... 焼きなまし法(Simulated annealing: SA)

確率的探索を用いて最適化問題を解く汎用近似解法の一つ。広い探索空間内の大域的最適解に対して、精度保証はないが多くの問題によい近似解を与えるヒューリスティックアルゴリズム。

※3 ... 最大カット問題

複数のノード(点)と、ノードを結ぶエッジ(線)からなるグラフにおいて、ノード群を2つの部分集合に分割する際、異なるグループに属するノード間に張られたエッジの数が最大となる分け方を求める問題。イジングモデルのエネルギー最小状態を求める問題と一対一対応する。

※4 ... 貪欲法(Greedy algorithm)

自明な初期解から始め、評価値が最も良いものの選択を繰返すアルゴリズム。

※5 ... 周期分極反転ニオブ酸リチウム(PPLN)導波路

異なる波長の光同士を相互作用させることが可能な「非線形光学効果」と呼ばれる特殊な特性を持つ結晶であるニオブ酸リチウム（LiNbO3）において、自発分極と呼ばれる結晶内の正負の電荷の向きを一定の周期で強制反転させた人工結晶を用いた光導波路。高い非線形光学効果を得ることができる。

※6 ... OPS (Operations per second)

1秒当たりの演算実行回数であり、演算性能を示す指標の一つ。100,512 行 100,512列の行列と100,512要素のベクトルとの積演算を制限時間内で実施するにあたり必要な乗算と可算の演算回数を1秒当たりに換算した量である。