日前，中國科學技術大學潘建偉、陸朝陽等學者組成的研究團隊與中國科學院上海微系統所與信息技術研究所、國家並行計算機工程技術研究中心合作，構建了76個光子的量子計算原型機“九章”。計算玻色採樣問題，“九章”處理5000萬個樣本只需200秒，而目前世界最快的超級計算機需要6億年。在新聞報導中，都會將“九章”和超算的計算速度作對比，但實際上，量子計算機和超算存在實質性的不同，遠不止計算能力上的差別。

出品：新浪科技《科學大家》、墨子沙龍

撰文：彼得·秀爾（Peter Shor），美國麻省理工學院數學系教授

量子計算機的“計算”有何不同？

計算機和物理實驗有什麼不同呢？有很多可能的答案，其中一個就是：電腦能回答數學問題， 而物理實驗回答物理問題。比如說，如果要分解一個很大的數字， 一個好辦法是用計算機來計算；而如果想要測試所有物體是否以相同的速率下降， 這時不會用電腦， 而是像圖中的伽利略那樣，用兩台不同的計算機測試它們是否會以相同的速度下落。

另一個答案是：物理實驗是一個非常大的定制儀器，也許會佔據整間屋子， 而計算機就是一個小盒子，可以放在桌子上或公文包裡。

不過時間若是回到上世紀五六十年代，計算機剛剛問世的時候，你能分辨出圖中哪個是計算機，哪個是加速器嗎？

其實圖片中左邊這個是粒子加速器，位於上世紀60年代的勞倫斯伯克利實驗室，而右邊這個是神奇的ENIAC，它是上世紀五十年代發明的世界上第一台計算機，位於賓夕法尼亞大學。這兩台儀器都體積巨大，但之後計算機的體積越來越小，而粒子加速器卻越來越大。為什麼會這樣呢？這是因為人們不需要針對每個數學問題都建造一台新的計算機。這意味著建造計算機的人可以進行大規模生產，使它們可以越來越高效，越來越便宜，越來越小。而做物理實驗的人每當遇到以前的實驗結果無法回答的問題時，就只能設法突破物理實驗的極限，就比如越來越大的加速器。

計算理論始於20世紀30年代，那時候計算機還沒有發明。上世紀三十年代，在數學邏輯方面，哥德爾證明了著名的不完備性定理，即並非所有的數學命題都能證明是真或是假，所以有些數學問題是無法得到答案的。計算數學與計算機科學密切相關，在哥德爾證明了這個定理六年之後， 四位科學家區分了可計算函數和不可計算函數的定義， 這些研究都源於哥德爾的理論。如果閱讀這些論文就會發現，它們包含三種對可計算函數的不同定義。而可計算函數的這三種定義都給出了可計算函數是完全相同的事實，這就引出了邱奇圖靈論題。

論文作者認為“丘奇-圖靈論題”是對的。這個圖靈機可以執行任何設備上的任何計算，這也是計算機的原始模型，它可以很很輕鬆的處理數學問題。

那麼，任何設備是什麼意思呢？圖靈和邱奇並沒有想到的一點是：這是一個我們可以在真實世界中建造和運行的機器。這樣它就是一個物理問題，而不是數學問題了。隨著實用計算機的發展， 不可計算函數和可計算函數的定義界限變得越來越不清晰。因為有的函數理論上是可以計算的，但需要非常長的時間來進行計算而且價值也不高，因此一個有效的程序必須要在合理的時間內完成計算。

所以什麼是合理的時間呢？你也許會問在一個超級計算機上用一年時間進行計算合理嗎？但是從數學的角度來說這是非常糟糕的， 所以一些理論計算機學家認為， 要在理論和實際中進行妥協。他們認為一個有效的算法應該滿足以下條件：它的運行時間必須是在多項式時間以內， 比如N，N的平方，N的立方，N的一萬次方等等， 而不是2的N次方這種指數級時間。

所以把能在多項式時間內求解的一類問題稱為P。一個需要說明的事實是，大多數的函數屬於P類問題，這說明大部分算法都是有效的。為了使定義更加有意義， P不應該依賴於何種計算機類型。

這就使得一些計算機科學家提出了量化丘奇論題。當然它也有許多其他叫法，但都指的是：圖靈機可以有效的執行任何計算任務。量化丘奇論題首先是由Alan Cobham在1965年提出的。因數分解算法對計算機科學家的重要影響在於，它將顯示這個“民間論題”（量化丘奇論題）是錯誤的。

