機(jī)器之心轉(zhuǎn)載

來源：知乎

作者：SIY.Z

12月4日，中國科學(xué)技術(shù)大學(xué)潘建偉研究團(tuán)隊(duì)與中科院上海微系統(tǒng)所、國家并行計算機(jī)工程技術(shù)研究中心合作，成功構(gòu)建了 76 個光子 100 個模式的高斯玻色取樣量子計算原型機(jī)「九章」，其處理特定問題的速度比目前最快的超級計算機(jī)「富岳」快了一百萬億倍。相關(guān)論文登上了國際頂級期刊《Science》雜志，引發(fā)學(xué)界、業(yè)界熱議。

近日，中科大校友、UC伯克利在讀博士、知乎用戶@SIY.Z 在一篇近兩萬字的長文中，詳細(xì)分析了“量子計算機(jī)和傳統(tǒng)電子計算機(jī)在算法方面的優(yōu)劣勢”。以下是原文內(nèi)容:

這是一篇我很早以前就想寫的文章。我的目的是給稍有數(shù)學(xué)等基礎(chǔ)的人，比較全面客觀地介紹量子計算和經(jīng)典計算在算法上的優(yōu)劣勢，而且會涉及到方方面面，可以說是一個大雜燴。我覺得我是有資格做這件事的，因?yàn)?1. 我本人就是計算機(jī)科班出身的，對計算機(jī)系統(tǒng)以及機(jī)器學(xué)習(xí)都有較為深刻的理解 2. 我本科參與過第一線的量子計算的研究 3. 我個人對多個學(xué)科都有涉獵，因此可以不至于錯的離譜地談?wù)撘恍?shí)際應(yīng)用問題。但是哪怕僅僅接觸到最表面的一些問題，如果要解釋清楚，都要花費(fèi)巨大的精力去解釋；此外，即使我寫了這樣一篇文章，可能也少有人關(guān)注，畢竟吧宣傳知識本身在知乎上可能已經(jīng)過時了，渲染情緒要容易的多，而且可以天天輸出。所以說，我寫這篇文章，也是靠了 “九章” 量子計算機(jī)的熱度，這讓我稍微有動力一些。

算法研究是一個非常非常復(fù)雜艱深的領(lǐng)域，特別是我需要橫跨量子和經(jīng)典兩大部分，而且涉及到的應(yīng)用涵蓋了組合優(yōu)化，密碼學(xué)，生物學(xué)，科學(xué)計算，理論計算機(jī)等各個領(lǐng)域，以個人水平很難涵蓋完整。而且考慮到受眾，我有必要模糊化和簡化一些概念，而只保證核心思想是正確的。因此如果過程中有差錯，請多多包涵。

此外這篇文章注定很長。與其說是讀一篇回答，不如說是看一本歷史小說。

第0章 算法和計算機(jī)

0.1 什么是算法？

對于大部分日常問題，我們不需要算法，直接按照直覺去做就行了。然而對于一個稍微復(fù)雜的問題，它的解決方案就不是那么簡單直接，往往需要一系列步驟。簡單來說，描述一個問題解決方案的步驟，就是算法。給定一個問題的算法，你就可以一步步的按照算法解決所有的類似的問題。其實(shí)生活中最明顯的算法的例子是說明書，它告訴你如何一步步地去按照說明書去完成一個功能，比如說如何安裝一個軟件，如何啟動一個電器，等等。

如果只是考慮到這一步，算法本身并沒有什么魅力。其實(shí)在生活中算法往往被視作 “機(jī)械、死板” 的代名詞。為什么？

人執(zhí)行算法的能力是非常有限的。哪怕對于一個固定的算法，人也需要大量的練習(xí)才能熟練解決問題，而這個過程并不有趣，長年按照 “算法” 去組裝元件的流水線的工人應(yīng)該深有體會。

人執(zhí)行算法的準(zhǔn)確性很低。比如 DIY 一個玩具，如果說明書只有 10 行，那么大多數(shù)人還是很自信的；如果發(fā)現(xiàn)說明書竟然要 100 多步，那么很多人組裝結(jié)束后，如果發(fā)現(xiàn)結(jié)果不對，會首先懷疑自己中間操作錯了。

記憶算法很困難。很多人玩過帶 “秘籍” 的魔方，可以按照說明書上的算法去慢慢還原魔方。但是一旦離開說明書，很多人就難以自己操作：這些算法需要一定的精力去記憶，而且熟練度很大程度上取決于記憶的難度。極其復(fù)雜的算法的對人來說首要挑戰(zhàn)是記憶，而不是操作。

算法描述的不精確性。說明書中的每一句話，因?yàn)樽匀徽Z言本身的缺陷和場景的復(fù)雜性，都容易產(chǎn)生歧義。由說明書產(chǎn)生的困惑是人類共有的體驗(yàn)。

由于以上這些問題，在歷史長河中，算法并不是科技和生產(chǎn)力的核心問題。雖然算法可能啟發(fā)來巴貝奇等人發(fā)明差分機(jī)，但是這并沒有扭轉(zhuǎn)歷史格局。直到 1936 年，一位英國的計算機(jī)學(xué)家，數(shù)學(xué)家，邏輯學(xué)家，密碼分析家兼理論生物學(xué)家，世界級長跑運(yùn)動員在數(shù)學(xué)上證實(shí)了一個無比強(qiáng)大的機(jī)器的存在。在他生后，計算機(jī)科學(xué)的最高成就會以他的名字命名。

0.2 執(zhí)行算法的終極機(jī)器——圖靈機(jī)

試想一下，在 100 年前，有人告訴你存在這樣一種機(jī)器：

這個機(jī)器非常簡單，至少是在數(shù)學(xué)模型的意義上。

這個機(jī)器的輸入的格式是有限的，這個機(jī)器可以執(zhí)行的操作也是有限的。所以在現(xiàn)實(shí)中你可以用有限的零件制造它。

需要構(gòu)成這個機(jī)器的基本操作都是非常簡單的，而且只需要固定的時間就可以完成。

這個機(jī)器是萬能的。只要你能夠用邏輯和數(shù)學(xué)描述一個算法，它就能自動執(zhí)行它。

這個機(jī)器是通用的，它可以模擬任何一種計算機(jī)器，包括它本身。

沒有任何一種機(jī)器在使用算法解決問題上比它更加強(qiáng)大。如果一個問題它不能解決，那么其他機(jī)器也一定不能解決。

你會相信這樣一種機(jī)器的存在嗎？

1936 年前后，阿蘭 · 圖靈（Alan Turing）構(gòu)造式地證明了這樣一種機(jī)器的存在

下面是一種更加簡單，但是更加接近現(xiàn)代計算機(jī)的一種圖靈機(jī)構(gòu)造（而不是最初的 “紙帶” 版本），我們在之后會多次提到它：

不過，阿蘭 · 圖靈發(fā)明這臺機(jī)器最初的動機(jī)并非來自于算法，而是為了解決邏輯學(xué)和數(shù)學(xué)問題，特別是數(shù)論公理化和數(shù)理邏輯等最根本的數(shù)學(xué)問題。當(dāng)時和他在一個圈子里面的人是希爾伯特，哥德爾，邱奇等人，因此整篇論文充滿了邏輯學(xué)的風(fēng)格。這也讓圖靈機(jī)在最初并沒有很快走出圈外，為公眾所知。在二戰(zhàn)期間，圖靈將大部分精力投入到了破譯納粹的密碼中，并獲得了巨大成功。

然而，隨后人們發(fā)現(xiàn)，圖靈機(jī)并不僅僅是一個數(shù)學(xué)玩具，它是執(zhí)行算法的最理想的萬能機(jī)器。我們來看圖靈機(jī)為何如此適合算法：上文中提到了人類自己執(zhí)行算法的缺陷，其中人執(zhí)行算法的能力和準(zhǔn)確性問題并不適用于機(jī)器，機(jī)器不會疲勞，不會出錯，不會有負(fù)面情緒；而算法的記憶問題，在圖靈機(jī)中只要把算法轉(zhuǎn)換成一串符號，寫入到中就可以了，自然也沒有問題；而算法描述的不精確性也是不存在的，在圖靈機(jī)中算法就是一堆符號決定的，嚴(yán)格按照來執(zhí)行，不存在不準(zhǔn)確。

所以最終問題只剩下 4 個：

如何確定一個問題可以被圖靈機(jī)解決。

如何設(shè)計算法。

如何將算法變成一堆符號。

如何制造圖靈機(jī)一樣的機(jī)器。

其中對于 “可計算性” 問題的研究，回答了問題 1 中的一些重要問題。人們知道一些經(jīng)典問題，比如“任意圖靈機(jī)的停機(jī)問題”，是不能被圖靈機(jī)解決的。

對于問題 2，算法設(shè)計也有了長足的發(fā)展，成為計算機(jī)科學(xué)的重要領(lǐng)域。本文中會繼續(xù)擴(kuò)展這一段。圖靈機(jī)的出現(xiàn)改變了算法和機(jī)器的關(guān)系：從前人們希望為算法找到一個機(jī)器，而現(xiàn)在人們?yōu)榱藱C(jī)器設(shè)計算法。

