量子計算作為量子信息技術(shù)的一個重要領(lǐng)域，在生物醫(yī)藥、化學(xué)材料、大數(shù)據(jù)分析優(yōu)化、人工智能等領(lǐng)域有廣泛的應(yīng)用前景。近年來，我國在量子計算領(lǐng)域取得了不少世界級的重要成果，在產(chǎn)業(yè)化方面也正在迅速起步。

為幫助大家更好地了解量子計算的行業(yè)發(fā)展前景，中國信息協(xié)會量子信息分會官方微信公眾號正式上線“量子計算專欄”，聚焦量子計算的應(yīng)用，同大家分享量子計算發(fā)展歷史、基本原理介紹、產(chǎn)業(yè)現(xiàn)狀等內(nèi)容。

本期將對量子計算的早期發(fā)展進行梳理匯總。

邱奇-圖靈論題

為了理解量子計算的起源，首先需要回顧一下計算機科學(xué)的發(fā)展。一般認(rèn)為，阿蘭·圖靈1936年那篇著名的文章宣告了現(xiàn)代計算機科學(xué)的誕生，文章中提出了如今被稱為圖靈機的計算模型。

在此基礎(chǔ)上，圖靈與阿隆佐·邱奇相互獨立地提出了所謂邱奇-圖靈論題：在任何硬件上實現(xiàn)的算法過程都能用通用圖靈機等價實現(xiàn)。

之后各種其他計算模型被陸續(xù)提出來。60年代末70年代初人們意識到，這些計算模型相比圖靈機并沒有計算能力上的顯著提升。從而誕生了強邱奇-圖靈論題：任何算法過程都能用圖靈機有效仿真。這里的“有效”是計算復(fù)雜度里的一個特定詞匯，大致可以理解為“在隨問題尺度多項式增長的時間內(nèi)”。

70年代中期，強邱奇-圖靈論題首次面臨挑戰(zhàn)：有人提出用隨機算法來概率性地解決問題。通過多次重復(fù)提升概率，有望超越?jīng)Q定性圖靈機的計算效率。這一挑戰(zhàn)可以通過修正強邱奇-圖靈命題來應(yīng)對：任何算法過程都能用概率性圖靈機有效仿真。

那么，有沒有可能徹底打破強邱奇-圖靈論題呢？這就是人們在80年代初提出量子計算的主要動機。

量子計算的提出

一般認(rèn)為，量子計算是由貝尼奧夫、曼寧以及費曼在80年代初先后獨立地提出的。曼寧和費曼都是從仿真量子系統(tǒng)的角度出發(fā)的：

也許【……】我們需要量子自動機的數(shù)學(xué)理論?！尽苛孔討B(tài)空間的容量遠(yuǎn)遠(yuǎn)大于經(jīng)典的：對于具有N 個態(tài)的經(jīng)典系統(tǒng)，它的量子版本因為允許疊加，可以容納c?個態(tài)。當(dāng)我們將兩個經(jīng)典體系合并時，它們的態(tài)數(shù)N?與N?會相乘，而在量子的情形我們會得到指數(shù)增長C????【……】這些粗略的估計表明系統(tǒng)的量子行為可能比它的經(jīng)典仿真復(fù)雜得多。

——尤里·曼寧（1980）

物理能用通用計算機仿真嗎？【……】物理世界是量子力學(xué)的，因此合理的問題是量子物理的仿真【……】對一個R個粒子的大系統(tǒng)的量子力學(xué)的完整描述【……】包含太多變量了，用正比于R那么多個元件的常規(guī)計算機是無法仿真的?！尽梢杂昧孔佑嬎銠C元件來仿真?！苛孔酉到y(tǒng)能用經(jīng)典（假定是概率性的）通用計算機來概率性地仿真嗎？如果你采用我之前描述的經(jīng)典類型計算機【……】答案肯定是，不能！

——理查德·費曼（1982）

他倆的思路是類似的：量子體系的態(tài)數(shù)目是指數(shù)式增長的，因而很難用經(jīng)典計算機（哪怕是概率性的）來有效仿真。但用量子體系構(gòu)建的量子計算機是有可能的，因為至少每個量子體系都可以有效地仿真其自身！

量子計算模型

1980年，保羅·貝尼奧夫在他的文章提出了量子圖靈機的初步構(gòu)想。

1985年，多伊奇推廣經(jīng)典計算機的邏輯門電路，提出了量子電路模型。進一步研究發(fā)現(xiàn)，二者實際上是等價的。量子電路因為簡單形象，現(xiàn)在被普遍接受。

