NTT物性科学基礎研究所（以下 NTT物性研）は、情報・システム研究機構 国立情報学研究所（以下 NII）と共同で、縮退光パラメトリック発振器^*1のネットワークを用いて組合せ最適化問題の解を高速に探索する情報処理の新手法「コヒーレントイジングマシン」の特性を評価する実験を行い、コヒーレントイジングマシンのもつ柔軟なノード間接続の仕組みが、複雑なグラフ構造の問題を高い正答率で解くうえで重要な役割を果たしていることを明らかにしました。今回の一連の実験では、コヒーレントイジングマシンだけでなく、超伝導量子ビット^*2を用いた情報処理手法「量子アニーリングマシン」でも同じ組合せ最適化問題で正答率を比較しました。その結果、辺密度^*3 の高いグラフに対して、コヒーレントイジングマシンが量子アニーリングマシンを上回る正答率を示すことを明らかにしました。この実験結果から、コヒーレントイジングマシンは、ノード間の柔軟な相互接続によって複雑なグラフ構造の問題を高い正答率で解くことが可能であり、組合せ最適化問題に適した情報処理手法であると評価できました。

本研究では、NTT物性研よび米国スタンフォード大学に設置されているコヒーレントイジングマシンと、米国NASAエイムズ研究センタに設置されている量子アニーリングマシンを用いて、様々な辺密度をもったグラフに対する最大カット問題^*4の正答率評価を行いました。その結果、辺密度の高いグラフにおける解探索に対して、コヒーレントイジングマシンが量子アニーリングマシンを上回る正答率を示すことが実験で確認されました。この研究成果は、コヒーレントイジングマシンに実装されている測定・フィードバック法と呼ばれる仕組みが、多数の縮退光パラメトリック発振器の間に複雑なネットワーク構造を実装する基盤技術として有用であることを示すものであり、より大規模な組合せ最適化問題を高速に解くイジング型計算機の実現に寄与することが期待されます。

本研究成果は、2019年5月24日14時（米国時間）に米国科学誌「サイエンス・アドバンシーズ」で公開されました。

なお、本研究開発は内閣府　総合科学技術・イノベーション会議が主導する革新的研究開発推進プログラム（ImPACT）の山本喜久プログラム・マネージャーの研究開発プログラムの一環として行われました。

⇒ニュースリリース
⇒量子光制御研究グループ

研究の背景と経緯

私たちの社会が高度化するにつれて、インターネットや交通・電力網、ソーシャルネットワークなどの様々なシステムの構造も複雑化してきました。これらのシステムを効率的に運用することが近年の重要な課題となっています。そして、その多くは組合せ最適化問題と呼ばれる数学的な問題に置き換えて考えることができるため、コンピュータで効率的な運用法を見つけることが期待されています。

組合せ最適化問題とは、互いに影響を及ぼしあう多くの選択肢の組合せの中から、目的に最も合致する組合せを探し出す問題です。この問題は、選択肢の数が増えるにつれて組合せの総数が爆発的に増加するため、現代のコンピュータでも実際的な時間で解けない問題のひとつとされています。

この組合せ最適化問題の多くは、「イジングモデル」と呼ばれる物理モデルとして表現が可能です。このイジングモデルは相互作用するスピン^*5群のモデルであり、スピンの上向き・下向きが組合せ最適化問題における二者択一の選択肢に相当します。つまり、このイジングモデルの全体のエネルギーが最小となるスピンの組合せ（基底状態）の探索結果が、そのまま難解な組合せ最適化問題の解となります。

この相互作用するスピン群であるイジングモデルを、実際の物理システム上に人工的なスピンのネットワークとして構築すると、その物理システムはおのずと全体のエネルギーが低くなるようにスピンの向きの組合せを変えていきます。このような物理システム上での時間変化を応用することで、イジングモデルの基底状態を高速に探索する新しい手法の研究が様々な種類の物理システムを用いて近年進展しています。

本研究のコヒーレントイジングマシン(coherent Ising machine)は、縮退光パラメトリック発振器(degenerated optical parametric oscillator: DOPO)と呼ばれる特殊なレーザ発振器を人工的なスピンとして用います。多数のDOPOをネットワーク化すると、組み合わせ最適化問題を高速に解ける新原理のイジングモデル計算機として使えるため、注目を集めています。本方式では、独立したDOPOの光位相は発振時に0またはのどちらかにランダムに定まるため、この2つの位相状態をそれぞれスピンの上向き・下向きに対応させます。そして、相互結合を導入してネットワーク化されたDOPO群は、理想的にはネットワーク全体の光損失が最小となる光位相の組合せで発振を始めるため、イジングモデルの基底状態を与えるスピンの組合せを高い確率で得ることができます（図1）。