現(xiàn)代編譯原理，程序語言設(shè)計和軟件工程解決了問題 3。這部分仍然在不斷進(jìn)步。

問題 4 我們將在 0.4 節(jié)中說明，并且我們還會引入量子計算的概念。

0.3 通用計算機(jī)——一樣的模型，不一樣的概念

圖靈機(jī)從數(shù)學(xué)模型到具體應(yīng)用的道路上，一個重要的節(jié)點(diǎn)是 “通用計算機(jī)” 這種思維的興起。早在 1937 年，圖靈就意識到因?yàn)閳D靈機(jī)的強(qiáng)大特性，一臺圖靈機(jī)可以同時模擬一臺甚至多臺圖靈機(jī)（現(xiàn)在最直接的應(yīng)用就是虛擬機(jī)）。圖靈等將這種模型稱為“通用圖靈機(jī)”，或者“通用計算機(jī)”。但是當(dāng)時人們只是把它當(dāng)作一個有趣特性，并不是特別在意：畢竟模擬另外一臺圖靈機(jī)并不會加快解決問題的速度，只能做理論分析時用一用；而且它只是一種概念，在具體的實(shí)現(xiàn)上并不會和圖靈機(jī)有區(qū)別。

所以 1946 年制造的第一個電子計算機(jī)——ENIAC，仍然 “忠實(shí)” 地按照圖靈機(jī)的方式執(zhí)行：對于每一個算法，首先去撥動一堆開關(guān)設(shè)置好，也就是計算機(jī)的“內(nèi)存”；然后啟動機(jī)器，等到停機(jī)時再讀取結(jié)果。

ENIAC 電子計算機(jī)

然而在 1946 年，就是 ENIAC 誕生的同一年，馮諾伊曼領(lǐng)悟到了 “通用計算機(jī)” 真正的意義，并發(fā)表了奠定現(xiàn)代計算機(jī)體系結(jié)構(gòu)和軟硬件生態(tài)的一篇論文：

馮諾伊曼關(guān)于電子計算機(jī)的論文，其中提到了 “存儲程序計算機(jī)” 和“通用計算機(jī)“的概念

馮諾伊曼想到，既然通用圖靈機(jī)，或者通用計算機(jī)可以模擬任意一個圖靈機(jī)，而每個圖靈機(jī)都可以執(zhí)行任意的算法，那么是不是意味著，我可以將所有的算法都放在同一個圖靈機(jī)里面，然后用另外一個算法，或者是操作員，去選擇我要具體執(zhí)行哪個算法？這樣一來，我就可以將所有的算法都預(yù)先準(zhǔn)備好，然后需要時直接選擇這個算法運(yùn)行就可以了，而不用像 ENIAC 一樣每次都要重新設(shè)置所有的開關(guān)。

馮諾伊曼的這種想法非常簡單，也許很多人在他之前就想到了。但是馮諾伊曼意識到這樣可以更進(jìn)一步：寫算法的人和機(jī)器的分離。我只要給機(jī)器寫一個說明書，告訴大家這臺機(jī)器所有支持的 “操作”（稱為“指令集”），以及每個指令對應(yīng)的符號編碼（稱為“機(jī)器碼”），這樣大家就只要用這些指令去描述算法（由于是圖靈機(jī)，必然可以用這些指令的組合描述所有的算法），然后把指令一個個翻譯成機(jī)器碼，刻錄到紙帶上。馮諾伊曼把這種紙帶上的內(nèi)容稱為“程序”。這些紙帶可以遠(yuǎn)程寄給計算機(jī)操作員，然后每次執(zhí)行前，就用另一個“轉(zhuǎn)錄” 程序把紙帶上的內(nèi)容寫到計算機(jī)的內(nèi)存里面，再用一個 “啟動” 程序去執(zhí)行這段程序，最后再用一個 “輸出” 程序把結(jié)果打印出來，寄回給原來寫程序的人。

馮諾伊曼稱這種這種通用計算機(jī)為“存儲程序計算機(jī)”，同時這種計算機(jī)的出現(xiàn)導(dǎo)致了一個新的職業(yè)的出現(xiàn)——程序員。有趣的是，最早的程序員更多的是女性，可能是當(dāng)時的人覺得女性更加耐心，而刻紙帶在固有印象中更像是“編織”。

0.4 在物理世界中制造通用計算機(jī)

如何將圖靈機(jī) / 通用計算機(jī)的數(shù)學(xué)概念變成一個真實(shí)的機(jī)器呢？對應(yīng)圖靈機(jī)的數(shù)學(xué)概念，我們需要狀態(tài)的集，符號的集合，列表和函數(shù)的物理實(shí)現(xiàn)。

馮諾伊曼等很快意識到，無論是狀態(tài)還是符號，在本質(zhì)上都是狀態(tài)。由于符號是有限的我們可以將每個符號一一映射到不同的狀態(tài)上。而符號的列表，只是把一堆狀態(tài)組合到一起罷了。

對狀態(tài)我們只有三個要求：

我們可以區(qū)分不同的狀態(tài)。

我們有足夠多的的狀態(tài)

如果我們知道具體的狀態(tài)，那么我們就可以將它改變?yōu)榱硗庖粋€具體的狀態(tài)。

現(xiàn)實(shí)中的物理狀態(tài)正好符合我們的要求——比如電壓的高和電壓的低就對應(yīng)了兩個狀態(tài)。因?yàn)樗鼈兊奈锢硖匦圆煌覀兛梢詤^(qū)分兩個狀態(tài)。同時我們有電子元件，可以在兩個狀態(tài)之間任意轉(zhuǎn)化。我們將兩個物理狀態(tài)稱為 0 和 1，這種基本單元也稱為“比特（bit）”

同時馮諾伊曼等人發(fā)現(xiàn)，只要最基本的 0 和 1，我們可以構(gòu)造出越來越多的狀態(tài)，而這些狀態(tài)依然滿足我們要求，而方法很簡單，就是將更多的 0 和 1 組合起來：比如 00，01，10，11 就是滿足我們要求的 4 個狀態(tài)，總之個比特就能夠表示個狀態(tài)。這樣要求 1 和 2 就滿足了。但是我們?nèi)绾慰刂七@么多狀態(tài)呢？

答案是 “組合邏輯” 這種技術(shù)。組合邏輯中，有一個特殊的 “元件” 叫 NAND 門（“門”這個詞出自于電路）。如果輸入狀態(tài)是 00，01，10，11，那么輸出就分別是 1，1，1，0。這也稱為 NAND 的真值表。此外還有一個沒什么存在感的東西：復(fù)制，也就是把輸入復(fù)制成任意多份，在電路中就是一根導(dǎo)線分成兩根。不要小看復(fù)制，這是一個非常重要的操作，我們在之后可以看到，在量子力學(xué)中，一般的復(fù)制竟然是禁止的，這導(dǎo)致了量子計算機(jī)和經(jīng)典計算機(jī)的重要差異。

NAND 門的真值表

然后組合邏輯的一個重要結(jié)論是：只要有 NAND，而且可以任意復(fù)制，那么我們可以實(shí)現(xiàn)任意多比特作為輸入的任意變換。這里舉一個簡單的例子：取反操作，也就是將 0 變成 1，將 1 變成 0。對于一個輸入 x，首先我們將它復(fù)制一份，然后將兩個 x 都輸入到 NAND 中，我就可以實(shí)現(xiàn)取反。通過 NAND 的真值表很容易驗(yàn)證這一點(diǎn)。

有了組合邏輯之后，給定一個圖靈機(jī)中的函數(shù)，我們就能實(shí)現(xiàn)它，無論它多么復(fù)雜。在硬件實(shí)現(xiàn)上，本質(zhì)上是利用物理模型的演化規(guī)則來控制物理狀態(tài)（比如晶體管是通過固體物理的一些原理，控制電路的電壓電流，從而控制每個比特的狀態(tài)是 0 還是 1）。

好了，我們終于搞定了狀態(tài)的問題，下面就容易多了：我們只要將圖靈機(jī)的各個部分變成各個部件，就能夠給出一個完整的設(shè)計圖了：

馮諾伊曼體系結(jié)構(gòu)

這個設(shè)計又稱為馮諾伊曼體系結(jié)構(gòu)。其中內(nèi)存單元（Memory Unit）對應(yīng)了圖靈機(jī)的 ， 每一個都對應(yīng)了獨(dú)立的一些比特；中央處理器（CPU，Central Processing Unit）對應(yīng)了狀態(tài) 和函數(shù)。又具體細(xì)化為改變的控制單元（Control Unit）和改變的計算 / 邏輯單元（Arithmetic/Logic Unit）；這些單元都可以由組合邏輯實(shí)現(xiàn)，而都是一些比特組成的。此外，為了實(shí)現(xiàn)馮諾伊曼“存儲程序計算機(jī)” 的想法，計算機(jī)需要輸入設(shè)備和輸出設(shè)備，這樣我們可以通過輸入設(shè)備將程序?qū)懭氲絻?nèi)存單元中，將結(jié)果從內(nèi)存單元輸出到輸出設(shè)備。

