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

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

量子アニーリングは、横磁場を印加して上向きスピンと下向きスピンの量子重ね合わせ状態にしたスピン群を最初の状態として、徐々に横磁場を弱めつつ求めたいイジングモデルに相当するスピン間相互作用を入力することで、量子揺らぎを利用して高い確率で基底状態を得るアルゴリズムです（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％の場合も正答率はほぼ変わらず、正答率が結合密度にほとんど依存しないことが分かります。
結合密度増大時のCIMとD-Wave QAの性能の違いは、スピン間結合方法の違いに起因していると考えられます。本研究で使用した2000スピンのD-Wave QAは、超伝導量子ビット群はキメラグラフと呼ばれるグラフ構造となるよう物理的配線により結合されており、各量子ビットは６本の結合しか有していません。そのため、解きたいイジング問題をキメラグラフ構造に変換して入力する必要がありますが、結合密度の高い問題をより結合密度の低い問題に変換すると使用するスピン数が増大します。一方、CIMではDOPO間には物理的配線はなく測定・フィードバックにより全結合が可能であるため、結合密度にかかわらずイジング問題をそのまま入力可能であるという違いがあります。
今回の実験では、イジング問題のキメラグラフへの変換手法として、D-Wave QAで標準的に用いられている、問題を規則的に埋め込み全結合を可能とするNative clique embedding法と、事前に問題に応じて最適な埋め込み方法を計算することで必要な量子ビット数を最小化するヒューリスティック法を用いました。この2手法を用いたD-Wave QAの50スピンのイジング問題に対する正答率と、CIMのそれとを比較した結果を図3に示します。ヒューリスティック法を用いることにより、D-Wave QAで解く実質的な問題のサイズを小さくすることができるため、正答率の向上がみられますが、d=5以上ですでに正答率はCIMに及ばず、密度が増大するに従い差が顕著になることがここでも分かりました。この結果は、CIMやQAのような物理システムに基づくイジング型コンピュータにおいて、複雑なイジング問題をスピン間に実装する方法が、計算性能に大きく影響することを示しています。

本稿では、現時点（正確には、2019年時点）でのCIMとD-Wave QAの性能比較について述べましたが、CIMもQAも、今後さらに研究開発が進み一層性能が向上することが期待されます。これら相転移現象や量子性を示す物理システムに基づく新しい計算機が、現代のデジタル計算機にどれだけ優位性を持ち得るか、またその優位性を社会に寄与する「応用」に結びつけることができるかを明らかにすることが今後の重要な課題です。

■参考文献
（1） www.dwavesys.com/
（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） 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） 新井・八木・内山・富田・宮原・巴・堀川：“イジング型計算機による組合せ最適化のためのハイブリッド計算基盤，”NTT技術ジャーナル，Vol. 31, No. 11, pp. 27-31, 2019.
（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） 梅木・風間・小林・圓佛・笠原・宮本：“低雑音高出力パラメトリック増幅中継技術，”NTT技術ジャーナル，Vol. 31，No. 3, pp. 22-26，2019．
（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） 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.