本書(shū)由數(shù)學(xué)家Bernhardt撰寫(xiě),用簡(jiǎn)明的數(shù)學(xué)語(yǔ)言來(lái)描述量子世界,只要求讀者具備高中數(shù)學(xué)知識(shí)。書(shū)中從量子計(jì)算的基本單位——量子比特開(kāi)始,然后討論量子比特測(cè)量、量子糾纏和量子密碼學(xué)。之后回顧了經(jīng)典計(jì)算中的標(biāo)準(zhǔn)主題—比特、門和邏輯,并描述了Edward Fredkin獨(dú)創(chuàng)的臺(tái)球計(jì)算機(jī)。*后定義了量子門,考慮量子算法的速度,以及量子計(jì)算對(duì)未來(lái)生活的影響。
做好準(zhǔn)備,跨入量子世界:從“墨子號(hào)”的前沿陣地,到“上帝擲骰子嗎”的科普領(lǐng)域,量子計(jì)算正在從實(shí)驗(yàn)室走向現(xiàn)實(shí)。如果你不滿足于新聞和故事里的量子世界,還想理解量子比特,那么請(qǐng)不要錯(cuò)過(guò)本書(shū)。只要熟悉高中數(shù)學(xué)知識(shí),并一路小跑跟上作者的思路,這就是你肯定能讀懂的量子計(jì)算。
硬核數(shù)學(xué),探尋計(jì)算本質(zhì):量子糾纏時(shí)發(fā)生了什么?量子隱形傳態(tài)如何傳遞信息?作為一位數(shù)學(xué)家,作者提煉出一套精簡(jiǎn)的數(shù)學(xué)表述來(lái)描繪光怪陸離的量子世界。這個(gè)世界與直覺(jué)相悖,看不見(jiàn)摸不著,語(yǔ)言只能觸及其表面,唯有數(shù)學(xué)才是探尋本質(zhì)的捷徑。借助數(shù)學(xué)的力量,你將真正讀懂量子計(jì)算。
本書(shū)的目的是介紹量子計(jì)算,使得任何一個(gè)熟悉高中數(shù)學(xué)知識(shí)和愿意投入一點(diǎn)時(shí)間的人都能理解。我們將會(huì)學(xué)習(xí)量子比特、量子糾纏、量子隱形傳態(tài)和量子算法,以及其他量子相關(guān)的主題。我們的目標(biāo)不是對(duì)這些概念給出一些不明確的想法,而是使它們清晰明了。
量子計(jì)算經(jīng)常出現(xiàn)在新聞中:中國(guó)通過(guò)隱形傳態(tài)將一個(gè)量子比特從地球傳送到一顆衛(wèi)星上;Shor算法使我們目前的加密方法面臨風(fēng)險(xiǎn);量子密鑰分發(fā)將使加密再次變得安全;Grover算法將加速數(shù)據(jù)檢索。但這一切究竟意味著什么?這一切是如何運(yùn)作的?所有這些都將在本書(shū)中得到解釋。
不使用數(shù)學(xué)能做到這一點(diǎn)嗎?如果我們想真正了解發(fā)生了什么,那就需要使用數(shù)學(xué)。量子力學(xué)的基本思想往往與直覺(jué)相悖。試圖用文字來(lái)描述這些是行不通的,因?yàn)槲覀冊(cè)谌粘I钪袑?duì)它們沒(méi)有經(jīng)驗(yàn)。更糟糕的是,文字描述常常給人留下這樣的印象:我們貌似理解了一些東西,而實(shí)際上我們還沒(méi)有理解。好消息是,我們并不需要引入太多的數(shù)學(xué)知識(shí)。作為一名數(shù)學(xué)家,我的職責(zé)是盡可能地簡(jiǎn)化數(shù)學(xué)(堅(jiān)持絕對(duì)的本質(zhì))并給出基本的例子來(lái)說(shuō)明它的用法與含義。也就是說(shuō),這本書(shū)可能包含你以前從未見(jiàn)過(guò)的數(shù)學(xué)概念,而且和所有的數(shù)學(xué)知識(shí)一樣,新的概念一開(kāi)始可能看起來(lái)很奇怪。重要的是不要忽略這些例子,而且要仔細(xì)閱讀計(jì)算的每一步。
量子計(jì)算是量子物理與計(jì)算機(jī)科學(xué)的完美融合,將20世紀(jì)物理學(xué)中一些最令人驚嘆的觀點(diǎn)融入一種全新的計(jì)算思維方式中。量子計(jì)算的基本單位是量子比特。我們將看到什么是量子比特以及測(cè)量量子比特時(shí)會(huì)發(fā)生什么。一個(gè)經(jīng)典比特要么是0,要么是1。如果是0,我們測(cè)量它,得到0;如果是1,我們測(cè)量它,得到1。在這兩種情況下,比特都保持不變。量子比特的情況則完全不同。一個(gè)量子比特可能是無(wú)限多個(gè)狀態(tài)中的某一個(gè)——0和1的疊加態(tài),但是當(dāng)我們測(cè)量它時(shí),和經(jīng)典情況一樣,我們只得到兩個(gè)值中的一個(gè)——0或1。測(cè)量會(huì)改變量子比特,一個(gè)簡(jiǎn)單的數(shù)學(xué)模型可以精確地描述這一切。
量子比特還可能糾纏。當(dāng)我們對(duì)其中一個(gè)進(jìn)行測(cè)量時(shí),會(huì)影響另一個(gè)的狀態(tài)。這是我們?cè)谌粘I钪袥](méi)有經(jīng)歷過(guò)的,但我們的數(shù)學(xué)模型完美地描述了這種現(xiàn)象。
這三個(gè)概念——疊加、測(cè)量和糾纏——是量子力學(xué)的核心。一旦我們理解了這些概念,就能知道如何在計(jì)算中使用它們。這正體現(xiàn)了人類的聰明才智。
數(shù)學(xué)家通常認(rèn)為:證明是美麗的,而且經(jīng)常包含意想不到的見(jiàn)解。對(duì)于我們將要討論的許多主題,我有完全相同的看法。貝爾定理、量子隱形傳態(tài)和超密編碼,這些都是珍寶。糾錯(cuò)線路和Grover算法更是相當(dāng)驚人的。
讀完本書(shū),你應(yīng)該理解了量子計(jì)算的基本概念,并會(huì)看到一些巧妙而漂亮的結(jié)構(gòu)。同時(shí),你還將認(rèn)識(shí)到量子計(jì)算和經(jīng)典計(jì)算并不是兩個(gè)截然不同的學(xué)科。量子計(jì)算是計(jì)算的一種更基本的形式——任何經(jīng)典計(jì)算機(jī)可以計(jì)算的都可以在量子計(jì)算機(jī)上計(jì)算。計(jì)算的基本單位是量子比特,而不是比特。從本質(zhì)上講,計(jì)算就是量子計(jì)算。
最后應(yīng)該強(qiáng)調(diào)的是,本書(shū)是關(guān)于量子計(jì)算理論的介紹。它是關(guān)于軟件的,而不是硬件的。雖然我們?cè)谀承┑胤胶?jiǎn)要地提到了硬件,偶爾也會(huì)討論如何在物理上糾纏量子比特,但這些只是題外話。這本書(shū)講的不是如何構(gòu)建量子計(jì)算機(jī),而是如何使用量子計(jì)算機(jī)。
以下是對(duì)這本書(shū)內(nèi)容的簡(jiǎn)要描述。
第1章。經(jīng)典計(jì)算的基本單位是比特。比特可以表示為處于兩種可能狀態(tài)之一的任何東西,標(biāo)準(zhǔn)例子是一個(gè)可以打開(kāi)或關(guān)閉的電子開(kāi)關(guān)。量子計(jì)算的基本單位是量子比特。這可以用電子的自旋或光子的偏振來(lái)表示,但自旋和偏振的性質(zhì)對(duì)我們來(lái)說(shuō)并不像開(kāi)關(guān)打開(kāi)或關(guān)閉那樣熟悉。
我們先來(lái)看看自旋的基本性質(zhì)。從奧托·斯特恩(Otto Stern)和瓦爾特·格拉赫(Walther Gerlach)的經(jīng)典實(shí)驗(yàn)開(kāi)始,他們?cè)趯?shí)驗(yàn)中研究了銀原子的磁性。我們可以看到在不同方向上測(cè)量自旋會(huì)發(fā)生什么。測(cè)量會(huì)影響量子比特的狀態(tài)。我們還會(huì)解釋與測(cè)量相關(guān)的隨機(jī)性。
該章的結(jié)論是,類似于自旋的實(shí)驗(yàn)可以用偏振濾光片和自然光來(lái)完成。
第2章。量子計(jì)算基于線性代數(shù)。幸運(yùn)的是,我們只需要一小部分概念。該章介紹我們需要的線性代數(shù)知識(shí),并說(shuō)明在后面的章節(jié)中如何使用這些知識(shí)。
我們將介紹向量、矩陣、如何計(jì)算向量的長(zhǎng)度以及如何判斷兩個(gè)向量是否垂直。首先介紹向量的初等運(yùn)算,然后介紹矩陣是如何同時(shí)進(jìn)行這些運(yùn)算的。
起初這些知識(shí)的作用并不明顯,但確實(shí)有用。線性代數(shù)是量子計(jì)算的基礎(chǔ)。由于本書(shū)其余部分使用了這里介紹的數(shù)學(xué)知識(shí),因此需要仔細(xì)閱讀。
第3章。該章介紹前兩章是如何聯(lián)系在一起的。線性代數(shù)給出了自旋或偏振的數(shù)學(xué)模型,這使我們能夠定義量子比特,并準(zhǔn)確地描述測(cè)量時(shí)會(huì)發(fā)生什么。
接下來(lái)書(shū)中舉了幾個(gè)在不同方向上測(cè)量量子比特的例子。最后介紹量子密碼學(xué),并描述BB84協(xié)議。
第4章。該章描述兩個(gè)量子比特糾纏的含義。使用文字很難描述糾纏,與之相對(duì),使用數(shù)學(xué)描述則很簡(jiǎn)單。張量積是一種新的數(shù)學(xué)思想,這是將單量子比特組合成多量子比特最簡(jiǎn)單的方法。
雖然糾纏的數(shù)學(xué)描述很直觀,但我們?cè)谌粘I钪胁⒉粫?huì)接觸到。當(dāng)測(cè)量一對(duì)糾纏量子比特中的某一個(gè)時(shí),會(huì)影響另一個(gè)。阿爾伯特·愛(ài)因斯坦(Albert Einstenin)不喜歡這種現(xiàn)象,并稱之為“幽靈般的超距作用”。我們會(huì)看幾個(gè)例子。
該章最后指出,我們不能使用糾纏來(lái)實(shí)現(xiàn)超光速通信。
第5章。我們看看愛(ài)因斯坦對(duì)糾纏的擔(dān)憂,以及隱變量理論能否保持定域?qū)嵲谛浴N覀冄芯控悹柌坏仁降臄?shù)學(xué)原理——這是一個(gè)顯著的結(jié)果,它提供了一種實(shí)驗(yàn)方法來(lái)確定愛(ài)因斯坦的論點(diǎn)是否正確。雖然貝爾當(dāng)時(shí)認(rèn)為愛(ài)因斯坦的觀點(diǎn)可能會(huì)被證明是正確的,但是愛(ài)因斯坦的觀點(diǎn)是錯(cuò)誤的。
阿圖爾·埃克特(Artur Ekert)意識(shí)到,測(cè)試貝爾不等式的裝置還可以用于生成密碼學(xué)中使用的安全密鑰,并同時(shí)測(cè)試是否存在竊聽(tīng)者。在該章的最后,我們描述了這種加密協(xié)議。
第6章。該章從計(jì)算的標(biāo)準(zhǔn)主題開(kāi)始:比特、門和邏輯。然后簡(jiǎn)要地介紹可逆計(jì)算和愛(ài)德華·弗雷德金(Edward Fredkin)的想法。我們證明了Fredkin門和Toffoli門都是通用的——你可以僅使用Fredkin門(或Toffoli門)來(lái)構(gòu)建一臺(tái)完整的計(jì)算機(jī)。最后介紹Fredkin的臺(tái)球計(jì)算機(jī)。盡管這并不是書(shū)中余下內(nèi)容真正需要的,但它十足的獨(dú)創(chuàng)性值得介紹。
這臺(tái)計(jì)算機(jī)是由相互碰撞的球和很多墻組成的。它使人聯(lián)想起粒子之間的相互作用。這激發(fā)了理查德·費(fèi)曼(Richard Feynman)對(duì)量子計(jì)算的興趣,費(fèi)曼寫(xiě)了該領(lǐng)域最早的一些論文。
第7章。該章開(kāi)始學(xué)習(xí)使用量子電路進(jìn)行量子計(jì)算,并定義了量子門。我們將看到量子門如何作用于量子比特,并意識(shí)到我們一直在使用這種思想。我們只需要改變觀點(diǎn):不再認(rèn)為正交矩陣作用于測(cè)量裝置,而是作用于量子比特。我們還證明了一些有關(guān)超密編碼、量子隱形傳態(tài)、克隆和糾錯(cuò)的驚人結(jié)果。
第8章。這可能是最具挑戰(zhàn)性的一章。我們會(huì)看到一些量子算法,并看到它們與經(jīng)典算法相比計(jì)算的速度有多快。為了討論算法的速度,我們需要引入復(fù)雜性理論中的思想。我們定義了查詢復(fù)雜性后,就開(kāi)始學(xué)習(xí)三個(gè)量子算法,并證明它們的查詢復(fù)雜性比經(jīng)典算法的更低。
量子算法揭示了正在解決的問(wèn)題的基本結(jié)構(gòu),它不僅僅是量子并行的思想——把輸入放進(jìn)所有可能狀態(tài)的疊加中。該章介紹了最后一部分?jǐn)?shù)學(xué)知識(shí)——矩陣的Kronecker積。實(shí)際上,這部分知識(shí)的困難源于我們正在以一種全新的方式進(jìn)行計(jì)算,而我們并沒(méi)有使用這些新思想來(lái)解決問(wèn)題的經(jīng)驗(yàn)。
第9章。最后一章著眼于量子計(jì)算將對(duì)生活帶來(lái)的影響。我們首先簡(jiǎn)要描述兩個(gè)重要的算法,一個(gè)是彼得·肖(Peter Shor)發(fā)明的,另一個(gè)是洛夫·格魯弗(Lov Grover)發(fā)明的。
Shor算法提供了一種將大數(shù)分解為質(zhì)因數(shù)的方法。這似乎并不重要,但我們的互聯(lián)網(wǎng)安全依賴于分解質(zhì)因數(shù)是個(gè)難以解決的問(wèn)題。能夠分解大質(zhì)數(shù)的乘積威脅到我們當(dāng)前計(jì)算機(jī)之間的安全交易?赡苓要等一段時(shí)間,我們才能擁有足夠強(qiáng)大的量子計(jì)算機(jī)來(lái)分解目前正在使用的這些大數(shù),但這一威脅是真實(shí)存在的,而且它已經(jīng)迫使我們思考如何重新設(shè)計(jì)計(jì)算機(jī)之間的安全對(duì)話方式。
Grover算法適用于特殊類型的數(shù)據(jù)檢索。我們展示了它是如何在一個(gè)小樣例中工作的,并說(shuō)明了它是如何在一般情況下工作的。Grover算法和Shor算法都很重要,不僅因?yàn)樗鼈兛梢越鉀Q問(wèn)題,還因?yàn)樗鼈円肓诵滤枷。這些基本思想正在被納入新一代算法中。
學(xué)習(xí)算法之后,我們轉(zhuǎn)個(gè)話題,簡(jiǎn)要地看一下如何使用量子計(jì)算來(lái)模擬量子過(guò)程。究其本質(zhì),化學(xué)就是量子力學(xué)。經(jīng)典計(jì)算化學(xué)的工作原理是利用量子力學(xué)方程,并用經(jīng)典計(jì)算機(jī)進(jìn)行模擬。這些模擬是近似的,忽略了細(xì)節(jié)。這種方法在很多情況下都很有效,但在某些情況下就行不通了。在這種情況下,你需要這些細(xì)節(jié),而量子計(jì)算機(jī)應(yīng)該能夠提供。
該章還簡(jiǎn)要地介紹了實(shí)際機(jī)器的構(gòu)建。這是一個(gè)快速發(fā)展的領(lǐng)域,第一批機(jī)器正在出售,“云”上甚至有一臺(tái)人人都可以免費(fèi)使用的機(jī)器?磥(lái)我們很快就會(huì)進(jìn)入量子霸權(quán)時(shí)代。(我們會(huì)解釋這意味著什么。)
本書(shū)的結(jié)論是,量子計(jì)算不是一種新型的計(jì)算,而是對(duì)計(jì)算本質(zhì)的發(fā)現(xiàn)。
致 謝
我非常感謝許多人對(duì)本書(shū)出版提供的幫助。Mart Coleman、Steve LeMay、Dan Ryan、Chris Staecker和三位匿名審稿人非常仔細(xì)地閱讀了各版原稿,他們的建議和修正使這本書(shū)得到了極大的改進(jìn)。我還要感謝Marie Lee和她在MIT出版社的團(tuán)隊(duì),感謝他們所有人的支持和努力,將一份粗略的提案變成了這本書(shū)。
作者簡(jiǎn)介:
克里斯·伯恩哈特(Chris Bernhardt)
美國(guó)費(fèi)爾菲爾德大學(xué)數(shù)學(xué)系教授,Turing's Vision: The Birth of Computer Science一書(shū)的作者。
譯者簡(jiǎn)介:
邱道文
中山大學(xué)計(jì)算機(jī)系教授。二十余年來(lái)從事量子計(jì)算與量子信息的研究,在量子計(jì)算模型、量子查詢算法、半量子密鑰分配、量子信息中的不完備性和極限問(wèn)題、模糊與概率自動(dòng)機(jī)和離散事件系統(tǒng)方面取得了重要成果,解決了國(guó)際知名學(xué)者C. Moore和J. P. Crutchfield、J. Gruska、S. Gudder提出的問(wèn)題。其研究將經(jīng)典與量子計(jì)算處理相互融合,以期達(dá)到物理可實(shí)現(xiàn)性和本質(zhì)上優(yōu)于經(jīng)典計(jì)算。在中科院一、二區(qū)和CCF A、B類等學(xué)術(shù)期刊和會(huì)議發(fā)表了160余篇學(xué)術(shù)論文,出版一部關(guān)于量子自動(dòng)機(jī)的學(xué)術(shù)專著。
譯者序
前言
致謝
第1章 自旋 …… 1
1.1 量子鐘 …… 7
1.2 同一方向的測(cè)量 …… 7
1.3 不同方向的測(cè)量 …… 8
1.4 測(cè)量 …… 10
1.5 隨機(jī)性 …… 11
1.6 光子與偏振 …… 13
1.7 小結(jié) …… 17
第2章 線性代數(shù) …… 19
2.1 復(fù)數(shù)與實(shí)數(shù) …… 20
2.2 向量 …… 21
2.3 向量的圖解 …… 22
2.4 向量的長(zhǎng)度 …… 23
2.5 標(biāo)量乘法 …… 23
2.6 向量加法 …… 24
2.7 正交向量 …… 25
2.8 bra-ket內(nèi)積 …… 26
2.9 bra-ket與長(zhǎng)度 …… 27
2.10 bra-ket與正交 …… 28
2.11 標(biāo)準(zhǔn)正交基 …… 30
2.12 向量的基表示 …… 31
2.13 有序基 …… 34
2.14 向量的長(zhǎng)度 …… 35
2.15 矩陣 …… 36
2.16 矩陣運(yùn)算 …… 39
2.17 正交矩陣與酉矩陣 …… 41
2.18 線性代數(shù)工具箱 …… 42
第3章 自旋與量子比特 …… 44
3.1 概率 …… 44
3.2 量子自旋的數(shù)學(xué)表示 …… 45
3.3 等價(jià)狀態(tài) …… 49
3.4 自旋方向與基 …… 51
3.5 裝置旋轉(zhuǎn)60° …… 54
3.6 光子偏振的數(shù)學(xué)模型 …… 55
3.7 偏振方向與基 …… 56
3.8 偏振濾波實(shí)驗(yàn) …… 57
3.9 量子比特 …… 59
3.10 Alice、Bob與Eve …… 61
3.11 概率偏振與相干性 …… 64
3.12 Alice、Bob、Eve和BB84協(xié)議 …… 65
第4章 糾纏 …… 69
4.1 非糾纏量子比特 …… 70
4.2 非糾纏量子比特的計(jì)算 …… 72
4.3 糾纏量子比特的計(jì)算 …… 74
4.4 超光速通信 …… 77
4.5 張量積的標(biāo)準(zhǔn)基 …… 79
4.6 如何制備糾纏的量子比特 …… 80
4.7 使用CNOT門制備糾纏的量子比特 …… 82
4.8 糾纏的量子鐘 …… 84
第5章 貝爾不等式 …… 87
5.1 不同基下的糾纏量子比特 …… 89
5.2 愛(ài)因斯坦與定域?qū)嵲谛?…… 93
5.3 愛(ài)因斯坦和隱變量 …… 95
5.4 糾纏的經(jīng)典解釋 …… 95
5.5 貝爾不等式 …… 97
5.6 量子力學(xué)的解釋 …… 98
5.7 經(jīng)典的解釋 …… 100
5.8 測(cè)量 …… 105
5.9 量子密鑰分發(fā)的Ekert協(xié)議 …… 106
第6章 經(jīng)典邏輯、門和電路 …… 109
6.1 邏輯 …… 110
6.2 布爾代數(shù) …… 112
6.3 功能的完備性 …… 115
6.4 門 …… 119
6.5 電路 …… 121
6.6 與非門是一個(gè)通用門 …… 123
6.7 門與計(jì)算 …… 123
6.8 存儲(chǔ) …… 126
6.9 可逆計(jì)算 …… 127
6.10 臺(tái)球計(jì)算 …… 135
第7章 量子門和電路 …… 141
7.1 量子比特 …… 142
7.2 受控非門 …… 143
7.3 量子門 …… 145
7.4 作用于一個(gè)量子比特的量子門 …… 146
7.5 是否存在通用量子門 …… 149
7.6 非克隆定理 …… 149
7.7 量子計(jì)算與經(jīng)典計(jì)算 …… 153
7.8 貝爾電路 …… 153
7.9 超密編碼 …… 156
7.10 量子隱形傳態(tài) …… 160
7.11 糾錯(cuò) …… 165
第8章 量子算法 …… 173
8.1 P與NP …… 174
8.2 量子算法是否比經(jīng)典算法快 …… 177
8.3 查詢復(fù)雜性 …… 178
8.4 Deutsch算法 …… 178
8.5 Hadamard矩陣的Kronecker積 …… 184
8.6 Deutsch-Jozsa算法 …… 188
8.7 Simon算法 …… 194
8.8 復(fù)雜性類 …… 206
8.9 量子算法 …… 209
第9章 量子計(jì)算的作用 …… 212
9.1 Shor算法與密碼分析 …… 213
9.2 Grover算法與數(shù)據(jù)檢索 …… 218
9.3 化學(xué)與模擬 …… 224
9.4 硬件 …… 226
9.5 量子霸權(quán)與平行宇宙 …… 231
9.6 計(jì)算 …… 232