### 2013-11-08 暨南大學周耀新老師演講投影片

```Quantum Computing

Grover演算法複雜度：
1/3  2/3
3
1.9

O
O

1,000,000次

1,000次





























|Ψ =
Bohr
|
+|
2
EinsteinEinstein



 運算、儲存、容錯
 量子邏輯閘
 輸入輸出一一對應(可逆)
 不會消除資訊
 不會產生額外耗能
 不會產生額外熱量

00
11
01
10
10
10
01
11
00





≡ |0
≡ |1

|0
|0
|0
|0
→ |0 , |1
→ |1 , |1
→ |1 , |1
→ |0 , |1
→ |1
→ |0
→ −|0
→ −|1





≡ |0
≡ |1

|0 →
|1 →
1
2
1
2
|00
|01
|10
|11
|0 + |1 ,
|0 − |1
→ |00 ,
→ |01 ,
→ |11 ,
→ |10





0
0
0
0
1
1
1
1
0
1
1
0

0
0
0
1
1
1
1
1
1
0

0
1
1

|0









• 非常高密度儲存
• 非揮發性
• 隨開即用
• 可同時儲存與處理資料
• 速度更快，消耗更低
• 室溫運行





• Bit flip

• Phase flip
• Bit and Phase flip
|0 + |1
|1
|0 +
− |0
|1





• Bit flip

• Phase flip
• Bit and Phase flip

error












Grover的快速搜尋法(Grover’s algorithm)



3



的複雜度在未排序之資料庫搜尋
Shor的質因數分解演算法(Shor’s algorithm)












SpongeBob

x1
y
x
a
x0
m
c
b
m
xc

①
②

AND

0

0
0我握有你們兩
1
1個的把柄了!!
0
1
1

0
0
0
0
1
0
1
1
Key：0 1

1
1
0
0
1
0
1
0
1
…
0
1
1
1
0
1
1
0
1
0

Oracle
Yes
No

+
1
|000
8
1
|100
8
+
+
1
|001
8
1
|101
8
+
+
1
|010
8
1
|110
8
+
+
1
|011
8
1
|111
8

+
1
|000
8
1
|100
8
+
−
1
|001
8
1
|101
8
+
+
1
|010
8
1
|110
8
+
+
1
|011
8
1
|111
8

1
+
|000 +
2 8
1
|100
2 8
+
1
|001 +
2 8
5
|101
2 8
+
1
|010 +
2 8
1
|110
2 8
+
1
|011
2 8
1
|111
2 8

1
+
|000 +
2 8
1
|100
2 8
−
1
|001 +
2 8
5
|101
2 8
+
1
|010 +
2 8
1
|110
2 8
+
1
|011
2 8
1
|111
2 8

－
1
|000 −
4 8
1
－ |100
4 8
1
|001 −
4 8
11
+
|101
4 8
1
|010 −
4 8
1
−
|110
4 8

1
|011
4 8
1
−
|111
4 8

1
|00
2
+
1
|01
2
+
1
|10
2
+
1
|11
2

1
|00
2
+
1
|01
2
−
1
|10
2
+
1
|11
2

1
|00
2
+
1
|01
2
−

1
|10
2
+
1
|11
2

= 15
3 × 5

± 1,
2
13 − 1,15 = 3
2
13 + 1,15 = 5
≤−1

|
,|
|0,0 + |1,0 + |2,0 + |3,0
1
+|4,0 + |5,0 + |6,0 + |7,0
16 +|8,0 + |9,0 + |10,0 + |11,0
+|12,0 + |13,0 + |14,0 + |15,0

⇒
13

15

|
,|
|0,1 + |1,13 + |2,4 + |3,7
1
+|4,1 + |5,13 + |6,4 + |7,7
16 +|8,1 + |9,13 + |10,4 + |11,7
+|12,1 + |13,13 + |14,4 + |15,7

|
1
|2 + |6 + |10 + |14
2
QFT

1
|0 + |4 + |8 + |12
2

1
|000 + |001 + |010 + |011
|100 + |101
|111 + |110
|101 + |111
|100
2 2 +|110
|0
H
H
|0
|0
H
H
|0
|0
H
H
|0

OK
• 網路碰撞
• 排程處理

Pa
Pb
0
0
0
1
50%+25%
1
0
50%
1
1

Pa
Pb
0
0
0
1
1
1
100%
1
0

1
Charlie
2
3
4
5
6

1
2
3
Charlie
6
4
5

Quantum Secure Direct Communication
(QSDC)

?
Quantum channel
?

QKD
v.s
QSDC

(Information
Leakage Before Eavesdropper
Detection)


Anybody who is not shocked by quantum theory
has not understood it.
By Niels Bohr (波爾)

I think I can safely say that nobody understands
the quantum theory.
By Richard Feynman (費因曼)

－
1
|000 −
4 8
1
－ |100
4 8
1
|001 −
4 8
11
−
|101
4 8
1
|010 −
4 8
1
−
|110
4 8
1
|011
4 8
1
−
|111
4 8

－
3
|000 −
4 8
3
－ |100
4 8
3
|001 −
4 8
7
+
|101
4 8
3
|010 −
4 8
3
−
|110
4 8
3
|011
4 8
3
−
|111
4 8
```