光を用いたコヒーレントイジングマシンと超伝導量子ビットを用いた量子アニーリングマシンの計算性能を実験で比較、ヒーレントイジングマシンの柔軟なノード間接続を可能にする仕組みが複雑なグラフ問題を解くための鍵となることが明らかに
2019-05-25 国立情報学研究所
日本電信電話株式会社（本社：東京都千代田区、代表取締役社長：澤田純、以下 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またはpのどちらかにランダムに定まるため、この2つの位相状態をそれぞれスピンの上向き・下向きに対応させます。そして、相互結合を導入してネットワーク化されたDOPO群は、理想的にはネットワーク全体の光損失が最小となる光位相の組合せで発振を始めるため、イジングモデルの基底状態を与えるスピンの組合せを高い確率で得ることができます（図1）。
〈図1〉
(a)コヒーレントイジングマシンの概念図。0またはπの位相のみをとるレーザ発振器である縮退光パラメトリック発振器(DOPO)をスピンとして用いる。イジングモデルにおけるスピン間相互作用は各DOPO光を相互に注入することで実現する。
(b)コヒーレントイジングマシンによるエネルギー最小状態の探索。DOPOネットワーク損失をDOPO群の位相の関数としてプロットしたもの。DOPOを駆動するポンプ光をゆっくりと増大することにより、多くの場合ネットワーク全体の損失が最小となる位相の組合せでDOPO群が発振する。発振時の各DOPOの位相を読み取ることで、該当するイジングモデルの基底状態を与える位相の組合せ(=スピンの組合せ)を高い確率で得ることができる。
これまでの研究で、全長1 kmの長距離光ファイバリング共振器中に2,048個のDOPOを一括発生させ、測定・フィードバック法と呼ばれる手法（図2）を用いて全てのDOPOの間に任意の相互結合を実装可能なコヒーレントイジグマシンを実現しており、このコヒーレントイジングマシンを用いて、2,000ノードのグラフに対して組合せ最適化問題の1つである最大カット問題の解探索を行い、デジタル計算機上での焼きなまし法（*6）と呼ばれるアルゴリズムとの解精度および計算速度の比較実験を行ってきました。
〈図2〉 測定・フィードバック法を用いたコヒーレントイジングマシンの実験系概略。PPLN導波路を用いた位相感応増幅器に、繰り返し周波数1 GHzのポンプ光を入力することで、1 kmの光ファイバ共振器内に2,048個のDOPOが一括発生する。この光ファイバ共振器内を周回するDOPOパルスをそれぞれ10%ずつ取り出して測定し、その測定結果を用いたスピン間結合の演算結果を再度光パルスに変換して光ファイバ共振器に帰還させることで、2,048個の全てのDOPO間に任意の相互結合を実装することができる。
研究の内容
今回、異なる方式のイジング型計算機の計算性能の比較実験を実施しました。NTT物性科学基礎研究所と米国スタンフォード大学のそれぞれに設置されているコヒーレントイジングマシンと、米国NASA エイムズ研究所に設置されている超伝導量子ビットを用いた量子アニーリングマシンを用いて、組合せ最適化問題の1つである最大カット問題における正答率の評価実験を行いました(図3, 4)。
〈図3〉コヒーレントイジングマシン(CIM)と量子アニーリングマシン(QA)の最大カット問題における正答率。辺密度の高いグラフ問題(50%)に対しては、コヒーレントイジングマシンの正答率が量子アニーリングマシンを大きく上回った。一方で、辺密度の低いグラフ問題(d=3)に対しては、量子アニーリングマシンの正答率が優位となった。
〈図4〉コヒーレントイジングマシン(CIM)と量子アニーリングマシン(QA)の50ノードのグラフ問題における正答率の辺密度依存性。量子アニーリングマシンに関して、問題をキメラグラフに埋め込むための2種類の方法について評価。コヒーレントイジングマシンは、グラフ変換が不要なため、辺密度が高くなっても正答率は大きな影響を受けない。
様々な構造のグラフ問題を解いた結果、ノード間の辺密度の低いグラフに対しては、量子アニーリングマシンがコヒーレントイジングマシンを上回る正答率を示しました。一方で、グラフの辺密度が高くなるにつれ、量子アニーリングマシンの正答率は低下していき、50ノード、辺密度50%のグラフに対しての正答率はおよそ0.001%となりました。これは、本研究で用いた量子アニーリングマシンでは、超伝導量子ビット間の最大結合数に制限があり、キメラグラフ(図5)と呼ばれる特殊なグラフ構造に問題を変換して解く必要があるため、正答率が低下していると考えられます。この辺密度増大に伴う計算性能の低下は、超伝導量子ビット間の最大結合数を増加することで今後緩和されていくと考えられています。
〈図5〉量子アニーリングマシンにおけるキメラグラフへの問題埋め込み方法
(a)Native clique embedding。問題を規則的に埋め込んでいく手法で、全てのノード間で結合が可能になるが、そのために大量の量子ビットが必要。
(b)Heuristic embedding。デジタル計算機による前処理によって、最適な埋め込み方法を探索する手法で、埋め込みに必要な量子ビット数を最小限にすることができる。一方、事前の計算時間が必要となり、埋め込み可能な結合数もある程度に制限される。
これに対して、コヒーレントイジングマシンでは、測定・フィードバック法を用いることで全ての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またはpの位相成分だけが増幅される位相感応増幅が得られ、位相が0またはpのみの光が発振するDOPOを実現できます。ここで、光が共振器を1周する時間が約5 ms、ポンプパルスの時間間隔が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