これまでの研究で、全長1 kmの長距離光ファイバリング共振器中に2,048個のDOPOを一括発生させ、測定・フィードバック法と呼ばれる手法（図2）を用いて全てのDOPOの間に任意の相互結合を実装可能なコヒーレントイジグマシンを実現しており、このコヒーレントイジングマシンを用いて、2,000ノードのグラフに対して組合せ最適化問題の1つである最大カット問題の解探索を行い、デジタル計算機上での焼きなまし法^*6と呼ばれるアルゴリズムとの解精度および計算速度の比較実験を行ってきました。

研究の内容

今回、異なる方式のイジング型計算機の計算性能の比較実験を実施しました。NTT物性科学基礎研究所と米国スタンフォード大学のそれぞれに設置されているコヒーレントイジングマシンと、米国NASA エイムズ研究所に設置されている超伝導量子ビットを用いた量子アニーリングマシンを用いて、組合せ最適化問題の1つである最大カット問題における正答率の評価実験を行いました(図3, 図4)。

様々な構造のグラフ問題を解いた結果、ノード間の辺密度の低いグラフに対しては、量子アニーリングマシンがコヒーレントイジングマシンを上回る正答率を示しました。一方で、グラフの辺密度が高くなるにつれ、量子アニーリングマシンの正答率は低下していき、50ノード、辺密度50%のグラフに対しての正答率はおよそ0.001%となりました。これは、本研究で用いた量子アニーリングマシンでは、超伝導量子ビット間の最大結合数に制限があり、キメラグラフ(図5)と呼ばれる特殊なグラフ構造に問題を変換して解く必要があるため、正答率が低下していると考えられます。この辺密度増大に伴う計算性能の低下は、超伝導量子ビット間の最大結合数を増加することで今後緩和されていくと考えられています。

これに対して、コヒーレントイジングマシンでは、測定・フィードバック法を用いることで全てのDOPO間に相互結合を実装することが可能であり、どのような構造のグラフもそのままの形で問題を解くことが可能です。そのため、グラフの辺密度によってコヒーレントイジングマシンの計算性能が大きく低下することはなく、50ノードの辺密度の高いグラフに対しても数十%程度の高い正答率で最大カット問題の解探索に成功し、量子アニーリングマシンを上回る計算性能を示すことが確認されました。

この研究成果は、物理システムを利用した大規模なイジング型計算機を実現する上で、ノード間の複雑なネットワーク構造をいかに柔軟に実現するかが、その計算性能を大きく左右することを示しています。今後、コヒーレントイジングマシンに実装されている測定・フィードバック法が、多数のDOPO間に複雑なネットワーク構造を実装する基盤技術として、より大規模な組合せ最適化問題を高速に解くイジング型計算機の実現に寄与することが期待されます。

技術のポイント

1. 全長1 kmの光ファイバ共振器中での大規模なDOPO群の発生
   コヒーレントイジングマシンの実験系を図2に示します。DOPOの発生には、周期分極反転ニオブ酸リチウム（Periodically Poled Lithium Niobate: PPLN）導波路^*7を用いた位相感応増幅器を光ファイバリング共振器の利得媒質として利用します。光ファイバ共振器には、長さ1 kmの偏波保持分散シフトファイバ、PPLN導波路、波長フィルタ、ファイバ伸縮器、および90:10光カプラが含まれています。外部から繰り返し周波数1 GHz (パルス間隔1 ns)のポンプパルス列を、PPLN導波路に入力することで、ポンプ光の位相に対して0またはの位相成分だけが増幅される位相感応増幅が得られ、位相が0またはのみの光が発振するDOPOを実現できます。ここで、光が共振器を1周する時間が約5 μs、ポンプパルスの時間間隔が1 nsなので、1つの共振器の中に5,000を超えるDOPOを一括発生することができます。NTTのコヒーレントイジングマシンでは、このDOPOのうち、2,048個を人工的なスピンとしてイジングモデルを模擬しています。