馮諾伊曼體系結(jié)構(gòu)奠定了現(xiàn)代計算機(jī)體系結(jié)構(gòu)的基礎(chǔ)，沿用至今。不過，當(dāng)今計算機(jī)做了一些優(yōu)化，比如說不再區(qū)分和，而且它們的數(shù)量有多個，稱為 “通用寄存器組”。而 所含的比特數(shù)，稱為計算機(jī)的“位數(shù)”，基于不同的的位數(shù)的程序 / 操作系統(tǒng)被稱為 xx 位程序 / xx 位操作系統(tǒng)（比如 32 位和 64 位程序）。此外，由于 memory 操作慢于邏輯和運(yùn)算，現(xiàn)代計算機(jī)中的“Memory Unit” 是分級的，CPU 擁有自己的容量更小，但是操作更快的 memory unit，稱為“緩存”（Cache），而在 CPU 之外有著一塊容量更大，但是操作更慢的 memory unit，這才是現(xiàn)在我們所指的“內(nèi)存”?，F(xiàn)代計算機(jī)中的優(yōu)化要比絕大多數(shù)人所想的復(fù)制的多，需要系統(tǒng)學(xué)習(xí)才能全部掌握，限于篇幅我不就不再繼續(xù)擴(kuò)展了。

0.5 物理狀態(tài)與通用計算機(jī)

在上一節(jié)中，我們大概了解了如何在物理世界中制造通用計算機(jī)。我們的途徑是：

在物理模型中找到一個基本的物理狀態(tài)。確保這個物理狀態(tài)可以通過組合產(chǎn)生任意大的狀態(tài)。

利用物理模型的演化規(guī)則來實(shí)現(xiàn)，從而可以控制狀態(tài)。

在電子計算機(jī)中，物理模型的演化規(guī)則是基于固體物理的，固體物理中研究了半導(dǎo)體等的能帶問題，本質(zhì)上還是基于量子力學(xué)；我們甚至可以說，現(xiàn)代電子計算機(jī)就是基于量子力學(xué)的，量子力學(xué)已經(jīng)給計算機(jī)帶來了巨大的革命。

那么，又是什么東西使得其他計算機(jī)機(jī)真正區(qū)別于 “電子計算機(jī)” 呢？答案是狀態(tài)！

電子計算機(jī)使用電壓表示狀態(tài)，用固體物理的性質(zhì)控制狀態(tài)。

生物計算機(jī)使用 DNA 和其他化學(xué)物質(zhì)表示狀態(tài)，用酶和其他化學(xué)物質(zhì)控制狀態(tài)。

光學(xué)計算機(jī)使用光的性質(zhì)表示狀態(tài)，用光學(xué)元件控制狀態(tài)。

量子計算機(jī)使用 “量子疊加態(tài)” 表示狀態(tài)，用固體物理 / 光學(xué)元件 / 光學(xué)共振腔等控制狀態(tài)。

生物計算機(jī)等的概念大家應(yīng)該很久前就聽過，但是為何現(xiàn)在主流的還是電子計算機(jī)？本質(zhì)上是因?yàn)樗鼈兊臓顟B(tài)并沒有給它們帶來根本性的優(yōu)勢，相比而言，電子計算機(jī)基于晶體管的設(shè)計倒是有極大的優(yōu)勢：

極高的內(nèi)部元件集成度。這意味著可以在極小的空間內(nèi)實(shí)現(xiàn)功能。這對硬件運(yùn)行速度有很大優(yōu)勢。現(xiàn)代電子元件的主頻可以達(dá)到 5GHz，也就是每秒鐘至少可以進(jìn)行 50 億次操作，即使按照真空中的光速，每次操作控制信號只能走 6 厘米，何況任何物理體系內(nèi)控制信號都無法始終以真空光速傳播，且整個路徑不一定是直線。其實(shí)在擁有 2 個 CPU 的高端服務(wù)器上已經(jīng)可以感受到光速的限制（這個例子并不確切，但是背后的原因是類似的）：由于內(nèi)存一般緊貼每個 CPU，所有對每個 CPU 而言，對方 CPU 的內(nèi)存要離自己更遠(yuǎn)一點(diǎn)；而離每個 CPU 較近的內(nèi)存訪問要比較遠(yuǎn)的內(nèi)存訪問更快，稱為 NUMA（非對稱內(nèi)存訪問），這是高性能計算軟件優(yōu)化的重點(diǎn)之一。

有 2 個 CPU 的高端服務(wù)器主板。可以看到每個 CPU 旁邊有緊貼有 4 個內(nèi)存槽。每個 CPU 訪問它旁邊的內(nèi)存，要快于訪問另一個 CPU 的內(nèi)存。

2. 極高的可擴(kuò)展性?；陔娦盘柡凸怆娹D(zhuǎn)換，電子計算機(jī)可以輕易組網(wǎng)?，F(xiàn)在全世界計算機(jī)都在互聯(lián)網(wǎng)上，已經(jīng)不足為奇了。對于高性能計算等領(lǐng)域，可以使用內(nèi)部的高速網(wǎng)絡(luò)將大量電子計算機(jī)互相連接起來，從而成倍地增加運(yùn)算速度，實(shí)現(xiàn)高效的并行計算，這類計算機(jī)也被稱為“超級計算機(jī)”。對于其他類型的計算機(jī)我們尚不知道怎么大規(guī)模擴(kuò)展。

3. 極高的穩(wěn)定性。從零下到接近 80 度，電子計算機(jī)都可以長期穩(wěn)定運(yùn)行。而且自從機(jī)械硬盤被替換為固態(tài)硬盤后，電子計算機(jī)內(nèi)除了散熱風(fēng)扇以外再也沒有活動的部件，因而抗震抗摔性能卓越，可以應(yīng)用到軍事或者衛(wèi)星等極端環(huán)境中?？梢哉f如果現(xiàn)在你摔一部手機(jī)，首先壞的是它的光學(xué)部分（屏幕，攝像頭），而不是它的電學(xué)部分。這些對生物計算機(jī)等是噩夢。

4. 電學(xué)狀態(tài)總體上是容易控制的。首先電學(xué)設(shè)備的能源很容易獲得和保存，生物計算機(jī)就要麻煩不少；其次電學(xué)設(shè)備的控制可以依賴電本身，而光學(xué)計算機(jī)中讓光控制光就很困難，因?yàn)榻^大多數(shù)情況下兩束光都會直接穿過對方，因此可能需要非線性晶體，而非線性晶體很難做到晶體管類似的控制精度；如果要通過干涉控制光，就需要相干光，而相干光的控制和維持比電路要復(fù)雜地多，而且光還存在衰減問題。至于生化反應(yīng)的控制。。。emmm，甚至有的時候還處于玄學(xué)范圍。

5. 電路甚至可以給自己編程。在制造 CPU 前，為了驗(yàn)證是否能夠正常工作，除了軟件仿真外，還會進(jìn)行硬件仿真。其中有種特殊設(shè)備叫 FPGA，就可以來更加精確地模擬硬件。FPGA 本身就是個電路，但是它支持向它寫入控制代碼，改變內(nèi)部電路在運(yùn)行時的“連接”，這是真正改變了內(nèi)部電路，而不是軟件模擬。最近微軟還有 Intel 等已經(jīng)將 FPGA 集成在主板還有網(wǎng)卡上，這樣一個軟件可以在運(yùn)行時向 FPGA 寫入控制碼，讓它成為一個專用硬件，從而大大提高處理效率。

既然如此，為何量子計算機(jī)那么受人重視呢？這是因?yàn)?，和生物計算機(jī)等不同，量子計算機(jī)使用量子疊加態(tài)作為狀態(tài)，在加速方面有根本性的提升。這甚至導(dǎo)致人們將所有不利用量子疊加態(tài)作為狀態(tài)的計算機(jī)都稱為“經(jīng)典計算機(jī)”，以區(qū)別于量子計算機(jī)。

在引入量子力學(xué)之前，我們先幻想一個更加簡單的物理學(xué)模型。通過這個物理學(xué)模型，我們會發(fā)現(xiàn)我們能夠制造更快的計算機(jī)。

第一章 量子計算機(jī)

1.1 在一個幻想的物理模型中制造計算機(jī)

在經(jīng)典計算機(jī)中，我們基于的狀態(tài)是 “經(jīng)典物理學(xué)” 的狀態(tài)，比如電壓，電流等等。這些 “經(jīng)典物理學(xué)” 的狀態(tài)有一個特點(diǎn)：它們都是用數(shù)字表示的。實(shí)際上，我們可以測量到的所有物理量或者物理狀態(tài)都是數(shù)字：長度，速度，質(zhì)量，能量，體積，輻射強(qiáng)度等等等等。但是你是否想過，會不會可觀察到的狀態(tài)只是真正的物理狀態(tài)的冰山一角？