本世紀(jì)初，人們提出了另一種通用量子計算模型，稱作“基于測量的量子計算”。這一模型完全脫離了對量子門的依賴，只通過初態(tài)制備、單比特測量和前饋來實現(xiàn)所有運算，又稱“單向模型”。值得一提的是，量子電路和單向模型都可以用ZX-演算來重新表述。（關(guān)于ZX-演算，我們之后會詳加介紹。）

肖爾算法

90年代初，人們已經(jīng)可以在一些人為問題上揭示出量子算法的優(yōu)越性。這些發(fā)展最終促成了彼得·肖爾1994年在大數(shù)分解問題上的突破。

我們稍微介紹一點肖爾算法背后的原理。量子比特可以處于疊加狀態(tài)：|ψ>=α|0>+β|1>.因此，一次單比特操作就可以實現(xiàn)長度為2的離散傅里葉變換。這其實是所謂的阿達(dá)馬門H：H|0>= (|0>+|1>)/√2,????H|1>= (|0>?|1>)/√2.

對n個量子比特都作用H門，可以實現(xiàn)n重長度2的離散傅里葉變換。這會在一些特殊的計算問題上體現(xiàn)出指數(shù)級的優(yōu)越性——正如多伊奇-喬薩算法和西蒙算法所展示的。

肖爾的獨創(chuàng)之處在于，他指出可以利用一系列n比特門直接實現(xiàn)長度為2?的離散傅里葉變換。相比于傅里葉變換的經(jīng)典算法，這一實現(xiàn)方案達(dá)到了指數(shù)級的加速。在此基礎(chǔ)上，肖爾給出了大數(shù)分解以及離散對數(shù)問題的高效算法，在理論上證實了量子計算在實際應(yīng)用方面的巨大潛力。同時，這也在一定程度上實現(xiàn)了人們早期發(fā)展量子計算的預(yù)期目標(biāo)。肖爾算法后來被推廣到一大類隱子群問題中，至今仍屬于熱門研究。

硬件實現(xiàn)方式

哪怕局限于以量子比特為基本單元的量子電路模型上，量子計算的硬件實現(xiàn)方式依然非常豐富。例如，中科大的“祖沖之號”用的是超導(dǎo)電路，而“九章”則用的是光量子。原則上任何包含兩個量子態(tài)的體系都可以用來實現(xiàn)量子比特。不同的硬件體系有各自的優(yōu)劣，目前還很難有定論。

本文將它們簡單分成兩類：拓?fù)鋵崿F(xiàn)和非拓?fù)鋵崿F(xiàn)，然后加以對比。作為朗道范式的推廣者，文小剛及其合作者在1989年提出了多體系統(tǒng)的“拓?fù)湫颉?。拓?fù)湫蛴审w系的長程量子糾纏決定，因而不受局域擾動的影響。1997年，阿列克謝·基塔耶夫進一步提出，利用拓?fù)湫蝮w系的拓?fù)浼ぐl(fā)——任意子，可以實現(xiàn)容錯量子計算。拓?fù)淞孔佑嬎愫髞沓蔀槲④浌镜闹饕l(fā)展方向。然而，拓?fù)湫蝮w系至今為止仍未在實驗中證實，給拓?fù)溆嬎愕陌l(fā)展帶來了巨大的困難。

非拓?fù)涞膶崿F(xiàn)方式則相對比較容易，但同時也更容易受到環(huán)境的影響，所以必須對物理量子比特進行糾錯，最終實現(xiàn)容錯計算。近十年來，多種硬件方案在門保真度和糾錯性能方面都取得了大幅的進步。

事實上，這兩種實現(xiàn)方式并非毫無關(guān)聯(lián)。在糾錯中廣泛采用的表面碼，就是一種特殊的拓?fù)湫蚰Ｐ汀碍h(huán)面碼”在平面上的形式。而利用當(dāng)前的超導(dǎo)量子電路，人們已經(jīng)能仿真出簡單拓?fù)湫蝮w系的一些性質(zhì)。或許在不遠(yuǎn)的將來，二者可以融為一體，共同形成一種實用的容錯量子計算機。

本文作者：

上海微觀紀(jì)元數(shù)字科技有限公司左芬博士。

參考文獻：

邁克爾·尼爾森,艾薩克·莊:《量子計算與量子信息》;

鮑勃·科克,亞里克斯·基辛格:《圖解量子過程：量子理論與圖形化推理入門》。