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

Size: px

Start display at page:

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

しまなわたぬき
5 years ago
Views:

1 量子計算基礎東京工業大学河内亮周

2 概要計算って何? 数理科学的に計算を扱うには量子力学を計算に使おう! 量子情報とは? 量子情報に対する演算 = 量子計算一般的な量子回路の構成方法

3 計算って何?

4 計算とは? 計算 = 入力情報から出力情報への変換入力計算機構 ( デジタルコンピュータ,etc ) 出力

5 計算とは? 計算 = 入力情報から出力情報への変換この関数はどれくらい計算が大変か?? n m 0,1 n f : 0,1 01 0,1 01 0,1 m { } { } { } { }

6 計算モデル計算の複雑さを定量的に扱いたい! 計算したい関数は難しい? 易しい? 入力の大きさに応じてどれぐらい難しくなる? まず基準となる計算モデルを決めよう! Turing 機械論理回路 ( 族 ) Branching Program etc

7 論理関数を使った計算論理関数 f n :0,1 0,1 { } { } m ( 今回は m=1) e.g.: 4 入力 1 出力論理関数 f x, x, x, x = x x x x x x ( ) ( ) ( ) 計算したい関数を基本素子で構成しよう! 基本素子 :AND, OR, NOT 計算 = 関数を基本構成要素の組合せで実現計算の複雑さ= 基本構成要素がどれくらいいるか?

8 AND: 2 { 01 0,1 } { 01 0,1 } OR: NOT: 2 { 01 0,1 } { 0,1 01 } { 01 0,1 } { 01 0,1 } x y x y x y x y x x 任意の論理関数が表現可能

9 入力 :n ビット列例 : 偶奇判定 { } x,, 0,1 1 L xn 出力 : 1 の数が偶数ならば 0, 奇数ならば 1 例 :4 ビットの偶奇判定を行う論理関数 f 0000 = 0 ( ) f ( 0001) = 1 f ( 0010) = 1 M f 1111 = 0 ( )

10 偶奇判定関数 ( L ) f x,, x = x L x 1 n 1 n : 排他的論理和 (XOR) (=mod 2 の足し算 ) x y x y

11 x y = ( x y) ( x y) x y x y

12 ( L ) f x,, x = x L x 1 n 1 n e.g., 4 変数の場合 ( x x ) ( x x ) = L L x x x x ( ) ( ) n 1 (( x x ) ( x x )) ( x x ) ( x x ) ( ) = n 再帰的に {AND,OR,NOT},, に展開可能! 偶奇判定関数は基本素子で実現可能計算の複雑さの指標 :e.g., 使用する素子数 ( O( n) )

13 オーダー記法について計算複雑さの評価 = 入力サイズ nの関数 n が大きくなるにつれて大体どうなるか? 支配的なところだけを抜き出したい例 : ある論理回路のサイズ s ( n ) がオーダー t( n) ( ) ( ) s ( n ) = O ( t ( n ) ) C > 0:lim s n < C n t n 2 2 ( ) = ( ) = ( ) s n n n s n O n ( ) = 5 log + 3 log log ( ) = ( log log ) n n s( n) = 50n 2 s n = O n 2 s n n n n n s n O n n ( ) ( )

14 一般の論理関数では? ( ) Shannon 展開を使うと O 2 n 個の素子で実現可能! Shannon 展開 ( ) = ( x f ( 1, x,..., x ) ) x f ( 0, x,..., x ) f x1, x2,..., xn ( ) ( ) 1 2 n 1 2 s n =n 変数論理関数を実現するのに十分な素子数 ( ) ( ) ( ) s n 2s n 1 + 4, s 1 = 1 ( ) = O( 2 n ) s n n

15 量子力学を計算に使おう! ~ 古典情報処理から量子情報処理へ ~

16 古典情報と量子情報の違い古典的な1ビットの内容は 0 or 1 量子情報における 1 ビットの内容は α 0 + β 1 0 である状態と 1 である状態の ( 量子力学的 ) 重ね合わせ α : 状態 0 の振幅 β : 状態 1 の振幅

17 量子ビット (q-bit) 量子ビットを観測すると α β 1 α + β = 1( α, β C ) 2 α 確率で 0 2 β 確率で 1 量子ビットは観測により確率的に振舞う

18 量子ビットの表現 1 量子ビット =2 次元複素ベクトル ( 長さ 1) =, 1 = 計算基底 0,1 0