這并不是我在說“有一條看不見摸不著的大龍在我的車庫里”，而是說有一些不能直接觀察到的東西，會導(dǎo)致不同的物理效應(yīng)。一個類似的例子是 X 射線：X 射線并不能被直接看到，但是不意味著它不存在，因?yàn)樗梢援a(chǎn)生讓膠卷感光這種物理效應(yīng)；不過確實(shí)因?yàn)?X 射線不能被直接看到，導(dǎo)致人們很久之后才發(fā)現(xiàn)它并研究它的規(guī)律。

同樣地，也許真正的物理狀態(tài)并不能被直接測量到，但是它的效應(yīng)是改變物理事件發(fā)生的概率，最終會改變你觀察到的狀態(tài)，甚至能展現(xiàn)出磁性，超導(dǎo)性等宏觀特性。這時候你觀察的工具就是“不斷制造相同的狀態(tài)，然后用統(tǒng)計學(xué)估計概率”。這實(shí)際上就是量子力學(xué)的核心所在。一個經(jīng)典的例子是單光子雙縫干涉（知乎上有非常多相關(guān)的內(nèi)容），通過不斷重復(fù)產(chǎn)生相同的狀態(tài)（一個通過雙縫的光子），你可以在對面屏幕上清楚地看到干涉條紋，這個條紋清晰地反應(yīng)了這些光子的狀態(tài)——如果你改變光的波長，或者雙縫的寬度，這些干涉條紋就會改變，因?yàn)楣庾拥臓顟B(tài)改變了。但是，你卻無法通過觀測某個光子來獲得它的狀態(tài)，如果你試圖單獨(dú)觀測每個光子，干涉條紋就會消失。然而，你卻不能因?yàn)橛^測單個光子，發(fā)現(xiàn)沒有觀測到“光子的狀態(tài)是同時從兩個縫中射出這種狀態(tài)”，而認(rèn)為這個狀態(tài)不存在，因?yàn)槟憧梢杂媒y(tǒng)計學(xué)方法確認(rèn)這種狀態(tài)改變了光子的分布。

特別在量子力學(xué)中，物理狀態(tài)被稱為“量子疊加態(tài)”，或者簡稱“量子態(tài)”。不過我首先不介紹更多的物理學(xué)概念，而是用一個類似但是更加簡單的幻想的物理狀態(tài)，來向讀者展示為啥不同的物理狀態(tài)會加速計算機(jī)執(zhí)行算法。

注意到我一直提的是 “加速”，而不是“超越” 經(jīng)典計算機(jī)。因?yàn)樵诶碚撚嬎銠C(jī)中，“超越”更偏向于指做到圖靈機(jī)做不到的事情，也就是解決一些原本即使給予圖靈機(jī)無限長的時間，無限大的內(nèi)存，也不可能解決的問題。這類模型稱為“超計算”。那么在現(xiàn)實(shí)物理世界中，是否可以實(shí)現(xiàn)超計算呢？目前的答案是否定的，因?yàn)槟壳耙阎某嬎愣家恍┳儜B(tài)的條件，比如將一個永遠(yuǎn)不會壞的無限大內(nèi)存的計算機(jī)扔到一個永遠(yuǎn)存在的蟲洞里面永遠(yuǎn)地進(jìn)行時間回溯，這樣計算機(jī)經(jīng)過的永恒的時間對于我們來說就是一瞬間，于是就有可能做到原來無法做到的事情。圖靈本人對超計算是否定的，他和邱奇有以下論題：

（大邱奇－圖靈論題）整個宇宙和一切物理過程都可以用圖靈機(jī)模擬。

所以按照這個理念，人屬于宇宙的一部分，那么人自然也可以被計算機(jī)模擬，那么計算機(jī)當(dāng)然可以擁有人的智能。所以圖靈后來提出 “人工智能” 這個概念，也不出意外。當(dāng)然這也成為了很多科幻小說和哲學(xué)問題的來源：我們這個宇宙本身會不會只是計算機(jī)的一個模擬？

好了，回到正題。下面是一個虛構(gòu)的物理模型：

這個物理模型中，物理狀態(tài)都是由向量而不是數(shù)表示。我們可以用固定的時間構(gòu)造任何我們想要的任何元素個數(shù)的向量。

這個物理模型中，你可以用固定時間構(gòu)造一個矩陣。這個世界遵循這樣的物理演化規(guī)則：你可以用這個矩陣乘這個向量得到一個新的向量，這個新的向量就是新的物理狀態(tài)。并且，這個操作用固定時間就可以完成（現(xiàn)實(shí)世界中需要和矩陣元素一樣多次乘法操作）。

首先我們證明利用這個物理模型構(gòu)造通用計算機(jī)，其運(yùn)行速度不會低于經(jīng)典計算機(jī)：

1、經(jīng)典計算機(jī)中的任意一個狀態(tài)，或者二進(jìn)制串，都可以對應(yīng)到一個向量：比如

這些都是正交的單位向量，且一個元素個數(shù)為的二進(jìn)制串對應(yīng)了一個元素個數(shù)為 的向量。有自然語言處理（NLP）經(jīng)驗(yàn)的應(yīng)該感到很熟悉，這其實(shí)就是 one-hot encoding。

2、經(jīng)典計算機(jī)中任意一個組合邏輯，都可以對應(yīng)到一個矩陣。這個很顯然，由于狀態(tài)都是單位基向量，所以只要往矩陣對應(yīng)的位置填上 1，就可以實(shí)現(xiàn)所有的功能。比如 NAND 對應(yīng)的矩陣： 。

由于只有右下角有一個 1，所以只有作為列向量相乘才會輸出。用類似的方法可以表示任何一個組合邏輯。

其次，我們證明這個計算機(jī)可以指數(shù)快的加速求解一類問題，比如單一結(jié)果的無結(jié)構(gòu)搜索問題，而經(jīng)典計算機(jī)做不到。單一結(jié)果的無結(jié)構(gòu)搜索問題的表述是：對于輸入，其中都是如同之前描述的單位正交向量，我們有一個算法，可以用固定的時間告訴我的結(jié)果是 0 還是 1。并且已知所有的中，有且只有一個 。求解的具體值。這個問題在現(xiàn)實(shí)中對應(yīng)的問題之一是密碼破解：對于固定長度的密碼，我們可以去一個個嘗試密碼是否正確，但是我們只知道只有一個密碼是正確的。對于經(jīng)典計算機(jī)，幾乎唯一的方法是一個個去試。假設(shè)密碼由個 bit 構(gòu)成，那么密碼的總數(shù)量就是，比如常用的 256 位 AES 密碼的總數(shù)量就有 115792089237316195423570985008687907853269984665640564039457584007913129639936 個，用經(jīng)典計算機(jī)去暴力破解是不可行的。但是注意到，我們這個利用虛擬物理構(gòu)建的計算機(jī)的輸入是向量，中間的規(guī)則是矩陣。首先我們定義函數(shù)然后我們就可以利用分配率來同時計算所有情況：

根據(jù)我們的物理模型，是可以常數(shù)時間構(gòu)造的，所以對于總數(shù)量的密碼，我們只要常數(shù)時間就可以破解，相對于經(jīng)典計算機(jī)平均需要次，快了指數(shù)倍。

1.2 利用量子態(tài)制造計算機(jī)

幸好上文的計算機(jī)是用我們宇宙不存在的物理模型制造的，否則任何密碼在一瞬間就會被破解了。不過，上文幻想的物理規(guī)律是去除了一些 “限制” 的量子力學(xué)，如果它發(fā)生在我們的宇宙中，會出現(xiàn)無數(shù)反常的情況，比如嚴(yán)重違背熱力學(xué)定律。這個模型實(shí)際上是 Scott Aaronson 于 2005 年提出的一個模型的簡化版本，原來的模型用于顯示只要對量子力學(xué)做輕微的修改，就能大大增強(qiáng)量子計算機(jī)的計算能力，不過這些修改只是存在理論中，與物理實(shí)驗(yàn)不符。

在量子力學(xué)的框架中，我們對之前的模型加入了以下約束（讀者沒有必要完全了解）：

物理狀態(tài)的約束：量子態(tài)向量的模長固定為 1。也就是只有向量的方向是重要的，你無法使用它的 “長度” 做任何計算。

狀態(tài)制備 / 初始狀態(tài)的約束：我們僅能夠使用步準(zhǔn)備一個元素個數(shù)為的 one-hot 量子態(tài)。這一般作為算法的最初輸入。one-hot 即整個向量中，只有一個系數(shù)是 1，其他均為 0。

演化的約束：從一個量子態(tài)到另一個量子態(tài)的演化對應(yīng)的矩陣必須是幺正的（幺正演化），不改變向量的模長。也就是唯一可以對向量進(jìn)行的操作是“旋轉(zhuǎn)”。所有的幺正演化都是可逆的矩陣。

讀出的約束：讀出結(jié)果只能通過 “觀測” 完成。根據(jù)量子力學(xué)的觀測公理，一個算法輸出的結(jié)果只能是一個 one-hot 量子態(tài)。得到某個 one-hot 量子態(tài)的概率為這個 one-hot 量子態(tài)在原來向量中的系數(shù)的平方（嚴(yán)格來說是模平方，因?yàn)橄禂?shù)可以是復(fù)數(shù)）。

