i i+1

春の学校：Particles, Strings, and Quantum Information
量子情報・計算の基礎
藤井啓祐
京都大学白眉センター/大学院理学研究科
エンタングルメント・量子測定
量子情報・計算
実現
量子重力!
(Ads/CFT)
量子誤り訂正
トイモデル
誤り耐性!
量子計算
吉田紅さんのセミナー
量子アルゴリズム
トポロジカル!
複雑性
量子計算
TQFT!
(Jones多項式)
量子暗号!
の安全性
トイモデル
復号化問題
量子相!
(トポロジカル秩序,エニオン) 統計力学!
(スピングラス)
可解模型
目次
第一部：量子計算!
・量子計算の基礎!
・量子アルゴリズム!
!
-Hadamardテスト!
!
-Shorの素因数分解アルゴリズム!
!
-Jones多項式の近似!
!
第二部：量子誤り訂正符号
参考資料：集中講義「量子コンピュータ概論」講義ノート!
http://quantphys.org/keisukefujii/lecture.html
arXiv: 1504.01444 to be published from SpringerBriefs
量子計算の基礎
量子ビット
計算基底(computational basis) |0i =
,
量子ビット
,
| i = ↵|0i + |1i
射影測定 {|0i, |1i}
2
↵,
✓
0
1
◆
2
単一光子,電子・核スピン,
Bloch球
古典ビット
|1i =
✓
2 C |↵|2 + | |2 = 1
p0 = |h0| i| , p1 = |h1| i|
y
1
0
◆
イオン・中性原子, 超伝導回路
z
2✓
x
↵ = cos ✓,
= ei sin ✓
Chiorescu et al, Science 2003
Pauli演算子
Pauli演算子
✓
◆
0 1
X=
1 0
Y =
✓
0
i
•反交換(anti-commute): ZX =
• XZ = iY
i
0
◆
X|1 = |0
(bit-flip)
Z|0 = |0
Z|1 =
(phase-flip)
Y |0 = i|1
Y |1 =
1
0
0
1
◆
XZ
X|0 = |1
|1
Z=
✓
i|0 (bit&phase-flip + global phase)
Pauli演算子の固有状態（Pauli基底）
Z ! |0i, |1i
Z basis
p
X ! |+i ⌘ (|0i + |1i)/ 2, | i ⌘ (|0i
X basis
p
|1i)/ 2
単一量子ビット演算
p
(|0i + i|1i)/ 2
y
x,y,z軸回転
RA (✓) = e
i ✓2 A
A = X, Y, Z
例） e
i⇡
4Y
|0i = |+i
RY (✓)
ブロッホ球
| i
|+i
RZ (✓) z
2✓
|0i
x
RX (✓)
SU(2)のEuler分解:
U = RX (↵)RZ ( )RX ( )
|1i
(|0i
p
i|1i)/ 2
多量子ビット系
合成系 =テンソル積：
B
A
テンソル積
HA ⌦ H B
|0i ⌦ |1i =
✓
1
0
◆
テンソル積空間の基底
⌦
✓
0
1
◆
0
1
0 |00
B 1 C|01 Kronecker!
C
=B
@ 0 A|10 product
0 |11
{|0i, |1i} ⌦ {|0i, |1i} ! |00i, |01i, |10i, |11i
p
エンタングル状態: (|00i + |11i)/ 2
多量子ビット系
n量子ビット系（2n次元）の記述
| i=
X
i1 ,i2 ,...,in
Ci1 ,i2 ,...,in |i1 i2 ...in i (ik = 0, 1)
2n 個の複素パラメータ!!!
“If a computer stimulates this …. require an exponentially
explosive growth in the size of the simulating computer.”
!
“Let the computer itself be built of quantum mechanical
elements which obey quantum mechanical laws.”
http://www.nobelprize.org/nobel_prizes/
physics/laureates/1965/feynman-bio.html
Richard Phillips
Feynman
(1918-1988)
“Simulating Physics with Computers”!
International Journal of Theoretical Physics (1982)
多量子ビット演算子
CNOT (controlled NOT)
1
0
0
0
⇤(X)
0
1
0
0
0
0
0
1
0
0
1
0
|00
|01
0
0
0
1
|00
|01
=
|0 0|
I + |1 1|
X
=
|0 0|
I + |1 1|
Z
|10
|11
CZ (controlled Z)
1
0
0
0
⇤(Z)
e
0
1
0
0
0
0
1
0
|10
|11
i /4(Z1 Z2 Z1 Z2 I)
量子回路
p
|+i = (|0i + |1i)/ 2
time
p
(|00i + |11i)/ 2
|0i
p
⇤c,t (X)|+ic |0it = (|00i + |11i)/ 2
量子回路
qubit
time
qubit
|ii
|ii|i
interaction
|ji
|11i
|01i
|10i
|00i
ji
⇤c,t (X)|iji = |i i
ji
XOR(排他的論理和)
多量子ビット演算子
CNOT (controlled NOT)
1
0
0
0
⇤(X)
0
1
0
0
0
0
0
1
0
0
1
0
|00
|01
0
0
0
1
|00
|01
=
|0 0|
I + |1 1|
X
=
|0 0|
I + |1 1|
Z
|10
|11
CZ (controlled Z)
1
0
0
0
⇤(Z)
e
0
1
0
0
0
0
1
0
|10
|11
i /4(Z1 Z2 Z1 Z2 I)
CNOT と SU(2) で任意のn 量子ビットユニタリ演算子を
構成できる． ! → 万能量子計算!
!
!
!
!
!
!
universal quantum computation
量子アルゴリズム
量子計算機で何が計算できるか？
Hadamardテスト
|0i + |1i
p
|+i =
2
1 0
0 i
◆
X
p± = k(h±| ⌦ I)| ik
2
⇤(U ) = |0ih0|
⌦ I + |1ih1| ⌦ U
1
p+ =
(1 + Reh00..0|U |00..0i)
2
1
p = (1
2
U
… …
… …
|0i
|0i
✓
|0i
|0i|0...0i + (I ⌦ U )|1i|0...0i
p
| i=
2
Reh00..0|U |00..0i)
h00..0|U |00..0i
2n×2n ユニタリ演算子の行列要素
Chernoff-Hoeffding 限界
Prob
✓
N+
N
p+ >
◆
 2e