量子計算機到底有多快？

那麼，當我發現因數分解算法後記者會問：量子計算機比經典計算機快多少呢？答案就是：這個問題無法回答。就像問船要比火車快多少的問題，這不僅僅是取決於船和火車，還取決於目的地在哪裡。所以對量子計算機和經典計算機來說，問題在於經過希爾伯特空間的捷徑能否有一個從輸入到輸出。因此要考慮到許多因素， 而事實上這樣的誤解非常普遍， 這也說明了公眾普遍接受了量化邱奇圖靈論點， 即認為計算機中最重要的是足夠的空間以及計算速度。然而量子計算機中的一步操作要比經典計算機中的一步操作長。但是量子計算機可以通過走希爾伯特空間的捷徑來加速計算，而經典計算機無法這樣做，這就大大減少了操作數。

去哪裡尋找定量丘奇圖靈論題的反例呢？可能會在難以模擬的物理系統中。那什麼樣的物理系統是難以模擬的呢？一個明顯的答案就是湍流問題，它跟納維爾-斯托克斯問題相關，是七個千禧年難題之一。陶哲軒思考過這個問題， 認為它和一些系統的偏微分方程組很相似。

湍流就是這樣一類很難去模擬的物理系統，而量子力學是另外一種很難模擬的系統，這首先是由Poplavskii和費曼提出的。用數字計算機來模擬量子力學是指數級低效的， 費曼曾指出， 量子計算機的態空間大小是指數級增長的。你把量子系統的狀態存儲到經典計算機中，然後去精確追踪它們，這需要天文級的時間，但是量子計算機也許能解決這個問題。

在量子算法領域的早期， 1985年， David Deutsch提出問題：量子計算機是否可以加速非量子力學問題的計算？並且他提出了一個非常新穎的例子。七年後，它和Jozsa合作提出了另外一個算法，然後有了更多的人找到新的算法。量子計算機可以加速這些計算，當然，這些算法是為一些問題特定構造的，量子計算機確實可以更快的解決這些問題， 然後呢？

量子算法

量子計算機擅長哪些事情呢？第一個擅長的事情是： 量子計算機可以更有效的模擬量子力學系統。這是Feynman和Manin首先提出的想法。也可以用量子計算機來尋找周期性，這就是Simon問題。還有用量子計算機來分解大數和求離散對數，還有Pell方程和一些其他數學問題也是尋找周期性，Grover則提出可以用量子計算機來有效進行更大空間的搜索。現在來看下什麼是因數分解。

假設你有一個整數33，你想要找到兩個整數相乘等於33，用3乘以11即可，兩個數字相乘對經典計算機來說非常簡單。但是如果我們有一個非常大的數字，想要找到它是由哪兩個質數相乘得到，這就是一個非常困難的問題了。如果我們想要分解一個L位的數字， 最好的經典方法是數域篩法， 它需要指數級的時間， 而量子計算機只需要平方級的時間。

用已知算法來進行大數分解的資源消耗估計，需要的經典指令數目上升的非常快， 而需要的量子門操作數上升的很緩慢， 這是因為要分解更多位的數，需要的經典指令數目會指數倍的增加。這個發現對計算機科學家來說是令人興奮的，但對密碼學家來說，互聯網的安全基於公鑰加密，比如RSA加密系統是基於以下事實：很容易將兩個因數相乘，但很難將一個大數進行因數分解。

這意味著我們可以這樣使用它：取兩個質數並把它們相乘就得到一個密鑰， 然後把它們分開，這樣其他人就無法分解這個密鑰， 別人也就無法破解你的信息。但是如果有量子計算機就可以破解信息，這意味著你可以監聽計算機之間的信息交流，比如在互聯網上購買東西時的信息交流。這就是為什麼這個算法在1994年提出後就像病毒一樣迅速傳播。

量子計算究竟是如何工作的

這個問題涉及的是量子計算機的基本原理， 包括疊加態原理，量子糾纏， 量子態空間的高維性，以及量子乾涉。

疊加態原理是說如果一個量子系統可以處在兩個可區分狀態中的一種，那麼它也可以同時處在這兩種狀態上，即它可以處在疊加態上。如下圖所示，其中和是複數， 並且它們模的平方和為1，這叫做波恩定則。如果你對這個系統進行測量，看它是處在量子態A還是量子態B，得到狀態A的概率是|α|平方，得到狀態B的概率是|β|平方。

