原標題：“九章”問世：量子計算機究竟有多快 來源：新浪科技

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

日前，中國科學技術(shù)大學潘建偉、陸朝陽等學者組成的研究團隊與中國科學院上海微系統(tǒng)所與信息技術(shù)研究所、國家并行計算機工程技術(shù)研究中心合作，構(gòu)建了 76 個光子的量子計算原型機 “九章”。計算玻色采樣問題，“九章”處理 5000 萬個樣本只需 200 秒，而目前世界最快的超級計算機需要 6 億年。

在新聞報道中，都會將 “九章”和超算的計算速度作對比，但實際上，量子計算機和超算存在實質(zhì)性的不同，遠不止計算能力上的差別。

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

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

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

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

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

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

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

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

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

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

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

量子計算機到底有多快？

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

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

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

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

量子算法

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

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

用已知算法來進行大數(shù)分解的資源消耗估計，需要的經(jīng)典指令數(shù)目上升的非?？?，而需要的量子門操作數(shù)上升的很緩慢，這是因為要分解更多位的數(shù)，需要的經(jīng)典指令數(shù)目會指數(shù)倍的增加。這個發(fā)現(xiàn)對計算機科學家來說是令人興奮的，但對密碼學家來說，互聯(lián)網(wǎng)的安全基于公鑰加密，比如 RSA 加密系統(tǒng)是基于以下事實：很容易將兩個因數(shù)相乘，但很難將一個大數(shù)進行因數(shù)分解。

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

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

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

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

下面講一下數(shù)學中的疊加態(tài)原理，量子態(tài)可以用復向量空間中的單位向量來表示，當兩個量子態(tài)可以用兩個正交向量表示，它們就是可區(qū)分的。

量子比特就是一個有兩個可區(qū)分狀態(tài)的量子系統(tǒng)。

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

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

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

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

量子計算機的線路模型

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

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

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

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

現(xiàn)在我們需要引入量子力學的另外一個原理：線性原理，即孤立量子系統(tǒng)的演化是線性的。孤立量子系統(tǒng)中純態(tài)的演化可以用作用在態(tài)空間上的密度矩陣來描述，干涉來源于量子態(tài)是用復數(shù)表示。

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

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

量子算法背后的理論

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

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

現(xiàn)在我們還剩兩項，其中一項給出一個因數(shù)，另一項給出另一個因數(shù)?，F(xiàn)在我們來分解下 33，令 a 等于 13，b 等于 2，而 169 除以 33 的余數(shù)是 4，所以 2 的平方等于 13 的平方除以 33 的余數(shù)，然后用 13 的平方減去 2 的平方的結(jié)果除以 33，其余數(shù)為 0。15 除以 3 的余數(shù)是 0，所以 15 就給出因數(shù) 3，11 給出因數(shù) 11。所以最終得到 33=11×3。這是歐幾里得兩千年前發(fā)明的算法，可以用來計算因數(shù)分解問題。

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

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

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

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

在分解算法中有一些很重要的地方，比如在第二步中，用了第二個寄存器進行計算，但是之后就再也不用它了，為什么不把這一步去掉呢？ 這樣不行，因為你去掉了這一步，就會去掉算法里面的干涉，最后就不會得到正確的答案了，這是因為量子力學定律。如果一個量子系統(tǒng)作用到另一個量子系統(tǒng)，那么第二個量子系統(tǒng)也會反作用于第一個系統(tǒng)。

這個算法能成功的原因在于：當你進行完傅里葉變換后，就在第一個寄存器中獲得了干涉，如果第一個寄存器的值跟周期相近，那么所有的系數(shù)相加后得到相長干涉，而如果這個值不是周期，那么所有系數(shù)相加后就得到相消干涉，因此你最終得到的結(jié)果是接近周期的。

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

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