19 量子ビットの表現 1 量子ビット =2 次元複素ベクトル ( 長さ 1) =, 1 = ( ) = ( 0 1 )

20 量子ビットの測定 ψ α 0 β 1 = + を射影測定 M = { M, M } 0 1 で測定 M M = 0 0 = [ 1 0 ], = = 1 1 = [ 0 1] = Pr "0" 牋幘 = ψ M0M0 ψ = ψ 0 0 ψ = α Pr "1" 牋幘 = ψ M1M1 ψ = ψ 1 1 ψ = β 2 2

21 量子ビットの測定 ψ = α 0 + β 1 を射影測定 M = M, M { } 0 1 で測定 M = 0 0, M = ψ β α

22 複数の量子ビット = 各ビットのテンソル積 ψ, ϕ = ψ ϕ = ψ ϕ = 0 0 = 0 0 = = e.g., 1 n 量子ビット= 2 n 次元複素ベクトル ( 長さ1)

23 < = 01 = = = < = = = = < < 3

24 おやくそく量子状態は純粋状態のみ測定は計算基底の射影測定のみ M = 0 0, ビット分の測定 : { } n ビット分の測定 : M n 協注上 n 協注上 = 0L00 0L00, 0L01 0L01, L, 1L11 1L n 凾

25 量子情報をどう処理する? 古典計算入出力 : 古典ビット列演算 : 論理回路基本論理素子の組み合わせにより実現量子計算入出力 : 量子状態演算 : ユニタリ変換 ( と測定 ) 基本量子素子と測定の組み合わせで実現ユニタリ変換には可逆性が必要! 入力長 = 出力長

26 基本的なユニタリ変換 Pauli 行列 (1 量子ビット入出力 ) i 1 0 X = Y = Z = 1 0 i X Y Z

27 基本的なユニタリ変換 X 0 1 = = 1 0 NOT = X = = α 0 + β 1 α 1 + β 0 X

28 基本的なユニタリ変換 Hadamard 変換 (1 量子ビット入出力 ) H = H

29 基本的なユニタリ変換 Hadamard 変換 (1 量子ビット入出力素子 ) H = = = ( ) 2 0 H ( ) 1 2

30 基本的なユニタリ変換 Hadamard 変換 (1 量子ビット入出力素子 ) H = = = ( 0 1 ) 2 1 H ( 0 1 ) 1 2

31 基本的なユニタリ変換制御 NOT(2 量子ビット入出力素子 ) CNOT = xy, { 0,1} x x y x y

32 基本的なユニタリ変換制御 NOT(2 量子ビット入出力素子 ) CNOT x = 0 x = 1 y を素通し y を反転 xy, { 0,1} x x y x y

33 基本的なユニタリ変換制御 NOT(2 量子ビット入出力素子 ) CNOT x = 0 x = 1 y を素通し y を反転 y { 0,1} 0 0 y 0 y = y

34 基本的なユニタリ変換制御 NOT(2 量子ビット入出力素子 ) CNOT x = 0 x = 1 y を素通し y を反転 y { 0,1} 1 1 y 1 y = y

35 量子回路の例 H

36 基本量子素子から大きな量子回路へ古典計算の場合,AND,OR,NOTを組み合わせて任意の論理関数を実現できた. ( ) 素子数 = O 2 n 個 (nビット入力) 量子計算の場合では? 1 量子ビット素子とCNOTで可能! 素子数 = O n 2 4 n 個 (n 量子ビット入力 ) ( )

37 1 量子ビット素子の構成 Bloch 球上の回転素子を使う Bloch 球 =1 量子ビットの幾何的表現方法

38 Bloch 球 z 0 θ θϕ,ϕ ( ) ψ y x ϕ ψ = cos θ e ϕ sin θ ( ) i ( )

39 θ π 2, ϕ 0 Bloch 球 z 1 i θ = π 2, ϕ = π 2 ( = = ) 0 ( ) y x 1 ψ = cos θ e ϕ sin θ 2 1 ( ) i ( )

40 回転行列 θ θ cos i sin θ θ 2 2 Rx ( θ) = exp( iθx 2) = cos I isin X = 2 2 θ θ i sin cos 2 2 θ θ cos sin θ θ 2 2 Ry ( θ) = exp( iθy 2) = cos I isin Y = 2 2 θ θ sin cos 2 2 iθ 2 θ θ e 0 Rz ( θ) = exp( iθz 2) = cos I isin Z = iθ e