下面講一下數學中的疊加態原理，量子態可以用複向量空間中的單位向量來表示，當兩個量子態可以用兩個正交向量表示，它們就是可區分的。

量子比特就是一個有兩個可區分狀態的量子系統。

一個常見的例子就是極化光子​​， 它只有兩個可區分的極化方向： 垂直極化和水平極化。一個極化光子，你只能看到垂直極化或水平極化，其他的所有狀態都可由這兩種狀態產生。比如右對角極化是垂直極化加上水平極化，左對角極化是水平極化減去垂直極化，也有右旋圓極化，其中相位滯後90度。

這聽起來比較奇怪， 但量子力學就是如此奇怪。如果你有兩個量子比特，那麼它們就可以處在4種狀態的疊加，現在不用水平極化和垂直極化來代表兩種可區分狀態，而是用0態和1態來表示，比如這種兩比特狀態， |01>-|10>，其中每個量子比特都沒有確定的狀態。

當兩個量子系統從整體上看處在確定的狀態， 但分開看卻處在不確定的狀態時，它們是糾纏的。這就是令愛因斯坦不安的地方， 他把這個稱為“鬼魅般的超距作用”。許多其他著名的科學家也對此感到困惑，糾纏為什麼令人不安呢？如果你用概率論來解釋，這就導致了所謂的局域實在論。你將不得不接受這樣一個結論：在一個地方進行的測量， 會影響到另外一個地方的測量結果，儘管這兩個地點間沒有任何联系，你可以認為它們分開的足夠遠。

如何解決這個問題呢？一種辦法就是去接受這種“鬼魅般的超距作用”，另一種方法是承認量子力學中的概率定律與經典情況不同。量子力學可以加速計算的第三個特性是量子系統的高維性，如果你有n個量子比特， 則它們的量子態由一個2的n次方維的向量描述。下面這些就是這個向量空間的基矢。

量子計算機的線路模型

這個空間的高維性也是量子計算擁有強大計算能力的原因之一。而量子計算機的線路模型是一個簡化模型，就像圖靈機的簡化模型一樣。不過一些量子計算機並不是嚴格的線路模型，它們會有些不同，不過這是一個很好的方式去理解量子計算機。

為了進行計算，我們需要給計算機輸入， 需要改變計算機的狀態，需要獲取計算機的輸出。那麼如何做到這些呢？對於輸入，我們可以在二進制輸入對應的狀態下啟動計算機， 比如，100101101， 我們把第一個量子比特置為1態，把第二個量子比特置為0態，其它量子比特同理置為某個狀態。我們也許需要額外的空間來運行算法，所以我們需要在初始化時添加額外的0，就像這些0一樣需要更多的空間。

下面來看看如何輸出。在計算結束時，量子計算機處在某種狀態， 比如這種一般的量子態。但我們不能通過測量完全標定出量子態， 因為有海森堡不確定性原理。假設是在標準基下進行投影測量的，那麼將會有||的概率得到結果i，比如你會有||的概率得到|0…001>，所以應該怎麼做呢？

當觀察量子計算機後卻得到一個概率分佈，且無法做得比這更好了，這是因為量子力學本質上是一種概率論。你肯定會問：那如何確定量子算法解決了問題呢？我們認為：當能夠以很大概率得到正確結果時，該量子算法就解決了問題，這跟用經典概率算法解決問題一樣。

現在我們需要引入量子力學的另外一個原理：線性原理，即孤立量子系統的演化是線性的。孤立量子系統中純態的演化可以用作用在態空間上的密度矩陣來描述，干涉來源於量子態是用複數表示。

如果對0態施加一次H變換， 則各有50%機率得到0態或者1態，但是如果應用了兩次變換，在這裡就會有一個負號， 這就意味著|0>這一項抵消了。也就是說，施加兩次變換後，|0>會變成|1>，|1>會變成-|0>，這就是量子計算運行的一個例子。

而說到計算，對單個或兩個量子比特進行變換操作時， 相當於用2*2或4*4矩陣乘它們， 這跟經典計算機進行計算是類似的，即任何經典計算都由基本的與或非門組成。

量子算法背後的理論

快速量子算法背後有幾個重要理論。在運用相關理論時，我們具體要做的就是設計算法使得那些產生錯誤結果的計算路徑相消干涉，用以降低得到錯誤答案的概率。讓那些產生正確結果的計算路徑相長干涉，這樣就能極大地增大獲得正確答案的概率。這也是導致設計一個量子算法很困難的原因。如此一來就很有必要介紹一下因數分解算法，其實我們要做的就是進行模運算。

