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

來(lái)源：知乎

作者：SIY.Z

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

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

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

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

此外這篇文章注定很長(zhǎng)。與其說(shuō)是讀一篇回答，不如說(shuō)是看一本歷史小說(shuō)。

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

0.1 什么是算法？

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

下面是一種更加簡(jiǎn)單，但是更加接近現(xiàn)代計(jì)算機(jī)的一種圖靈機(jī)構(gòu)造（而不是最初的 “紙帶” 版本），我們?cè)谥髸?huì)多次提到它：

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

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

所以最終問(wèn)題只剩下 4 個(gè)：

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

如何設(shè)計(jì)算法。

如何將算法變成一堆符號(hào)。

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

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

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

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

問(wèn)題 4 我們將在 0.4 節(jié)中說(shuō)明，并且我們還會(huì)引入量子計(jì)算的概念。

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

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

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

ENIAC 電子計(jì)算機(jī)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

NAND 門的真值表

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

有 2 個(gè) CPU 的高端服務(wù)器主板?？梢钥吹矫總€(gè) CPU 旁邊有緊貼有 4 個(gè)內(nèi)存槽。每個(gè) CPU 訪問(wèn)它旁邊的內(nèi)存，要快于訪問(wèn)另一個(gè) CPU 的內(nèi)存。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

如果我們使用量子態(tài)為基礎(chǔ)去構(gòu)造圖靈機(jī)，用某個(gè) “幺正演化” 構(gòu)造轉(zhuǎn)移函數(shù)，那么我們我們就實(shí)現(xiàn)了量子圖靈機(jī)，或者是量子通用計(jì)算機(jī)（和之前一樣，兩者主要是概念上的區(qū)別）。我們可以證明的是，不會(huì)有一種量子計(jì)算機(jī)，比量子圖靈機(jī) / 通用量子計(jì)算機(jī)更加“強(qiáng)大”，比如可以解決通用量子圖靈機(jī)不能解決的問(wèn)題；此外通用量子計(jì)算機(jī)甚至可以高效模擬任何量子力學(xué)過(guò)程。量子通用計(jì)算機(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ì)算機(jī)的例子中，我們知道我們可以把狀態(tài)分解為一串比特，而狀態(tài)的轉(zhuǎn)變可以用組合邏輯表示，任意組合邏輯又可以用 NAND 門和 “復(fù)制” 來(lái)實(shí)現(xiàn)。那么我們可否在量子力學(xué)中構(gòu)造類似的東西呢？

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

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

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

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

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

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

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

2.1 什么是量子算法

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

編寫(xiě)量子算法是非常困難的，原因主要有 4 個(gè)：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.4 問(wèn)題的分類游戲

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

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

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

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

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

P ?= NP

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

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

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

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

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

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

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

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

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

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

復(fù)雜度類的 Venn 圖

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

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

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

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

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

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

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

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

（請(qǐng)?jiān)徫以谙旅娴慕榻B中不使用算法復(fù)雜度標(biāo)記，因?yàn)槲矣X(jué)得沒(méi)有必要再介紹新的概念了）

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

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

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

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

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

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

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

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

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

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

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

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

? THE END

轉(zhuǎn)載請(qǐng)聯(lián)系本公眾號(hào)獲得授權(quán)

投稿或?qū)で髨?bào)道：content@jiqizhixin.com

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

閱讀原文