_第１回アドバイザー会議

1 12 12 / D AA ) 2CAD /AA 12 /AA AAD#2 2A 2 2 A ( ( ~ 組み合わせ最適化問題を解くコヒーレント イジングマシン ~ 国 立立情報学研究所 宇都宮聖 子 ImPACT 量量 子 人 工脳を量量 子ネットワークでつなぐ 高度度知識識社会基盤の実現 第 1 回アドバイザー会議

背景 組み合わせ最適化問題 組み合わせ最適化問題 (NP- hard) : 現代社会における最も重要な問題 - 解きたい問題サイズの増加によって 計算時間が指数発散してしまう最も難しい問題 動的に変化する組み合わせ最適化問題 - SNS 解析, 危険予知, 脳機能ネットワークの解析など - 動的に変化するグラフのリアルタイム処理理を 行行う - 時系列列変化のデータに基づいて計算を 行行うため 扱うデータ量量が膨 大 - スーパーコンピュータを 用いても問題サイズ N>100 の厳密解は解けない 組み合わせ最適化問題を効率率率よく解く 手法 - ニューラルネット ( 機械学習 脳型情報処理理 ): Deep learning(siri 音声 画像認識識), SyNAPSE(DARPA: ニューロチップ ) - ヒューリスティック ( 焼き鈍し法など : そこそこよい近似解を 高速に求める ) - 量量 子アニーリング :D- waveなど 極低温動作が必要 大規模化が課題 難しい 計算の複雑さ NP- 困難. MAX- CUT, TSP Ising model NP 素因数分解 NP- complete SAT, 数独 P 最短経路路問題 BQP (bounded error quantum polynomial time)

スピンの組み合わせ問題イジング モデル ある種の磁性体では 系のエネルギーはスピンの向きが ( アップ ダウン ) のいずれか によって以下のように決められる : H = X i,j J i<j iz jz J ij >0ならば2つのスピンは同じ向きになろうとする i j J ij =- 1 再隣接のスピン同士は相互作用をする ( J ij ) J ij <0 ならば 2 つのスピンは 逆向きになろうとする i j J ij =+1 11

世界初の商 用量量 子アニーリングマシン D-wave II (D-wave systems, inc.) - - 超伝導 (FLUX) 量量 子ビット 512 ビットを搭載 極低温へ冷冷却が必要 T op ~ 10mk - 原理理 : 量量 子アニーリング ( 断熱計算 ) - ~ 次世代は 1,000 ビット - 疎結合のみの実装 ( 完全結合は困難 ) http://www.dwavesys.com T. Kadowaki et al., Phys. Rev. E 58, 5355 (1998) D. Aharanov et al., SIAM Rev. (2008) M. W. Johnson et al., Nature194, 473 (2011) D- wave Oneのキメラグラフ構造疎結合により任意の結合を実装するため 8 量量 子ビットで1ロジカルビットを表現 Nグラフを実装するのにN 2 量量 子ビット必要 The $15 million D-Wave Two is still no faster than a desk top computer right now, in certain situations. D-wave two can sometimes achieve speeds up to five times faster than the Intel PC. S. Boixo et al., Nature Physics 10, 218 224 (2014) 4

イジングハミルトニアンをレーザーネットワークの損失 (= 発振利利得 ) にマップする H = X i,j J i<j iz jz 光の発振器の同期現象を使った コヒーレントイジングマシン 結合レーザー系に相互注 入が導 入されると 全体でのロスを少なくするような ( 相互結合による内部パワーの増加を最 大化するような ) 発振モードを 発振器ネットワークが 自分 自 身で選択する 最 小損失 最 小エネルギー状態 イジングスピン イジング結合 : 各レーザーの発振モード : レーザーネットワークの結合強度度と位相 - - 各レーザーが 自発的に 系に実装された条件に応じて最も効率率率の良良い発振基底を選ぶ その発振基底の組み合わせ (1/2 N 個の候補のうちの 1 通り ) が解きたい問題の答えに対応する

DOPO ネットワークを 用いたコヒーレントイジングマシン DOPO( 縮退型光パラメトリック発振器 ) EOM EOM PD m EOM +SHG i OC IC ポンプ (2ω) N 光パルス ( 単 一共振器内 ) 相互結合パスの数 : N- 1 PPLN() シグナル : ω:1550nm イジングハミルトニアン : H = X i,j J i<j iz jz イジングスピン : OPO 発振モード ( 位相 :0 または π) イジング結合 : 光相互結合の振幅と位相 6

量量 子測定 - フィードバックを 用いたコヒーレントイジングマシン 00 = = NG 00/0) D LN=k O G HN m, kp12 ( G = # DA ) ) 各周回ごとに光パルスはホモダイン検波により測定される すべての光パルスの測定データ σ iz をもとに 光結合を実現するフィードバックパルスを 生成する Σ j J ij σ jz を電気信号により計算し 結合 用の光パルスを加 工する 問題 (J ij ) を実装するために必要だった N 本遅延線が 1 本で実装可能

ImPACT 量量 子 人 工脳プロジェクト構成 - (NII) : - Mabuchi (Stanford) : - - () :,, - (NII) : - (NTT) : DOPO - () : FPGA- - (NII) : XY/ - Byer, Fejer, Mabuchi (Stanford) : DOPO, PPLN, FPGA - : 8

! HFOGk! d z9p 9 m 9P 9BPN GOHNA1290 GOHFO6H= k9 128 bit 2048 bit 10 5 bit (OPO) (FPGA) (OPO) (FPGA) (OPO) (FPGA) 2015.10 2016.3 2018.12 CMOS >10N 2 1.6 x 10 5 CMOS!10N 2 4 x 10 7 CMOS!10N 2 10 11 CMOS 3 6 9 21

OPO/ OPO OPO#=# 10

DOPO ネットワーク ( コヒーレント イジングマシン :CIM) の計算能 力力 ~完全グラフに対する焼きなまし法 (SA) と精度度保証つきアルゴリズム (GW) との 比較 ~ K 800 K 4000 DOPO ~10 3 SA SDP DOPO ~10 4 SA SDP 精度度保証付き近似 手法 Goemans Williamson Semi- Definite GW O(N 3.5 ) 20 日 Programming (approximate algorithm) 87.8% の精度度で解が求まることを保証 ヒューリスティック Simulated Annealing ( 焼き鈍し法 ) SA O(N 2 ) DOPO 100 秒 10-3 秒 精度度保証はないが ある程度度のレベルで 正解に近い解を求めることができる

10 GHz + 2km N=10 5 : N 2 () 1 (-) - - ADC/DAC, FPGA - - FPGA - - /OPO ~O(1) - N - 6+N 2 - (N-1)+N 12