在量子力學(xué)的限制下，我們利用量子態(tài)來構(gòu)造的計算機(jī)的加速能力也會相應(yīng)受到限制。比如說，上文的“單一結(jié)果的無結(jié)構(gòu)搜索問題”，量子計算機(jī)最多可以帶來平方的加速，也就是著名的 Grover 算法。Grover 算法顯示了量子計算機(jī)優(yōu)勢的同時，也被認(rèn)為顯示了量子計算機(jī)的局限性。所以量子計算機(jī)其實(shí)并不能像很多人想象一樣，輕松破解所有的密碼，AES 等加密方案面對量子計算機(jī)是安全的；不過之后我們會談到，RSA 等加密方案在未來可能因?yàn)榱孔佑嬎銠C(jī)變得不安全。

如果我們使用量子態(tài)為基礎(chǔ)去構(gòu)造圖靈機(jī)，用某個 “幺正演化” 構(gòu)造轉(zhuǎn)移函數(shù)，那么我們我們就實(shí)現(xiàn)了量子圖靈機(jī)，或者是量子通用計算機(jī)（和之前一樣，兩者主要是概念上的區(qū)別）。我們可以證明的是，不會有一種量子計算機(jī)，比量子圖靈機(jī) / 通用量子計算機(jī)更加“強(qiáng)大”，比如可以解決通用量子圖靈機(jī)不能解決的問題；此外通用量子計算機(jī)甚至可以高效模擬任何量子力學(xué)過程。量子通用計算機(jī)是一些量子算法的預(yù)設(shè)，但是我們離物理上實(shí)現(xiàn)它還差的很遠(yuǎn)。

1.3 量子門與實(shí)現(xiàn)量子圖靈機(jī)中的轉(zhuǎn)移函數(shù)（選讀）

在上文中，我們使用 “幺正演化” 構(gòu)造轉(zhuǎn)移函數(shù)，實(shí)現(xiàn)了量子圖靈機(jī)。但是在實(shí)現(xiàn)中， 可能是極其復(fù)雜的。在經(jīng)典計算機(jī)的例子中，我們知道我們可以把狀態(tài)分解為一串比特，而狀態(tài)的轉(zhuǎn)變可以用組合邏輯表示，任意組合邏輯又可以用 NAND 門和 “復(fù)制” 來實(shí)現(xiàn)。那么我們可否在量子力學(xué)中構(gòu)造類似的東西呢？

首先，量子力學(xué)中，一個 one-hot 量子態(tài)在物理上可以分解為一個個獨(dú)立的，只有 2 個基的向量，而它們可以有獨(dú)立的物理載體（比如每個對應(yīng)一個光子，或者超導(dǎo)約瑟夫森結(jié)，或者一個冷原子）。類比于經(jīng)典的比特，我們稱它們?yōu)椤傲孔颖忍亍?。作用在量子比特上的操作稱為“量子門”。

那么 “幺正演化” 是否可以由一些簡單的 “量子門” 來構(gòu)成呢？答案是無法用有限的量子門來組成任意的幺正演化，但是如果只要求是近似，是可以的。一般認(rèn)為 H，S，T，，CNOT 這幾個量子門就足夠了。其中 H，S，T，都是作用到一個量子比特上，而 CNOT 是唯一一個作用到兩個量子比特上的操作，也是現(xiàn)實(shí)中最難實(shí)現(xiàn)的操作。

此外量子線路的一個特殊操作是測量，根據(jù)量子力學(xué)的公設(shè)，（簡單地說）測量會導(dǎo)致量子態(tài)變成一個 one-hot encoding 的量子態(tài)，我們可以將這種量子態(tài)對應(yīng)到經(jīng)典的比特上，用于控制一些量子門（比如 1 對應(yīng)使用量子門，0 對應(yīng)不使用量子門）。下圖展示了一個典型的量子線路：

“量子隱形傳態(tài)”（quantum teleportation）的量子線路

由于任何一個量子線路都可以被通用量子計算機(jī)等效地執(zhí)行，而通用量子計算機(jī)依然離我們很遠(yuǎn)，所以很多量子算法都只是用量子線路來描述的，而這些算法在真正的物理實(shí)現(xiàn)上也是類似量子線路的形式。之前 Google 的超導(dǎo)量子計算機(jī)和現(xiàn)在的“九章”，都更接近量子線路（甚至它們比一般的量子線路都特殊得多），而不是通用量子計算機(jī)。當(dāng)我們能夠制造出一個類似 FPGA（上文提到過 FPGA）一樣的設(shè)備，可以任意編寫大規(guī)模（比如大于 100,000 個可靠的量子門）的量子線路時，我們離通用量子計算機(jī)就近了。

第二章 量子算法與應(yīng)用

這一章節(jié)中，我將反復(fù)使用的一個詞是 “fineprint（細(xì)小的條款）”。這也是一些量子計算研究者會用的詞，因?yàn)樵谟懻摿孔铀惴〞r，經(jīng)常有一些微妙的差別，從而導(dǎo)致完全不同的結(jié)果。

2.1 什么是量子算法

類似經(jīng)典算法，量子算法通過對量子狀態(tài)進(jìn)行一步步操作，進(jìn)而解決問題。然而，不同于經(jīng)典算法，量子算法的每一步，要不就是一個幺正操作，要不就是測量。這給編寫量子算法帶來了很大的困難。

編寫量子算法是非常困難的，原因主要有 4 個：

最直接的困難就是，不允許對未知的一個狀態(tài)進(jìn)行復(fù)制（比如說算法輸入的某個量子態(tài)，以及所有受到輸入影響的狀態(tài)；這里要順便指出量子圖靈機(jī)中的 “讀取” 和“寫入”也不是通過復(fù)制完成的，而是通過 “交換“或者” 觀測 “等量子力學(xué)允許的方式實(shí)現(xiàn)）。這是“量子不可克隆定理” 限定的，本質(zhì)上是幺正操作和測量無法復(fù)制未知的狀態(tài)。這讓很多經(jīng)典算法設(shè)計思想很難應(yīng)用到量子算法設(shè)計上。

如何利用量子態(tài)的性質(zhì)來加速也是一個問題，因?yàn)槿绻O(shè)計出來的算法沒有明顯超過經(jīng)典算法，那么在解決問題上是沒有意義的。如果使用經(jīng)典的算法設(shè)計思想，是很難造出超過經(jīng)典算法的量子算法的。

輸入輸出問題。如果輸入輸出是某個特定的 “量子態(tài)”，那么設(shè)計一些量子算法會變得相當(dāng)容易，但是現(xiàn)實(shí)世界無法去直接利用量子態(tài)（因?yàn)榱孔恿W(xué)根本上阻止我們直接觀測它們）。因此如何從經(jīng)典比特構(gòu)造出想要的“量子態(tài)”，以及如何保證最終將“量子態(tài)” 通過觀測變成想要的經(jīng)典比特，是一個大麻煩。

通用量子計算機(jī)出現(xiàn)前，相關(guān)領(lǐng)域缺乏研究動力。

綜上原因，目前已知的量子算法要遠(yuǎn)遠(yuǎn)少于經(jīng)典算法。

2.2 一個簡單但關(guān)鍵的量子算法：QFFT

在僅有的一些量子算法中，相當(dāng)多的算法（特別是遠(yuǎn)遠(yuǎn)優(yōu)于經(jīng)典算法的一些）的共同特點(diǎn)是使用了 QFFT （量子快速傅立葉變換）。這是 Shor 算法以及 HHL 算法的基礎(chǔ)。

快速傅立葉變換本身就是一個相當(dāng)重要的數(shù)值算法，它可以快速地分析出數(shù)據(jù)中的周期，在時域和頻域之間轉(zhuǎn)換，并可以加速卷積等操作。

快速傅立葉變換有 3 個重要特性導(dǎo)致它很容易擁有對應(yīng)的量子實(shí)現(xiàn)：

規(guī)模為的快速傅立葉變換可以被的矩陣乘法描述

快速傅立葉變換是可逆的，它的逆變換也是矩陣

快速傅立葉應(yīng)用于向量不會改變向量的模長

這 3 個重要特性讓人立刻意識到，快速傅立葉變換和逆變換都對應(yīng)量子力學(xué)中的幺正變換。然后，這個幺正變換可以用含有個量子門的量子線路描述！而我們只需要 個量子比特就可以構(gòu)成元素個數(shù)為的輸入向量。而經(jīng)典算法中，用電路對一個元素個數(shù)為 N 的向量進(jìn)行快速傅立葉變換，電路深度為，這意味著，量子算法對經(jīng)典算法在 FFT 上有指數(shù)加速。

