更新日:2021/03/12

    コヒーレントイジングマシンと量子アニーリングの性能比較実験NTT物性科学基礎研究所

    NTT技術ジャーナル2021年3月号:特集「新原理コンピュータへの取り組み」より

    武居 弘樹(たけすえ ひろき)/ 稲垣 卓弘(いながき たかひろ)/ 稲葉 謙介(いなば けんすけ)/ 本庄 利守(ほんじょう としもり)

    はじめに

    組合せ最適化問題は、たくさんの選択肢の組の中から最適なものを見つけ出す問題で、従来のコンピュータが多くの場合効率良く解くことができない問題として知られています。近年、組合せ最適化問題を相互作用するスピンの理論モデル(イジングモデル)のエネルギー最小状態探索問題に変換し、スピンを模擬する物理システムを用いて実験で解くコンピュータ(イジング型コンピュータ)がさかんに研究されています。近年のイジング型コンピュータの先駆けとなったのが、超伝導量子ビットを人工スピンとして用いる量子アニーリングマシン(QA)で、すでにカナダのD-Wave社により数千の量子ビットを実装した計算システムがリリースされています(1)。コヒーレントイジングマシン(CIM)は、縮退光パラメトリック発振器(DOPO)を人工スピンとして用いるイジング型コンピュータであり(2)(3)、NTTではCIMに基づく計算システム「LASOLV®」の研究開発を行っています(4)。本稿では、NTTが米国NASA、スタンフォード大学と共同で実施したCIMとD-Wave QAの性能比較実験について説明します(5)

    コヒーレントイジングマシン

    DOPOは光共振器中に位相感応増幅器(PSA)を配置して実現する光発振器です。PSAは非線形光学媒質にポンプ光を入力することで、光パラメトリック増幅過程によりポンプ光位相に対して0またはπ位相の成分の光がもっとも効率良く増幅される光増幅器です(6)。そのため、発振しきい値より上ではDOPOの位相は0またはπのいずれかのみとなります。よって、例えば位相0状態を上向きスピン、π状態を下向きスピンと見立てることで、イジングスピンを表現することができます。NTTでは、約1 kmの光ファイバを含む光共振器を用い、PSAを1 GHzの周波数でオンオフすることで、時間多重された数千のDOPOパルスを一括生成しています(図1)。DOPOパルス間の相互作用(=スピン間相互作用)は測定・フィードバックにより実装します。測定・フィードバック法では、数千(N個とします)のDOPOパルス群が1 km光ファイバ共振器中を一周するごとに、ビームスプリッタでそのエネルギーの一部分を分岐し、すべてのDOPOパルスの振幅を測定、その結果を行列演算回路に入力します。行列演算回路には、あらかじめ解きたいイジング問題に対応するスピン間結合情報(N×N行列)を格納しておきます。そして、測定結果(要素数Nのベクトル)と結合行列の行列演算をすることで、次の周回における各パルスへのフィードバック情報を算出します。その情報を光パルスに乗せて、ビームスプリッタを介して光共振器中のDOPOパルスに注入することで、DOPOパルス間の結合を実現します。この測定・フィードバックの過程を、ポンプ光強度を0の状態から増大させながら、DOPOパルス群が共振器を100~1000周する間繰り返すうち、当初はランダムであったDOPOパルスの位相はより安定な組合せに時間発展し、最終的に入力したイジングモデルの基底状態に高い確率で到達します。NTTでは、2016年に測定・フィードバックに基づく2000スピンのCIMを実現し、最新のデジタルコンピュータ上で実装した焼きなまし法に比べ、2000要素の組合せ最適化問題の解を約50倍高速に得ることを報告しました(2)

    図1 測定・フィードバックを用いたコヒーレントイジングマシン
    図1 測定・フィードバックを用いたコヒーレントイジングマシン

    量子アニーリングマシンとの比較実験

    量子アニーリングは、横磁場を印加して上向きスピンと下向きスピンの量子重ね合わせ状態にしたスピン群を最初の状態として、徐々に横磁場を弱めつつ求めたいイジングモデルに相当するスピン間相互作用を入力することで、量子揺らぎを利用して高い確率で基底状態を得るアルゴリズムです(7)。これを、超伝導量子ビットを人工スピンとして用いて実装したD-Wave社のQA装置は、交通流の最適化に適用されるなど(8)、すでに実社会への応用をめざした取り組みに用いられています。今回、CIMを開発しているNTTとスタンフォード大学のそれぞれのCIM装置と、米国NASA Ames研究所が所有する2000量子ビットのD-Wave QA装置を用いて、共通のイジング問題を解いた場合の正答率の比較実験を行いました(5)。問題のスピン数をNp、各スピンと結合しているスピンの平均個数をd、結合密度をD=d/Npとします。結合密度50%のさまざまなサイズの問題に対する正答率の評価結果を図2(a)に示します。このように、CIMでは正答率は問題サイズを大きくしても顕著には低下せず、Np=80でも数10%を保ちました。一方、D-Wave QAではNpが大きくなると正答率は急激に悪化し、Np=50ですでに0.001%にまで低下しました。さらに、異なるdの問題に対する正答率とスピン数の関係を図2(b)に示します。d=3の疎な結合の問題の場合、D-Wave QAがわずかにCIMを上回りますが、dの値が増大するにつれ急激に正答率は低下します。一方、CIMではd=3の場合も、D=50%の場合も正答率はほぼ変わらず、正答率が結合密度にほとんど依存しないことが分かります。…

    ■参考文献

    1. (1)www.dwavesys.com/
    2. (2)T. Inagaki, Y. Haribara, K. Igarashi, T. Sonobe, S. Tamate, T. Honjo, A. Marandi, P. L. McMahon, T. Umeki, K. Enbutsu, O. Tadanaga, H. Takenouchi, K. Aihara, K. Kawarabayashi, K. Inoue, S. Utsunomiya, and H. Takesue:“A coherent Ising machine for 2000-node optimization problems,”Science, Vol. 354, No. 6312, pp. 603-606, Nov. 2016.
    3. (3)P. L. McMachon, A. Marandi, Y. Haribara, R. Hamerly, C. Langrock, S. Tamate, T. Inagaki, H. Takesue, S. Utsunomiya, K. Aihara, R. L. Byer, M. M. Fejer, H. Mabuchi, and Y. Yamamoto:“A fully programmable 100-spin coherent Ising machine with all-to-all connections,” Science, Vol. 354, No. 6312, pp. 614-617, Nov. 2016.
    4. (4)新井・八木・内山・富田・宮原・巴・堀川:“イジング型計算機による組合せ最適化のためのハイブリッド計算基盤,”NTT技術ジャーナル,Vol. 31, No. 11, pp. 27-31, 2019.
    5. (5)R. Hamerly, T. Inagaki, P. L. McMahon, D. Venturelli, A. Marandi, T. Onodera, E. Ng, C. Langrock, K. Inaba, T. Honjo, K. Enbutsu, T. Umeki, R. Kasahara, S. Utsunomiya, S. Kako, K. Kawarabayashi, R. L. Byer, M. M. Fejer, H. Mabuchi, D. Englund, E. Rieffel, H. Takesue, and Y. Yamamoto:“Experimental investigation of performance differences between coherent Ising machines and a quantum annealer,”Sci. Adv., Vol. 5, No. 5, eaau0823, May 2019.
    6. (6)梅木・風間・小林・圓佛・笠原・宮本:“低雑音高出力パラメトリック増幅中継技術,”NTT技術ジャーナル,Vol. 31,No. 3, pp. 22-26,2019.
    7. (7)T. Kadowaki and H. Nishimori:“Quantum annealing in the transverse Ising model,”Phys. Rev. E, Vol. 58, No.5, pp. 5355-5363, 1998.
    8. (8)F. Neukart, G. Compostella, C. Seidel, D. V. Dollen, S. Yarkoni, and B. Parney:“Traffic flow optimization using a quantum annealer,”Frontiers in ICT, Vol. 4, No. 29, Dec. 2017.

    関連するコンテンツ