2. 測定・フィードバック法による任意のDOPO結合回路の実現
   コヒーレントイジングマシンでは、光学デバイスと電子演算回路を組み合わせた測定・フィードバック法と呼ばれる手法で、DOPO間の相互結合を実装しています(図2)。この手法では、光ファイバリング共振器内を周回するDOPOの一部は90:10カプラにより共振器外に取り出され、バランスドホモダイン検出器によって、それぞれの光振幅と位相が測定されます。この測定結果を用いて、1つのDOPOに対して他のDOPOから注入される光振幅の合計値が行列演算回路で計算され、再度光パルスに変換されて共振器に注入されます。この行列演算回路に解きたいイジングモデルのネットワーク構造に相当する行列を入力することで、全てのDOPO間に任意の相互結合が実現可能になります。この方法により、コヒーレントイジングマシンでは2,048ノードまでのグラフ問題をそのままの形で実装することができます。
3. 量子アニーリングマシンにおける超伝導量子ビットの結合
   本研究で用いた量子アニーリングマシンでは、超伝導量子ビット間が物理的な配線で結合されており、1つの量子ビットからの結合数は最大6本になっています。そのため、6本よりも多い結合数を持ったイジングモデルを模擬するために、キメラグラフと呼ばれる特殊なグラフ構造上で、複数の量子ビットの集団を1つのスピンとして扱うことで実効的な結合数を増やす方式が使われています。このキメラグラフへの問題の埋め込みには様々な方法が考えられています(図5)。1つはNative clique embeddingで、キメラグラフ上に問題を規則的に埋め込んでいくことで、必然的に全てのノード間での結合が可能になります。しかし、辺密度の高いグラフを埋め込むためには、より多くの量子ビットが必要となるため、実機に埋め込めるグラフサイズは制限され、計算の正答率が低下する一因にもなります。他にも、Heuristic embeddingとして、事前にデジタル計算機を用いて最適な埋め込み方法を探索することで必要となる量子ビットの総数を最小化し、量子アニーリングマシンの正答率を改善する方法があります。一方で、キメラグラフへの埋め込み方法の探索そのものが難しい問題となってしまい、事前計算に時間がかかります。また、グラフの辺密度の高い場合には良い埋め込み方法が見つからないこともあります。図4には、それぞれの手法で問題を解いた時の量子アニーリングマシンの正答率を示しています。このようにキメラグラフへの変換方法には、それぞれ利点と課題がありますが、今後１つの量子ビット当たりの最大結合数の増加に伴って、キメラグラフへの問題埋め込みの難しさは緩和されていくと考えられています。

今後の展開

今回の特性評価実験で解いた最大カット問題は、最適解探索の正答率を比較するために、デジタル計算機でも高速に最適解が探索可能な数十～数百ノードの小規模なグラフを対象としています。GPUやFPGA等のデジタル計算機上でのアルゴリズムも日々進化を続けており、組合せ最適化問題に対しても高い計算性能を発揮しています。今後、コヒーレントイジングマシンをはじめ、イジングモデルに基づいた新しい原理の計算機が、これらデジタル計算機に対して有用性を示すためには、数千～数万ノード以上の大規模なグラフ問題を高速に解くことが重要になると想定されます。NTTにおいても、さらに大規模なコヒーレントイジングマシンを開発し、組合せ最適化問題の高速な解探索に取り組んでいきます。

論文情報

　“Experimental investigation of performance differences between Coherent Ising Machines and a quantum annealer”
（コヒーレントイジングマシンと量子アニーリングマシンの計算特性の実験的評価）
Science Advances

用語解説

*1 ... 縮退光パラメトリック発振器
レーザ発振器の一種で、共振器の利得媒質に非線形光学効果を用いた位相感応増幅器を用いる。この位相感応増幅器の効果によって、ポンプ光に対する光位相が0またはのみの光が発振する。

*2 ... 超伝導量子ビット
量子アニーリングマシンで用いられている超伝導量子ビットは、超伝導リングにジョセフソン接合を配置した磁束量子ビットであり、超伝導リングを右回り・左回りに流れる巨視的な超伝導電流の状態を量子ビットとして利用している。

*3 ... グラフの辺密度
頂点（ノード）と、ノードを接続する辺によって表現されるグラフにおいて、1つのノードから接続できる他のノードの総数に対して、実際に接続される辺数の割合。

*4 ... 最大カット問題
グラフにおいて、ノードを2つの部分集合に分割する際、切れる辺数が最大となる分け方を求める問題。

*5 ... スピン
電子などの素粒子は小さな磁石としての性質をもつ。この磁石としての性質を古典的な球の自転になぞらえて「スピン」と呼ぶ。

*6 ... 焼きなまし法
シミュレーティド・アニーリング(Simulated Annealing, SA)とも呼ばれ、確率的探索を用いて最適化問題を解く汎用近似解法の一つ。広い探索空間内の大域的最適解に対して、精度保証はないが多くの問題によい近似解を与えるヒューリスティックアルゴリズム。

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