不過不要高興得太早，這里有一個 fineprint（細(xì)小的條款）：量子算法中的 “向量” 是量子比特構(gòu)成的量子態(tài)，和用比特構(gòu)成的數(shù)值的向量是兩回事。也就是這個量子算法操作的對象是量子態(tài)對應(yīng)的向量的系數(shù)，因而只要個量子比特；而經(jīng)典算法中每一個系數(shù)都是都是實(shí)實(shí)在在的用比特表示的數(shù)字。也就是，根據(jù)量子力學(xué)的基本原理，我們沒有任何辦法，直接寫入或者讀取這些系數(shù)。而且我們甚至沒有已知有效方法將任何經(jīng)典算法中一個向量，轉(zhuǎn)變成量子態(tài)向量的系數(shù)，因而 QFFT 并不能加速 FFT。

QFFT 的輸出結(jié)果的幾乎唯一的一個用途，就是如果輸出的向量的系數(shù)中，有一個系數(shù)相對其他的系數(shù)特別大，那么我們對這個向量進(jìn)行觀測后，就會以很大概率獲得這個系數(shù)對應(yīng)的 one-hot encoding，而這個 one-hot encoding 直接對應(yīng)了一個經(jīng)典的比特串。但是，正是這個用途，讓很多算法得到了巨大的加速。

這些算法的共同特點(diǎn)是：1. 輸入的量子態(tài)比較容易構(gòu)造 2.輸入 QFFT 的向量中有一個明顯的“周期”，QFFT 變換到頻率領(lǐng)域后，對應(yīng)的頻率的系數(shù)很大，因而我們最終能以較大概率得知這個周期是什么。我們之后可以看到，這成為了 Shor 攻破 RSA 加密算法的關(guān)鍵（當(dāng)然前提是有一個可以跑 Shor 算法的量子計算機(jī)，就目前擁有的信息還早的很）。

2.2.1 最早讓量子計算機(jī)出名的算法：Shor 算法

Shor 算法顯示，量子計算機(jī)可以指數(shù)加速 “分解大質(zhì)因數(shù)” 這個問題，從而對 RSA 這種非對稱加密算法構(gòu)成威脅。在《夏日大作戰(zhàn)》中，主角讀了 Shor 算法后破解了 RSA 加密，造成了一次互聯(lián)網(wǎng)危機(jī)（其實(shí)人腦按照 Shor 算法去分解 21=3*7，可能比刷一整頁《吉米多維奇》的不定積分花的時間還要長）。

《夏日大作戰(zhàn)》中看的論文的標(biāo)題就是 Shor 算法

首先簡要介紹一下非對稱加密。非對稱加密是指一類加密和解密密鑰并不相同的加密算法，這兩個密鑰分別稱為 “公鑰” 和“私鑰”，且經(jīng)典計算機(jī)中根據(jù)公鑰計算出私鑰是困難的。非對稱加密可以做非常多對稱加密（用同一個密鑰加密解密）無法完成的事情，比如向任何一個人證明自己的身份（也就是私鑰的擁有者）：首先你向全世界公開你的身份 A，A 可以是一個虛擬身份，你的公鑰是 p。由于之前不存在一個是 A 的人，所以大家都知道 A 這個身份就和公鑰 p 綁定了。然后某次交易中，對方需要確認(rèn)你的身份是 A，對方可以用你公開的公鑰 p 加密一個隨機(jī)的無法猜出的文本，由于只有你擁有私鑰 q，所以只有你可以很快地解密內(nèi)容發(fā)送回去，這樣對方就知道你確實(shí)是 A。現(xiàn)實(shí)中的一個最常用的應(yīng)用就是網(wǎng)絡(luò)安全。如果網(wǎng)站的地址包括“https”，那么這個網(wǎng)站就實(shí)現(xiàn)了 SSL 協(xié)議，這個協(xié)議可以讓你驗(yàn)證這個網(wǎng)站是否是真實(shí)的：在 CA，操作系統(tǒng)以及瀏覽器的共同作用下，你本地存放有對應(yīng)的網(wǎng)址的公鑰，你就可以通過上述方法去驗(yàn)證這個網(wǎng)站的身份；如果有人通過攻擊改變了這個網(wǎng)址對應(yīng)的網(wǎng)站，比如說劫持居民的光纖，由于攻擊者沒有私鑰，你會發(fā)現(xiàn)對方無法證實(shí)身份，這樣就可以及時終止交易，避免泄露個人信息。注意到，對稱加密是無法解決這種問題的：你不能將可以解密的密鑰給用戶，因?yàn)檫@個是你的身份的“證明”，而對稱加密中，加密解密使用同樣一個密鑰，所以無法工作。

在上述協(xié)議中，如果有人可以用很小的代價從公鑰推導(dǎo)出私鑰，那么后果將是災(zāi)難性的。特別地，對于 RSA 這種非對稱加密算法，如果你有高效解決 “大質(zhì)因數(shù)分解” 問題的算法，就可以高效地從公鑰推導(dǎo)出私鑰。

Shor 算法就是一種高效的分解大質(zhì)因數(shù)的算法。大質(zhì)因數(shù)分解問題的陳述如下：

已知  ,  和  是兩個很大的質(zhì)因數(shù)。已知  ，求解  和  。

在數(shù)論中，我們有這樣一個問題：是待分解的一個大數(shù)。對于任何一個數(shù)，如果不是的因數(shù)（否則你就分解了），求解最小的正整數(shù)，使得(也就是 a 的 r 次方除以 N 余數(shù)是 1)。

通過數(shù)論可以證明如果解決了這個問題，就可以通過后續(xù)簡單的步驟解決分解大質(zhì)因數(shù)問題。

而很顯然：是待分解的一個大數(shù)。對于任何一個數(shù)，如果不是的因數(shù)（否則你就分解了），定義，的最小周期就是。這是因?yàn)?/p>

而我們怎么求周期呢？既然是周期函數(shù)，一個簡單的方法是對進(jìn)行傅立葉變換，找出周期對應(yīng)的頻率。可惜現(xiàn)實(shí)中 FFT 算法對于這個問題實(shí)在是太慢了，而且即使我們進(jìn)行了傅立葉變換，在這么大的范圍內(nèi)尋找周期，是不現(xiàn)實(shí)的。這個時候，我們的 QFFT 就有了用途了：首先構(gòu)造出一個量子態(tài)向量，這個向量編碼了對所有 的計算結(jié)果。然后我們用 QFFT 對向量進(jìn)行傅立葉分析，然后對輸出的向量進(jìn)行測量。由于傅立葉變換后周期對應(yīng)的頻率的 “系數(shù)” 比較大，那么量子測量后根據(jù)測量公設(shè)就會以很大概率得到周期對應(yīng)的單位基向量，且錯誤率是一個有限的常數(shù)。這意味著不斷重復(fù)這些步驟就可以以非常高的概率得到正確的周期，進(jìn)而最終分解 。

我們看到 Shor 算法成功的原因是根本原因是巧妙利用了周期特性，然后用 QFFT 求出周期。這個技巧可以用于構(gòu)造破解所有現(xiàn)在大量使用的非對稱加密算法，包括離散對數(shù)，橢圓曲線。由于這些算法都依賴于數(shù)論中的難題，因而都可以構(gòu)造出類似的周期，從而被破解。

那么是否所有的非對稱加密算法都可以被量子計算機(jī)破解呢？答案是否定的。Shor 算法在上個世紀(jì)公開以后，密碼學(xué)界就開始研究新的一類非對稱加密算法，稱為“后量子密碼學(xué)”，這些算法避開了數(shù)論難題，并基于格點(diǎn)，糾錯編碼，哈希函數(shù)等新的數(shù)學(xué)對象構(gòu)造數(shù)學(xué)難題。目前尚未發(fā)現(xiàn)有高效解決這些問題的量子算法。由于新的數(shù)學(xué)難題會稍微增加加密解密的計算量，所以在量子通用計算機(jī)出現(xiàn)之前，尚未有主流網(wǎng)站用后量子加密算法取代 RSA。

通用計算機(jī)量子計算機(jī)被認(rèn)為是必要的原因是，以目前的發(fā)展水平，實(shí)驗(yàn)中展示出的用 Shor 算法分解的最大的數(shù)是 21。而要破解現(xiàn)在通用的 RSA 算法，則需要分解一個大約 2048 位的數(shù)，也就是分解類似這樣的數(shù): 32317006071311007300714876688669951960444102669715484032130345427524655138867890893197201411522913463688717960921898019494119559150490921095088152386448283120630877367300996091750197750389652106796057638384067568276792218642619756161838094338476170470581645852036305042887575891541065808607552399123930385521914333389668342420684974786564569494856176035326322058077805659331026192708460314150258592864177116725943603718461857357598351152301645904403697613233287231227125684710820209725157101726931323469678542580656697935045997268352998638215525166389437335543602135433229604645318478604952148193555853611059596230655

2.3 量子和經(jīng)典算法的快慢，還是量子計算機(jī)和經(jīng)典計算機(jī)的快慢？我們究竟在比較什么？

在我們最初的討論中，我們是想比較量子計算和經(jīng)典計算機(jī)的快慢。但是讀者會發(fā)現(xiàn)，到這里時，似乎我們轉(zhuǎn)向了討論量子算法和經(jīng)典算法的快慢。這兩個東西是一樣的嗎？

