機器之心轉載
來源：知乎
作者：SIY.Z
12月4日，中國科學技術大學潘建偉研究團隊與中科院上海微系統所、國家並行計算機工程技術研究中心合作，成功構建了 76 個光子 100 個模式的高斯玻色取樣量子計算原型機「九章」，其處理特定問題的速度比目前最快的超級計算機「富嶽」快了一百萬億倍。相關論文登上了國際頂級期刊《Science》雜誌，引發學界、業界熱議。
近日，中科大校友、UC伯克利在讀博士、知乎用戶@SIY.Z 在一篇近兩萬字的長文中，詳細分析了「量子計算機和傳統電子計算機在算法方面的優劣勢」。以下是原文內容:
這是一篇我很早以前就想寫的文章。我的目的是給稍有數學等基礎的人，比較全面客觀地介紹量子計算和經典計算在算法上的優劣勢，而且會涉及到方方面面，可以說是一個大雜燴。我覺得我是有資格做這件事的，因為 1. 我本人就是計算機科班出身的，對計算機系統以及機器學習都有較為深刻的理解 2. 我本科參與過第一線的量子計算的研究 3. 我個人對多個學科都有涉獵，因此可以不至於錯的離譜地談論一些實際應用問題。但是哪怕僅僅接觸到最表面的一些問題，如果要解釋清楚，都要花費巨大的精力去解釋；此外，即使我寫了這樣一篇文章，可能也少有人關注，畢竟吧宣傳知識本身在知乎上可能已經過時了，渲染情緒要容易的多，而且可以天天輸出。所以說，我寫這篇文章，也是靠了 「九章」 量子計算機的熱度，這讓我稍微有動力一些。
算法研究是一個非常非常複雜艱深的領域，特別是我需要橫跨量子和經典兩大部分，而且涉及到的應用涵蓋了組合優化，密碼學，生物學，科學計算，理論計算機等各個領域，以個人水平很難涵蓋完整。而且考慮到受眾，我有必要模糊化和簡化一些概念，而只保證核心思想是正確的。因此如果過程中有差錯，請多多包涵。
此外這篇文章註定很長。與其說是讀一篇回答，不如說是看一本歷史小說。
第0章 算法和計算機
0.1 什麼是算法？
對於大部分日常問題，我們不需要算法，直接按照直覺去做就行了。然而對於一個稍微複雜的問題，它的解決方案就不是那麼簡單直接，往往需要一系列步驟。簡單來說，描述一個問題解決方案的步驟，就是算法。給定一個問題的算法，你就可以一步步的按照算法解決所有的類似的問題。其實生活中最明顯的算法的例子是說明書，它告訴你如何一步步地去按照說明書去完成一個功能，比如說如何安裝一個軟體，如何啟動一個電器，等等。
如果只是考慮到這一步，算法本身並沒有什麼魅力。其實在生活中算法往往被視作 「機械、死板」 的代名詞。為什麼？
人執行算法的能力是非常有限的。哪怕對於一個固定的算法，人也需要大量的練習才能熟練解決問題，而這個過程並不有趣，長年按照 「算法」 去組裝元件的流水線的工人應該深有體會。
人執行算法的準確性很低。比如 DIY 一個玩具，如果說明書只有 10 行，那麼大多數人還是很自信的；如果發現說明書竟然要 100 多步，那麼很多人組裝結束後，如果發現結果不對，會首先懷疑自己中間操作錯了。
記憶算法很困難。很多人玩過帶 「秘籍」 的魔方，可以按照說明書上的算法去慢慢還原魔方。但是一旦離開說明書，很多人就難以自己操作：這些算法需要一定的精力去記憶，而且熟練度很大程度上取決於記憶的難度。極其複雜的算法的對人來說首要挑戰是記憶，而不是操作。
算法描述的不精確性。說明書中的每一句話，因為自然語言本身的缺陷和場景的複雜性，都容易產生歧義。由說明書產生的困惑是人類共有的體驗。
由於以上這些問題，在歷史長河中，算法並不是科技和生產力的核心問題。雖然算法可能啟發來巴貝奇等人發明差分機，但是這並沒有扭轉歷史格局。直到 1936 年，一位英國的計算機學家，數學家，邏輯學家，密碼分析家兼理論生物學家，世界級長跑運動員在數學上證實了一個無比強大的機器的存在。在他生後，計算機科學的最高成就會以他的名字命名。
0.2 執行算法的終極機器——圖靈機
試想一下，在 100 年前，有人告訴你存在這樣一種機器：
這個機器非常簡單，至少是在數學模型的意義上。
這個機器的輸入的格式是有限的，這個機器可以執行的操作也是有限的。所以在現實中你可以用有限的零件製造它。
需要構成這個機器的基本操作都是非常簡單的，而且只需要固定的時間就可以完成。
這個機器是萬能的。只要你能夠用邏輯和數學描述一個算法，它就能自動執行它。
這個機器是通用的，它可以模擬任何一種計算機器，包括它本身。
沒有任何一種機器在使用算法解決問題上比它更加強大。如果一個問題它不能解決，那麼其他機器也一定不能解決。
你會相信這樣一種機器的存在嗎？
1936 年前後，阿蘭 · 圖靈（Alan Turing）構造式地證明了這樣一種機器的存在
下面是一種更加簡單，但是更加接近現代計算機的一種圖靈機構造（而不是最初的 「紙帶」 版本），我們在之後會多次提到它：
不過，阿蘭 · 圖靈發明這臺機器最初的動機並非來自於算法，而是為了解決邏輯學和數學問題，特別是數論公理化和數理邏輯等最根本的數學問題。當時和他在一個圈子裡面的人是希爾伯特，哥德爾，邱奇等人，因此整篇論文充滿了邏輯學的風格。這也讓圖靈機在最初並沒有很快走出圈外，為公眾所知。在二戰期間，圖靈將大部分精力投入到了破譯納粹的密碼中，並獲得了巨大成功。
然而，隨後人們發現，圖靈機並不僅僅是一個數學玩具，它是執行算法的最理想的萬能機器。我們來看圖靈機為何如此適合算法：上文中提到了人類自己執行算法的缺陷，其中人執行算法的能力和準確性問題並不適用於機器，機器不會疲勞，不會出錯，不會有負面情緒；而算法的記憶問題，在圖靈機中只要把算法轉換成一串符號，寫入到中就可以了，自然也沒有問題；而算法描述的不精確性也是不存在的，在圖靈機中算法就是一堆符號決定的，嚴格按照來執行，不存在不準確。
所以最終問題只剩下 4 個：
如何確定一個問題可以被圖靈機解決。
如何設計算法。
如何將算法變成一堆符號。
如何製造圖靈機一樣的機器。
其中對於 「可計算性」 問題的研究，回答了問題 1 中的一些重要問題。人們知道一些經典問題，比如「任意圖靈機的停機問題」，是不能被圖靈機解決的。
對於問題 2，算法設計也有了長足的發展，成為計算機科學的重要領域。本文中會繼續擴展這一段。圖靈機的出現改變了算法和機器的關係：從前人們希望為算法找到一個機器，而現在人們為了機器設計算法。
現代編譯原理，程序語言設計和軟體工程解決了問題 3。這部分仍然在不斷進步。
問題 4 我們將在 0.4 節中說明，並且我們還會引入量子計算的概念。
0.3 通用計算機——一樣的模型，不一樣的概念
圖靈機從數學模型到具體應用的道路上，一個重要的節點是 「通用計算機」 這種思維的興起。早在 1937 年，圖靈就意識到因為圖靈機的強大特性，一臺圖靈機可以同時模擬一臺甚至多臺圖靈機（現在最直接的應用就是虛擬機）。圖靈等將這種模型稱為「通用圖靈機」，或者「通用計算機」。但是當時人們只是把它當作一個有趣特性，並不是特別在意：畢竟模擬另外一臺圖靈機並不會加快解決問題的速度，只能做理論分析時用一用；而且它只是一種概念，在具體的實現上並不會和圖靈機有區別。
所以 1946 年製造的第一個電子計算機——ENIAC，仍然 「忠實」 地按照圖靈機的方式執行：對於每一個算法，首先去撥動一堆開關設置好，也就是計算機的「內存」；然後啟動機器，等到停機時再讀取結果。
ENIAC 電子計算機
然而在 1946 年，就是 ENIAC 誕生的同一年，馮諾伊曼領悟到了 「通用計算機」 真正的意義，並發表了奠定現代計算機體系結構和軟硬體生態的一篇論文：
馮諾伊曼關於電子計算機的論文，其中提到了 「存儲程序計算機」 和「通用計算機「的概念
馮諾伊曼想到，既然通用圖靈機，或者通用計算機可以模擬任意一個圖靈機，而每個圖靈機都可以執行任意的算法，那麼是不是意味著，我可以將所有的算法都放在同一個圖靈機裡面，然後用另外一個算法，或者是操作員，去選擇我要具體執行哪個算法？這樣一來，我就可以將所有的算法都預先準備好，然後需要時直接選擇這個算法運行就可以了，而不用像 ENIAC 一樣每次都要重新設置所有的開關。
馮諾伊曼的這種想法非常簡單，也許很多人在他之前就想到了。但是馮諾伊曼意識到這樣可以更進一步：寫算法的人和機器的分離。我只要給機器寫一個說明書，告訴大家這臺機器所有支持的 「操作」（稱為「指令集」），以及每個指令對應的符號編碼（稱為「機器碼」），這樣大家就只要用這些指令去描述算法（由於是圖靈機，必然可以用這些指令的組合描述所有的算法），然後把指令一個個翻譯成機器碼，刻錄到紙帶上。馮諾伊曼把這種紙帶上的內容稱為「程序」。這些紙帶可以遠程寄給計算機操作員，然後每次執行前，就用另一個「轉錄」 程序把紙帶上的內容寫到計算機的內存裡面，再用一個 「啟動」 程序去執行這段程序，最後再用一個 「輸出」 程序把結果列印出來，寄回給原來寫程序的人。
馮諾伊曼稱這種這種通用計算機為「存儲程序計算機」，同時這種計算機的出現導致了一個新的職業的出現——程式設計師。有趣的是，最早的程式設計師更多的是女性，可能是當時的人覺得女性更加耐心，而刻紙帶在固有印象中更像是「編織」。
0.4 在物理世界中製造通用計算機
如何將圖靈機 / 通用計算機的數學概念變成一個真實的機器呢？對應圖靈機的數學概念，我們需要狀態的集，符號的集合，列表和函數的物理實現。
馮諾伊曼等很快意識到，無論是狀態還是符號，在本質上都是狀態。由於符號是有限的我們可以將每個符號一一映射到不同的狀態上。而符號的列表，只是把一堆狀態組合到一起罷了。
對狀態我們只有三個要求：
我們可以區分不同的狀態。
我們有足夠多的的狀態
如果我們知道具體的狀態，那麼我們就可以將它改變為另外一個具體的狀態。
現實中的物理狀態正好符合我們的要求——比如電壓的高和電壓的低就對應了兩個狀態。因為它們的物理特性不同我們可以區分兩個狀態。同時我們有電子元件，可以在兩個狀態之間任意轉化。我們將兩個物理狀態稱為 0 和 1，這種基本單元也稱為「比特（bit）」
同時馮諾伊曼等人發現，只要最基本的 0 和 1，我們可以構造出越來越多的狀態，而這些狀態依然滿足我們要求，而方法很簡單，就是將更多的 0 和 1 組合起來：比如 00，01，10，11 就是滿足我們要求的 4 個狀態，總之個比特就能夠表示個狀態。這樣要求 1 和 2 就滿足了。但是我們如何控制這麼多狀態呢？
答案是 「組合邏輯」 這種技術。組合邏輯中，有一個特殊的 「元件」 叫 NAND 門（「門」這個詞出自於電路）。如果輸入狀態是 00，01，10，11，那麼輸出就分別是 1，1，1，0。這也稱為 NAND 的真值表。此外還有一個沒什麼存在感的東西：複製，也就是把輸入複製成任意多份，在電路中就是一根導線分成兩根。不要小看複製，這是一個非常重要的操作，我們在之後可以看到，在量子力學中，一般的複製竟然是禁止的，這導致了量子計算機和經典計算機的重要差異。
NAND 門的真值表
然後組合邏輯的一個重要結論是：只要有 NAND，而且可以任意複製，那麼我們可以實現任意多比特作為輸入的任意變換。這裡舉一個簡單的例子：取反操作，也就是將 0 變成 1，將 1 變成 0。對於一個輸入 x，首先我們將它複製一份，然後將兩個 x 都輸入到 NAND 中，我就可以實現取反。通過 NAND 的真值表很容易驗證這一點。
有了組合邏輯之後，給定一個圖靈機中的函數，我們就能實現它，無論它多麼複雜。在硬體實現上，本質上是利用物理模型的演化規則來控制物理狀態（比如電晶體是通過固體物理的一些原理，控制電路的電壓電流，從而控制每個比特的狀態是 0 還是 1）。
好了，我們終於搞定了狀態的問題，下面就容易多了：我們只要將圖靈機的各個部分變成各個部件，就能夠給出一個完整的設計圖了：
馮諾伊曼體系結構
這個設計又稱為馮諾伊曼體系結構。其中內存單元（Memory Unit）對應了圖靈機的 ， 每一個都對應了獨立的一些比特；中央處理器（CPU，Central Processing Unit）對應了狀態 和函數。又具體細化為改變的控制單元（Control Unit）和改變的計算 / 邏輯單元（Arithmetic/Logic Unit）；這些單元都可以由組合邏輯實現，而都是一些比特組成的。此外，為了實現馮諾伊曼「存儲程序計算機」 的想法，計算機需要輸入設備和輸出設備，這樣我們可以通過輸入設備將程序寫入到內存單元中，將結果從內存單元輸出到輸出設備。
馮諾伊曼體系結構奠定了現代計算機體系結構的基礎，沿用至今。不過，當今計算機做了一些優化，比如說不再區分和，而且它們的數量有多個，稱為 「通用寄存器組」。而 所含的比特數，稱為計算機的「位數」，基於不同的的位數的程序 / 作業系統被稱為 xx 位程序 / xx 位作業系統（比如 32 位和 64 位程序）。此外，由於 memory 操作慢於邏輯和運算，現代計算機中的「Memory Unit」 是分級的，CPU 擁有自己的容量更小，但是操作更快的 memory unit，稱為「緩存」（Cache），而在 CPU 之外有著一塊容量更大，但是操作更慢的 memory unit，這才是現在我們所指的「內存」。現代計算機中的優化要比絕大多數人所想的複製的多，需要系統學習才能全部掌握，限於篇幅我不就不再繼續擴展了。
0.5 物理狀態與通用計算機
在上一節中，我們大概了解了如何在物理世界中製造通用計算機。我們的途徑是：
在物理模型中找到一個基本的物理狀態。確保這個物理狀態可以通過組合產生任意大的狀態。
利用物理模型的演化規則來實現，從而可以控制狀態。
在電子計算機中，物理模型的演化規則是基於固體物理的，固體物理中研究了半導體等的能帶問題，本質上還是基於量子力學；我們甚至可以說，現代電子計算機就是基於量子力學的，量子力學已經給計算機帶來了巨大的革命。
那麼，又是什麼東西使得其他計算機機真正區別於 「電子計算機」 呢？答案是狀態！
電子計算機使用電壓表示狀態，用固體物理的性質控制狀態。
生物計算機使用 DNA 和其他化學物質表示狀態，用酶和其他化學物質控制狀態。
光學計算機使用光的性質表示狀態，用光學元件控制狀態。
量子計算機使用 「量子疊加態」 表示狀態，用固體物理 / 光學元件 / 光學共振腔等控制狀態。
生物計算機等的概念大家應該很久前就聽過，但是為何現在主流的還是電子計算機？本質上是因為它們的狀態並沒有給它們帶來根本性的優勢，相比而言，電子計算機基於電晶體的設計倒是有極大的優勢：
極高的內部元件集成度。這意味著可以在極小的空間內實現功能。這對硬體運行速度有很大優勢。現代電子元件的主頻可以達到 5GHz，也就是每秒鐘至少可以進行 50 億次操作，即使按照真空中的光速，每次操作控制信號只能走 6 釐米，何況任何物理體系內控制信號都無法始終以真空光速傳播，且整個路徑不一定是直線。其實在擁有 2 個 CPU 的高端伺服器上已經可以感受到光速的限制（這個例子並不確切，但是背後的原因是類似的）：由於內存一般緊貼每個 CPU，所有對每個 CPU 而言，對方 CPU 的內存要離自己更遠一點；而離每個 CPU 較近的內存訪問要比較遠的內存訪問更快，稱為 NUMA（非對稱內存訪問），這是高性能計算軟體優化的重點之一。
有 2 個 CPU 的高端伺服器主板。可以看到每個 CPU 旁邊有緊貼有 4 個內存槽。每個 CPU 訪問它旁邊的內存，要快於訪問另一個 CPU 的內存。
2. 極高的可擴展性。基於電信號和光電轉換，電子計算機可以輕易組網。現在全世界計算機都在網際網路上，已經不足為奇了。對於高性能計算等領域，可以使用內部的高速網絡將大量電子計算機互相連接起來，從而成倍地增加運算速度，實現高效的並行計算，這類計算機也被稱為「超級計算機」。對於其他類型的計算機我們尚不知道怎麼大規模擴展。
3. 極高的穩定性。從零下到接近 80 度，電子計算機都可以長期穩定運行。而且自從機械硬碟被替換為固態硬碟後，電子計算機內除了散熱風扇以外再也沒有活動的部件，因而抗震抗摔性能卓越，可以應用到軍事或者衛星等極端環境中。可以說如果現在你摔一部手機，首先壞的是它的光學部分（屏幕，攝像頭），而不是它的電學部分。這些對生物計算機等是噩夢。
4. 電學狀態總體上是容易控制的。首先電學設備的能源很容易獲得和保存，生物計算機就要麻煩不少；其次電學設備的控制可以依賴電本身，而光學計算機中讓光控制光就很困難，因為絕大多數情況下兩束光都會直接穿過對方，因此可能需要非線性晶體，而非線性晶體很難做到電晶體類似的控制精度；如果要通過幹涉控制光，就需要相干光，而相干光的控制和維持比電路要複雜地多，而且光還存在衰減問題。至於生化反應的控制。。。emmm，甚至有的時候還處於玄學範圍。
5. 電路甚至可以給自己編程。在製造 CPU 前，為了驗證是否能夠正常工作，除了軟體仿真外，還會進行硬體仿真。其中有種特殊設備叫 FPGA，就可以來更加精確地模擬硬體。FPGA 本身就是個電路，但是它支持向它寫入控制代碼，改變內部電路在運行時的「連接」，這是真正改變了內部電路，而不是軟體模擬。最近微軟還有 Intel 等已經將 FPGA 集成在主板還有網卡上，這樣一個軟體可以在運行時向 FPGA 寫入控制碼，讓它成為一個專用硬體，從而大大提高處理效率。
既然如此，為何量子計算機那麼受人重視呢？這是因為，和生物計算機等不同，量子計算機使用量子疊加態作為狀態，在加速方面有根本性的提升。這甚至導致人們將所有不利用量子疊加態作為狀態的計算機都稱為「經典計算機」，以區別於量子計算機。
在引入量子力學之前，我們先幻想一個更加簡單的物理學模型。通過這個物理學模型，我們會發現我們能夠製造更快的計算機。
第一章 量子計算機
1.1 在一個幻想的物理模型中製造計算機
在經典計算機中，我們基於的狀態是 「經典物理學」 的狀態，比如電壓，電流等等。這些 「經典物理學」 的狀態有一個特點：它們都是用數字表示的。實際上，我們可以測量到的所有物理量或者物理狀態都是數字：長度，速度，質量，能量，體積，輻射強度等等等等。但是你是否想過，會不會可觀察到的狀態只是真正的物理狀態的冰山一角？
這並不是我在說「有一條看不見摸不著的大龍在我的車庫裡」，而是說有一些不能直接觀察到的東西，會導致不同的物理效應。一個類似的例子是 X 射線：X 射線並不能被直接看到，但是不意味著它不存在，因為它可以產生讓膠捲感光這種物理效應；不過確實因為 X 射線不能被直接看到，導致人們很久之後才發現它並研究它的規律。
同樣地，也許真正的物理狀態並不能被直接測量到，但是它的效應是改變物理事件發生的概率，最終會改變你觀察到的狀態，甚至能展現出磁性，超導性等宏觀特性。這時候你觀察的工具就是「不斷製造相同的狀態，然後用統計學估計概率」。這實際上就是量子力學的核心所在。一個經典的例子是單光子雙縫幹涉（知乎上有非常多相關的內容），通過不斷重複產生相同的狀態（一個通過雙縫的光子），你可以在對面屏幕上清楚地看到幹涉條紋，這個條紋清晰地反應了這些光子的狀態——如果你改變光的波長，或者雙縫的寬度，這些幹涉條紋就會改變，因為光子的狀態改變了。但是，你卻無法通過觀測某個光子來獲得它的狀態，如果你試圖單獨觀測每個光子，幹涉條紋就會消失。然而，你卻不能因為觀測單個光子，發現沒有觀測到「光子的狀態是同時從兩個縫中射出這種狀態」，而認為這個狀態不存在，因為你可以用統計學方法確認這種狀態改變了光子的分布。
特別在量子力學中，物理狀態被稱為「量子疊加態」，或者簡稱「量子態」。不過我首先不介紹更多的物理學概念，而是用一個類似但是更加簡單的幻想的物理狀態，來向讀者展示為啥不同的物理狀態會加速計算機執行算法。
注意到我一直提的是 「加速」，而不是「超越」 經典計算機。因為在理論計算機中，「超越」更偏向於指做到圖靈機做不到的事情，也就是解決一些原本即使給予圖靈機無限長的時間，無限大的內存，也不可能解決的問題。這類模型稱為「超計算」。那麼在現實物理世界中，是否可以實現超計算呢？目前的答案是否定的，因為目前已知的超計算都要一些變態的條件，比如將一個永遠不會壞的無限大內存的計算機扔到一個永遠存在的蟲洞裡面永遠地進行時間回溯，這樣計算機經過的永恆的時間對於我們來說就是一瞬間，於是就有可能做到原來無法做到的事情。圖靈本人對超計算是否定的，他和邱奇有以下論題：
（大邱奇－圖靈論題）整個宇宙和一切物理過程都可以用圖靈機模擬。
所以按照這個理念，人屬於宇宙的一部分，那麼人自然也可以被計算機模擬，那麼計算機當然可以擁有人的智能。所以圖靈後來提出 「人工智慧」 這個概念，也不出意外。當然這也成為了很多科幻小說和哲學問題的來源：我們這個宇宙本身會不會只是計算機的一個模擬？
好了，回到正題。下面是一個虛構的物理模型：
這個物理模型中，物理狀態都是由向量而不是數表示。我們可以用固定的時間構造任何我們想要的任何元素個數的向量。
這個物理模型中，你可以用固定時間構造一個矩陣。這個世界遵循這樣的物理演化規則：你可以用這個矩陣乘這個向量得到一個新的向量，這個新的向量就是新的物理狀態。並且，這個操作用固定時間就可以完成（現實世界中需要和矩陣元素一樣多次乘法操作）。
首先我們證明利用這個物理模型構造通用計算機，其運行速度不會低於經典計算機：
1、經典計算機中的任意一個狀態，或者二進位串，都可以對應到一個向量：比如
這些都是正交的單位向量，且一個元素個數為的二進位串對應了一個元素個數為 的向量。有自然語言處理（NLP）經驗的應該感到很熟悉，這其實就是 one-hot encoding。
2、經典計算機中任意一個組合邏輯，都可以對應到一個矩陣。這個很顯然，由於狀態都是單位基向量，所以只要往矩陣對應的位置填上 1，就可以實現所有的功能。比如 NAND 對應的矩陣： 。
由於只有右下角有一個 1，所以只有作為列向量相乘才會輸出。用類似的方法可以表示任何一個組合邏輯。
其次，我們證明這個計算機可以指數快的加速求解一類問題，比如單一結果的無結構搜索問題，而經典計算機做不到。單一結果的無結構搜索問題的表述是：對於輸入，其中都是如同之前描述的單位正交向量，我們有一個算法，可以用固定的時間告訴我的結果是 0 還是 1。並且已知所有的中，有且只有一個 。求解的具體值。這個問題在現實中對應的問題之一是密碼破解：對於固定長度的密碼，我們可以去一個個嘗試密碼是否正確，但是我們只知道只有一個密碼是正確的。對於經典計算機，幾乎唯一的方法是一個個去試。假設密碼由個 bit 構成，那麼密碼的總數量就是，比如常用的 256 位 AES 密碼的總數量就有 115792089237316195423570985008687907853269984665640564039457584007913129639936 個，用經典計算機去暴力破解是不可行的。但是注意到，我們這個利用虛擬物理構建的計算機的輸入是向量，中間的規則是矩陣。首先我們定義函數然後我們就可以利用分配率來同時計算所有情況：
根據我們的物理模型，是可以常數時間構造的，所以對於總數量的密碼，我們只要常數時間就可以破解，相對於經典計算機平均需要次，快了指數倍。
1.2 利用量子態製造計算機
幸好上文的計算機是用我們宇宙不存在的物理模型製造的，否則任何密碼在一瞬間就會被破解了。不過，上文幻想的物理規律是去除了一些 「限制」 的量子力學，如果它發生在我們的宇宙中，會出現無數反常的情況，比如嚴重違背熱力學定律。這個模型實際上是 Scott Aaronson 於 2005 年提出的一個模型的簡化版本，原來的模型用於顯示只要對量子力學做輕微的修改，就能大大增強量子計算機的計算能力，不過這些修改只是存在理論中，與物理實驗不符。
在量子力學的框架中，我們對之前的模型加入了以下約束（讀者沒有必要完全了解）：
物理狀態的約束：量子態向量的模長固定為 1。也就是只有向量的方向是重要的，你無法使用它的 「長度」 做任何計算。
狀態製備 / 初始狀態的約束：我們僅能夠使用步準備一個元素個數為的 one-hot 量子態。這一般作為算法的最初輸入。one-hot 即整個向量中，只有一個係數是 1，其他均為 0。
演化的約束：從一個量子態到另一個量子態的演化對應的矩陣必須是么正的（么正演化），不改變向量的模長。也就是唯一可以對向量進行的操作是「旋轉」。所有的么正演化都是可逆的矩陣。
讀出的約束：讀出結果只能通過 「觀測」 完成。根據量子力學的觀測公理，一個算法輸出的結果只能是一個 one-hot 量子態。得到某個 one-hot 量子態的概率為這個 one-hot 量子態在原來向量中的係數的平方（嚴格來說是模平方，因為係數可以是複數）。
在量子力學的限制下，我們利用量子態來構造的計算機的加速能力也會相應受到限制。比如說，上文的「單一結果的無結構搜索問題」，量子計算機最多可以帶來平方的加速，也就是著名的 Grover 算法。Grover 算法顯示了量子計算機優勢的同時，也被認為顯示了量子計算機的局限性。所以量子計算機其實並不能像很多人想像一樣，輕鬆破解所有的密碼，AES 等加密方案面對量子計算機是安全的；不過之後我們會談到，RSA 等加密方案在未來可能因為量子計算機變得不安全。
如果我們使用量子態為基礎去構造圖靈機，用某個 「么正演化」 構造轉移函數，那麼我們我們就實現了量子圖靈機，或者是量子通用計算機（和之前一樣，兩者主要是概念上的區別）。我們可以證明的是，不會有一種量子計算機，比量子圖靈機 / 通用量子計算機更加「強大」，比如可以解決通用量子圖靈機不能解決的問題；此外通用量子計算機甚至可以高效模擬任何量子力學過程。量子通用計算機是一些量子算法的預設，但是我們離物理上實現它還差的很遠。
1.3 量子門與實現量子圖靈機中的轉移函數（選讀）
在上文中，我們使用 「么正演化」 構造轉移函數，實現了量子圖靈機。但是在實現中， 可能是極其複雜的。在經典計算機的例子中，我們知道我們可以把狀態分解為一串比特，而狀態的轉變可以用組合邏輯表示，任意組合邏輯又可以用 NAND 門和 「複製」 來實現。那麼我們可否在量子力學中構造類似的東西呢？
首先，量子力學中，一個 one-hot 量子態在物理上可以分解為一個個獨立的，只有 2 個基的向量，而它們可以有獨立的物理載體（比如每個對應一個光子，或者超導約瑟夫森結，或者一個冷原子）。類比於經典的比特，我們稱它們為「量子比特」。作用在量子比特上的操作稱為「量子門」。
那麼 「么正演化」 是否可以由一些簡單的 「量子門」 來構成呢？答案是無法用有限的量子門來組成任意的么正演化，但是如果只要求是近似，是可以的。一般認為 H，S，T，，CNOT 這幾個量子門就足夠了。其中 H，S，T，都是作用到一個量子比特上，而 CNOT 是唯一一個作用到兩個量子比特上的操作，也是現實中最難實現的操作。
此外量子線路的一個特殊操作是測量，根據量子力學的公設，（簡單地說）測量會導致量子態變成一個 one-hot encoding 的量子態，我們可以將這種量子態對應到經典的比特上，用於控制一些量子門（比如 1 對應使用量子門，0 對應不使用量子門）。下圖展示了一個典型的量子線路：
「量子隱形傳態」（quantum teleportation）的量子線路
由於任何一個量子線路都可以被通用量子計算機等效地執行，而通用量子計算機依然離我們很遠，所以很多量子算法都只是用量子線路來描述的，而這些算法在真正的物理實現上也是類似量子線路的形式。之前 Google 的超導量子計算機和現在的「九章」，都更接近量子線路（甚至它們比一般的量子線路都特殊得多），而不是通用量子計算機。當我們能夠製造出一個類似 FPGA（上文提到過 FPGA）一樣的設備，可以任意編寫大規模（比如大於 100,000 個可靠的量子門）的量子線路時，我們離通用量子計算機就近了。
第二章 量子算法與應用
這一章節中，我將反覆使用的一個詞是 「fineprint（細小的條款）」。這也是一些量子計算研究者會用的詞，因為在討論量子算法時，經常有一些微妙的差別，從而導致完全不同的結果。
2.1 什麼是量子算法
類似經典算法，量子算法通過對量子狀態進行一步步操作，進而解決問題。然而，不同於經典算法，量子算法的每一步，要不就是一個么正操作，要不就是測量。這給編寫量子算法帶來了很大的困難。
編寫量子算法是非常困難的，原因主要有 4 個：
最直接的困難就是，不允許對未知的一個狀態進行複製（比如說算法輸入的某個量子態，以及所有受到輸入影響的狀態；這裡要順便指出量子圖靈機中的 「讀取」 和「寫入」也不是通過複製完成的，而是通過 「交換「或者」 觀測 「等量子力學允許的方式實現）。這是「量子不可克隆定理」 限定的，本質上是么正操作和測量無法複製未知的狀態。這讓很多經典算法設計思想很難應用到量子算法設計上。
如何利用量子態的性質來加速也是一個問題，因為如果設計出來的算法沒有明顯超過經典算法，那麼在解決問題上是沒有意義的。如果使用經典的算法設計思想，是很難造出超過經典算法的量子算法的。
輸入輸出問題。如果輸入輸出是某個特定的 「量子態」，那麼設計一些量子算法會變得相當容易，但是現實世界無法去直接利用量子態（因為量子力學根本上阻止我們直接觀測它們）。因此如何從經典比特構造出想要的「量子態」，以及如何保證最終將「量子態」 通過觀測變成想要的經典比特，是一個大麻煩。
通用量子計算機出現前，相關領域缺乏研究動力。
綜上原因，目前已知的量子算法要遠遠少於經典算法。
2.2 一個簡單但關鍵的量子算法：QFFT
在僅有的一些量子算法中，相當多的算法（特別是遠遠優於經典算法的一些）的共同特點是使用了 QFFT （量子快速傅立葉變換）。這是 Shor 算法以及 HHL 算法的基礎。
快速傅立葉變換本身就是一個相當重要的數值算法，它可以快速地分析出數據中的周期，在時域和頻域之間轉換，並可以加速卷積等操作。
快速傅立葉變換有 3 個重要特性導致它很容易擁有對應的量子實現：
規模為的快速傅立葉變換可以被的矩陣乘法描述
快速傅立葉變換是可逆的，它的逆變換也是矩陣
快速傅立葉應用於向量不會改變向量的模長
這 3 個重要特性讓人立刻意識到，快速傅立葉變換和逆變換都對應量子力學中的么正變換。然後，這個么正變換可以用含有個量子門的量子線路描述！而我們只需要 個量子比特就可以構成元素個數為的輸入向量。而經典算法中，用電路對一個元素個數為 N 的向量進行快速傅立葉變換，電路深度為，這意味著，量子算法對經典算法在 FFT 上有指數加速。
不過不要高興得太早，這裡有一個 fineprint（細小的條款）：量子算法中的 「向量」 是量子比特構成的量子態，和用比特構成的數值的向量是兩回事。也就是這個量子算法操作的對象是量子態對應的向量的係數，因而只要個量子比特；而經典算法中每一個係數都是都是實實在在的用比特表示的數字。也就是，根據量子力學的基本原理，我們沒有任何辦法，直接寫入或者讀取這些係數。而且我們甚至沒有已知有效方法將任何經典算法中一個向量，轉變成量子態向量的係數，因而 QFFT 並不能加速 FFT。
QFFT 的輸出結果的幾乎唯一的一個用途，就是如果輸出的向量的係數中，有一個係數相對其他的係數特別大，那麼我們對這個向量進行觀測後，就會以很大概率獲得這個係數對應的 one-hot encoding，而這個 one-hot encoding 直接對應了一個經典的比特串。但是，正是這個用途，讓很多算法得到了巨大的加速。
這些算法的共同特點是：1. 輸入的量子態比較容易構造 2.輸入 QFFT 的向量中有一個明顯的「周期」，QFFT 變換到頻率領域後，對應的頻率的係數很大，因而我們最終能以較大概率得知這個周期是什麼。我們之後可以看到，這成為了 Shor 攻破 RSA 加密算法的關鍵（當然前提是有一個可以跑 Shor 算法的量子計算機，就目前擁有的信息還早的很）。
2.2.1 最早讓量子計算機出名的算法：Shor 算法
Shor 算法顯示，量子計算機可以指數加速 「分解大質因數」 這個問題，從而對 RSA 這種非對稱加密算法構成威脅。在《夏日大作戰》中，主角讀了 Shor 算法後破解了 RSA 加密，造成了一次網際網路危機（其實人腦按照 Shor 算法去分解 21=3*7，可能比刷一整頁《吉米多維奇》的不定積分花的時間還要長）。
《夏日大作戰》中看的論文的標題就是 Shor 算法
首先簡要介紹一下非對稱加密。非對稱加密是指一類加密和解密密鑰並不相同的加密算法，這兩個密鑰分別稱為 「公鑰」 和「私鑰」，且經典計算機中根據公鑰計算出私鑰是困難的。非對稱加密可以做非常多對稱加密（用同一個密鑰加密解密）無法完成的事情，比如向任何一個人證明自己的身份（也就是私鑰的擁有者）：首先你向全世界公開你的身份 A，A 可以是一個虛擬身份，你的公鑰是 p。由於之前不存在一個是 A 的人，所以大家都知道 A 這個身份就和公鑰 p 綁定了。然後某次交易中，對方需要確認你的身份是 A，對方可以用你公開的公鑰 p 加密一個隨機的無法猜出的文本，由於只有你擁有私鑰 q，所以只有你可以很快地解密內容發送回去，這樣對方就知道你確實是 A。現實中的一個最常用的應用就是網絡安全。如果網站的地址包括「https」，那麼這個網站就實現了 SSL 協議，這個協議可以讓你驗證這個網站是否是真實的：在 CA，作業系統以及瀏覽器的共同作用下，你本地存放有對應的網址的公鑰，你就可以通過上述方法去驗證這個網站的身份；如果有人通過攻擊改變了這個網址對應的網站，比如說劫持居民的光纖，由於攻擊者沒有私鑰，你會發現對方無法證實身份，這樣就可以及時終止交易，避免洩露個人信息。注意到，對稱加密是無法解決這種問題的：你不能將可以解密的密鑰給用戶，因為這個是你的身份的「證明」，而對稱加密中，加密解密使用同樣一個密鑰，所以無法工作。
在上述協議中，如果有人可以用很小的代價從公鑰推導出私鑰，那麼後果將是災難性的。特別地，對於 RSA 這種非對稱加密算法，如果你有高效解決 「大質因數分解」 問題的算法，就可以高效地從公鑰推導出私鑰。
Shor 算法就是一種高效的分解大質因數的算法。大質因數分解問題的陳述如下：
已知 , 和 是兩個很大的質因數。已知 ，求解 和 。
在數論中，我們有這樣一個問題：是待分解的一個大數。對於任何一個數，如果不是的因數（否則你就分解了），求解最小的正整數，使得(也就是 a 的 r 次方除以 N 餘數是 1)。
通過數論可以證明如果解決了這個問題，就可以通過後續簡單的步驟解決分解大質因數問題。
而很顯然：是待分解的一個大數。對於任何一個數，如果不是的因數（否則你就分解了），定義，的最小周期就是。這是因為
而我們怎麼求周期呢？既然是周期函數，一個簡單的方法是對進行傅立葉變換，找出周期對應的頻率。可惜現實中 FFT 算法對於這個問題實在是太慢了，而且即使我們進行了傅立葉變換，在這麼大的範圍內尋找周期，是不現實的。這個時候，我們的 QFFT 就有了用途了：首先構造出一個量子態向量，這個向量編碼了對所有 的計算結果。然後我們用 QFFT 對向量進行傅立葉分析，然後對輸出的向量進行測量。由於傅立葉變換後周期對應的頻率的 「係數」 比較大，那麼量子測量後根據測量公設就會以很大概率得到周期對應的單位基向量，且錯誤率是一個有限的常數。這意味著不斷重複這些步驟就可以以非常高的概率得到正確的周期，進而最終分解 。
我們看到 Shor 算法成功的原因是根本原因是巧妙利用了周期特性，然後用 QFFT 求出周期。這個技巧可以用於構造破解所有現在大量使用的非對稱加密算法，包括離散對數，橢圓曲線。由於這些算法都依賴於數論中的難題，因而都可以構造出類似的周期，從而被破解。
那麼是否所有的非對稱加密算法都可以被量子計算機破解呢？答案是否定的。Shor 算法在上個世紀公開以後，密碼學界就開始研究新的一類非對稱加密算法，稱為「後量子密碼學」，這些算法避開了數論難題，並基于格點，糾錯編碼，哈希函數等新的數學對象構造數學難題。目前尚未發現有高效解決這些問題的量子算法。由於新的數學難題會稍微增加加密解密的計算量，所以在量子通用計算機出現之前，尚未有主流網站用後量子加密算法取代 RSA。
通用計算機量子計算機被認為是必要的原因是，以目前的發展水平，實驗中展示出的用 Shor 算法分解的最大的數是 21。而要破解現在通用的 RSA 算法，則需要分解一個大約 2048 位的數，也就是分解類似這樣的數: 32317006071311007300714876688669951960444102669715484032130345427524655138867890893197201411522913463688717960921898019494119559150490921095088152386448283120630877367300996091750197750389652106796057638384067568276792218642619756161838094338476170470581645852036305042887575891541065808607552399123930385521914333389668342420684974786564569494856176035326322058077805659331026192708460314150258592864177116725943603718461857357598351152301645904403697613233287231227125684710820209725157101726931323469678542580656697935045997268352998638215525166389437335543602135433229604645318478604952148193555853611059596230655
2.3 量子和經典算法的快慢，還是量子計算機和經典計算機的快慢？我們究竟在比較什麼？
在我們最初的討論中，我們是想比較量子計算和經典計算機的快慢。但是讀者會發現，到這裡時，似乎我們轉向了討論量子算法和經典算法的快慢。這兩個東西是一樣的嗎？
首先，討論機器本身的快慢實際上沒有意義的，最終我們希望的是解決問題，因此比較的是「在經典計算機上解決問題的（最優）算法，和在量子計算機上解決同一個問題的（最優）算法的快慢」，簡稱為「算法的快慢」。
為了消除歧義性，我們首先需要定義什麼是算法的「快慢」。算法有實際上的快慢，也就是生活中我們運行一個程序跑的時間，但是實際中的快慢是難以進行理論分析的：它受到的影響很多，比如硬體的價格和工藝，軟體的編寫質量，環境的溫度，甚至是是否在運行過程中受到其他程序幹擾。何況算法的目的是為了使用，我們往往在使用之前，甚至設計之前就需要知道它的快慢。
在這一章節中，我們希望理論分析算法的快慢，因為這才是對選用算法以及設計算法真正有用的東西。在理論分析中，算法的快慢定義為「圖靈機執行的時間」，我們進而約定經典圖靈機和量子圖靈機執行一步的時間都是固定的，因此時間其實對應了圖靈機執行的步數。在量子圖靈機的每一步中，都可以對整個量子態，也就是整個向量進行操作，比如 QFFT 中的一個量子門；而經典圖靈機卻做不到：如果將這種向量和矩陣的乘法作為經典圖靈機的一個操作，那麼這步操作的時間就沒有上限，因此不能稱為「固定時間的操作」，所以這不能作為經典圖靈機的一個基本操作。這樣一來，經典圖靈機中的算法就需要用更多步數實現向量和矩陣的乘法。因此，在有些算法中，量子圖靈機可以充分利用自己的優勢，設計出執行步數少得多的算法。所以在我們的理論分析中，解決同一個問題的最優算法的快慢就反映了量子圖靈機和經典圖靈機的相對優勢：如果最優的量子算法快於經典算法，說明量子計算機本質上支持用更快的算法解決相同的問題，這就是量子計算機的優勢。
2.4 問題的分類遊戲
然而，具體研究解決問題的算法時，我們發現大部分 「非平凡」 的問題會有一個參數，稱為輸入規模。比如快速傅立葉變換中的輸入規模就是輸入向量的元素個數，破解密碼的規模是密碼的長度。一般而言，規模和問題的輸入佔用經典計算機的比特數成正比。我們對算法進行分析後，會發現某個問題的最優算法的執行步數是輸入規模數學表達式，比如快速傅立葉變換是 。算法分析中，我們關心的是某個問題的最優算法的執行時間隨著輸入規模 的變化趨勢，我們可以根據變化趨勢給問題分類，而我們將同一個類型的問題歸入同一個集合。
顯然，相同的問題，對於量子計算機和經典計算機，可能有不同的分類，這意味著量子計算機和經典計算機會將問題劃分為不同的集合（下面所有的算法都默認是對應問題的最優算法）。
2.5 經典計算機視角下的問題分類
首先，我們可以定義一個集合 P，集合 P 包涵了所有的一類經典計算機的最優算法能夠在輸入規模的多項式時間（算法時間的表達式是一個多項式，或者比多項式增長更慢的項，比如 logN 等）內解決的問題。這類問題包括排序，快速傅立葉變換，求解兩地直接的最短路徑等等。P 內部的問題在理論分析中被認為是「容易的問題」。
另外我們可以定義一個集合 NP，集合 NP 包涵了所有的可以多項式內驗證結果的問題。顯然 P 是 NP 的子集，因為 P 問題可以通過再解一遍驗證結果。如果 P 問題類似檢查數學證明，那麼 NP 類似於給出證明。關於 P 和 NP 有一個非常著名的數學難題：
P ?= NP
雖然 P 是 NP 的子集，但是我們至今都沒有證明它是真子集。大多數理論計算機學家都相信 P 不等於 NP，一是因為 「驗證答案的難度和寫出答案的難度一樣」 過於違背直覺，二是因為人們發現了一個 NP 的子集，稱為 NPC（NP-complete）。NPC 內部的問題有這樣一個性質：如果其中任何一個問題被證明屬於 P，那麼 P = NP。NPC 內部有非常多有趣的問題，比如邏輯滿足問題，定點著色問題，哈密頓迴路問題，子圖同構問題，但是若干年都沒有任何一個人發現多項式時間解決它們的算法（就像找不到黎曼猜想的反例一樣），這讓大家愈加相信 P != NP。
此外，非常有趣的一點是，相當多和密碼學相關的問題都屬於 NP（RSA，離散對數，橢圓曲線），但是它們既不屬於 P，也不屬於 NPC。
如果我們更進一步，如果問題詢問的是結果是 「真」 的結果的個數，且驗證每一個結果所用的時間是多項式時間（相當於對一個證明題，我不僅要求一個證明，還要求得到所有不多於某個字數的所有的證明的個數），這些問題的集合稱為 #P。顯然 NP 是 #P 的一個子集，因為它至多只有一個結果為真，我們只要解決這一個問題就可以了。
經典算法中有一大類稱為「隨機算法」，這些算法的執行有隨機性，不一定每次都能給出正確結果，但是正確的概率更大。所以只要通過多次執行，我們就可以通過統計越來越清楚地知道哪個是正確的結果。其中一類問題的集合是 BPP (bounded-error probabilistic polynomial time) 。BPP 中的問題對應的算法，每次執行的時間是多項式的，結果錯誤率是一個低於 1/2 的常數，也就意味著我們總共只要多項式的時間就可以以很高的概率得到正確結果。典型的問題是判斷一個數是否是素數。此外集合 PP (probabilistic polynomial time) 不再限制錯誤率是一個低於 1/2 的常數，而是允許它隨著問題規模任意接近 1/2，所以其中可能有一些問題相當難以解決。顯然 BPP 包含於 PP。
除了時間意外，我們可以用問題使用的內存分類問題。以上所有問題都包括在 PSPACE 這個集合內，因為解決它們所消耗的內存是規模的多項式倍；我們還可以考慮一個更大的集合，EXPSPACE，這個集合包括了消耗的內存是規模的指數倍的問題，幾乎所有能夠想到的問題都存在於 EXPSPACE 中，否則問題的內存消耗就能夠窮盡整個宇宙的物質。
算法分類問題是名副其實的數學上最難的問題之一， P ?= NP 只是其中的問題之一，實際上我們不知道以下任何一對集合的是否相等（不過人們傾向於認為它們之間都是真包含的），也就是有 15 個未解決的難題：
P ?= BPP ?= NP ?= #P ?= PP ?= PSPACE
2.6 量子計算機視角下的問題分類
由於量子計算機天生就有隨機性，所以量子計算機的問題分類結果主要是按照隨機算法，而量子計算機視角下對應於經典計算機 BPP 定義的集合稱為 BQP(bounded-error quantum polynomial time)。
我們考慮所有問題的集合，畫出我們定義的這些集合的 Venn 圖（根據理論進展，有些問題的複雜度類可能會發生改變）：
複雜度類的 Venn 圖
其中 BPP 集合內部的問題，可以認為是經典計算機可以 「高效」 解決的問題，而 BQP 集合內的問題，是量子計算機可以高效解決的問題。我們注意到兩點：1. BQP 集合內包括比 BPP 更多的問題，這意味著有更多經典計算機難以高效解決的問題，可以被量子計算機高效解決。2. BQP 沒有完整包括 NP，所以依然有大量有趣的問題無法被量子計算機高效解決，因此量子計算機並不是解決一切的「萬能工具」。
註：BQP 和 NP 兩者的具體關係還沒有解決，我們只知道有些 BQP 內的問題不屬於 NP（也就是必然存在一些問題，量子計算機可以高效解決，經典計算機不能高效解決）
但是 NP 是不是 BQP 的子集呢？這是一個未解決的問題，不過一般的看法是否定的。這是因為 1. 我們沒有發現任何一個 NPC 內的問題屬於 BQP 2. 「單一結果的無結構搜索問題」是一個 NP 問題，但是量子計算機最多只能帶來平方的加速，也就是著名的 Grover 算法；而相當多虛構的可以高效解決任何 NP 問題的機器都可以指數加速這個問題（比如上文中的虛構物理體系中），這可能暗示了量子計算機的局限性。
2.7 量子算法的物理實現難度和用途
首先，我們討論對於經典計算機無法高效解決的問題，也就是在 P 之外的問題。
在上面的 Venn 圖中，我們發現根據量子算法相對經典計算機的優勢是各不相同的。但是我們結合它們的實現難度，以及用途來列一張表：
結合這個表格，下一步最有價值也最容易實現的還是量子體系的模擬，這也是已經展示了量子霸權的各個量子計算團隊下一步的重要目標之一。
然後我們討論經典計算機已經可以高效解決的問題，也就是在 P 之內的問題。
（請原諒我在下面的介紹中不使用算法複雜度標記，因為我覺得沒有必要再介紹新的概念了）
是不是如果一個問題，經典計算機已經可以高效解決，那麼就不需要量子計算機呢？這可不一定。算法理論中的「簡單，高效」，往往是指對於規模，可以在大約這種多項式時間內解決的問題。當比較大的時候，現實中已經很難解決很大規模的問題；一個非常極端的例子是 AKS 素數測試算法，也就是一個判斷數是不是素數的算法，在最新的結果中，這個算法的（問題規模是素數的位數），在實際中很難運用，所以實際中真正使用的反而是一些隨機算法，這些隨機算法雖然有微乎其微的概率錯判，但是要比 AKS 快的多。
這裡我們討論一個非常有代表性的問題：線性方程組的解。我們知道，對於一個規模為 的稠密（大部分係數不是 0）的線性方程組，用經典算法求解需要大約步；而對於稀疏（大部分係數是 0）的線性方程組，用經典算法求解需要大約步，其中是矩陣的「條件數」(矩陣極大和極小特徵值或者奇異值的比值)，是「稀疏度」。
對於稀疏矩陣而言，存在一個稱為 HHL 的算法（HHL 代表了 Arram Harrow, Avinatan Hassidim 和 Seth Lloyd 三人，發表於 2008 年），僅用（改進版本），也就是大約步就可以解這個方程組。這相對於經典算法的相對問題規模快了指數倍。
這個算法在當時引起了轟動，因為解線性方程組是一個非常非常重要的問題，幾乎用於各個領域。下面好幾年出現了一大堆「指數加速算法」，基本思想都是找一個經典的依賴解線性方程組的問題，然後用 HHL 算法指數加速。這在 2014 年左右又大火了一波，因為大家開始對機器學習感興趣，而一大堆機器學習問題中都要解線性方程組。
2015 年，量子算法權威 Scott Aaronson 在 HHL 作者的幫助下，直接發了一篇 nature 評論 「Quantum Machine Learning Algorithms: Read the Fine Print「 指出了很多人對 HHL 的「使用不當」（有趣的是這篇評論的引用數佔了原 HHL 的 1/5，考慮到發表時間已經相當多了）。那麼 HHL 有哪些「fineprint」 呢？
和 QFFT 一樣，輸入的向量必須編碼到是量子態向量的係數上。如果向量最初是經典計算機中的向量，那麼顯然讀取數據就需要步（因為向量本身有 個元素），這樣你就無法獲得加速優勢。同樣的，矩陣本身的元素也不能全部來自經典計算機的稀疏矩陣，否則讀取數據就會佔用更多時間。所以大部分機器學習問題，除非人為構造數據，否則很難直接用 HHL 加速。
矩陣必須是稀疏的，也就是遠小於，否則主導運行時間的就是，而不是，加速效果就會大打折扣。完全無視這一點的相關研究可以說幾乎是故意在騙人了。當然，也有一個 HHL 的變種算法，可以加速稠密的線性方程組的求解，但是相對經典算法並沒有指數加速。
輸入的稀疏矩陣必須是可逆的，而且數值特性良好，否則狀態數會很大，這樣也會失去加速。
這個算法的輸出和輸入一樣，也是編碼到量子態向量的係數上的，這意味著你沒有辦法直接將結果直接轉換成經典的表示，比如導出成一個數組，列印到屏幕上。不過，你可以通過一些後續的算法研究這種輸出的一些性質（雖然還是不能直接得到輸出）。
如果你的問題沒有上述任何一個困擾，那麼恭喜你，你可以使用 HHL 來指數加速你的問題求解。
看到這些 fineprint，你可能會發現 HHL 和之前的 QFFT 算法有一些相當類似的「共性」，這是因為 HHL 本身就是依賴 QFFT 的。HHL 算法的例子說明了，指數加速一個經典問題，有的時候並不是免費的午餐，越大的加速往往就帶來了越多的對求解問題的限制（這也間接說明了量子計算機是有局限性的，不是萬能的機器）。
這一個例子進一步展現了量子通用計算機的重要性：有相當多的量子算法，可以對各類非常具體的經典問題進行一定的加速，但不是指數加速，因而在量子通用計算機研製出來之前，無法展現優勢，其加速不及指數加速也導致它們難以像 Shor 算法，HHL 算法一樣有很高的宣傳熱度。也許最壞的情況是，等到通用量子計算機出現後，人們發現大部分實際問題在實際的條件下只能獲得平方加速，但是這並不意味著通用量子計算機的概念並不偉大——要知道比起平方加速，我們很多時候只是優化常數。
© THE END
轉載請聯繫本公眾號獲得授權
投稿或尋求報導：content@jiqizhixin.com
原標題：《「九章」刷屏的背後：萬字長文解析，量子計算機和電子計算機各有何優劣？》
閱讀原文