NTTとNII,光で解を求めるコヒーレントイジングマシンと量子アニーリングマシンを比較

日本電信電話(NTT)と国立情報学研究所(NII)は,NTTが開発する「コヒーレントイジングマシン」と,カナダD-WaveSystemsの「量子アニーリングマシン」に,それぞれ同じグラフ構造の問題を解かせることによって,両者がどのような計算特性を持っているのかを実験により明らかにした。

複数の街を一番効率よく回る経路を求める「巡回セールスマン問題」に代表される組合せ最適化問題は,二者択一の選択肢が積みあがることで組合せの総数が爆発的に増えるため,現在のデジタルコンピューターによる総当たり計算では時間的に追いつかなくなる。

組合せ最適化問題を解くには,物理マシンで解ける形で表現する
組合せ最適化問題を解くには,物理マシンで解ける形で表現する

こうした組合せ最適化問題の多くは,頂点を選択肢とし,辺の重みを時間や距離といったコスト関数に見立てた「グラフ」で表現することができる。さらに,このグラフの頂点をスピンの向き,辺の重みを磁性の結合に置き換えることで「イジングモデル」と呼ばれる物理モデルで表現することができる。

相互作用するスピンの上・下の向きの組合せを二者択一の選択肢としてイジングモデルを人工的なスピンのネットワークで構築すると,そのシステムは全体のエネルギーが低くなるようにおのずとスピンの組合せを変化させる。このとき,最も全体のエネルギーが低い基底状態におけるスピンの組合せが問題の解となる。

D-Wave Systemsの量子アニーリングマシンは,超電導量子ビットを物理配線によって結合したスピンネットワークによりイジングモデルを構築する。量子ビットがグラフの頂点,そこから出る配線が辺となるので,辺密度の高いグラフをそのまま埋め込むと辺の数が不足するが,その場合は複数の量子ビットを1つのスピンとして利用する。

しかし,これにより扱うグラフサイズが制限されると共に正答率も低下する。そこで,事前に使用する量子ビット総数が最小化となるよう,最適な埋め込み方法を時間をかけてデジタルコンピューターで探し出し,正答率を改善することが行なわれている。

測定・フィードバック法を用いたコヒーレントイジングマシンの実験の様子(上)と概略図(提供:NTT)
測定・フィードバック法を用いたコヒーレントイジングマシンの実験の様子(上)と概略図(提供:NTT)

一方,NTTのコヒーレントイジングマシンは,縮退光パラメトリック発振器(DOPO)によるレーザーパルスの位相(0,p)を,それぞれスピンの上向き・下向きに置き換えることでイジングモデルを模擬する。相互結合を導入してネットワーク化されたDOPO群は,ネットワーク全体の光損失が最小となる光位相の組合せで発振するため,イジングモデルの基底状態となるスピンの組合せを得ることができる。

具体的には,全長1kmの長距離光ファイバーリング共振器中に2,048個のDOPOを一括発生させ,一部のDOPOパルスを取り出して測定,演算,変調を行ない,再び共振器に戻す「測定・フィードバック法」を用いることで,全てのDOPOの間に任意の相互結合を実装可能なコヒーレントイジグマシンを実現した。これにより,多数の頂点や辺を持つ複雑なグラフも,そのまま解くことができる。

今回の比較実験は,最大カット問題と呼ばれる,グラフの頂点を2つの部分集合に分割する際,頂点を結ぶ辺を切る数が最大となる分け方を求める問題で行なった。比較のためデジタルコンピューターで解ける大きさの問題を使って正解を用意し,コヒーレントイジングマシンと量子アニーリングマシンのどちらの最適解の到達確率が高いかを調べた。

両マシンのグラフ問題における正答率の辺密度 依存性。量子アニーリングマシンは辺密度が高 くなると正答率が急激に下がる(出典:NTT)
両マシンのグラフ問題における正答率の辺密度 依存性。量子アニーリングマシンは辺密度が高 くなると正答率が急激に下がる(出典:NTT)

様々な構造のグラフ問題を解いた結果,頂点間の辺密度が3本のグラフでは,量子アニーリングマシンの正答率がコヒーレントイジングマシンを僅かに上回った。しかし,グラフの辺密度が高くなるにつれ,量子アニーリングマシンの正答率は低下していき,50頂点,辺密度50%のグラフに対しての正答率は約0.001%まで下がった。

これは,研究で用いた量子アニーリングマシンの超伝導量子ビット間の最大結合数の制限が原因と考えられる。この辺密度増大に伴う計算性能の低下は量子アニーリングマシンの研究グループも認識しており,今後,超伝導量子ビット間の最大結合数を増やすことで改善が予想されるという。

一方,コヒーレントイジングマシンは,測定・フィードバック法により,グラフの辺密度によって計算性能が大きく低下することがない。そのため,50頂点と辺密度の高いグラフに対しても数十%程度の高い正答率を示し,量子アニーリングマシンを上回ったことを確認した。

今回用いた,2,048個のDOPOパルスを用いるコヒーレントイジングマシンの性能は,組合せ最適化問題においてデジタルコンピューターとほぼ同等だが,NTTは今後DOPOパルス数を10万に増やし,大幅に性能を向上したシステムを目指す。そのためには,光ファイバーリング共振器長の伸長や繰り返し周波数を上げると共に,このシステムの心臓部でもある位相を増幅する位相反応増幅器(PPLN導波路)のゲインをさらに上げる必要があるという。

さらに,このシステムがどのように社会実装されるのかも大きな課題となる。様々なアプリケーションが提示される中,本当に有効なものを見つけ出すことも,このシステムの実現に向けて同時に求められる。◇

(月刊OPTRONICS 2019年7月号掲載)

その他関連ニュース

  • 理研ら,3ピコ秒で進む分子構造変化を追跡 2019年11月28日
  • 東北大とNEC,量子アニーリングマシンで提携 2019年10月23日
  • 東大ら,チップ量子コンピューターへ一歩 2019年10月22日
  • 東北大ら,「疑似」量子ビット素子を開発 2019年09月19日
  • OIST,電子の量子状態を新たな方法で検出 2019年09月10日
  • 市大ら,ESR分光法で電子スピンの量子状態を制御 2019年08月23日
  • 量子コンピューティングの本命は?-東大でシンポ開催
    量子コンピューティングの本命は?-東大でシンポ開催 2019年07月03日
  • 東大ら,ホログラフィー原理で対称性の破れを証明 2019年06月21日