1．は じ め に
我々の社会構造が高度化するにつれて，それに含ま れる問題も複雑化していき，ディジタルコンピュータを もってしても困難な問題領域が生まれつつある．これに 対する新しい潮流として，量子コンピュータを筆頭とし た，従来のディジタルコンピュータとは異なる自然原理 で動作する新しい物理計算機の研究が始められており， 難解な問題に特化した高速化・効率化が期待されている． 当然ながら，ディジタルコンピュータにおいてもこれら の難問に対するアルゴリズム研究が進められており，そ の計算性能は非常に強力である．近年になって，実際に 動き始めた物理計算機とディジタルコンピュータとの比 較競争が始まり，我々の情報処理にとってこれら物理計 算機が新たな選択肢となり得るか否かが試される途上に ある．本稿で紹介するコヒーレントイジングマシンは， イジングモデルと呼ばれる物理モデルに変換された組合 せ最適化問題を解くことに特化した新原理の計算機であ り，2 048 個の縮退光パラメトリック発振器という特殊 な光発振器で構成されたネットワークに生じる自然現象 に基づいて効率的な解探索を行う計算機である． 1･1 組合せ最適化問題とは 我々の生活の中には，さまざまな選択肢が並んでいる． それは分かれ道の右左であったり，昼食を食べるか食べ ないかであったりする．それらの選択肢の大半において， 一つの選択は他の選択の結果へと影響を与える．そして， その生じた影響は関連する選択肢へとバタフライ効果の ように連鎖的に波及していく．組合せ最適化問題とは， このように複雑に影響し合う多数の選択肢の中で，全体 を俯瞰的に見たときに最も良い結果をもたらす選択肢の 選び方を模索する問題である． ここで例として，単純な二者択一（二択）の選択肢に おける組合せ最適化問題について考える．選択肢の数が n個の場合，可能な選択肢の組合せ総数は 2 の n 乗通 りとなる．つまり 2 000 個の選択肢からなる問題には約 10の 602 乗の組合せが存在することになり，一つの組 合せの確認を 1 ps で処理したとしても，すべてを調べ 終わるには 10 の 582 乗年以上かかってしまう．このよ うな問題を総当たり計算で解くことはもはや現実的では なく，より効率的に処理するための手法が研究されてき た． 1･2 ヒューリスティックな解探索手法 これまでの多くの計算では，然るべきプロセスを経る ことで，想定された時間のうちに，保証された精度の解 にたどり着くことが前提にされていた．しかし，先に述 べたように計算量が指数関数的に増加する問題に対して は，総当たり計算などの堅実な手法では現実的な時間内 に計算が終了しないことが多い．このような問題を解決 する方法論の一つとして，精度保証のある解に必ずたど り着くという前提条件を取り払うことによって，より能 動的に解の探索を行うヒューリスティックと呼ばれる手 法がある．この手法では，経験則や推論に基づいた戦略 のもとで，試行錯誤を繰り返すことによって徐々に解の 精度を向上させていく．その性質上，計算が失敗に終わ ることもあるが，精度保証のある手法と比較して極めて 短時間のうちに高精度な解を見つけてくる可能性が高い 手法である．このような確率的な動作に対して，「必ず 答えにたどり着かないものは計算とは呼べない」という 意見もあるが，素因数分解のような数学的な問題を別と して，現実的な問題では，用途に合った短い時間内に適 切な精度での解探索が重要視されることが多い．計算に かける時間と得られる解の精度，このトレードオフな関 係を用途に合わせて柔軟に調整できるという点がヒュー リスティックの利点であるといえる．現在，ディジタル コンピュータで広く活用されているヒューリスティック光発振器のネットワークを利用した
組合せ最適化
Combinatorial Optimization with a Network of Optical Oscillators
稲垣 卓弘
日本電信電話株式会社 NTT 物性科学基礎研究所Takahiro Inagaki NTT Basic Research Laboratories. [email protected]
Keywords:
combinatorial optimization, optical parametric oscillator, coherent Ising machine. 「自然界に見いだす数物構造を利用した知的情報処理」な手法の一つが，焼なまし法（Simulated Annealing： SA）と呼ばれる手法であり，組合せ最適化問題の解探 索に強力な性能を発揮する．SA では，勾配計算により 解精度を向上させていく過程で，図 1（a）のように外 乱として解精度が低下する方向にも一定の割合で組合せ を選択していく．これは局所解と呼ばれる状態に解が収 束してしまうことを避けるための工夫であり，この外乱 の割合を時間とともに徐々に下げていくことによって， 高精度な解へと計算結果を収束させることが可能にな る．このように局所解への収束を効率良く回避するため の工夫が組合せ最適化問題を解くうえで重要であり，用 途に合わせてさまざまな戦略をもったアルゴリズムが研 究されている． 1･3 イジングモデルとイジング型計算機 近年になって，組合せ最適化問題に対して物理現象を 応用することで，より高速かつ効率的な解探索を行うと いうアプローチが始まっている．組合せ最適化問題の多 くは，イジングモデルと呼ばれる物理モデルに変換して 解くことが可能であることが知られている．イジングモ デルは相互作用するスピン系の振舞いを記述する統計力 学上のモデルであり，上向き（＋1）と下向き（−1）の 二つの状態をもつスピンと，それらのスピン間に発生す る相互作用の関係を表している．このイジングモデルの ハミルトニアンは H jij i<j i =－ σ σj として定義される．ここで，σiは i 番目のスピン状態を， Jijは i 番目と j 番目のスピン間相互作用係数を表してい る．より一般的には，これに外部磁場を表す項が加わる． この式はスピン系のエネルギーを表しており，このエネ ルギーを最小化するスピン状態σiの組合せをイジング モデルの基底状態と呼ぶ．このイジングモデルにおける 個々のスピン状態は，組合せ最適化問題における二択の 選択肢に割り当てることができ，スピン間相互作用 Jij はそれぞれの選択肢によって変化するコスト関数に相当 する．つまり組合せ最適化問題を変換することで Jijが 与えられたとき，このイジングモデルの基底状態を探索 することで，元の問題のコスト関数を最小化もしくは最 大化するための解を得ることが可能となる． イジングモデルは物理系を記述するためのモデルであ り，条件を満たす現実の物理システムを用いて高速にシ ミュレートすることができる．また，それぞれの物理シ ステムの特性を利用することで，より効率的にイジング モデルの基底状態探索が可能になると期待されている． 近年，超伝導量子回路のネットワークに生じる量子ト ンネル効果を用いた量子アニーリング [Johnson 11] や， 集積化された CMOS 回路を応用した手法 [Yamaoka 15] など，さまざまな物理システムを用いたイジング型計算 機が実現し，組合せ最適化問題の解探索に挑戦を始めて いる．
2．コヒーレントイジングマシン
我々は，イジングモデルを実装する物理システムと して，縮退光パラメトリック光発振器（Degenerate Optical Parametric Oscillator：DOPO）と呼ばれるレー ザ発振器のネットワークを用い，新原理のイジング型計 算機を実現した．DOPO から出力されるレーザ光の位 相は，発振しきい値以下では完全にランダムな位相状態 となるが，外部からの利得上昇によって発振しきい値を 超える際に，0 位相もしくはπ位相のどちらかの位相状 態に等確率で分岐していく性質がある．コヒーレントイ ジングマシンでは，この離散化した二つの光位相をイジ ングモデルにおけるスピン状態として扱う．一方で，イ ジングスピン間の相互作用 Jijは DOPO 間の光結合係数 として実装される．この結合係数が正の場合，図 1（b） のように結合される二つの DOPO が同位相であれば光 の干渉によって互いに強め合い光利得となり，逆位相で あれば互いに弱め合い光損失となる．また，結合係数が 負の場合は逆の関係となる．ここで，DOPO ネットワー ク内の光結合によって生じる光損失の総和は，元となる イジングモデルにおけるスピン系のエネルギーに対応す る．つまり，イジングモデルの基底状態探索という問題 を，ネットワーク全体の光損失が最小となる DOPO 光 位相の組合せの探索問題へと置き換えることができる． 2･1 レーザ発振を利用した基底状態探索 コヒーレントイジングマシンでは，光損失が最小化 される DOPO 光位相の組合せを効率的に探索するため， レーザ発振器のもつ発振しきい値特性を利用している． 一般的にレーザ発振器では，光を増幅するために周回構 造となった光共振器内に，周回光を増幅する利得媒質が 配置されている．ここで，光が共振器内を周回する際に は，さまざまな光学素子を通過することで比率の固定さ れた光損失が発生する．この共振器内の光損失が発振し きい値となり，利得媒質から与えられる増幅率がこのし きい値を上回ることで，周回光が連鎖的に増幅されるよ 図 1 （a）組合せ最適化を解くさまざまな手法，（b）スピンの組合 せによるイジングエネルギーの変化うになりレーザ発振が始まる．この発振しきい値付近に おけるレーザ光の出力強度の変化は非常に急峻であり， わずかな光利得の変化に対して鋭敏に反応する． ここで DOPO 間に光結合を導入すると，相互注入さ れる光位相の組合せを反映した光利得（もしくは光損 失）がおのおのの共振器内の周回光に加わる．このとき， 共振器内の利得媒質による増幅率が発振しきい値付近で あった場合，DOPO 間の光結合によって加わる光利得の 変動によって，おのおのの DOPO が発振しきい値を超 えるか否かが左右されることになる．これは，結合した DOPO光位相の組合せによって，実効的な発振しきい値 が変化することを意味する．そして図 1（a）のように， DOPOの利得媒質の増幅率をゆっくりと上昇させてい くことで，原理的にはネットワーク全体の利得が最大と なる（損失が最小となる）光位相の組合せで最初に発振 しきい値を超えることになる．このようにして発振を始 めた各 DOPO の光位相を測定することでイジングモデ ルの基底状態を得ることが可能になる．当然ながら，現 実の物理システムでは，利得媒質の増幅率などの制御パ ラメータには時間的な揺らぎがあり，その影響で基底状 態よりも発振しきい値の高い光位相の組合せで発振が始 まることもある．しかし，基本的には損失の少ない組合 せから発振しきい値を超えていくため，イジングモデル として見たときに高エネルギーな局所解となる可能性は 低く，基底状態付近の高精度な近似解へと収束する可能 性が高くなることがこの手法の利点といえる．このよう にコヒーレントイジングマシンでは，DOPO ネットワー クが発振過程において，全体として損失の少ない光位相 の組合せを自発的に選択するという性質を利用すること で，イジングモデルの基底状態探索を効率的に行うこと が可能になる． 2･2 コヒーレントイジングマシンの変遷 レーザ発振器のネットワーク構造とその発振しきい値 特性を利用したイジングモデルの基底状態探索は，2011 年に国立情報学研究所の宇都宮聖子らによって提唱され た [Utsunomiya 11]．当初の研究では，面発光レーザの 偏波状態（右回り円偏光，左回り円偏光）をイジングモ デルのスピン状態として見立て，相互の注入同期によっ て生じる光損失を最小化することで解探索を行うという 仕組みで実験が行われた．この方式では，各イジングス ピンに対して複数のレーザ発振器を割り当てて，それら の間に空間的な光結合を実装する必要があるため，実験 系の構築があまり容易ではなかった． この状況を変えたのが 2014 年にスタンフォード大学 の Alireza Marandi らが行った時間領域で多重化された DOPOネットワークの構築であった [Marandi 14, Wang 13]．彼らは長尺な光共振器を構築し，その 1 周を時間 領域で分割することで，同時に複数の DOPO を一つの 光発振器で一括発生させることに成功した．この方法で は，DOPO を時間領域で多重化するため，イジング型計 算機の計算時間としては不利に働くが，すべての DOPO が同一の光共振器内で発生するため，非常に均質かつ互 いに干渉性の良い DOPO を大量に用意することが可能 となり，実験装置を構成するうえでの恩恵が非常に大き い．また，DOPO の光位相をスピン状態として扱うこ とで，面発光のレーザの偏波状態と比較して制御性や光 測定における利便性が大幅に向上された．彼らは四つの DOPOを時間多重で発生させ，時間遅延のある光干渉計 を用いた光結合を実装し，4 スピンのコヒーレントイジ ングマシンを実現した．また，この方式を拡張した 16 スピンのイジングモデルの基底状態探索も行われている [Takata 16]． ここで，イジング型計算機で現実的な組合せ最適化問 題を解くためには，イジングモデルのスピン数を大幅に 増加させる必要がある．そのためには，共振器のさらな る長距離化が必須となる．しかし，4 スピンのコヒーレ ントイジングマシンでは，空間光学系と呼ばれる反射用 のミラーなどを配置した実験系で光共振器が構築されて おり，実現可能な共振器の長さにも限界があった．そこ で我々は，全長 1 km の光ファイバを利用した長距離の リング型共振器を構築し，DOPO ネットワークの大規模 化を行った [Inagaki 16a, Takesue 16]．これにより数千 から数万個の規模の DOPO を一括発生することが可能 になり，2016 年に 10 000 スピンの一次元イジングモデ ルの模擬実験に成功した．この実験では，遅延光干渉計 の位相差を変化させることで，DOPO ネットワークが一 次元イジングモデルにおける強磁性的・反強磁性的な振 舞いや，ドメイン構造の形成など，低温下のスピン集団 の振舞いをよく模擬していることが実証された． 一方で，DOPO 間に実装可能な光結合の数や自由度 も，複雑な構造のイジングモデルを解くうえで重要とな る．しかし，光ファイバ共振器内に多数の遅延光干渉計 を導入することは困難である．そこで我々は測定・フィー ドバック法と呼ばれる手法を用いて，すべての DOPO 間に擬似的な光結合を実装した．後述するように，この 手法では光学システムと電子計算のハイブリッドな処理 によって，実際の光配線をすることなくすべての DOPO 間での相互結合が可能となる．この結果，2016 年には NTTで 2 048 個の DOPO，スタンフォード大学で 100 個の DOPO に対して任意の複雑なネットワーク構造を もった光結合を設定可能なコヒーレントイジングマシン が実現し，本格的な組合せ最適化問題の解探索が可能と なった [Inagaki 16b, McMahon 16]．
3．イジングマシンの構成
ここでは，NTT 物性科学基礎研究所に設置されてい る 2048-DOPO のコヒーレントイジングマシンの構成を 紹介する．図 2（a）に示すように，このマシンの中核となる部分は全長 1 km の光ファイバリング共振器であり， その利得媒質として位相感応増幅器が配置されている． また，測定・フィードバック法による擬似的な光結合 の実装として，DOPO 出力光の位相測定装置，結合係数 演算のための FPGA モジュール，演算結果を光パルス として共振器内に注入する光学系が組み込まれている． 3･1 位相感応増幅器 DOPOの発生には，位相感応増幅と呼ばれる非線形光 学現象が用いられる．一般に光パラメトリック増幅と呼 ばれる非線形光学現象では，二次（もしくは三次）の非 線形光学効果をもつ媒質に，角周波数ωpのポンプ光と 角周波数ωsのシグナル光を入力すると，角周波数ωp− ωsのアイドラ光が発生する．このとき，シグナル光の ポンプ光との位相差がθであれば，発生するアイドラ光 のポンプ光との位相差は−θとなる．ここで，シグナル 光とアイドラ光の角周波数が縮退しているとき（ωi＝ωs のとき），シグナル光に生じる増幅率は実効的に cosθに 比例するようになり，ポンプ光との位相差が 0 位相もし くはπ位相のシグナル光が最も効率良く増幅される．こ の現象が位相感応増幅であり，このような縮退条件下で の光パラメトリック増幅過程を用いた光発振器が DOPO と呼ばれている．2048-DOPO のコヒーレントイジング マシンでは，位相感応増幅器として，NTT 先端集積デ バイス研究所の梅木毅伺らによって作製された周期分 極反転ニオブ酸リチウム（Periodically Poled Lithium Niobate：PPLN）導波路中のパラメトリック下方変換 過程を利用している [梅木 15]． 3･2 測定・フィードバックシステム 遅延光干渉計のような実際の光配線を伴わずに，任 意の DOPO 間で光結合を実現するため，測定・フィー ドバック法と呼ばれる手法が提案された [Haribara 16]． この手法では，図 2 のように共振器を周回する光の一部 分を光カップラで分岐し，2 048 個の DOPO の光振幅と 位相をホモダイン検出器で測定する．そして検出器から 出力された測定信号は，ディジタル信号へと変換されて FPGAモジュールへと入力される．FPGA モジュールに は DOPO のネットワーク構造を指定する結合行列 Jijが 入力されており，おのおのの DOPO にフィードバック する光振幅・位相を計算する．この計算結果を再び光パ ルスに変換し，対象となる DOPO に同期させて注入す ることで，任意の DOPO 間の相互結合を擬似的に実現 することが可能となる．ここで，DOPO が 1 km の共振 器を周回する時間は約 5 μsであり，FPGA モジュールは それ以下の時間でフィードバック信号を計算する必要が ある．そのため，FPGA モジュールでは単純な相互結合 の計算（すなわち「問題の入力」）のみが実行され，イ ジングモデルのエネルギー計算や組合せ最適化などの処 理はいっさい行われていない．このようにコヒーレント イジングマシンでは，光学システムと電子計算のハイブ リッドな処理によって，実際の光配線をすることなくす べての DOPO 間での相互結合が実現することができる．
4．性 能 評 価 実 験
測定・フィードバック法を用いることで，2 048 個の DOPO間に任意の相互結合が可能なコヒーレントイジ ングマシンが実現し，さまざまなネットワーク構造に対 して組合せ最適化問題の解探索が可能になった．このコ ヒーレントイジングマシンの性能を評価するため，我々 図 2 （a）測定・フィードバック法による 2048-DOPO コヒーレントイジングマシンの構成概略図． （b）NTT 物性科学基礎研究所に設置される最新のコヒーレントイジングマシン「LASOLV」の外観 図 3 位相感応増幅器に用いる PPLN 導波路デバイスはディジタルコンピュータや他のイジング型計算機であ る量子アニーリングマシンとの比較実験を行った． 4･1 ディジタルコンピュータとの比較実験 コヒーレントイジングマシンの性能評価のため，基本 的な組合せ最適化問題の一つである最大カット問題の解 探索を行い，ディジタルコンピュータとの計算時間の比 較実験を行った [Inagaki 16b]．最大カット問題の厳密解 は，変換されたイジングモデルの基底状態と 1 対 1 で対 応するため，イジング型計算機にとって最も実装に適し た組合せ最適化問題であるといえる．ここで，問題のネッ トワーク構造として，2 000 頂点の完全グラフ（約 200 万辺，辺の重みはランダムに±1）を用いて計算性能の 評価を行った．2 000 頂点の問題では厳密解を評価する ことは非常に困難であるため，目標とする精度の近似解 に到達するまでに要した時間を評価する．近似解の目標 精度は，GW-SDP と呼ばれる精度保証のあるアルゴリズ ムで算出された解のイジングエネルギー値（−60 278） とした．ディジタルコンピュータによる計算時間の比較 対象として，今回は SA を用いた．コヒーレントイジン グマシンの動作は基本的にヒューリスティックであり， これに対して総当たり計算や精度保証のあるアルゴリズ ムを計算時間の比較対象とするのは公平ではない．そ のため，最も一般的なヒューリスティックである SA を 採用することにし，Intel Xeon X5650（2.67 GHz）の CPU上で計算を行うことにした．これは，頂点サイズ が 2 000 程度の組合せ最適化問題を解くにあたっては， CPUのキャッシュ上に結合行列 Jijをすべて実装し，行 列計算におけるメモリアクセス時間を最小化すること が，現時点では最も有効な手段であると考えられるため である．このようにして，2 000 頂点の同じグラフ問題 に対して最大カット問題の解探索を行い，それぞれの計 算時間を比較した結果が図 4（c）であり，ディジタル コンピュータでの SA に対してコヒーレントイジングマ シンの約 50 倍の計算時間の高速化が確認された．加え て，さまざまな構造のグラフ問題で計算精度を比較した 結果，特に辺密度の高いグラフ問題において SA での計 算量が増加するため，コヒーレントイジングマシンの優 位性が現れる結果となった． 4･2 量子アニーリングとの比較実験 次に，異なる物理システムを用いたイジング型計算機 との性能比較として，米国 NASA Ames 研究センタに設 置されている超伝導量子回路を用いた量子アニーリング マシンとのベンチマーク実験を実施した [Hamerly 18]． ディジタルコンピュータで厳密解を求めることができる 100頂点程度の小規模なグラフ問題を対象に，イジング モデルの基底状態探索の成功確率を比較した結果，辺密 度の高いランダムグラフ問題においてコヒーレントイジ ングマシンの優位性が顕著に現れることが示された．一 方で，各頂点に接続される辺数が 3 本程度の辺密度が低 いランダムグラフに対しては，量子アニーリングマシン の成功確率がコヒーレントイジングマシンを上回ること がわかった． このベンチマーク実験における成功確率の差は，基盤 となっている物理システムの性質に加えて，その相互結 合の実装方法の違いに起因していると考えられる．先述 のように，コヒーレントイジングマシンでは，2 048 個 の DOPO は時間領域で多重化され，測定・フィードバッ ク法によって擬似的な光結合が 1 系統の光配線で実現さ れるため，空間的な制約を受けることなく任意の相互結 合が可能である．一方で，量子アニーリングマシンでは， 2 048個の超伝導回路が空間的に並列配置されており， それらの間に物理的な配線が行われている．そのため， 空間的な制約から一つの頂点回路から接続可能な結合数 が限られることになり，辺密度の高いグラフ構造を実装 するためには，より多くの超伝導回路を用いて間接的な 相互結合を導入する必要がある．つまり，同じ頂点数の グラフ問題を解く際に，より大きな頂点数のグラフ問題 に変換して計算を行わなければならないため，計算の成 功確率が低下しているものと考えられる．このような物 理的な相互結合が受ける空間的な制約は，量子アニーリ ングに限った問題ではなく，物理システムを用いたイジ ング型計算機の多くが本質的に抱える問題である．今後， さまざまな物理システムがもつ利点をそれぞれ最大限に 追求する中で，ネットワーク構造における相互結合の柔 図 4 （a）2000-DOPO の計算過程における挙動のヒストグラム，（b）2 000 個中 50 個の DOPO 振幅の時間発展， （c）2 000 頂点の完全グラフ問題の組合せ最適化におけるイジングエネルギーの時間変化
軟性をいかにして確保するかが，イジング型計算機の総 合的な計算能力向上の大きな鍵となると予想される．
5．今 後 の 展 開
2 048個の DOPO で構成されるコヒーレントイジング マシンが，最大カット問題といった基礎的な組合せ最適 化問題を高速に解くことができることが実験で確認され てきた．一方で，現実的な問題は最大カット問題よりも さらに複雑な構造をもっている．例えば巡回セールスマ ン問題では，セールスマンが各都市を 1 回ずつ訪れると いう制約条件の中で，移動にかかる時間や費用といった コストを最小化する経路の組合せを探す必要がある．こ のような制約条件をイジング型計算機に実装するために は，イジングモデルのハミルトニアンに外部磁場を表す 項を追加しなければならない．また，各経路のコストを 表現するためにスピン間相互作用 Jijの大きさにもある 程度の分解能が要求される．2016 年の時点では，我々の コヒーレントイジングマシンには外部磁場を加える機能 がなく，設定可能なスピン間相互作用 Jijの値も 0，±1 の 3 値に制限されていた．その後，光学系と測定・フィー ドバックに用いる FPGA モジュールが改良され，外部 磁場項と 8 bit 分解能の Jijが設定可能となった．これら の追加機能を利用することで，地図の配色問題やグラフ クラスタリング問題などをコヒーレントイジングマシン で高速に解くことができるようになってきている．一方 で，今後のイジング型計算機の新しいアプリケーション の探索には，より多くのユーザにこのマシンを利用して もらうことが重要である．そのため，コヒーレントイジ ングマシンをインターネット経由で利用できるクラウド システムが開発されており，2017 年にはすでにその一 部が公開されている [Qnn 17]．また，実装できる問題の 大規模化に向けて，さらに長尺な光ファイバ共振器を構 築中であり，10 万頂点の組合せ最適化問題を解くこと ができる次世代のコヒーレントイジングマシンの研究開 発が現在進められている． 組合せ最適化問題において，最も重要な目標は厳密解 となる組合せを見つけることである．しかしながら，現 実世界でその組合せを利用するのは我々人間であり，あ るコスト関数に対して最適化された答えが，すべての人 に対して常に最良の答えであるとは限らない．目的地ま で最短経路で行きたい日もあれば，少し遠回りでも海沿 いの道を走りたい日もある．我々のコヒーレントイジン グマシンが見つけてくる解には，物理計算機に特有のノ イズや揺らぎによって，同程度の解精度をもった多様な 選択肢の組合せが含まれることになる．今後このような 物理計算機を活用することで，一つの問題に対して高い 品質と多様性をもった解を多数用意し，その中から我々 の一人一人にとって最良の選択肢を提示することができ るようになると期待をしている． 謝 辞 本研究は，総合科学技術・イノベーション会議に より制度設計された革新的研究開発推進プログラム （ImPACT）により，科学技術振興機構を通して委託さ れたものです．◇ 参 考 文 献 ◇
[Hamerly 18] Hamerly, R., et al.: Scaling advantages of all-to-all connectivity in physical annealers: The coherent Ising
machine vs. D-Wave 2000Q, https://arxiv.org/abs/
1805.05217（2018）
[Haribara 16] Haribara, Y., et al.: Computational principle and performance evaluation of coherent Ising machine based on degenerate optical parametric oscillator network, Entropy, Vol. 18, p. 151（2016）
[Inagaki 16a] Inagaki, T., et al.: Large-scale Ising spin network based on degenerate optical parametric oscillators, Nature
Photon., Vol. 10, p. 415（2016）
[Inagaki 16b] Inagaki, T., et al.: A coherent Ising machine for 2000-node optimization problems, Science, Vol. 354, p. 603 （2016）
[Johnson 11] Johnson, M. W., et al.: Quantum annealing with manufactured spins, Nature, Vol. 473, p. 194（2011）
[Marandi 14] Marandi, A., et al.: Network of time-multiplexed optical parametric oscillators as a coherent Ising machine,
Nature Photon., Vol. 8, p. 937（2014）
[McMahon 16] McMahon, P.L., et al.: A fully programmable 100-spin coherent Ising machine with all-to-all connections,
Science, Vol. 354, p. 614（2016）
[Qnn 17] コヒーレントイジングマシンのクラウドシステム公開
Webサイト：https://qnncloud.com（2017）
[Takata 16] Takata, K., et al.: A 16-bit coherent Ising machine for one-dimensional ring and cubic graph problems, Scientific
Reports, Vol. 6, p. 34089（2016）
[Takesue 16] Takesue, H., et al.: 10 GHz clock time-multiplexed degenerate optical parametric oscillators for a photonic Ising spin network, Opt. Lett., Vol. 41, p. 4273（2016）
[梅木 15] 梅木毅伺 ほか：極限に挑む低雑音位相感応光増幅技術，
NTT技術ジャーナル，Vol. 27, No. 11, pp. 18-22（2015）
[Utsunomiya 11] Utsunomiya, S., et al.: Mapping of Ising models onto injection-locked laser systems, Optics. Express, Vol. 19, p. 18091（2011）
[Wang 13] Wang, Z., et al.: Coherent Ising machine based on degenerate optical parametric oscillators, Phys. Rev. A, Vol. 88, p. 063853（2013）
[Yamaoka 15] Yamaoka, M., et al.: A 20k-spin Ising chip to solve combinatorial optimization problems with CMOS annealing,
IEEE J. Solid-State Circuits, Vol. 51, p. 303（2015） 2018年 7 月 11 日 受理
