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

Size: px

Start display at page:

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

うきえこしの
4 years ago
Views:

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

2 背景組み合わせ最適化問題組み合わせ最適化問題 (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)

3 スピンの組み合わせ問題イジングモデルある種の磁性体では系のエネルギーはスピンの向きが ( アップダウン ) のいずれかによって以下のように決められる : 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

Kadowaki et al., Phys. Rev. E 58, 5355 (1998) D. Aharanov et al., SIAM Rev. (2008) M. W. Johnson et al.

4 世界初の商用量量子アニーリングマシン D-wave II (D-wave systems, inc.) - - 超伝導 (FLUX) 量量子ビット 512 ビットを搭載極低温へ冷冷却が必要 T op ~ 10mk - 原理理 : 量量子アニーリング ( 断熱計算 ) - ~ 次世代は 1,000 ビット - 疎結合のみの実装 ( 完全結合は困難 ) 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, (2014) 4

イジングハミルトニアンをレーザーネットワークの損失 (= 発振利利得 ) にマップする H = X i,j J i<j iz jz 光の発振器の同期現象を使ったコヒーレントイジングマシン結合レーザー系に相互注入が導入されると全体でのロスを少なくするような ( 相互結合による内部パワーの増加を最大化するような ) 発振モードを

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

6 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

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

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

9 ! HFOGk! d z9p 9 m 9P 9BPN GOHNA1290 GOHFO6H= k9 128 bit 2048 bit 10 5 bit (OPO) (FPGA) (OPO) (FPGA) (OPO) (FPGA) CMOS >10N x 10 5 CMOS!10N 2 4 x 10 7 CMOS!10N CMOS

10 OPO/ OPO OPO#=# 10

11 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 秒精度度保証はないがある程度度のレベルで正解に近い解を求めることができる

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

Microsoft PowerPoint - qcomp.ppt [互換モード]

Microsoft PowerPoint - qcomp.ppt [互換モード] 量子計算基礎東京工業大学河内亮周概要計算って何? 数理科学的に計算を扱うには量子力学を計算に使おう! 量子情報とは? 量子情報に対する演算 = 量子計算一般的な量子回路の構成方法計算って何? 計算とは? 計算 = 入力情報から出力情報への変換入力計算機構 ( デジタルコンピュータ,etc ) 出力計算とは? 計算 = 入力情報から出力情報への変換この関数はどれくらい計算が大変か??