一個數除以M得到的餘數就是模運算的結果， 比如13加9除以17的餘數是5，而5乘7除以17的餘數是1，我們將在因數分解算法中用到它。現在來講下所有快速分解算法背後的思路， 比如我前面講過的數域篩法，它是經典算法。還比如量子分解算法，要分解一個大數N，需要找到兩個數a和b， 它們滿足a的平方等於b的平方除以N的餘數，但是a不等於正負b除以N的餘數，然後你可以得到這個方程，a的平方減b的平方等於a+b乘以a減b ，它又等於N的整數倍，因為a的平方減去b的平方除以N的餘數為0。

現在我們還剩兩項，其中一項給出一個因數，另一項給出另一個因數。現在我們來分解下33，令a等於13，b等於2，而169除以33的餘數是4，所以2的平方等於13的平方除以33的餘數，然後用13的平方減去2的平方的結果除以33，其餘數為0。15除以3的餘數是0，所以15就給出因數3， 11給出因數11。所以最終得到33=11×3。這是歐幾里得兩千年前發明的算法， 可以用來計算因數分解問題。

下面用量子分解算法來對大數N進行分解，首先要找到一個序列的周期，一個序列的周期就是經過多久它會重複，即經過多久再次出現。獲得這個數後，就知道了周期r，而x的r次方除以N的餘數就等於1，如果我們幸運的話，r剛好是偶數，然後計算這個公式就能得到因數。

我們現在通過取最大公約數得到兩個因子， 最後就可以給出一些不錯的結果， 至少對於隨機選擇的x中的一半是如此。我們再舉一個分解33的例子，取x等於5，然後得到序列：1，5， 5的平方25，5的立方為26，5的四次方為31 （結果為除以33的餘數）， 5的10次方除以33的餘數是1，因此5的5次方除以33的餘數是23，然後把33分解成（23+1）×（23-1），就等於24×22，最後24就給出一個因數3，22給出一個因數11，這樣我們就分解了33，33=3×11。

因此我們需要找到x的次方除以N的餘數的周期， 方法就是利用傅里葉變換，這樣可以很容易找到週期性。在找x的次方除以N的餘數的周期時會遇到問題，問題就是這些序列可能會有指數級長的周期，解決辦法就是利用量子計算機的指數級增大的態空間，去指數級加速傅里葉變換。正如經典算法中用FFT（快速傅里葉變換）來計算傅里葉變換，我們可以改造成量子傅里葉變換。

那麼因數分解算法呢？首先我們需要將第一個量子寄存器置為疊加態， 然後隨機選擇x。如果i在第一個寄存器中， 就在第二個寄存器中計算x的i次冪除以N的餘數， 這兒還是經典計算機的計算。這裡就可以使用經典方法來進行計算，再對第一個寄存器進行量子傅里葉變換，接著測量第一個寄存器，由此就得到了量子計算機的輸出結果。然後在經典計算機上進行數據處理後，就可以得到因數。

在分解算法中有一些很重要的地方， 比如在第二步中，用了第二個寄存器進行計算， 但是之後就再也不用它了，為什麼不把這一步去掉呢？這樣不行，因為你去掉了這一步，就會去掉算法裡面的干涉，最後就不會得到正確的答案了，這是因為量子力學定律。如果一個量子系統作用到另一個量子系統， 那麼第二個量子系統也會反作用於第一個系統。這個算法能成功的原因在於：當你進行完傅里葉變換後， 就在第一個寄存器中獲得了乾涉，如果第一個寄存器的值跟周期相近，那麼所有的係數相加後得到相長干涉，而如果這個值不是周期，那麼所有係數相加後就得到相消干涉，因此你最終得到的結果是接近週期的。

量子計算未來或許能夠在很多具有實用價值的領域發揮巨大作用。領導團隊開發“九章”的中國量子領域著名專家潘建偉曾在採訪中說：“量子計算機在原理上具有超快的並行計算能力，可望通過特定算法在密碼破譯、大數據優化、天氣預報、材料設計、藥物分析等領域，提供比傳統計算機更強的算力支持。” 奧地利科學院院長、沃爾夫獎得主、美國科學院院士Anton Zeilinger則認為，“我預測很有可能有朝一日量子計算機會被廣泛使用。甚至每個人都可以使用。”

量子計算將給人類社會的發展帶來什麼樣的變化，我們拭目以待。