首先，討論機(jī)器本身的快慢實(shí)際上沒有意義的，最終我們希望的是解決問題，因此比較的是“在經(jīng)典計算機(jī)上解決問題的（最優(yōu)）算法，和在量子計算機(jī)上解決同一個問題的（最優(yōu)）算法的快慢”，簡稱為“算法的快慢”。

為了消除歧義性，我們首先需要定義什么是算法的“快慢”。算法有實(shí)際上的快慢，也就是生活中我們運(yùn)行一個程序跑的時間，但是實(shí)際中的快慢是難以進(jìn)行理論分析的：它受到的影響很多，比如硬件的價格和工藝，軟件的編寫質(zhì)量，環(huán)境的溫度，甚至是是否在運(yùn)行過程中受到其他程序干擾。何況算法的目的是為了使用，我們往往在使用之前，甚至設(shè)計之前就需要知道它的快慢。

在這一章節(jié)中，我們希望理論分析算法的快慢，因?yàn)檫@才是對選用算法以及設(shè)計算法真正有用的東西。在理論分析中，算法的快慢定義為“圖靈機(jī)執(zhí)行的時間”，我們進(jìn)而約定經(jīng)典圖靈機(jī)和量子圖靈機(jī)執(zhí)行一步的時間都是固定的，因此時間其實(shí)對應(yīng)了圖靈機(jī)執(zhí)行的步數(shù)。在量子圖靈機(jī)的每一步中，都可以對整個量子態(tài)，也就是整個向量進(jìn)行操作，比如 QFFT 中的一個量子門；而經(jīng)典圖靈機(jī)卻做不到：如果將這種向量和矩陣的乘法作為經(jīng)典圖靈機(jī)的一個操作，那么這步操作的時間就沒有上限，因此不能稱為“固定時間的操作”，所以這不能作為經(jīng)典圖靈機(jī)的一個基本操作。這樣一來，經(jīng)典圖靈機(jī)中的算法就需要用更多步數(shù)實(shí)現(xiàn)向量和矩陣的乘法。因此，在有些算法中，量子圖靈機(jī)可以充分利用自己的優(yōu)勢，設(shè)計出執(zhí)行步數(shù)少得多的算法。所以在我們的理論分析中，解決同一個問題的最優(yōu)算法的快慢就反映了量子圖靈機(jī)和經(jīng)典圖靈機(jī)的相對優(yōu)勢：如果最優(yōu)的量子算法快于經(jīng)典算法，說明量子計算機(jī)本質(zhì)上支持用更快的算法解決相同的問題，這就是量子計算機(jī)的優(yōu)勢。

2.4 問題的分類游戲

然而，具體研究解決問題的算法時，我們發(fā)現(xiàn)大部分 “非平凡” 的問題會有一個參數(shù)，稱為輸入規(guī)模。比如快速傅立葉變換中的輸入規(guī)模就是輸入向量的元素個數(shù)，破解密碼的規(guī)模是密碼的長度。一般而言，規(guī)模和問題的輸入占用經(jīng)典計算機(jī)的比特數(shù)成正比。我們對算法進(jìn)行分析后，會發(fā)現(xiàn)某個問題的最優(yōu)算法的執(zhí)行步數(shù)是輸入規(guī)模數(shù)學(xué)表達(dá)式，比如快速傅立葉變換是 。算法分析中，我們關(guān)心的是某個問題的最優(yōu)算法的執(zhí)行時間隨著輸入規(guī)模 的變化趨勢，我們可以根據(jù)變化趨勢給問題分類，而我們將同一個類型的問題歸入同一個集合。

顯然，相同的問題，對于量子計算機(jī)和經(jīng)典計算機(jī)，可能有不同的分類，這意味著量子計算機(jī)和經(jīng)典計算機(jī)會將問題劃分為不同的集合（下面所有的算法都默認(rèn)是對應(yīng)問題的最優(yōu)算法）。

2.5 經(jīng)典計算機(jī)視角下的問題分類

首先，我們可以定義一個集合 P，集合 P 包涵了所有的一類經(jīng)典計算機(jī)的最優(yōu)算法能夠在輸入規(guī)模的多項(xiàng)式時間（算法時間的表達(dá)式是一個多項(xiàng)式，或者比多項(xiàng)式增長更慢的項(xiàng)，比如 logN 等）內(nèi)解決的問題。這類問題包括排序，快速傅立葉變換，求解兩地直接的最短路徑等等。P 內(nèi)部的問題在理論分析中被認(rèn)為是“容易的問題”。

另外我們可以定義一個集合 NP，集合 NP 包涵了所有的可以多項(xiàng)式內(nèi)驗(yàn)證結(jié)果的問題。顯然 P 是 NP 的子集，因?yàn)?P 問題可以通過再解一遍驗(yàn)證結(jié)果。如果 P 問題類似檢查數(shù)學(xué)證明，那么 NP 類似于給出證明。關(guān)于 P 和 NP 有一個非常著名的數(shù)學(xué)難題：

P ?= NP

雖然 P 是 NP 的子集，但是我們至今都沒有證明它是真子集。大多數(shù)理論計算機(jī)學(xué)家都相信 P 不等于 NP，一是因?yàn)?“驗(yàn)證答案的難度和寫出答案的難度一樣” 過于違背直覺，二是因?yàn)槿藗儼l(fā)現(xiàn)了一個 NP 的子集，稱為 NPC（NP-complete）。NPC 內(nèi)部的問題有這樣一個性質(zhì)：如果其中任何一個問題被證明屬于 P，那么 P = NP。NPC 內(nèi)部有非常多有趣的問題，比如邏輯滿足問題，定點(diǎn)著色問題，哈密頓回路問題，子圖同構(gòu)問題，但是若干年都沒有任何一個人發(fā)現(xiàn)多項(xiàng)式時間解決它們的算法（就像找不到黎曼猜想的反例一樣），這讓大家愈加相信 P != NP。

此外，非常有趣的一點(diǎn)是，相當(dāng)多和密碼學(xué)相關(guān)的問題都屬于 NP（RSA，離散對數(shù)，橢圓曲線），但是它們既不屬于 P，也不屬于 NPC。

如果我們更進(jìn)一步，如果問題詢問的是結(jié)果是 “真” 的結(jié)果的個數(shù)，且驗(yàn)證每一個結(jié)果所用的時間是多項(xiàng)式時間（相當(dāng)于對一個證明題，我不僅要求一個證明，還要求得到所有不多于某個字?jǐn)?shù)的所有的證明的個數(shù)），這些問題的集合稱為 #P。顯然 NP 是 #P 的一個子集，因?yàn)樗炼嘀挥幸粋€結(jié)果為真，我們只要解決這一個問題就可以了。

經(jīng)典算法中有一大類稱為“隨機(jī)算法”，這些算法的執(zhí)行有隨機(jī)性，不一定每次都能給出正確結(jié)果，但是正確的概率更大。所以只要通過多次執(zhí)行，我們就可以通過統(tǒng)計越來越清楚地知道哪個是正確的結(jié)果。其中一類問題的集合是 BPP (bounded-error probabilistic polynomial time) 。BPP 中的問題對應(yīng)的算法，每次執(zhí)行的時間是多項(xiàng)式的，結(jié)果錯誤率是一個低于 1/2 的常數(shù)，也就意味著我們總共只要多項(xiàng)式的時間就可以以很高的概率得到正確結(jié)果。典型的問題是判斷一個數(shù)是否是素數(shù)。此外集合 PP (probabilistic polynomial time) 不再限制錯誤率是一個低于 1/2 的常數(shù)，而是允許它隨著問題規(guī)模任意接近 1/2，所以其中可能有一些問題相當(dāng)難以解決。顯然 BPP 包含于 PP。

除了時間意外，我們可以用問題使用的內(nèi)存分類問題。以上所有問題都包括在 PSPACE 這個集合內(nèi)，因?yàn)榻鉀Q它們所消耗的內(nèi)存是規(guī)模的多項(xiàng)式倍；我們還可以考慮一個更大的集合，EXPSPACE，這個集合包括了消耗的內(nèi)存是規(guī)模的指數(shù)倍的問題，幾乎所有能夠想到的問題都存在于 EXPSPACE 中，否則問題的內(nèi)存消耗就能夠窮盡整個宇宙的物質(zhì)。

算法分類問題是名副其實(shí)的數(shù)學(xué)上最難的問題之一， P ?= NP 只是其中的問題之一，實(shí)際上我們不知道以下任何一對集合的是否相等（不過人們傾向于認(rèn)為它們之間都是真包含的），也就是有 15 個未解決的難題：

P ?= BPP ?= NP ?= #P ?= PP ?= PSPACE

2.6 量子計算機(jī)視角下的問題分類

由于量子計算機(jī)天生就有隨機(jī)性，所以量子計算機(jī)的問題分類結(jié)果主要是按照隨機(jī)算法，而量子計算機(jī)視角下對應(yīng)于經(jīng)典計算機(jī) BPP 定義的集合稱為 BQP(bounded-error quantum polynomial time)。

