量子计算与密码学

《量子计算与密码学》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、量子計算與密碼學曾文貴交通大學資訊科學系愛因斯坦(AlbertEinstein)說『上帝不丟骰子』，意味著他相信世界的下一步是確定的；然而經由驗證「貝爾不等式」(J.Bell’sinequality)，代表「世界的下一步是隨機的」的量子(quantummechanics)學派得到現今大多數物理學家的認同。物理的論證似乎有了一個定論，但是密碼學家的夢靨才剛剛要開始。自從費因曼(RichardFeynman)在八十年代提出利用量子現象來增加計算的速度之後，量子電腦(quantumcomputer)的概念漸漸的形成。量子電腦的最大特點是N個儲存位元可以同時儲存2N個資料，因此量子電腦可以在多

2、項式時間內解決一些目前電腦還需要指數計算量才能解決的問題，例如質因數分解、計算整數對數等；另外，量子電腦也可以加快完全搜尋(exhaustivesearch)的速度。根據估計，只要有幾千量子位元(qbits,quantumbits)的量子電腦，它的計算能力就要比現今地球上所有電腦的計算能力總和強上不知凡幾倍。目前具有幾個量子位元的量子電腦已經實驗成功，20至30量子位元的量子電腦也在設計與實驗中。如果實用的量子電腦實現了，密碼的研究要往哪裡走呢？這篇文章介紹「量子計算」(quantumcomputation)、「量子密碼分析」(quantumcryptanalysis)、「量子密碼方法

3、」(quantumcryptography)等，並討論未來密碼研究的方向。奇妙量子的世界物質具有粒子與波的雙重特性，到了次原子的世界，他們所產生的量子現象實在是令人難以相信。我們先來說一個大家熟悉的電子繞射干擾實驗，圖一中的電子槍E將電子一顆一顆的射向有A和B兩個細縫閘的薰黑玻璃，這時螢幕S上會有光點一個一個出現，而且漸漸地顯示出明顯的干涉條文。但是如果將B閘遮蓋起來，則螢幕上會呈現出如圖二的一片模糊。我們現在來看這個實驗的量子現象，在圖二中，當一個電子從E到達A閘時，它可以到達螢幕上的任一點，因此螢幕呈現出一團模糊的光點。在圖一中多一個B閘，因此一個電子可以到達A閘或是B6閘，然後再

4、到螢幕上顯像出來。問題是當一個電子在A閘(或B閘)時，它如何得知B閘(或A閘)是開的，然後跑到螢幕相關的位置上而形成干涉條文，這不是很奇怪嗎？量子論對此的解釋是一個電子是可以「同時」出現在A 閘與B閘，因此它知道要在螢幕上形成干涉的條文，量子論稱同時出現在不同的位置為「重位置」(superposition)，也就是這些量子狀態coherence在一起。因此我們可以用一個量子來「同時」表示兩個不同的狀態，這稱為一個量子位元(qbit)；以此類推，N個量子位元可以「同時」表示2N種不同的狀態！舉例來說，目前兩個位元的暫存器，在一個時間上只能表示00、01、10和11中的一種狀態，但是兩個量

5、子位元的暫存器，在一個時間上卻可以同時表示00、01、10和11四種狀態(四個數字)，我們可以把一個運算同時作用在這四個數字上。量子電腦的超級計算能力就是來自這裡。量子電腦如何計算一個量子位元的兩個狀態以a

6、0ñ和b

7、1ñ來表示，其中a和b為虛數，但是

8、a

9、+

10、b

11、=1；兩個量子位元的暫存器(2-qbitregister)可以代表a1

12、00ñ、a2

13、01ñ、a3

14、10ñ和a4

15、11ñ，其中各ai為虛數，而且

16、a1

17、+

18、a2

19、+

20、a3

21、+

22、a4

23、=1；其餘的以此類推。b1

24、000ñb2

25、001ñb3

26、010ñb4

27、011ñb5

28、100ñb6

29、101ñb7

30、110ñb8

31、111ña1F

32、0

33、00ña2F

34、001ña3F

35、010ña4F

36、011ña5F

37、100ña6F

38、101ña7F

39、110ña8F

40、111ñFa1

41、000ña2

42、001ña3

43、010ña4

44、011ña5

45、100ña6

46、101ña7

47、110ña8

48、111ñ=我們可以把一個運算(unitaryoperation)F對N量子位元暫存器作運算，將重位置由a1

49、00×××0ñ、a2

50、00×××1ñ、×××、a2N

51、11×××1ñ轉換成b1

52、00×××0ñ、b2

53、00×××1ñ、×××、b2N

54、11×××1ñ，例如，圖三中的F對三個量子位元暫存器的八個數字作運算而得到新的重位置。因此F是對這2N個數字同時作運算，也就是

55、『量子平行運算』，但是只要有個量子位元的暫存器及一些量子邏輯閘即可。量子電腦的功能雖然強大，實際使用時必須克服一些問題；主要是「量子狀態的不可回覆性」及「量子狀態的脆弱性」。雖然量子電腦可以同時表示2N個值，但是如果我們要得到暫存器的內容時，必須作de-coherence的動作，也就是摧毀量子狀態而得到一個值，這個值是所有狀態的一種，而且得到某個值的機會是相對狀態的係數的長度。更困難的是，量子狀態一但de-coherence6之後就無法恢復到原