量子計算基礎 東京工業大学 河内亮周
概要 計算って何? 数理科学的に 計算 を扱うには 量子力学を計算に使おう! 量子情報とは? 量子情報に対する演算 = 量子計算 一般的な量子回路の構成方法
計算って何?
計算とは? 計算 = 入力情報から出力情報への変換 入力 計算機構 ( デジタルコンピュータ,etc ) 出力
計算とは? 計算 = 入力情報から出力情報への変換 この関数はどれくらい計算が大変か?? 01 01 n m 0,1 n f : 0,1 01 0,1 01 0,1 m { } { } { } { }
計算モデル 計算の複雑さ を定量的に扱いたい! 計算したい関数は難しい? 易しい? 入力の大きさに応じてどれぐらい難しくなる? まず 基準 となる計算モデルを決めよう! Turing 機械 論理回路 ( 族 ) Branching Program etc
論理関数を使った計算 論理関数 f n :0,1 0,1 { } { } m ( 今回は m=1) e.g.: 4 入力 1 出力論理関数 f x, x, x, x = x x x x x x ( ) ( ) ( ) 1 2 3 4 1 2 4 3 1 2 計算したい関数を 基本素子 で構成しよう! 基本素子 :AND, OR, NOT 計算 = 関数 を 基本構成要素 の組合せで実現 計算の複雑さ= 基本構成要素 がどれくらいいるか?
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 0 0 0 0 0 0 0 1 1 0 0 1 0 1 1 0 0 1 0 0 1 1 1 1 1 1 1 1 任意の論理関数が表現可能
入力 :n ビット列 例 : 偶奇判定 { } x,, 0,1 1 L xn 出力 : 1 の数が偶数ならば 0, 奇数ならば 1 例 :4 ビットの偶奇判定を行う論理関数 f 0000 = 0 ( ) f ( 0001) = 1 f ( 0010) = 1 M f 1111 = 0 ( )
偶奇判定関数 ( L ) f x,, x = x L x 1 n 1 n : 排他的論理和 (XOR) (=mod 2 の足し算 ) x y x y 0 0 0 1 0 1 0 1 1 1 1 0
x y = ( x y) ( x y) x y x y
( L ) f x,, x = x L x 1 n 1 n e.g., 4 変数の場合 ( x x ) ( x x ) = L L x x x x ( ) ( ) 1 2 3 4 1 2 n 1 (( x x ) ( x x )) ( x x ) ( x x ) ( ) = 1 2 3 4 1 2 3 4 n 再帰的に {AND,OR,NOT},, に展開可能! 偶奇判定関数は基本素子で実現可能 計算の複雑さの指標 :e.g., 使用する素子数 ( O( n) )
オーダー記法について 計算複雑さの評価 = 入力サイズ nの関数 n が大きくなるにつれて 大体 どうなるか? 支配的なところだけを抜き出したい 例 : ある論理回路のサイズ s ( n ) がオーダー t( n) ( ) ( ) s ( n ) = O ( t ( n ) ) C > 0:lim s n < C n t n 2 2 ( ) = 4 + 200 + 84241 ( ) = ( ) s n n n s n O n ( ) = 5 log + 3 log log ( ) = ( log log ) 10 0.08n 10 0.08n s( n) = 50n 2 s n = O n 2 s n n n n n s n O n n ( ) ( )
一般の論理関数では? ( ) 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
量子力学を計算に使おう! ~ 古典情報処理から量子情報処理へ ~
古典情報と量子情報の違い 古典的な1ビットの内容は 0 or 1 量子情報における 1 ビットの内容は α 0 + β 1 0 である状態と 1 である状態の ( 量子力学的 ) 重ね合わせ α : 状態 0 の振幅 β : 状態 1 の振幅
量子ビット (q-bit) 量子ビットを 観測 すると α 2 2 0 + β 1 α + β = 1( α, β C ) 2 α 確率で 0 2 β 確率で 1 量子ビットは観測により確率的に振舞う
量子ビットの表現 1 量子ビット =2 次元複素ベクトル ( 長さ 1) 1 0 0 =, 1 = 0 1 1 計算基底 0,1 0
量子ビットの表現 1 量子ビット =2 次元複素ベクトル ( 長さ 1) 1 0 0 =, 1 = 0 1 1 1 1 1 0 ( 0 + 1 ) = + 2 2 0 2 1 1 2 ( 0 1 )
量子ビットの測定 ψ α 0 β 1 = + を射影測定 M = { M, M } 0 1 で測定 M M 0 1 1 1 0 = 0 0 = [ 1 0 ], = 0 0 0 0 0 0 = 1 1 = [ 0 1] = 1 0 1 Pr "0" 牋幘 = ψ M0M0 ψ = ψ 0 0 ψ = α Pr "1" 牋幘 = ψ M1M1 ψ = ψ 1 1 ψ = β 2 2
量子ビットの測定 ψ = α 0 + β 1 を射影測定 M = M, M { } 0 1 で測定 M = 0 0, M = 1 1 0 1 1 ψ β 2 0 2 α
複数の量子ビット = 各ビットのテンソル積 ψ, ϕ = ψ ϕ = ψ ϕ 1 1 0 00 = 0 0 = 0 0 = = 0 0 0 0 e.g., 1 n 量子ビット= 2 n 次元複素ベクトル ( 長さ1)
0 00 1 < 0 0 1 1 1 0 1 0 1 = 01 = = = 0 0 0 0 1 0 0 0 <1 0 0 2 0 1 0 3 10 = = 0 0 0 11 = = 1 0 1 < 2 1 1 0 0 1 < 3
おやくそく 量子状態は純粋状態のみ 測定は計算基底の射影測定のみ M = 0 0, 1 1 1 ビット分の測定 : { } n ビット分の測定 : M n 協注上 n 協注上 6474864748 = 0L00 0L00, 0L01 0L01, L, 1L11 1L11 14444444444244444444443 2 n 凾
量子情報をどう処理する? 古典計算 入出力 : 古典ビット列 演算 : 論理回路 基本論理素子の組み合わせにより実現 量子計算 入出力 : 量子状態 演算 : ユニタリ変換 ( と測定 ) 基本量子素子と測定の組み合わせで実現 ユニタリ変換には可逆性が必要! 入力長 = 出力長
基本的なユニタリ変換 Pauli 行列 (1 量子ビット入出力 ) 0 1 0 i 1 0 X = Y = Z = 1 0 i 0 0 1 X Y Z
基本的なユニタリ変換 X 0 1 = = 1 0 NOT 0 1 0 1 1 0 = X 0 1 0 = = 0 1 1 α 0 + β 1 α 1 + β 0 X
基本的なユニタリ変換 Hadamard 変換 (1 量子ビット入出力 ) 1 1 1 H = 2 1 1 H
基本的なユニタリ変換 Hadamard 変換 (1 量子ビット入出力素子 ) H 0 1 1 1 1 1 1 1 = = 2 1 1 0 2 1 = ( 0 + 1 ) 2 0 H ( 0 + 1 ) 1 2
基本的なユニタリ変換 Hadamard 変換 (1 量子ビット入出力素子 ) H 1 1 1 1 0 1 1 1 = = 2 1 1 1 2 1 = ( 0 1 ) 2 1 H ( 0 1 ) 1 2
基本的なユニタリ変換 制御 NOT(2 量子ビット入出力素子 ) CNOT = 0 1 1 0 0 1 1 0 xy, { 0,1} x x y x y
基本的なユニタリ変換 制御 NOT(2 量子ビット入出力素子 ) CNOT x = 0 x = 1 y を素通し y を反転 xy, { 0,1} x x y x y
基本的なユニタリ変換 制御 NOT(2 量子ビット入出力素子 ) CNOT x = 0 x = 1 y を素通し y を反転 y { 0,1} 0 0 y 0 y = y
基本的なユニタリ変換 制御 NOT(2 量子ビット入出力素子 ) CNOT x = 0 x = 1 y を素通し y を反転 y { 0,1} 1 1 y 1 y = y
量子回路の例 0 0 + 1 0 0 0 + 1 1 0 0 2 2 0 H 0 0 0 + 1 1 2
基本量子素子から大きな量子回路へ 古典計算の場合,AND,OR,NOTを組み合わせて任意の論理関数を実現できた. ( ) 素子数 = O 2 n 個 (nビット入力) 量子計算の場合では? 1 量子ビット素子とCNOTで可能! 素子数 = O n 2 4 n 個 (n 量子ビット入力 ) ( )
1 量子ビット素子の構成 Bloch 球上の 回転素子 を使う Bloch 球 =1 量子ビットの幾何的表現方法
Bloch 球 z 0 θ θϕ,ϕ ( ) ψ y x ϕ ψ = cos θ 2 0 + e ϕ sin θ 2 1 1 ( ) i ( )
1 1 0 + 1 2 2 θ π 2, ϕ 0 Bloch 球 z 1 i 0 + 1 2 2 θ = π 2, ϕ = π 2 ( = = ) 0 ( ) y x 1 ψ = cos θ 2 0 + e ϕ sin θ 2 1 ( ) i ( )
回転行列 θ θ 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θ 2 2 2 0 e
R π x 2 0 z 1 i 0 1 2 2 θ = π 2, ϕ = 3π 2 ( ) R x y x π cos sin 4 i π π 4 1 1 1 1 i 0 0 1 2 = π π 0 = 2 i = 2 2 i sin cos 4 4
回転行列による表現 θ θ 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 ˆ θ
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
n 量子ビット上ユニタリ行列 方針 1. n-qbit U 一般化 CNOT+ 制御 1qbit 素子 2. 一般化 CNOT 1-qbit 素子 +CNOT 3. 制御 1-qbit 素子 1-qbit 素子 +CNOT 最終的には 1-qbit 素子 +CNOT で構成可能!
一般化 CNOT 素子 x1 x1 x n x n y ( L ) x x y 1 n 黒丸 白丸 : 1 が入力されるとスイッチオン : 0 が入力されるとスイッチオン
一般化 CNOT 素子 ( 例 ) x1 x1 x2 x2 x3 x3 y ( ) x x x y 1 2 3 x, x, x = 0,0,1 のときのみ y を反転 ( ) ( ) 1 2 3
制御 1-qbit 素子 c c ψ U U c ψ 1 0 0 0 1 CU ( ) = 0 U
詳細は板書にて
Toffoli 素子 (CCNOT 素子 ) CCNOT = 8 6447448 1 0 O 0 0 1 0 1 0 1 0,, 0,1 x { } 1 x2 y 2 x1 x1 x x2 y ( ) x x y 1 2 x1, x2 ともに 1 が入力されたときのみ y を反転
Toffoli o 素子 (CCNOT 素子 ) CCNOT = T T T S H T T T T H H 1 1 1 1 0 1 0 = T = S = i 4 2 1 1 π 0 e 0 i
指数関数 vs. 多項式関数 量子回路の一般的構成は入力サイズnに対して指数関数的! 効率が悪すぎる 計算量理論では 多項式関数的 である方が現実的だと考えられている. 特定の問題に対して良い回路設計 (=アルゴリズム設計 ) は?
量子計算の主な結果 高速素因数分解アルゴリズム (Shor, 1994) 素因数分解問題を高速に解くことができる. RSA 公開鍵暗号の解読 高速検索アルゴリズム (Grover, 1996) 構造の全くない検索問題に対して高速検索 次の講義で解説
古典 vs 量子 合成数 N ( 二進 log N 桁 ) の素因数分解 古典 : 一般数体篩法 計算量 : 準指数関数 2 ( exp (( + () 1 )( ln ) ( ln ln ) )), = ( 64 9) 13 23 13 O C o N N C 量子 :Shor のアルゴリズム (1994) 計算量 : 多項式関数 O log 2 (( ) 2 N )
n = log 2 N ( 二進表現の桁数 = 入力サイズ ) ( 13 13 23 ) C N = exp 64 9 ln N ln ln N ( ) ( ) ( ) ( ) ( ) ( ) = N 2 QN log 2 N 2 960 C N 2 10, Q N 2 10 ( ) ( ) ( ) 9.9 25 9 参考 : 京速計算機 (10PFLOPS, 1 秒間に 16 10 回浮動小数点演算 ) で 25 2 10 回の浮動小数点演算に対して必要な時間 63.4 年 参考 :RSA 公開鍵暗号の主流のパラメータ n = 1024 ( 推奨 n = 2048)
量子計算の主な結果 高速素因数分解アルゴリズム (Shor, 1994) 素因数分解問題を高速に解くことができる. RSA 公開鍵暗号の解読 高速検索アルゴリズム (Grover, 1996) 構造の全くない検索問題に対して高速検索 次の講義で解説