2
2
N
Hadamardテスト
|+i
X
固有値
U |Ei = e |Ei
U
… …
i
… …
固有状態 |Ei
hE|U |Ei = ei
をもっと精度よく推定できないか？
量子フーリエ変換 & Kitaevの位相推定!
U に対しては を多項式桁まで推定できる．
→ある性質をもったの Shorの素因数分解アルゴリズム
N , x ：互いに素な整数． !
r : 位数
(xr/2
r
GCD → Nの因数
x = 1 mod N
Peter Shor
Ux =
X
y
1)(xr/2 + 1) = 0 mod N
|xy mod N ihy|
位相推定
Ux |us i = e2⇡i(s/r) |us i (連分数展開)
(
http://wwwmath.mit.edu/ shor/
r 1
X
1
|us i = p
e
r
k=0
2⇡i(s/r)k
k
|x mod N i.
)
Jones多項式の近似量子アルゴリズム
Jones多項式の近似と量子計算
Jones多項式：結び目(knot)不変量（多項式）!
TQFT/Chern-Simons theory [Witten89]
TQFT 量子計算 [Freedman-Kitaev-Larsen-Wang03]
量子計算 [Aharonov-Jones-Landau08]
ブレイド(組紐)群
結び目
閉包
不変量
Jones多項式
(2+1)-D non-Abelian
gauge theory &!
non-Abelian anyon
ユニタリ表現
(Temperley-Lieb代数)
行列トレース
万能性
(SU(2N)で稠密）
量子計算
結び目(knot)
結び目の変形：
連続変形
Reidemeister変形
2次元での射影図
(II)
=
(I)
=
= =
(III)
これらの変形に対して不変な量は？
=
Jones多項式
結び目L !
(2次元射影図)
交点
全ての交点を{
Kauffman多項式：hLi
s+≡
=
の数,
Jones多項式： VL (t)
X
A
s
s-≡
s+ s
d
の数,
= ( A)
,
3w(L)
}で置き換える→状態 s (state)
|s| 1
|s|≡ループの数,
hLi
t=A
w(L)≡（ の数）ー（ の数）
ひねり数(writhe)
d=
4
(A2 + A
2
)
Jones多項式
Kauffman多項式
h h = A h h+ A h h
-1
h h + Ah h
= (d A +A) h h
= -A h h
= d A-1
-1
-3
Jones多項式は不変！
Reidemeister変形(II), (III)に対しても同様に不変である事が示せる．
ブレイド(組紐)群
結び目
閉包
不変量
Jones多項式
(2+1)-D non-Abelian
gauge theory &!
non-Abelian anyon
ユニタリ表現
(Temperley-Lieb代数)
行列トレース
万能性
(SU(2N)で稠密）
量子計算
ブレイド群 Bn
生成元 { i }：
i j
ブレイド!
（組紐）
=
i i+1 i
i
積で閉じる→群：
b1
=
j i
=
for |i
2
i+1 i i+1 .
…
b1b2
…
i i+1
b1
＝
b2
j|
b2
変形(III)
Temperley-Lieb代数 T Ln (d)
生成元 {Ei }：
Ei Ej = Ej Ei for |i
j|
Ei Ei±1 Ei = Ei ,
2
Ei
Ei =
= dEi .
2,
…
…
i i+1
タングル図
⇢˜( i ) ⌘ A⇢(Ei ) + A
1
! ! ↑!
TL代数の表現
⇢˜ (
)
≡
⇢( A
+A-1
I
＝
)
Jones多項式とブレイド群
⇢˜( i ) ⌘ A⇢(Ei ) + A
⇢˜ (
)
≡ ⇢( A
+A-1
1
I
)
トレース閉包
d
Tr[˜
⇢(
n 1
行列トレース
=
h
]
(
Jones多項式
Vbtr (t) = ( A)
h
Kauffman!
多項式
ブレイド群の表現のトレース
3w(btr ) n 1
d
Tr[˜
⇢(b)]
Jones多項式と量子計算
ブレイド群の表現のトレース
Jones多項式
Vbtr (t) = ( A)
3w(btr ) n 1
d
|+i
X
U
… …
… …
I
2
⌦n
Tr[˜
⇢(b)]
完全混合状態
ブレイド群のユニタリ表現
n
Tr[U ]/2
ブレイド(組紐)群
結び目
閉包
(2+1)-D non-Abelian
gauge theory &!
non-Abelian anyon
ユニタリ表現
(Temperley-Lieb代数)
path-model表現
不変量
Jones多項式
行列トレース
万能性
(SU(2N)で稠密）
量子計算
Path-model表現
1次元グラフ（k-1頂点）上の n ステップウォークを考える
1
2
k-1
path: p=1→2→1→2→3…..
左、右への移動によって0,1表示
p= 1
0
1
1 …..
pathを基底として空間を構成→ |pi 2 Hn,k
Path-model表現
zi 2 {1, ..., k
1} :ステップi の前にいた頂点
⇢(Ei )|...vi
1 00vi+2 ...i
=
⇢(Ei )|...vi
1 01vi+2 ...i
=
zi 1
zi
⇢(Ei )|...vi
1 10vi+2 ...i
=
⇢(Ei )|...vi
1 11vi+2 ...i
=
j
0,
zi +1
zi
|...vi
|...vi
1 10vi+2 ...i
+
p
p
…
…
i i+1
zi +1 zi 1
zi
zi +1 zi 1
zi
|...vi
1 10vi+2 ...i,
|...vi
1 01vi+2 ...i,
0,
= sin(j⇡/k) A = ie
( j = 1, ..., k
1 01vi+2 ...i +
Ei =
i⇡/(2k)
d = 2 cos(⇡/k)
1)
⇢˜( i ) はユニタリ演算子
→ ⇢(Ei ) はエルミート、 (SU(2) Chern-Simons level-(k-2) theory [Witten89])
プラット閉包
トレース閉包
dn
1
Tr[˜
⇢(
プラット閉包
…
b
…
(] = h
h
…
b
…
…
path |p0 i ⌘ |1010...10i
への射影演算子(定数倍)
Jones多項式と量子計算
プラット閉包
d
n/2 1
hp0 |˜
⇢(
Vbpr (t) = ( A)
3w(bpr ) n/2 1
d
Jones多項式
)|p0 i= h
hp0 |˜
⇢(b)|p0 i
Hadamard test
|p0 i
量子計算機をシミュレートできることも示せる．!
（←4stepエンコーディング）
X
U
……
ie
Jones多項式のA = （k>4,
k≠6）!
|+i
……
i⇡/(2k)
h
ブレイド(組紐)群
結び目
閉包
(2+1)-D non-Abelian
gauge theory &!
non-Abelian anyon
ユニタリ表現
(Temperley-Lieb代数)
path-model表現
不変量
k>4, k≠ 6
万能性
(SU(2N)で稠密）
行列トレース
量子計算
Jones多項式
|+i
……
|0i
U
……
|1i
|0i
X
エンタングルメント・量子測定
量子情報・計算
実現
量子重力!
(Ads/CFT)
量子誤り訂正
トイモデル
誤り耐性!
量子計算
吉田紅さんのセミナー
量子アルゴリズム
量子暗号!
の安全性
トポロジカル!
複雑性
量子計算
TQFT!
(Jones多項式)
トイモデル
復号化問題
量子相!
(トポロジカル秩序)
統計力学!
(スピングラス)
可解模型
レポート： Path-model表現
zi 2 {1, ..., k
1} :ステップi の前にいた頂点
↓ブレイド群の表現になっていることを示せ．
⇢˜( i ) ⌘ A⇢(Ei ) + A
1
…
Ei =
I
i i+1
↓TL代数の表現になっていることを示せ．
⇢(Ei )|...vi
1 00vi+2 ...i
=
⇢(Ei )|...vi
1 01vi+2 ...i
=
zi 1
zi
⇢(Ei )|...vi
1 10vi+2 ...i
=
⇢(Ei )|...vi
1 11vi+2 ...i
=
j
0,
zi +1
zi
|...vi
|...vi
1 10vi+2 ...i +
p
zi +1 zi 1
zi
zi +1 zi 1
zi
|...vi
1 10vi+2 ...i,
|...vi
1 01vi+2 ...i,
0,
= sin(j⇡/k) A = ie
( j = 1, ..., k
1 01vi+2 ...i +
p
i⇡/(2k)
…
d = 2 cos(⇡/k)
1 )
⇢˜( i ) はユニタリ演算子←示せ．
→ ⇢(Ei )はエルミート、