Comments
Description
Transcript
工学者のための量子計算 基礎の基礎
工学者のための量子計算
基礎の基礎
慶應義塾大学理工学部
物理情報工学科
伊藤公平
目次
量子コンピュータとは何か？を学部レベルの知識でも理解できるよう説明し，量子コ
ンピュータ開発にむけていかなる工学技術が必要か考える機会を提供する．
１．計算のリソース
２．量子コンピュータとユニタリ変換
３．量子回路
４．量子並列性と観測問題
５．量子力学的離散フーリエ変換
６．量子計算アルゴリズム
a) Deutsch-Jozsa アルゴリズム
b) Grover’sデータベース検索アルゴリズム
c) Shor’s素因数分解アルゴリズム
７．量子ビットの求められる性質
参考文献
本講義の内容は，最終章を除いて，以下の3冊の本の内容をまとめた
ものです．
１．上坂吉則 「量子コンピュータの基礎数理」コロナ社
２．ゲナディ・P・ベルマン，ゲーリー・D・ドーレン，ロンニエ・マイニエリ，
ウラジミール・I・チフリノビッチ 「入門 量子コンピュータ」 訳：松 田和典，パーソナルメディア社
３．Michael A. Nielsen and Isaac L. Chuang, “Quantum Computation and Quantum Information,”
Cambridge University Press
計算のリソース
問題： N個の正整数を大きい順に並べる．
★古典的コンピュータ
L | N log
N ステップ必要
最低 2 ★スパゲッティ−コンピュータ[西野哲朗：中国人郵便配達問題=コンピューサイエンス最大の難関，講談社(1999)]
スパゲッティ−をN本用意し，正整数の大きさに切る（Nステップ）
束ねて机の上に立てる（1ステップ）
500 00
長い順に取り出し机に並べる（Nステップ）
400 00
なぜ，スパゲティーコンピュータ
は効率が良いのか？
総ステップ数
以上の総ステップ数は2N+1
300 00
古典的コンピュータ
200 00
スパゲッティ−コンピュータ
100 00
0
0
1000
2000
N
3000
4000
5000
量子コンピュータとは
時間に依存する
波動関数
d<
i!
dt
Hが時間に対して不変の
場合（緩和時間が長い）
< ( t ) U ( t )< ( 0 )
+<
U( t ) e
iHt / !
+
I
! §¨ w 2
w2
w 2 ¸·
V ( x, y,z )
2m ©¨ wx 2 wy 2 wz 2 ¸¹
iHt / ! iHt / ! 2 iHt / ! 3
ここでU(t)はユニタリ行列
1!
UU *
2!
3!
(1)
I
<をリソースとして，それらに何ステップものユニタリ演算をほどこすのが量子計算
Δt おきにユニタリ演算U を施すと
< ( 't ) U ( 0 )< ( 0 )
< ( 2't ) U ( 't )< ( 't )
< ( 3't ) U ( 2't )< ( 2't )
・・・
< n U n1U n 2 U 0< 0
U'< 0
(2)
有限空間で考えると
z
<を有限次元空間に属するベクトルと仮定する
e0
e1
0
ª1 º
« 0»
¬ ¼
1
ª 0º
«1 »
¬ ¼
I0>
基底
1
0 1
2
< ( t ) a ( t )e0 b( t )e1
I1>
a ( t ) 0 b( t ) 1
+
I
z
!Z 0 I z
IZ はエルミート行列（=複素共役）
1 ª1 0 º
2 «¬0 1»¼
U( t ) e
iHt / !
A
ªa00
«a
¬ 10
a01 º
a11 »¼
*
A
ªa*00
« *
¬ a01
* º
a10
* »
a11
¼
iHt / ! iHt / ! 2 iHt / ! 3
I
1!
2!
3!
UU *
I
ユニタリ演算の例（１）
例１ 一量子ビット回転ゲート(NOT演算）
e0
（ユニタリかつエルミート）
UR
UR 0
< 0 1e0 0e1 1 0 0 1
ª0 1º
«1 0» を
¼
¬
<0
ª 0 1 º ª1 º
«1 0» « 0»
¼¬ ¼
¬
0e0 1e1
ª 0º
«1 »
¬ ¼
1 と UR 1
U R< ( t ) a ( t ) 0 b( t ) 1
ディラック記法では、U R
0 0 11
ª0 1 º ª 0 º
« 1 0 » «1 »
¬
¼¬ ¼
a ( t ) 1 b( t ) 0
0 11 0
e1
にほどこすと
ª1º
« »
¬0 ¼
0
0
ª1 º
« 0»
¬ ¼
1
ª 0º
«1 »
¬ ¼
のように反転（回転）させる．
U R はXゲート(IX)とも呼ばれ重要である。
ª1 º
ª0 º
ª0 0 º ª0 1 º
>
@
>
@
0
1
1
0
«0 »
«1 0 » « 0 0 »
«1 »
¬ ¼
¬ ¼
¬
¼ ¬
¼
UR 1
0 11 1 0 1
UR 0
0 10 1 0 0
0
1
基底
0
ik
ª0 1 º
«1 0 »
¼
¬
>1
0@
1
>0 1@
G ik
U R U *R
0 01 1
I
ユニタリ演算の例（２）
例２ ニ量子ビット制御ノット(controlled NOT)演算 （22×22の行列が必要）
基底
e0
e2
00
10
ª1 º
«0 »
« »
«0 »
« »
¬0 ¼
ª0 º
«0 »
« »
«1»
« »
¬0 ¼
01
e1
11
e3
テンソル積
x1
x2
0
0
ª x1,0 º ª x2,0 º
«x »
«x »
¬ 1,1 ¼ ¬ 2,1 ¼
ª1 º ª1 º
« 0 »
«0 »
¬ ¼ ¬ ¼
ª1º
«0 »
« »
«0 »
« »
¬0 ¼
（ユニタリかつエルミート）
ª0 º
«1 »
« »
«0 »
« »
¬0 ¼
標的ビット
制御ビット
U CN 10
ª0 º
«0 »
« »
«0 »
« »
¬1 ¼
ª x1,0 x2,0 º
«x x »
« 1,0 2,1 »
« x1,1x2,0 »
«
»
¬ x1,1x2,1 ¼
00
ª1
«0
«
«0
«
¬0
0 0 0 º ª0 º
1 0 0 » «0 »
»« »
0 0 1 » «1 »
»« »
0 1 0 ¼ ¬0 ¼
ª0 º
«0 »
« »
«0 »
« »
¬1 ¼
11
まとめると
x1x2
U CN 00
00 ,
U CN 01
01 ,
U CN 10
11 ,
U CN 11
01 .
入力 \ i
a1 00 a2 01 a3 10 a4 11
出力 \ f
U CN\ i
a1 00 a2 01 a3 11 a4 10
量子並列性：2準位系の2量子ビットで22状態が一度に
計算できる。N量子ビットでは2n状態を並列計算。
U CN
00 00 01 01 10 11 11 10
*
U CN U CN
00 00 01 01 10 10 11 11
I
古典演算との違い−可逆性
可逆（古典、量子）
NOT演算
（回転ゲート）
bf
ai , bi
ai
0,1
不可逆（古典）
AND演算
cf
aibi
不可逆（古典）
XOR演算
cf
ai bi
aibi ai bi
bf
可逆（量子）
ai
bi
af
bf
0
1
Controlled NOT
制御NOT
0
0
0
0
1
0
0
1
0
1
1
0
1
1
1
1
1
0
ai
ai bi
bf
aibi ai bi
ai b i cf
0
0
0
0
1
0
1
0
0
1
1
1
量子回路
A
A
B
A B
ai b i cf
0
0
0
0
1
1
1
0
1
1
1
0
量子計算で利用される単一量子ビット操作
Hadamard gate （アダマードゲート）
D 0 E1
H
0 1
0 1
D
E
2
2
Pauli matrices （パウリ行列）
D 0 E1
X
E 0 D 1
D 0 E1
Y
i E 0 D 1 D 0 E1
Z
D 0 E1
X
ª0 1 º
UR { «
»
¬1 0¼
1 ª1 1 º
H{
2 «¬1 1»¼
ª0 i º
Y {«
»
¬i 0 ¼
ª1 0º
I {«
»
¬0 1 ¼
\
D 0 E1, D2 E2 1
\
T º
ª T
eiJ «cos 0 eiM sin 1 »
2
2 ¼
¬
\
cos
T
2
0 eiM sin
T
2
z
より
1
0
ブロッホ球
\
T
ª1 0 º
Z {«
»
¬0 1¼
y
M
x
1
Hadamard gate
H{
1º
1 ª1
«
»
2 ¬1 1¼
0 1
Ǿ0
2
Ǿ1
H looks like a ‘square-root of NOT’ gate,
though H2 is not a NOT gate.
0 1
2
§ 0 1
Ǿ¨¨
2
©
·
¸
¸
¹
0
§ 0 1
Ǿ¨¨
2
©
·
¸
¸
¹
1
0
0 1
2
y
0 1
2
1
y
y
回転操作
ブロッホ球のx, y, z軸それぞれを中心とした角度Tの回転
Rx T { e
iTX / 2
R y T { e
iTY / 2
T
T
cos I i sin X
2
2
T
T
cos I i sin Y
2
2
T
ª
cos
«
2
«
T
« i sin
¬
2
T
ª
cos
«
2
«
T
« sin
¬
2
Tº
i sin »
2
T »
cos »
2 ¼
\
cos
T
2
0 eiM sin
z
Tº
sin »
2
T »
cos »
2 ¼
T
2
1
0
\
T
y
Rz T { e
iTZ / 2
T
T
cos I i sin Z
2
2
ªe iT / 2
«
«¬ 0
0 º
»
eiT / 2 »¼
M
x
1
量子計算の例（
１）
交換回路
反転した三つの制御NOT
単一制御NOT
A
B
B
A
A
B
A B
1,0 o 1,1 0
A, B o A, A B
o A A B , A B
o B , A B B
A
B, A
B, A B
o 1 1 0 ,1 0
o 0 ,1 0 0
0 ,1 0
0 ,1
量子計算の例（
２）
制御制御NOTゲート
制御制御NOT（controlled controlled NOT）
ai
af
bi
bf
ci
cf
af
cf
または
cf
ai , b f bi
ci , ai bi 1 の場合
c f その他
aibi ci
ai
0
0
0
0
1
1
1
1
NOTゲート： ai
bi
0
0
1
1
0
0
1
1
ci
0
1
0
1
0
1
0
1
bi 1
の場合
制御NOTゲート：ai
ANDゲート： ci
0
af
0
0
0
0
1
1
1
1
cf
1 の場合 b f
の場合 c f
bf
0
0
1
1
0
0
1
1
cf
0
1
0
1
0
1
1
0
ci
bi ,c f
aibi
bi ci
古典計算もで
きる！
制御制御NOTゲートは3量子ビットゲート
ª1
«0
«
«0
«
0
U CCN { «
«0
«
«0
«0
«
«¬0
制御制御NOT（controlled controlled NOT）
af
cf
または
ai
af
bi
bf
ci
cf
ai , b f bi
ci , ai bi 1 の場合
c f その他
cf
aibi ci
CCN
0 0 0 0 0 0 0º
1 0 0 0 0 0 0»
»
0 1 0 0 0 0 0»
»
0 0 1 0 0 0 0»
0 0 0 1 0 0 0»
»
0 0 0 0 1 0 0»
0 0 0 0 0 0 1»
»
0 0 0 0 0 1 0»¼
000 000 001 001 010 010 011 011 100 100 101 101 110 111 111 110
十進数表記で
CCN
0 0 1 1 2 23 3
4 4 5 5 6 7 7 6
宿題
ai
ai
bi
bi
ci
ci
d=0
di
この量子回路が加算器であることを示しなさい．
万能ゲートと観測問題
◎ 万能ゲート：すべてのユニタリー変換が、一量子ビット回転ゲート(UR)と
二量子ビット制御ノットゲート(UCN)の組み合わせで実現
できる。または、三量子ビット制御制御ノットゲートのみの
組み合わせでもよい。
量子並列性と矛盾？ 本来は100量子ビットの量子並列演
算には 2100×2100のユニタリ行列が必要。
\ U \ a a2 01
a3 11 a ◎ 観測問題： 出力 を観測した場合 f CN i 1 00
4 10
2
ai
ei ( |00>, |01>, |10>, |11>) が確率 a 2 a 2 a 2 a 2 , i 0,1,2,3
1
2
3
4
で観測され、その後、波束はei の状態に収束する。
よって、正解の確率振幅を他より増大させる工夫が必要。
量子フーリエ変換（１）
◎入力ベクトルの確率振幅をフーリエ変換した結果が出力ベクトルの確率振幅となる．
b
~
f ( y ) ³ K ( y, x) f ( x)dx で K ( y, x) e ixy , a
~
f ( y)
f, b f だとフーリエ変換
a
N 1
N 1
x 0
x 0
¦ K ( y, x) f ( x) が離散フーリエ変換 f ( y )
§ N 1
U
量子離散フーリエ変換（ユニタリ変換） ¨¨ ¦ f ( x) x
©x 0
選択的回転変換
~
f ( y)
N 1
iT
¦ e x G xy f ( x) e
iT y
~
¦ K * ( y, x) f ( x) が逆変換
·
¸
¸
¹
N 1 ~
¦ f ( y) y
y 0
f ( y)
x 0
例：Hadamard gate （アダマードゲート） 1量子ビット離散フーリエ変換（可逆）
1º
1 ª1
0 1
0 1
{
H
D 0 E1
D
E
H
«
»
2
2
2 ¬1 1¼
H x
1 1
¦ 1xy y
2y 0
量子フーリエ変換（２）
◎ n量子ビット量子フーリエ変換は以下の量子回路で実行できる．
H
j1
Rn-1
R2
0 e 2Si 0. j1 jn 1
Rn
H
j2
Rn-2
0 e 2Si 0. j2 jn 1
Rn-1
H
jn 1
0 e 2Si 0. jn 1 jn 1
R2
H
jn
位相ゲート R j k 1
0 e 2Si 0. jn 1
§ S ·
0 j 0k 0 j 0k 0 j1k 0 j1k 1 j 0k 1 j 0k exp¨
¸ 1 j1k 1 j1k
© 2k j ¹
0º
ª1
j k 1 »
R j k 1 { «
2S i / 2
«¬ 0 e
»¼
３キュービット量子フーリエ変換の例
j1
H
R2
R3
H
j2
Step 3
Step 4
×
0º
ª1
R2 { «
iS / 2 »
¬0 e
¼
0º
ª1
R3 { «
iS / 4 »
¬0 e
¼
0 3
1 2
0 1 { 010
1
0 1 1 010 011 2
2
1
R2(1 2)
R2(1 2)
010 011 1 §¨ 010 exp§¨ i S ·¸ 011 ·¸ 1 010 i 011 2
2©
2
© 2¹
¹
1
R3(13)
R3(13)
010 i 011 1 010 i 011 2
2
1
H2
^ 0 0 1 0 i 0 0 1 1 ` 1 ^ 000 010 i 001 i 011 `
2
2
Step 1 H1 010
Step 2
R2
H
j3
入力
×
Step 5
R2( 23)
Step 6
H3
Step 7（逆転）
hjk o kjh
0
1
1
^ 000 010 i 001 i 011 `
2
1
^ 000 100 010 110 i 001 i 101 i 011 i 111 `
8
1
^ 000 001 010 011 i 100 i 101 i 110 i 111 `
8
フーリエ変換終了
Quantum algorithms
¾ Deutsch-Jozsa algorithm
¾ Grover’s algorithm
¾ Shor’s algorithms
Deutsch-Jozsa algorithm（１）
補題１：量子並列性
f ( x ) : ^0,1`
U f x , y o x , y f x 0 1
2
x
0
y
データ，ターゲット
\
0 1
,0
2
Uf
o
0 , f 0 1, f 1
2
H
0
H
0
\
2
§ 0 1
¨¨
2
©
H
2
·§ 0 1
¸¸¨¨
2
¹©
·
¸¸
¹
y f ( x)
2関数を並列計算
Walsh-Hadamard transformを利用すると
0
Uf
00 01 10 11
2
と記す
x
\
Deutsch-Jozsa algorithm（２）
補題1：量子並列性（つづき）
0
n
H
n
0
入力
出力
x
Uf
y
0
1
n
y f (x)
1
¦ x f x 2n x
0
¦ x f x 2n x
x
1
2
n
0, f 0 1, f 1 2, f 2 x, f x 0∼xの入力を並列計算
Deutsch-Jozsa algorithm（３）
補題２：Deutschの問題
入力
\0
\1
\2
\2
\3
\3
\0
\1
\2
0
H
x
1
H
y
01
§ 0 1
¨¨
2
©
·§ 0 1
¸¸¨¨
2
¹©
·
¸¸
¹
§ 0 1 ·§ 0 1 ·
¸¸¨¨
¸¸
r ¨¨
2
2
©
¹©
¹
§ 0 1 ·§ 0 1 ·
¸¸¨¨
¸¸
r ¨¨
2 ¹©
2 ¹
©
§ 0
r 0 ¨¨
©
§ 0
r 1 ¨¨
©
1
2
·
¸¸
¹
1 ·
¸
2 ¸¹
if f 0 f 1
if f 0 z f 1
if f 0 \3
if f 0 z f 1
Uf
H
y f (x)
§ 0 1
U f x ¨¨
2
©
f 1
x
\3
·
¸¸
¹
1 f x x
§ 0 1
¨¨
2
©
§ 0 1
r f 0 f 1 ¨¨
2
©
·
¸¸
¹
f 0 f 1 を1回で決定できる．
古典的には最低2回必要．
·
¸¸
¹
Deutsch-Jozsa algorithm（４）
本題
x
f x : ^0 ,1`
¾ constant : f(x) is constant
¾ balanced : f(x) is half 0 and half 1
n
0 ,1, ,2 1
Mission : Judge whether f(x) is constant or balanced.
n
0
H
n
x
H
y
1
\0
\0
0
n
1
Uf
y f ( x)
x § 0 1 ·
¸¸
¨¨
¦
n
2 ¹
x^0,1`n 2 ©
\3
\2
\1
\1
H
n
x
\2
\3
¦
1 f x x § 0
x
¦¦
z x
¨¨
©
2n
1
2
1xz f x z
2n
·
¸¸
¹
§ 0 1 ·
¨¨
¸¸
2
©
¹
Example: n=2
0
n
1
H
n
x
H
y
f ( x)
0
0
1
ª 0 1 º ª 0 1 º
«
»
«
»
H1
2
2
¬«
¼» ¬«
¼»
H
n
y f ( x)
º ª 0 1
»
«
2
»¼ «¬
º
»
H1
»¼
Get 0 if f(x) is
constant.
r 0
0
H1
0
1
0
H1
2
1
1
H1
3
( 0,0,1,1)
ª 0 1
«
2
«¬
f ( x)
Uf
( 0,0,0,0 ) or (1,1,1,1)
ª 0 1
r«
2
«¬
f ( x)
x
º ª 0 1
»
«
2
»¼ «¬
º
»
H1
»¼
(1,0,0,1)
ª 0 1
«
2
«¬
º ª 0 1
»
«
2
»¼ «¬
º
»
H1
»¼
Grover’s algorithm (1)
データベース検索：N=2n個のファイルがあり，0からN-1までのアドレスがつけられている．
指定された内容のファイルを少ないステップで見つけたい．古典的にはNステップ必要だ
f x 1 その他では0．
が，グローバーの手法では N でよい．正解のアドレスでは 0
n
H
n
測定
G
G
G
オラクル用
N
回程度
Gの中身
n
オラクル
オラクル用
x o 1 f x x
H
n
Phase
0 o 0
x ox
H
n
Grover’s algorithm (2)
Gの中身
n
オラクル
オラクル用
H
n
Phase
0 o 0
x ox
H
n
x o 1 f x x
x o 1 f x x ，すなわちオラクルは正解f(x)=1のときのみに反転させる
H
n PH
n
2 \
H
n 2 0 0 I H
n
\ I ¦ k D k k
¦ D k 2 D
2\ \ I
k
k
すなわち振幅の平均値<Į>を中心として反転させる
Grover’s algorithm (3)
例：4量子ビットで正解が一つで
1 の場合（2nにおいてn=2に対応）
x
0
1
2
3
00
01
10
11
0.5
0.25
0.5
1.0
0
素因数分解の計算（15=3×5の場合）
確定的モデル 15÷2, 15÷3, 15÷4・
・・
・
をつづけ
割り算の答えとあまりを求める
確率的モデル （
乱数でためす）
n mnをNで割ったあまり
Fn m mod N を求める
Fn
n
2 mod15
例としてN=15, m=2を選ん
だ場合を考える
確率的計算 Fn
N=15, m=2
F0=20÷15のあまり
F1 =21÷15のあまり
F2 =22÷15のあまり
F3 =23÷15のあまり
F4 =24÷15のあまり
F5 =25÷15のあまり
F6 =26÷15のあまり
F7 =27÷15のあまり
こたえ
1
2
4
8
1
2
4
8
2n mod15
周期 r=４
m r / 2 1 24 / 2 1 5
m r / 2 1 24 / 2 1 3
n
確率的計算 （例２） Fn 11 mod15
N=15, m=11
F0=110÷15のあまり
F1 =111÷15のあまり
F2 =112÷15のあまり
F3 =113÷15のあまり
F4 =114÷15のあまり
F5 =115÷15のあまり
F6 =116÷15のあまり
こたえ
1
11
1
11
1
11
1
緑下線の数字とN=15の
最大公約数をとると３と５
F7 =117÷15のあまり
11
古典的にrを求めるのが難しい
周期 r=2
m r / 2 1 112 / 2 1 12
m r / 2 1 112 / 2 1 10
古典的計算機内での処理 Fn
10進
Fn
F0
F1
F2
F3
F4
F5
F6
F7
2n(mod
1
2
4
8
1
2
4
8
15)
2n mod15
2進
0
1
0
1
0
1
レジスターY
2n (mod 15)
0 0 0 1
0 0 1 0
0 1 0 0
1 0 0 0
0 0 0 1
0 0 1 0
0 1 1 0
0 1 1 1
0 1 0 0
1 0 0 0
レジスターX (n)
0
0
0
0
0
0
0
0
0
0
1
1
0
0
1
1
0
0
20
21
22
23
20
21
22
23
Fn
量子計算では 10進
Fn
F0
F1
F2
F3
F4
F5
F6
F7
2n(mod 15)
1
2
4
8
1
2
4
8
2進量子情報
レジスターX (n)
0
0
0
0
0
0
0
1
0
1
0
1
0 1 1 0
0 1 1 1
0
0
0
0
1
1
0
0
1
1
0
0
2n mod15
レジスターY
2n (mod 15)
0 0 0 1
0 0 1 0
0 1 0 0
1 0 0 0
0 0 0 1
0 0 1 0
20
21
22
23
20
21
22
23
0 1 0 0
1 0 0 0
Xに重ね合わせ状態、Yに絡みあった状態をつくる
¦ x , f x x
0 1 1 0
0 1 1 1
0 1 0 0
1 0 0 0
0
0
0
0
0
0
0
0
0
0
1
1
0
0
1
1
0
0
0
1
0
1
0
1
10
20
21
22
23
20
21
22
23
r=4
8
6
4
2
0
0
2
4
6
8
10
12
Fnのnの値
フーリエ変換
可能性の高さ
レジスターY
2n (mod 15)
0 0 0 1
0 0 1 0
0 1 0 0
1 0 0 0
0 0 0 1
0 0 1 0
レジスターX(n)
2n mod15
2n(mod 15)の値
量子計算では（2）
Fn
0
2
4
6
周期rの値
8
10
12
Shor’s algorithm (1)
例：3量子ビットでf(x)の周期がr=2の場合を考える．
X :
1
000 001 010 011 100 101 110 111
8
1
0 1 2 3 4 5 6 7 8
X ,Y : \
1
¦ x , f x 8 x
離散フーリエ変換をȥに適用する．（
知りたいのはf(x)の周期r）
\'
7 2S
1
1
ikx / 8
x , f x 0 ^ f 0 f 1 f 2 f 7 ` ¦e
8
8 x ,k 0
1
1 f 0 e 2S i / 8 f 1 e 2S i 2 / 8 f 2 e 2S i 7 / 8 f 7 8
1
2 f 0 e 4S i / 8 f 1 e 4S i 2 / 8 f 2 e 4S i 7 / 8 f 7 8
．．．．．．
1
7 f 0 e14 S i / 8 f 1 e14 S i 2 / 8 f 2 e14 S i 7 / 8 f 7 8
^
^
^
`
`
`
Shor’s algorithm (2)
f(x)も計算の結果，周期r=2であれば，f(0)=f(2)=f(4)=f(6)および
f(1)=f(3)=f(5)=f(7)なので以下のようにくくれる．
\'
1
0 ^ f 0 f 1 ` 2
1
1 f 0 e 0 eS i / 2 eS i e 3S i / 2 f 1 eS i / 4 e 3S i / 4 e 5S i / 4 e 7S i / 4 8
^ `
1
2 ^ f 0 e 0 eS i e 2S i e 3S i f 1 eS i / 2 e 3S i / 2 e 5S i / 2 e 7S i / 2 `
8
1
3 ^ f 0 e 0 e 3S i / 2 e 3S i e 9S i / 2 f 1 e 3S i / 4 e 9S i / 4 e15 S i / 4 e 21S i / 4 `
8
^
`
1
4 f 0 e 0 e 2S i e 4S i e 6S i f 1 eS i e 3S i e 5S i e 7S i ．．．．．．
8
同色の色線で引かれた位相同士は干渉により弱めあい，ゼロとなる．
結果として生き残るのが
\'
^
1
0 , f 0 0 , f 1 4 , f 0 e i S 4 , f 1
2
`
よってX測定では0か4を同確率でえる．
Shor’s algorithm (3)
ショアのアルゴリズムによると測定結果kは，k=0, 2n/r, 2×2n/r, 3×2n/r, ・
・
・(r-1)2n/rをとる．
前ページの例ではn=3，k=0,4からr=2が求まる．
(r-1)2n/rと何種類の値をとれるため，周期r
疑問： kは，k=0, 2n/r, 2×2n/r, 3×2n/r, ・
・・
は決定できないのでは？
7量子ビットでr=8の例で考えると27=128．よってXの測定で8つのk=0, 16, 32, 48…, 112
のうちの1つが結果として得られる．たとえばkを測定して80が得られたとする．
27
k
128
80
8
5
他のkでも同じようにすると
27
k
8
4 8
8, 4 , , 2 , ,
3
3 7
分子に注目すると正解r=8が50%の確率で
得られることがわかる．これで十分！
入力に誤差がある場合の影響
◎例題：
f(x)=kx, k=0, 1, 2, ・・N-1が入力された場合の勾配kを知りたい。
xy
方法： ユニタリ行列 U >U xy @, U xy Z / N , Z exp(2Si / N ), x, y 0,1,...., N 1
\ k Z fk (0)e0 Z f k ( x )ex Z fk ( N 1)eN 1 / N
入力
忠実に計算すると：U\ k ek となり確率１で正解が得られる。 1
·
§ § § 2Si · ·0
例：N=2, k=1の場合
§ 2Si · ·
§
1
1
º
ª
¨
¸
¨
¸
¨
1
0
1
1 ¨ © 2 ¹ ¸ ª º ¨ © 2 ¹ ¸ ª º¸
S
i
2
§
·
«
U\ 1
¨¨e
¨
¸»
¸ « »¸
¸ « » ¨e
2 «1 e
¬
© 2 ¹»
¼
2 ¨¨
©©
¸ ¬0 ¼ ¨
©
¹
¸ ¬1¼ ¸
¹
¹
◎入力fkが正確に行えず g k ( x) (k H ) x, H 1 が
U \ b bk e bk 入力されると k k , 0e 0 , x x
, N 1e N 1
g x) 4 .2 が
x
が出力される。N=16, k=4, H=0.2では 4 ( 高い確率で得られる。繰り返し測定が重要。
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
e x が得られる確率(N=16, k=4,
H=0.2)
量子コンピュータの基本要素
1. 初期化
量子ビット#1
2. 量子演算
3. 読み出し
S
N
量子ビット#2
量子ビット#3
回転
単一スピン
検出
量子ビット#4
量子ビット#5
制御ノット
量子ビット#6
量子ビット数
総演算ステップ数
超並列計算
0
0
0
0
1
1
1
1
0
0
1
1
0
0
1
1
2進数
0
1
0
1
0
1
0
1
0
1
2
3
4
5
6
7
10進数
2n通りの数
を一気に
処理できる
量子ビットに必要な性質
１．初期化が容易である．
２．位相緩和時間が長い（Hが時間に依存しない）
外界との相互作用が小さい
３．１ステップに必要な演算時間が短い
４．多量子ビット演算に充分な相互作用がえられる．
他の量子ビットとの相互作用をon/offできる．
５．単一ビットの状態測定（
読み出し）
が容易である．
量子コンピュータの実現にむけて
１．量子ビット数(n)の増加 → 状態数 2n
２．総演算ステップ数Ł
位相緩和時間 T2
スイッチ時間 ts
量子ビット
緩和時間 T2 (秒)
電子準位
10 −9
10 −13
10 4
電子スピン
10 −6
10 −10
10 4
イオン準位
10 −1
10 −14
10 13
核スピン
10 3
10 −4
10 7
光子
スイッチ時間 ts （秒）
総演算ステップ数
量子ビットのジレンマ（核スピンの例）
長所
１．外界との相互作用が小さい
極めて長い緩和時間 T2 1000秒?
２．スイッチ時間 ts 0.0001秒
（核磁気共鳴周波数(KHz)の逆数）
３．実現可能な演算ステップ数 107回
短所
１．外界との相互作用が小さい
演算・
単一スピン測定が困難
２．初期化が困難
∼10μK
キャビティー QED
中性イオン
光学結晶
固体システム
量子ドット中の電荷
の光学的操作
イオントラップ
分子核磁気共鳴
（溶液NMR）
量子ドット中の電子
スピンの光学的操作
全シリコン
量子計算
超伝導における
電荷状態の利用
単一スピン
検知プローブ
バルク結晶
核磁気共鳴
半導体中の不
純物核スピン
超伝導における
磁束状態の利用
半導体中の不
純物電子スピン
量子ドット中の電荷
の電気的操作
量子ドット中の電子
スピンの電気的操作
液体ヘリウム
上の2次元電
子系
その他:
線形光学、非線形
光学, STM, . . .
量子ビット操作最前線
*
Vandersypen
PRL 00
総演算ステップ数
Vandersypen
APL 00
Vandersypen
PRL 99
Chuang
Nature 98
02 NEC
02 Delft
量子ビット数
Vandersypen
Nature 2001
factoring 15