41 R π x 2 0 z 1 i θ = π 2, ϕ = 3π 2 ( ) R x y x π cos sin 4 i π π i = π π 0 = 2 i = 2 2 i sin cos 4 4

42 回転行列による表現 θ θ Rˆ ˆ ˆ ˆ n I i n xx n yy n zz 2 2 ( θ ) = cos sin ( + + ) ( 3,, ) nˆ = nˆ nˆ nˆ : 回転軸 x y z 定理 U :2 次元ユニタリ変換 (1 量子ビット素子 ) i α, nˆ, θ s.t. U = e α R ( ) n ˆ θ

43 Z-Y 回転分解定理 U :2 次元ユニタリ変換 (1 量子ビット素子 ) α, β, γ, δ s.t. iα U = e R z β R y γ R z β γ δ ( ) ( ) ( ) iα e α ( ) ( ) 大域的位相を無視すれば 1 量子ビット素子は回転素子 R θ, R θ で実現できる ( R と R を入れ替えたX-Y 回転分解も可能 ) z x y z

44 n 量子ビット上ユニタリ行列方針 1. n-qbit U 一般化 CNOT+ 制御 1qbit 素子 2. 一般化 CNOT 1-qbit 素子 +CNOT 3. 制御 1-qbit 素子 1-qbit 素子 +CNOT 最終的には 1-qbit 素子 +CNOT で構成可能!

45 一般化 CNOT 素子 x1 x1 x n x n y ( L ) x x y 1 n 黒丸白丸 : 1 が入力されるとスイッチオン : 0 が入力されるとスイッチオン

46 一般化 CNOT 素子 ( 例 ) x1 x1 x2 x2 x3 x3 y ( ) x x x y x, x, x = 0,0,1 のときのみ y を反転 ( ) ( ) 1 2 3

47 制御 1-qbit 素子 c c ψ U U c ψ CU ( ) = 0 U

48 詳細は板書にて

49 Toffoli 素子 (CCNOT 素子 ) CCNOT = O ,, 0,1 x { } 1 x2 y 2 x1 x1 x x2 y ( ) x x y 1 2 x1, x2 ともに 1 が入力されたときのみ y を反転

50 Toffoli o 素子 (CCNOT 素子 ) CCNOT = T T T S H T T T T H H = T = S = i π 0 e 0 i

51 指数関数 vs. 多項式関数量子回路の一般的構成は入力サイズnに対して指数関数的! 効率が悪すぎる計算量理論では多項式関数的である方が現実的だと考えられている. 特定の問題に対して良い回路設計 (=アルゴリズム設計 ) は?

52 量子計算の主な結果高速素因数分解アルゴリズム (Shor, 1994) 素因数分解問題を高速に解くことができる. RSA 公開鍵暗号の解読高速検索アルゴリズム (Grover, 1996) 構造の全くない検索問題に対して高速検索次の講義で解説

53 古典 vs 量子合成数 N ( 二進 log N 桁 ) の素因数分解古典 : 一般数体篩法計算量 : 準指数関数 2 ( exp (( + () 1 )( ln ) ( ln ln ) )), = ( 64 9) O C o N N C 量子 :Shor のアルゴリズム (1994) 計算量 : 多項式関数 O log 2 (( ) 2 N )

54 n = log 2 N ( 二進表現の桁数 = 入力サイズ ) ( ) C N = exp 64 9 ln N ln ln N ( ) ( ) ( ) ( ) ( ) ( ) = N 2 QN log 2 N C N 2 10, Q N 2 10 ( ) ( ) ( ) 参考 : 京速計算機 (10PFLOPS, 1 秒間に回浮動小数点演算 ) で回の浮動小数点演算に対して必要な時間 63.4 年参考 :RSA 公開鍵暗号の主流のパラメータ n = 1024 ( 推奨 n = 2048)

55 量子計算の主な結果高速素因数分解アルゴリズム (Shor, 1994) 素因数分解問題を高速に解くことができる. RSA 公開鍵暗号の解読高速検索アルゴリズム (Grover, 1996) 構造の全くない検索問題に対して高速検索次の講義で解説

Information is physical. Rolf Landauer It from bit. John Wheeler I think there is a world market for maybe five computers. Thomas Watson

量子情報基礎阿部英介慶應義塾大学先導研究センター応用物理情報特別講義 A 216 年度春学期後半金曜 4 限 @14-22 Information is physical. Rolf Landauer It from bit. John Wheeler I think there is a world market for maybe five computers. Thomas Watson