我們考慮所有問題的集合，畫出我們定義的這些集合的 Venn 圖（根據(jù)理論進(jìn)展，有些問題的復(fù)雜度類可能會發(fā)生改變）：

復(fù)雜度類的 Venn 圖

其中 BPP 集合內(nèi)部的問題，可以認(rèn)為是經(jīng)典計算機(jī)可以 “高效” 解決的問題，而 BQP 集合內(nèi)的問題，是量子計算機(jī)可以高效解決的問題。我們注意到兩點(diǎn)：1. BQP 集合內(nèi)包括比 BPP 更多的問題，這意味著有更多經(jīng)典計算機(jī)難以高效解決的問題，可以被量子計算機(jī)高效解決。2. BQP 沒有完整包括 NP，所以依然有大量有趣的問題無法被量子計算機(jī)高效解決，因此量子計算機(jī)并不是解決一切的“萬能工具”。

注：BQP 和 NP 兩者的具體關(guān)系還沒有解決，我們只知道有些 BQP 內(nèi)的問題不屬于 NP（也就是必然存在一些問題，量子計算機(jī)可以高效解決，經(jīng)典計算機(jī)不能高效解決）

但是 NP 是不是 BQP 的子集呢？這是一個未解決的問題，不過一般的看法是否定的。這是因?yàn)?1. 我們沒有發(fā)現(xiàn)任何一個 NPC 內(nèi)的問題屬于 BQP 2. “單一結(jié)果的無結(jié)構(gòu)搜索問題”是一個 NP 問題，但是量子計算機(jī)最多只能帶來平方的加速，也就是著名的 Grover 算法；而相當(dāng)多虛構(gòu)的可以高效解決任何 NP 問題的機(jī)器都可以指數(shù)加速這個問題（比如上文中的虛構(gòu)物理體系中），這可能暗示了量子計算機(jī)的局限性。

2.7 量子算法的物理實(shí)現(xiàn)難度和用途

首先，我們討論對于經(jīng)典計算機(jī)無法高效解決的問題，也就是在 P 之外的問題。

在上面的 Venn 圖中，我們發(fā)現(xiàn)根據(jù)量子算法相對經(jīng)典計算機(jī)的優(yōu)勢是各不相同的。但是我們結(jié)合它們的實(shí)現(xiàn)難度，以及用途來列一張表：

結(jié)合這個表格，下一步最有價值也最容易實(shí)現(xiàn)的還是量子體系的模擬，這也是已經(jīng)展示了量子霸權(quán)的各個量子計算團(tuán)隊(duì)下一步的重要目標(biāo)之一。

然后我們討論經(jīng)典計算機(jī)已經(jīng)可以高效解決的問題，也就是在 P 之內(nèi)的問題。

（請原諒我在下面的介紹中不使用算法復(fù)雜度標(biāo)記，因?yàn)槲矣X得沒有必要再介紹新的概念了）

是不是如果一個問題，經(jīng)典計算機(jī)已經(jīng)可以高效解決，那么就不需要量子計算機(jī)呢？這可不一定。算法理論中的“簡單，高效”，往往是指對于規(guī)模，可以在大約這種多項(xiàng)式時間內(nèi)解決的問題。當(dāng)比較大的時候，現(xiàn)實(shí)中已經(jīng)很難解決很大規(guī)模的問題；一個非常極端的例子是 AKS 素數(shù)測試算法，也就是一個判斷數(shù)是不是素數(shù)的算法，在最新的結(jié)果中，這個算法的（問題規(guī)模是素數(shù)的位數(shù)），在實(shí)際中很難運(yùn)用，所以實(shí)際中真正使用的反而是一些隨機(jī)算法，這些隨機(jī)算法雖然有微乎其微的概率錯判，但是要比 AKS 快的多。

這里我們討論一個非常有代表性的問題：線性方程組的解。我們知道，對于一個規(guī)模為 的稠密（大部分系數(shù)不是 0）的線性方程組，用經(jīng)典算法求解需要大約步；而對于稀疏（大部分系數(shù)是 0）的線性方程組，用經(jīng)典算法求解需要大約步，其中是矩陣的“條件數(shù)”(矩陣極大和極小特征值或者奇異值的比值)，是“稀疏度”。

對于稀疏矩陣而言，存在一個稱為 HHL 的算法（HHL 代表了 Arram Harrow, Avinatan Hassidim 和 Seth Lloyd 三人，發(fā)表于 2008 年），僅用（改進(jìn)版本），也就是大約步就可以解這個方程組。這相對于經(jīng)典算法的相對問題規(guī)模快了指數(shù)倍。

這個算法在當(dāng)時引起了轟動，因?yàn)榻饩€性方程組是一個非常非常重要的問題，幾乎用于各個領(lǐng)域。下面好幾年出現(xiàn)了一大堆“指數(shù)加速算法”，基本思想都是找一個經(jīng)典的依賴解線性方程組的問題，然后用 HHL 算法指數(shù)加速。這在 2014 年左右又大火了一波，因?yàn)榇蠹议_始對機(jī)器學(xué)習(xí)感興趣，而一大堆機(jī)器學(xué)習(xí)問題中都要解線性方程組。

2015 年，量子算法權(quán)威 Scott Aaronson 在 HHL 作者的幫助下，直接發(fā)了一篇 nature 評論 “Quantum Machine Learning Algorithms: Read the Fine Print“ 指出了很多人對 HHL 的“使用不當(dāng)”（有趣的是這篇評論的引用數(shù)占了原 HHL 的 1/5，考慮到發(fā)表時間已經(jīng)相當(dāng)多了）。那么 HHL 有哪些“fineprint” 呢？

和 QFFT 一樣，輸入的向量必須編碼到是量子態(tài)向量的系數(shù)上。如果向量最初是經(jīng)典計算機(jī)中的向量，那么顯然讀取數(shù)據(jù)就需要步（因?yàn)橄蛄勘旧碛?nbsp;個元素），這樣你就無法獲得加速優(yōu)勢。同樣的，矩陣本身的元素也不能全部來自經(jīng)典計算機(jī)的稀疏矩陣，否則讀取數(shù)據(jù)就會占用更多時間。所以大部分機(jī)器學(xué)習(xí)問題，除非人為構(gòu)造數(shù)據(jù)，否則很難直接用 HHL 加速。

矩陣必須是稀疏的，也就是遠(yuǎn)小于，否則主導(dǎo)運(yùn)行時間的就是，而不是，加速效果就會大打折扣。完全無視這一點(diǎn)的相關(guān)研究可以說幾乎是故意在騙人了。當(dāng)然，也有一個 HHL 的變種算法，可以加速稠密的線性方程組的求解，但是相對經(jīng)典算法并沒有指數(shù)加速。

輸入的稀疏矩陣必須是可逆的，而且數(shù)值特性良好，否則狀態(tài)數(shù)會很大，這樣也會失去加速。

這個算法的輸出和輸入一樣，也是編碼到量子態(tài)向量的系數(shù)上的，這意味著你沒有辦法直接將結(jié)果直接轉(zhuǎn)換成經(jīng)典的表示，比如導(dǎo)出成一個數(shù)組，打印到屏幕上。不過，你可以通過一些后續(xù)的算法研究這種輸出的一些性質(zhì)（雖然還是不能直接得到輸出）。

如果你的問題沒有上述任何一個困擾，那么恭喜你，你可以使用 HHL 來指數(shù)加速你的問題求解。

看到這些 fineprint，你可能會發(fā)現(xiàn) HHL 和之前的 QFFT 算法有一些相當(dāng)類似的“共性”，這是因?yàn)?HHL 本身就是依賴 QFFT 的。HHL 算法的例子說明了，指數(shù)加速一個經(jīng)典問題，有的時候并不是免費(fèi)的午餐，越大的加速往往就帶來了越多的對求解問題的限制（這也間接說明了量子計算機(jī)是有局限性的，不是萬能的機(jī)器）。

這一個例子進(jìn)一步展現(xiàn)了量子通用計算機(jī)的重要性：有相當(dāng)多的量子算法，可以對各類非常具體的經(jīng)典問題進(jìn)行一定的加速，但不是指數(shù)加速，因而在量子通用計算機(jī)研制出來之前，無法展現(xiàn)優(yōu)勢，其加速不及指數(shù)加速也導(dǎo)致它們難以像 Shor 算法，HHL 算法一樣有很高的宣傳熱度。也許最壞的情況是，等到通用量子計算機(jī)出現(xiàn)后，人們發(fā)現(xiàn)大部分實(shí)際問題在實(shí)際的條件下只能獲得平方加速，但是這并不意味著通用量子計算機(jī)的概念并不偉大——要知道比起平方加速，我們很多時候只是優(yōu)化常數(shù)。

? THE END

轉(zhuǎn)載請聯(lián)系本公眾號獲得授權(quán)

投稿或?qū)で髨蟮溃篶ontent@jiqizhixin.com

原標(biāo)題：《「九章」刷屏的背后：萬字長文解析，量子計算機(jī)和電子計算機(jī)各有何優(yōu)劣？》

閱讀原文