一

　　前　言

　　對(duì)于所有非物理專業(yè)的畢業(yè)生而言，量子這個(gè)概念多半是模糊而又熟悉的，因?yàn)闆]有系統(tǒng)學(xué)習(xí)過量子力學(xué)，因此對(duì)什么是量子往往難以理解并說不清楚，但近年來量子這個(gè)詞又不斷高頻出現(xiàn)在大眾視野面前，從量子通信、量子衛(wèi)星到量子計(jì)算···

　　但真正第一次打動(dòng)我并讓我產(chǎn)生無限好奇，想靜下來花功夫好好搞懂什么是量子、什么是量子計(jì)算機(jī)的是一段TED演講，里面明確告知了我們量子計(jì)算機(jī)不是傳統(tǒng)的計(jì)算機(jī)的升級(jí)加強(qiáng)版，而是像電燈與蠟燭那樣，同樣是發(fā)光，但具有本質(zhì)的不同，不是同一個(gè)時(shí)代的產(chǎn)物！

　　量子計(jì)算機(jī)和傳統(tǒng)計(jì)算機(jī)到底有多大的區(qū)別呢？用一個(gè)游戲演示：

　　假如我們和一臺(tái)計(jì)算機(jī)一起玩翻硬幣的游戲，游戲規(guī)則是計(jì)算機(jī)翻動(dòng)一次，我們?nèi)朔瓌?dòng)一次，然后計(jì)算機(jī)再翻動(dòng)一次，如果最終正面朝上則我們贏，反之則是計(jì)算機(jī)贏，由于互相都看不到翻動(dòng)情況，是翻動(dòng)還是不翻動(dòng)都由各自決定，因此結(jié)果最終是50%正朝上，雙方勝率是各一半。如果計(jì)算機(jī)不是傳統(tǒng)計(jì)算機(jī)，換成一臺(tái)量子計(jì)算機(jī)，你能猜到結(jié)果是什么樣嗎？計(jì)算機(jī)幾乎全勝（勝率超過97%，那3%的失敗均是因?yàn)榱孔佑?jì)算機(jī)的故障導(dǎo)致）！

　　那么，讓我們仔細(xì)看看這個(gè)神奇的量子計(jì)算吧。

　　二

　　量子計(jì)算發(fā)展歷史

　　談到量子計(jì)算總會(huì)感覺神秘而陌生，2015谷歌宣布實(shí)現(xiàn)了9 個(gè)超導(dǎo)量子比特的高精度操縱，2017年IBM推出了20量子比特量子計(jì)算云服“IBM Q系統(tǒng)”，以及2018英特爾的49量子比特超導(dǎo)量子計(jì)算測試芯片“Tangle Lake”，中科院也將大量的研究資源投入到量子計(jì)算中…，可見量子計(jì)算是一個(gè)當(dāng)前很重要的一個(gè)前沿科技領(lǐng)域。

　?。薄槭裁磿?huì)誕生量子計(jì)算？

　?。幔┚w管進(jìn)入原子級(jí)尺寸極限

　　當(dāng)前，我們熟悉的電子計(jì)算機(jī)性能已經(jīng)十分強(qiáng)大了，為什么還需要量子計(jì)算機(jī)呢？過去傳統(tǒng)計(jì)算機(jī)運(yùn)算能力的飛速發(fā)展，離不開“摩爾定律”的作用，而隨著計(jì)算機(jī)中的晶體管已經(jīng)小到極限（原子級(jí)別）并且當(dāng)前對(duì)電磁規(guī)律的掌控也已經(jīng)幾乎到了極限，這也代表了基于晶體管的電子計(jì)算機(jī)的能力遭遇了瓶頸。如果說電子計(jì)算機(jī)的算力是“汽油”級(jí)別的話，那么量子計(jì)算機(jī)的算力就是“核能”級(jí)別的。這兩種算力根本不是一個(gè)級(jí)別，解決問題的能力也不再是簡單地在原來的基礎(chǔ)上畫一條延長線。

　　量子計(jì)算與經(jīng)典計(jì)算

　?。猓?duì)海量計(jì)算的加速需求

　　一直以來，我們對(duì)復(fù)雜大規(guī)模海量計(jì)算的需求從未停止過，半導(dǎo)體工業(yè)摩爾定律延續(xù)了40年，計(jì)算機(jī)性能一直保持指數(shù)級(jí)增長，但對(duì)算力的追求我們從未滿足過，更不會(huì)停步！具體而言主要在以下幾個(gè)方面：

　　1）、基因定位和太空探索

　　基因定位到太空探索，人類活動(dòng)帶來了越來越多的數(shù)據(jù)。比如探索未知太空時(shí)，通過衛(wèi)星收集大量的圖像和視頻資料，產(chǎn)生海量數(shù)據(jù)。要精細(xì)搜索和分析如此多的數(shù)據(jù)，經(jīng)過數(shù)以萬計(jì)的統(tǒng)計(jì)，我們發(fā)現(xiàn)經(jīng)典計(jì)算機(jī)并不擅長從海量圖片中迅速完成識(shí)別任務(wù)。迫切需要可以比經(jīng)典計(jì)算機(jī)更快地篩選海量數(shù)據(jù)的計(jì)算能力，協(xié)助我們分析并指出哪些圖像和視頻我們應(yīng)該做進(jìn)一步分析，哪些可以忽略。

　　比如，2019年4月人類拍攝到的第一張黑洞照片，拍攝的數(shù)據(jù)用現(xiàn)在最好的電子計(jì)算機(jī)也要算兩年，才能把照片“沖洗”出來，當(dāng)前計(jì)算機(jī)的計(jì)算能力限制了人類探索更大的宇宙。

　　2）、生物分子運(yùn)動(dòng)

　　下面是來自IBM Research的一幅精彩插圖，該圖展示了世界上最強(qiáng)大的超級(jí)計(jì)算機(jī)所能模擬出的最復(fù)雜的分子F團(tuán)簇（F cluster）。由圖可見（在圖片左下方），該分子其實(shí)根本不復(fù)雜，如果我們想模擬更為復(fù)雜的分子的方法來尋找更好的藥物療法、研究生物，我們必須另辟蹊徑，采取具有革命性的運(yùn)算方法，提供足夠的算力。

　　分子模擬問題（Chemistry:化學(xué)Nitrogenase enzyme…：參與氮?dú)猓∟2）轉(zhuǎn)化為銨根（NH4）過程的固氮酶Simulating this cluster…：模擬該簇已經(jīng)是傳統(tǒng)計(jì)算機(jī)運(yùn)算能力的上限）。

　　3）、密碼分析破譯

　　現(xiàn)有密碼算法安全性均是基于數(shù)學(xué)，比如RSA公鑰密碼算法基于大數(shù)質(zhì)因數(shù)分解，破譯它即使是使用未來速度最快的傳統(tǒng)計(jì)算機(jī)也無法完成這樣的復(fù)雜計(jì)算任務(wù)，原因是計(jì)算一個(gè)數(shù)的質(zhì)因數(shù)的復(fù)雜度呈指數(shù)式增長。因此，破譯現(xiàn)有密碼算法迫切需要超強(qiáng)的大數(shù)分解、復(fù)雜路徑搜索等計(jì)算能力，這背后的價(jià)值無以衡量。

　　量子計(jì)算基礎(chǔ)原理

　　計(jì)算本質(zhì)是--所有的計(jì)算系統(tǒng)其實(shí)都是在操控一個(gè)物理系統(tǒng)去完成計(jì)算。而計(jì)算，并不一定是特指去計(jì)算數(shù)字，凡是按照需求完成輸入、運(yùn)算和輸出的都是計(jì)算。我們常常容易錯(cuò)誤地認(rèn)為電子計(jì)算機(jī)是在控制著一個(gè)一個(gè)的電子進(jìn)行計(jì)算，相應(yīng)的量子計(jì)算機(jī)就是控制更小的量子來進(jìn)行計(jì)算。其實(shí)真實(shí)情況是，電子計(jì)算是利用的是經(jīng)典電磁規(guī)律操控物理系統(tǒng)，而量子計(jì)算是利用量子力學(xué)規(guī)律操控物理系統(tǒng)。

　　1）經(jīng)典比特和量子比特的區(qū)別

　　經(jīng)典比特可以表示0和1兩種不同的狀態(tài)，就像是一個(gè)硬幣的兩面要么是0要么是1，并且經(jīng)過邏輯門運(yùn)算之后得出的結(jié)果是0或1的某一種情況，絕對(duì)不會(huì)出現(xiàn)既是了0又是1的情況。

　　經(jīng)典比特

　　量子比特卻不同。大學(xué)物理上談到過薛定諤的貓，簡單地可以認(rèn)為是有一只量子貓，它可以同時(shí)既處于生又處于死的狀態(tài)。也就是說其實(shí)薛定諤的這只貓就可以被看做一個(gè)量子比特。這個(gè)量子比特可以既是0 又是1，兩種狀態(tài)同時(shí)存在，這種狀態(tài)在量子力學(xué)中稱作“量子疊加態(tài)”。而且不只是能讓0 和1 同時(shí)存在，還可以在初始化時(shí)控制量子比特疊加態(tài)中0，1之間的占比，可以是20%的0 和80% 的1，也可以是70% 的0 和30%的1。量子計(jì)算中就是在操控量子比特，量子計(jì)算過程就是量子比特疊加態(tài)的演化過程。

　　量子比特

　　2）量子比特提升信息容量

　　從計(jì)算的本質(zhì)可見，提升計(jì)算能力的關(guān)鍵在于信息容量--即它代表了一個(gè)計(jì)算機(jī)的信息存儲(chǔ)能力。經(jīng)典比特提升信息容量空間的方法有兩種，第一種方法是追加物理資源，利用資源交換計(jì)算能力。第二種方法是把元器件越做越小，用更小的芯片存放更多的比特?cái)?shù)。但是到了今天，摩爾定律已經(jīng)到達(dá)極限而且線性增長計(jì)算能力的方法無法應(yīng)付按指數(shù)規(guī)模增長的問題。

　　量子比特增加信息容量的方法是采用了全新的編碼方式。我們通過利用量子疊加態(tài)的特性，能夠?qū)崿F(xiàn)更加高級(jí)的編碼方式，可以把這種編碼方式叫做“量子二進(jìn)制編碼”。由于量子疊加性，每一個(gè)量子比特同一時(shí)刻可以處在兩個(gè)不同的狀態(tài)上，這個(gè)“同時(shí)”帶來的好處十分明顯。

　　舉個(gè)淺顯的例子，假如有兩個(gè)人，一個(gè)人的10根手指是普通手指，另一個(gè)人的10根手指是量子手指。如果在他們面前只有一份蘋果的話，那么不論是普通手指還是量子手指都沒有差別，很容易表達(dá)出這份蘋果的分量或數(shù)量來。但是如果面前是兩份蘋果呢？那就完全不同了，普通手指只能表示其中一份，如果還想表示另外一份，那么就必須增加資源。他就需要再叫一個(gè)人過來，用那個(gè)人的手指表示第二份蘋果。這個(gè)時(shí)候量子手指就能顯出它的優(yōu)勢來了，因?yàn)榱孔邮种赣携B加狀態(tài)，所以通過編碼后，它就可以同時(shí)既表示第一份蘋果的個(gè)數(shù)，又同時(shí)表示第二份蘋果的個(gè)數(shù)。最厲害的是，就算是有1024份蘋果擺在面前，10根量子手指也能同時(shí)表示出來。經(jīng)典手指的話就必須找1024個(gè)人一起來才能完整表示。n個(gè)量子比特的信息容量比n個(gè)經(jīng)典比特大了2的n次方倍。目前探知整個(gè)宇宙原子的數(shù)量是2的300次方這么多，如果用量子比特表示的話，只需要300個(gè)就能數(shù)清宇宙所有的原子。

　?。?、量子計(jì)算發(fā)展歷程

　　１）量子力學(xué)發(fā)展史

　　1900年，德國物理學(xué)家普朗克提出量子概念，他假定光輻射與物質(zhì)相互作用時(shí)其能量不是連續(xù)的，而是一份一份的，一份“能量”就是所謂量子。從此“量子論”就宣告誕生。

　　1905年，愛因斯坦引進(jìn)光量子（光子）的概念，成功地解釋了光電效應(yīng)。其后，他又提出固體的振動(dòng)能量也是量子化的，從而解釋了低溫下固體比熱問題。

　　1925年，量子力學(xué)創(chuàng)始人之一的海森堡給出了量子力學(xué)的矩陣形式（矩陣力學(xué)），提出了“不確定性原理”（又稱“海森堡不確定性原理”），其后還發(fā)布了一部量子力學(xué)領(lǐng)域的經(jīng)典著作《量子論的物理學(xué)基礎(chǔ)》。

　　1926年薛定諤提出薛定諤方程，為量子力學(xué)奠定了堅(jiān)實(shí)的基礎(chǔ)。薛定諤方程是量子力學(xué)中描述微觀粒子運(yùn)動(dòng)狀態(tài)的基本定律，它在量子力學(xué)中的地位大致相似于牛頓運(yùn)動(dòng)定律在經(jīng)典力學(xué)中的地位。

　　除了以上這些科學(xué)家之外，還有很多科學(xué)家都為量子科學(xué)的研究發(fā)展做出了杰出的貢獻(xiàn)，各種量子力學(xué)定律、特性都逐步展示在了人類面前，下一步如何將這項(xiàng)技術(shù)轉(zhuǎn)化為社會(huì)生產(chǎn)力成為了后來者需要思考并解決的問題。

　　２）量子計(jì)算的發(fā)展史

　　雖然量子力學(xué)從20世紀(jì)初就逐步得到確立，但不同于經(jīng)典力學(xué)的漫長應(yīng)用過程，量子力學(xué)轉(zhuǎn)化為真正的社會(huì)技術(shù)進(jìn)程明顯較快。

　　一）20世紀(jì)80年代

　　1981年，20世紀(jì)成果最具豐富多彩的科學(xué)家、諾貝爾獎(jiǎng)獲得者Richard Feynman在量子計(jì)算領(lǐng)域提出了兩個(gè)問題，大大推動(dòng)了量子計(jì)算的發(fā)展。

　　第一個(gè)問題：經(jīng)典計(jì)算機(jī)是否能夠有效的模擬量子系統(tǒng)？雖然在量子理論中，仍用微分方程來描述量子系統(tǒng)的演化，但變量的數(shù)目卻遠(yuǎn)遠(yuǎn)多于經(jīng)典物理系統(tǒng)。所以費(fèi)曼針對(duì)這個(gè)問題的結(jié)論是：不可能。因?yàn)槟壳皼]有任何可行的方法，可以求解出這么多變量的微分方程。

　　第二個(gè)問題：如果我們放棄經(jīng)典的圖靈機(jī)模型，是否可以做得更好？他說如果我們拓展一下計(jì)算機(jī)的工作方式，不是使用邏輯門來建造計(jì)算機(jī)，而是一些其他的東西，比如分子和原子，如果我們使用這些量子材料，它們具有非常奇異的性質(zhì)，尤其是波粒二象性。是否能建造出模擬量子系統(tǒng)的計(jì)算機(jī)？于是他提出了這個(gè)問題，并做了一些驗(yàn)證性實(shí)驗(yàn)。然后他推測，這個(gè)想法也許可以實(shí)現(xiàn)。由此，基于量子力學(xué)的新型計(jì)算機(jī)的研究被提上了科學(xué)發(fā)展的歷程。此后，計(jì)算機(jī)科學(xué)家們一直在努力攻克這一艱巨挑戰(zhàn)。

　　1985年，David Deutsch描述了通用量子計(jì)算機(jī)，使得量子計(jì)算機(jī)的構(gòu)建更加清晰。

　　二）20世紀(jì)90年代

　　時(shí)間來到20世紀(jì)90年代，在這個(gè)年代里，量子計(jì)算機(jī)的算法發(fā)展有了巨大的進(jìn)步。

　　1992年，Deutsch–Jozsa提出了D-J量子算法。

　　1994年，Peter Shor 提出了的Shor算法，這一算法在大數(shù)分解方面比目前已知的最有效的經(jīng)典質(zhì)因數(shù)分解算法快得多，因此對(duì)RSA加密構(gòu)成極大威脅性，該算法帶來的巨大影響力同時(shí)也進(jìn)一步堅(jiān)定了科學(xué)家們發(fā)展量子計(jì)算機(jī)的決心。

　　1996年，Lov Grover提出了Grover量子搜索算法，該算法被公認(rèn)為繼shor算法后的第二大算法。

　　1998年，Bernhard Omer提出量子計(jì)算編程語言，拉開了量子計(jì)算機(jī)可編程的序章。

　　三）21世紀(jì)

　　2009年，MIT三位科學(xué)家聯(lián)合開發(fā)了一種求解線性系統(tǒng)的量子算法HHL。眾所周知，線性系統(tǒng)是很多科學(xué)和工程領(lǐng)域的核心，由于HHL算法在特定條件下實(shí)現(xiàn)了相較于經(jīng)典算法有指數(shù)級(jí)加速效果，從而未來能夠在機(jī)器學(xué)習(xí)、數(shù)值計(jì)算等場景有優(yōu)勢體現(xiàn)。配合Grover算法在數(shù)據(jù)方面的加速，業(yè)界認(rèn)為這將是未來量子機(jī)器學(xué)習(xí)、人工智等科技得以突破的關(guān)鍵性技術(shù)。

　　2013年，加拿大D-Wave系統(tǒng)公司發(fā)布了512Q的量子計(jì)算設(shè)備。

　　2016年，IBM發(fā)布了6量子比特的可編程的量子計(jì)算機(jī)。

　　2017年，本源量子發(fā)布了32位量子計(jì)算虛擬系統(tǒng)，同時(shí)還建立了以32位量子計(jì)算虛擬系統(tǒng)為基礎(chǔ)的本源量子云計(jì)算平臺(tái)。

　　2018年初，Intel和Google分別測試了49位和72位量子芯片。

　　隨著時(shí)間的前進(jìn)，人類在量子計(jì)算應(yīng)用發(fā)展的道路上行進(jìn)的速度也越來越快，量子計(jì)算全面爆發(fā)的時(shí)代或許很快就要到來。

　　2019年，我國中科大實(shí)現(xiàn)24位超導(dǎo)量子比特處理器，并進(jìn)行了多體量子系統(tǒng)模擬。

　　2019年，清華大學(xué)利用單量子比特實(shí)現(xiàn)了精度為98.8%的量子生成對(duì)抗網(wǎng)絡(luò)。

　　2019年1月，IBM展示了具有20位量子比特的超導(dǎo)量子計(jì)算機(jī)，并在9月將量子比特?cái)?shù)量更新為53位。

　　2019年10月，Google公司在《自然》雜志報(bào)道實(shí)現(xiàn)了基于53位量子比特的超導(dǎo)處理器，在解決隨機(jī)量子線路采樣特定計(jì)算問題時(shí)，具有遠(yuǎn)超過現(xiàn)有超級(jí)計(jì)算機(jī)的處理能力。

　　2020年9月1日，IBM發(fā)布了65個(gè)量子比特的量子計(jì)算機(jī)，并計(jì)劃于2023年發(fā)布1121量子比特的量子計(jì)算機(jī)…

　　三

　　量子計(jì)算機(jī)工作原理及實(shí)現(xiàn)模式

　　作為一個(gè)熱門概念，我們經(jīng)常聽到量子計(jì)算又有新突破的消息。但很少人清楚，今天的量子計(jì)算技術(shù)究竟走到了哪一步？到底有多少種實(shí)現(xiàn)量子計(jì)算的方式？

　　國外科技巨頭英特爾、微軟、IBM、谷歌，國內(nèi)巨頭阿里巴巴、騰訊、百度、華為等都認(rèn)為：量子計(jì)算的黃金時(shí)代即將到來！利用量子力學(xué)，為電腦運(yùn)算帶來指數(shù)級(jí)的巨幅加速即將實(shí)現(xiàn)！為此，大家都在向量子計(jì)算投入千萬美元的研發(fā)資金。其實(shí)，他們是在對(duì)不同的量子計(jì)算技術(shù)下賭注--沒有人知道采用哪種量子比特（qubit）能造出有實(shí)用價(jià)值的量子計(jì)算機(jī)。

　　1、Qbit的實(shí)現(xiàn)方法

　　量子計(jì)算的基礎(chǔ)和核心是量子比特的實(shí)現(xiàn)，量子比特相比傳統(tǒng)計(jì)算機(jī)比特更強(qiáng)大，是因?yàn)樗昧藘蓚€(gè)獨(dú)特的量子現(xiàn)象：疊加（superposition）和糾纏（entanglement）。量子疊加使量子比特能夠同時(shí)具有 0 和 1 的數(shù)值，可進(jìn)行“同步計(jì)算”（simultaneous computation）。量子糾纏使分處兩地的兩個(gè)量子比特能共享量子態(tài)，創(chuàng)造出超疊加效應(yīng)：每增加一個(gè)量子比特，運(yùn)算性能就翻一倍。

　　任何兩級(jí)量子力學(xué)系統(tǒng)都可以用作量子比特。如果多級(jí)系統(tǒng)具有可以有效地與其余狀態(tài)解耦的兩個(gè)狀態(tài)（例如，非線性振蕩器的基態(tài)和第一激發(fā)態(tài)），則也可以使用多級(jí)系統(tǒng)。

　　當(dāng)前實(shí)現(xiàn)量子比特的幾個(gè)典型物理方法有：

　　2、量子計(jì)算的實(shí)現(xiàn)方法

　　當(dāng)前已知的量子計(jì)算主流實(shí)現(xiàn)方式方法有：超導(dǎo)、離子囚禁、量子退火、硅量子點(diǎn)、量子光學(xué)、拓?fù)淞孔佑?jì)算等等幾種。

　　主流量子計(jì)算實(shí)現(xiàn)方式與廠家

　　1）超導(dǎo)

　　超導(dǎo)量子計(jì)算是利用超低溫“凍結(jié)”粒子的運(yùn)動(dòng)進(jìn)而實(shí)現(xiàn)粒子狀態(tài)的控制，量子比特有超導(dǎo)相位、超導(dǎo)磁通和超導(dǎo)電荷三種形式。超導(dǎo)量子計(jì)算的核心單元是約瑟夫森結(jié)，約瑟夫森結(jié)是一種“超導(dǎo)體—絕緣體—超導(dǎo)體”的三層結(jié)構(gòu)。利用超導(dǎo)約瑟夫森結(jié)來觀測宏觀量子現(xiàn)象最早由 Leggett 于1985 年提出，隨后研究人員在超導(dǎo)約瑟夫森結(jié)器件中陸續(xù)觀測并實(shí)現(xiàn)了能級(jí)量子化、量子隧穿、量子態(tài)疊加、量子相干振蕩等現(xiàn)象。

　　超導(dǎo)量子計(jì)算是目前進(jìn)展最快最好的一種固體量子計(jì)算實(shí)現(xiàn)方法。由于超導(dǎo)量子電路的能級(jí)結(jié)構(gòu)可通過外加電磁信號(hào)進(jìn)行調(diào)控，電路的設(shè)計(jì)定制的可控性強(qiáng)。同時(shí)，得益于基于現(xiàn)有的成熟集成電路工藝， 超導(dǎo)量子電路具有多數(shù)量子物理體系難以比擬的可擴(kuò)展性。但是在實(shí)現(xiàn)超導(dǎo)量子比特體系過程中，由于量子體系的不可封閉性，環(huán)境噪聲、磁通型偏置噪聲等大量不易操控的自由度導(dǎo)致耗散和退相干。此外，超導(dǎo)量子系統(tǒng)工作對(duì)物理環(huán)境要求極為苛刻（超低溫）均是超導(dǎo)量子計(jì)算實(shí)現(xiàn)過程中不可避免的問題。

　　超導(dǎo)路線是谷歌的主選，也是目前業(yè)界最熱的量子計(jì)算實(shí)現(xiàn)方向。谷歌超導(dǎo)量子計(jì)算開始于雇傭了加州大學(xué)圣芭芭拉分校（University of California, Santa Barbara）的超導(dǎo)量子比特專家 John Martinis，他研究過 D-Wave 的量子退火運(yùn)行方式和缺陷。在 2014 年，谷歌把整個(gè)加州大學(xué)圣芭芭拉分校研究團(tuán)隊(duì)的全部十幾個(gè)人都給招募了。這之后，John Martinis 團(tuán)隊(duì)宣布，他們已經(jīng)建成了 9 量子比特的機(jī)器，是當(dāng)時(shí)世界上可編程的量子計(jì)算機(jī)中最大的之一，而且他們一直試圖擴(kuò)大規(guī)模。為了避免大堆纏繞的電線，他們?cè)?2D 平面結(jié)構(gòu)上重建系統(tǒng)，系統(tǒng)鋪設(shè)在一塊晶圓上，所有控制電路都蝕刻在上面。

　　John Martinis 團(tuán)隊(duì)工程師開始是用三個(gè)超導(dǎo)量子比特來模擬氫分子的基態(tài)（ground state）能量，這展示在模擬簡單的量子系統(tǒng)上量子計(jì)算機(jī)可以做到和傳統(tǒng)計(jì)算機(jī)一樣好。Martinis團(tuán)隊(duì)一年后造出 49 量子比特計(jì)算機(jī)，并于2019年造出了擁有53量子比特的“量子霸權(quán)”計(jì)算設(shè)備，并帶動(dòng)整個(gè)業(yè)界研究熱點(diǎn)向超導(dǎo)量子計(jì)算方向聚焦。

　　2）離子囚禁

　　離子阱的技術(shù)原理是利用電荷與電磁場間的交互作用力牽制帶電粒子體運(yùn)動(dòng)，并利用受限離子的基態(tài)和激發(fā)態(tài)組成的兩個(gè)能級(jí)作為量子比特。盡管離子阱技術(shù)本身的發(fā)展可以追溯到 1980 年，但是利用離子阱技術(shù)實(shí)現(xiàn)量子計(jì)算是由奧地利奧地利因斯布魯克大學(xué)（Innsbruck） Blatt 實(shí)驗(yàn)室的 Circa 和 Zoller 于 1995 年首次提出的。2003年，該實(shí)驗(yàn)室實(shí)現(xiàn)利用失諧激光束照射和激光冷卻控制非門，同年該實(shí)驗(yàn)室第一次成功地利用離子阱技術(shù)實(shí)現(xiàn)了Deutsch-Jozsa 算法。離子阱量子計(jì)算具有量子比特品質(zhì)高、相干時(shí)間較長以及量子比特的制備和讀出效率較高三大特點(diǎn)。

　　然而，離子阱技術(shù)目前仍面臨四大難點(diǎn)：一是離子阱暫時(shí)難以儲(chǔ)存多條離子鏈；二是由于外加激光強(qiáng)度、頻率及相位的不穩(wěn)定，且離子對(duì)電場噪聲敏感導(dǎo)致的消相干問題；三是可擴(kuò)展性差；四是體積龐大，小型化尚需時(shí)日。目前開展離子阱量子計(jì)算技術(shù)研究的有 IonQ、NIST、Sandia National Lab、ETH。IonQ于2018年12月11日公布了兩個(gè)新型離子阱量子計(jì)算機(jī)，具有 160 個(gè)存儲(chǔ)量子比特，可實(shí)現(xiàn) 79 個(gè)量子比特長度上的單比特門操縱，11比特長度雙比特操縱。保真度方面，單比特平均保真度 99%，雙比特平均保真度 98%。

　　3）量子退火

　　2007年，加拿大初創(chuàng)公司 D-Wave Systems 宣布，他們使用16個(gè)超導(dǎo)量子比特成功制成量子計(jì)算機(jī)，一舉震驚了世界。但是 D-Wave 的機(jī)器并沒有使所有的量子比特發(fā)生糾纏，并且不能一個(gè)量子比特接著一個(gè)量子比特地編程（be programmed qubit by qubit），而是另辟蹊徑，使用了一項(xiàng)名為“量子退火”（quantum annealing）的技術(shù)。該技術(shù)下，每個(gè)量子比特只和臨近的量子比特糾纏并交互，這并沒有建立起一組并行計(jì)算，而是一個(gè)整體上的、單一的量子狀態(tài)。D-Wave 開發(fā)者希望把復(fù)雜的數(shù)學(xué)問題映射到該狀態(tài)，然后使用量子效應(yīng)尋找最小值。對(duì)于優(yōu)化問題（比如提高空中交通效率的）來說，這是一項(xiàng)很有潛力的技術(shù)。

　　但批評(píng)者們指出：D-Wave 并沒有攻克許多公認(rèn)的量子計(jì)算難題，比如錯(cuò)誤修正（error correction）。包括谷歌和洛克希德馬丁在內(nèi)的幾家公司，購買并測試了 D-Wave 的設(shè)備，他們初步的共識(shí)是--D-Wave 做到了一些能稱之為量子計(jì)算的東西，而且，在處理一些特定任務(wù)時(shí)，他們的設(shè)備確實(shí)比傳統(tǒng)計(jì)算機(jī)要快。

　　4）半導(dǎo)體量子點(diǎn)

　　半導(dǎo)體量子點(diǎn)也是基于現(xiàn)有半導(dǎo)體工藝的一種量子計(jì)算物理實(shí)現(xiàn)方法。在平面半導(dǎo)體電子器件上制備出單電子晶體管，其電子服從量子力學(xué)運(yùn)動(dòng)規(guī)律，電子自旋的向上和向下組成的系統(tǒng)可作為一個(gè)量子比特。根據(jù)電子的泡利不相容原理，通過自旋和電荷之間的關(guān)聯(lián)，可以通過普通的電子開關(guān)（門）對(duì)電子自旋進(jìn)行控制，完成包括單量子比特操作、兩量子比特操作及結(jié)果的讀出等在內(nèi)的對(duì)電子自旋編碼的量子比特的各種操作。

　　半導(dǎo)體量子點(diǎn)體系具有良好的可擴(kuò)展性，量子點(diǎn)的原子性質(zhì)可以通過納米加工技術(shù)和晶體生長技術(shù)來人為調(diào)控，比一般的量子體系更容易集成。此外，半導(dǎo)體量子點(diǎn)的制備可與現(xiàn)有半導(dǎo)體芯片工藝完全兼容，因而成熟的傳統(tǒng)半導(dǎo)體工藝可為半導(dǎo)體量子點(diǎn)的技術(shù)實(shí)現(xiàn)與后續(xù)部署帶來極大便利。但是半導(dǎo)體量子點(diǎn)體系受周圍核自旋影響嚴(yán)重，面臨退相干以及保真度不足兩大挑戰(zhàn)。

　　技術(shù)進(jìn)展方面，荷蘭代爾夫特大學(xué)的 Kouwenhoven 團(tuán)隊(duì)于2004年在半導(dǎo)體器件上首次實(shí)現(xiàn)了自旋量子比特的制備。3年后，代爾夫特大學(xué)的Vanderspyen團(tuán)隊(duì)在同一塊半導(dǎo)體量子點(diǎn)器件上實(shí)現(xiàn)了量子比特制備、量子邏輯門操作、量子相干與測量等自旋量子計(jì)算的全部基本要素。2014年新南威爾士大學(xué)獲得了退相干時(shí)間120微秒、保真度99.6%的自旋量子比特。2015年，英特爾宣布將向荷蘭代爾夫特理工大學(xué)的量子技術(shù)研究項(xiàng)目QuTech 投資 5000 萬美元。2017年，日本理化研究所在硅鍺系統(tǒng)上獲得了退相干時(shí)間達(dá)到20微秒、保真度超過 99.9%的量子比特。2018年中國科技大學(xué)郭光燦院士團(tuán)隊(duì)制備了半導(dǎo)體6量子點(diǎn)芯片，并實(shí)現(xiàn)了3量子比特的Toffoli 門操控，成為國際上首個(gè)在半導(dǎo)體量子點(diǎn)體系中實(shí)現(xiàn)的3量子比特邏輯門。

　　不同于離子或原子，量子點(diǎn)不需要激光來困住它。但是基于硅的量子比特研究大大落后于囚禁離子和超導(dǎo)量子技術(shù)。

　　5）量子光學(xué)

　　光學(xué)量子計(jì)算（OQC）是基于測量的量子計(jì)算方案，利用光子的偏振或其他自由度作為量子比特。光子是一種十分理想的量子比特的載體，以常用的量子光學(xué)手段就可實(shí)現(xiàn)量子操作。光學(xué)量子計(jì)算根據(jù)其物理架構(gòu)分為兩種：KLM 光學(xué)量子計(jì)算以及團(tuán)簇態(tài)光學(xué)量子計(jì)算。KLM 光學(xué)量子計(jì)算僅使用單光子、線性光學(xué)和測量，允許通過和可擴(kuò)展光學(xué)量子計(jì)算，目前已經(jīng)實(shí)現(xiàn)了光子-光子之間的兩量子位的邏輯操作。團(tuán)簇態(tài)光學(xué)量子計(jì)算由一個(gè)高度糾纏的成為團(tuán)簇態(tài)的多粒子態(tài)組成，與單量子測量和前饋相結(jié)合，實(shí)現(xiàn)可擴(kuò)展的通用量子計(jì)算，具有降低整體復(fù)雜性、放寬測量過程的物理要求，以及更有效利用物理資源等技術(shù)優(yōu)勢。

　　由于光子與環(huán)境相互作用很小，光學(xué)量子計(jì)算具有相干時(shí)間長、操控手段簡單、與光纖和集成光學(xué)技術(shù)相兼容，以及簡單的資源可擴(kuò)展性等優(yōu)點(diǎn)。但也正是由于光子之間相互作用微乎其微，導(dǎo)致兩量子比特之間的邏輯門操作難以實(shí)現(xiàn)。技術(shù)進(jìn)展方面，目前中國研究團(tuán)隊(duì)已經(jīng)在實(shí)驗(yàn)室產(chǎn)生了同時(shí)具備高系統(tǒng)效率（33%）、高純度（97%）和高全同性（90%）的高品質(zhì)單光子源和基于參量下轉(zhuǎn)換的10光子糾纏。在此基礎(chǔ)上，光學(xué)量子計(jì)算的基本操作（如概率性的控制邏輯門）和各種算法（大數(shù)分解算法、數(shù)據(jù)庫搜索、線性方程組求解算法、機(jī)器學(xué)習(xí)、波色取樣）的簡單演示驗(yàn)證也已經(jīng)實(shí)現(xiàn)。在光學(xué)量子計(jì)算可集成研究方面，麻省理工學(xué)院、牛津大學(xué)、布里斯托大學(xué)、維也納大學(xué)、昆士蘭大學(xué)等小組基于硅光子學(xué)、鈮酸鋰波導(dǎo)、二氧化硅波導(dǎo)等平臺(tái)，通過刻蝕或激光直寫等方式產(chǎn)生10個(gè)通道左右的量子線路用于少數(shù)光子數(shù)的原理性研究。單光子探測方面，美國國家技術(shù)標(biāo)準(zhǔn)局、荷蘭代爾夫特大學(xué)等機(jī)構(gòu)已經(jīng)可以生產(chǎn)同時(shí)具備高探測效率（93%）、高重復(fù)頻率（150MHz）的超導(dǎo)納米線單光子探測器。

　　6）拓?fù)淞孔?/p>

　　拓?fù)淞孔佑?jì)算建立在全新的計(jì)算思路之上，應(yīng)用任意子的交換相位、交換過程的“編辮”程序?qū)崿F(xiàn)量子計(jì)算的信息處理。拓?fù)鋵W(xué)研究幾何形象在幾何元素的連續(xù)變形下保持不變的性質(zhì)。如果構(gòu)成量子比特的元素是拓?fù)洳蛔兊?，基于這些量子比特的運(yùn)算結(jié)果也具有拓?fù)洳蛔冃?。由此?gòu)造的量子計(jì)算對(duì)環(huán)境干擾、噪音、雜質(zhì)有很大的抵抗能力。但拓?fù)淞孔佑?jì)算尚停留在理論層面，實(shí)際上還未把這些理論付諸成器件化的現(xiàn)實(shí)。

　　拓?fù)淞孔邮俏④浀倪x擇路線，它基于非阿貝爾任意子（nonabelian anyons）的拓?fù)淞孔颖忍兀╰opological qubits）。這些根本就不是物體，它們是沿著不同物質(zhì)邊緣游動(dòng)的準(zhǔn)粒子（quasiparticles）。量子態(tài)由不同交叉路線（braiding Paths）來表現(xiàn)。因?yàn)榻徊媛肪€的形狀導(dǎo)致了量子疊加，它們會(huì)受到拓?fù)浔Ｗo(hù)（topologically protected）而不至于崩潰，這類似于打結(jié)的鞋帶不會(huì)散開一樣。。

　　理論上拓?fù)淞孔佑?jì)算機(jī)不需要在錯(cuò)誤修正上花費(fèi)那么多量子比特。早在2005年，微軟帶領(lǐng)的一支研究團(tuán)隊(duì)就提出了一種在半導(dǎo)體-超導(dǎo)體混合結(jié)構(gòu)中建造拓?fù)浔Ｗo(hù)量子比特的方法。微軟已經(jīng)投資了數(shù)個(gè)團(tuán)隊(duì)進(jìn)行嘗試，他們近期的論文還有貝爾實(shí)驗(yàn)室的一項(xiàng)獨(dú)立研究都展示了關(guān)鍵的任意子以電路中電流的模式進(jìn)行移動(dòng)的“征兆”，這已經(jīng)很接近展示真正的量子比特了?？茖W(xué)家Preskill 說：“我認(rèn)為在一兩年內(nèi)，我們就可以看到結(jié)果--拓?fù)淞孔颖忍卮_實(shí)存在”。

　　3、量子計(jì)算實(shí)現(xiàn)中面臨的主要問題

　　量子計(jì)算理論已經(jīng)相對(duì)成熟，但實(shí)現(xiàn)中面臨著眾多棘手難題，甚至許多難題眼下還處于無解的狀態(tài)，最突出的問題主要有以下幾個(gè)方面：

　　1）量子比特本身不能抑制噪聲

　　傳統(tǒng)計(jì)算機(jī)和量子計(jì)算機(jī)之間的主要區(qū)別之一是它如何處理系統(tǒng)中很小的、不需要的變化或噪聲。由于傳統(tǒng)比特位是1或0，因此即使該值略有偏離（系統(tǒng)中存在一些噪聲），對(duì)該信號(hào)進(jìn)行的運(yùn)算也很容易消除該噪聲。實(shí)際上，當(dāng)今的構(gòu)建計(jì)算機(jī)的傳統(tǒng)邏輯門只能在比特位上操作，具有很大的噪聲余量--它們可以抑制輸入中的大變化并仍然產(chǎn)生無噪聲的輸出，但是量子比特容錯(cuò)率卻極低。

　　因?yàn)榱孔游豢梢允且缓土愕娜魏谓M合，這當(dāng)中涉及到相位。所以量子位和量子門不能輕易地抑制物理電路中出現(xiàn)的小錯(cuò)誤（噪聲）。這就使得在創(chuàng)建所需的量子運(yùn)算時(shí)一旦出現(xiàn)小錯(cuò)誤，或者耦合到物理系統(tǒng)中存在任何雜散信號(hào)，最終都會(huì)導(dǎo)致在計(jì)算中出現(xiàn)錯(cuò)誤的輸出。因此，對(duì)于在物理量子位上運(yùn)行的系統(tǒng)來說，最重要的設(shè)計(jì)參數(shù)之一就是錯(cuò)誤率。低錯(cuò)誤率目前很難實(shí)現(xiàn)，即使在2018年底，具有5個(gè)或更多量子比特的系統(tǒng)上，量子比特操作的錯(cuò)誤率也超過百分之幾。雖然在比特位較小的系統(tǒng)中已經(jīng)證明了可以實(shí)現(xiàn)更低的錯(cuò)誤率，但是這種改進(jìn)的操作保真度需要轉(zhuǎn)移到較大的量子比特系統(tǒng)上，量子計(jì)算才能成功。

　　2）無誤差量子計(jì)算需要量子錯(cuò)誤校正

　　既然降噪難度這么大，那可不可以發(fā)展一個(gè)糾錯(cuò)方式呢？盡管量子位操作對(duì)噪聲敏感，但是我們可以在物理量子計(jì)算機(jī)上運(yùn)行量子錯(cuò)誤校正（QEC）算法，以模擬無噪聲或“完全錯(cuò)誤校正”的量子計(jì)算機(jī)。如果沒有QEC，復(fù)雜的量子程序（例如實(shí)現(xiàn)Shor算法的程序）不太可能在量子計(jì)算機(jī)上正確運(yùn)行。但是，目前發(fā)現(xiàn)QEC在模擬和執(zhí)行方面都會(huì)產(chǎn)生大量損耗。盡管QEC對(duì)于將來創(chuàng)建無誤差的量子計(jì)算機(jī)至關(guān)重要，但它們需要的資源過于龐大，無法在短期內(nèi)使用。這就是說，在短期內(nèi)量子計(jì)算機(jī)的計(jì)算還是會(huì)出錯(cuò)。

　　3）大數(shù)據(jù)輸入不能被高效載入至量子計(jì)算機(jī)

　　雖然量子計(jì)算機(jī)可以使用少量的量子位來表示大量的數(shù)據(jù)，但目前尚沒有一種將大量經(jīng)典數(shù)據(jù)快速轉(zhuǎn)換為量子狀態(tài)的方法（除非可以生成數(shù)據(jù)）。對(duì)于需要大量輸入的問題，創(chuàng)建輸入量子狀態(tài)所需的時(shí)間通常要占據(jù)計(jì)算時(shí)間，并大大降低量子優(yōu)勢。

　　4）量子算法設(shè)計(jì)難度較大

　　測量量子計(jì)算機(jī)的狀態(tài)會(huì)將大的量子狀態(tài)“坍縮”成單個(gè)經(jīng)典結(jié)果。這意味著一個(gè)人只能從一臺(tái)量子計(jì)算機(jī)中提取與從相同大小的經(jīng)典計(jì)算機(jī)中可以提取的數(shù)據(jù)數(shù)量一樣。為了獲得量子計(jì)算機(jī)的好處，量子算法必須獨(dú)特地利用諸如干擾和糾纏之類的量子特征才能獲得最終的經(jīng)典結(jié)果。因此，要實(shí)現(xiàn)量子加速，就需要全新的算法設(shè)計(jì)原理和非常聰明的算法設(shè)計(jì)，量子算法的開發(fā)成為關(guān)鍵。

　　5）量子計(jì)算機(jī)將需要一個(gè)全新的軟件棧

　　與所有計(jì)算機(jī)一樣，構(gòu)建有用的設(shè)備比僅創(chuàng)建硬件要復(fù)雜得多，需要工具來創(chuàng)建和調(diào)試特定于量子計(jì)算機(jī)的軟件。由于量子程序與傳統(tǒng)計(jì)算機(jī)程序不同，因此需要進(jìn)行研究和開發(fā)以進(jìn)一步開發(fā)軟件工具堆棧。由于這些軟件工具驅(qū)動(dòng)硬件，因此硬件和軟件工具鏈的同時(shí)開發(fā)才能縮短量子計(jì)算機(jī)的開發(fā)時(shí)間。目前量子計(jì)算機(jī)軟件設(shè)計(jì)的思路依然是參考了經(jīng)典計(jì)算機(jī)設(shè)計(jì)中使用的方法，這可能與量子計(jì)算機(jī)硬件并不匹配。

　　6）量子計(jì)算機(jī)的中間態(tài)無法被直接測量

　　調(diào)試量子硬件和軟件的方法至關(guān)重要。當(dāng)前用于經(jīng)典計(jì)算機(jī)的調(diào)試方法依賴于內(nèi)存和中間計(jì)算機(jī)狀態(tài)的讀取。在量子計(jì)算機(jī)中，這都是不可能的。按照不可克?。╪o-cloning）定理，量子狀態(tài)不可以像傳統(tǒng)邏輯門扇出（fanout）那樣簡單復(fù)制以供以后檢查，并且對(duì)量子狀態(tài)的任何測量都會(huì)將其坍縮為一組經(jīng)典比特，從而使計(jì)算停止。新的調(diào)試方法對(duì)于大規(guī)模量子計(jì)算機(jī)的開發(fā)至關(guān)重要。

　　7）從理論到工程跨域?qū)崿F(xiàn)困難

　　通常來講，通用量子計(jì)算做到更多比特主要是硬件上的困難，理論上像大家常說的那樣，并沒有特別基礎(chǔ)的難題需要解決（當(dāng)然理論方面也有很多開放性的問題存在）。

　　工程實(shí)現(xiàn)上問題存在兩部分，一個(gè)是量子糾纏到更多比特級(jí)別，另一個(gè)是量子計(jì)算到更多級(jí)別。

　　就前者來說，量子糾纏現(xiàn)在最多的比如像超導(dǎo)比特有谷歌的53比特，數(shù)量越往上難度指數(shù)級(jí)增加，畢竟如果一個(gè)比特坍塌是e^-\gamma那在沒有校正的情況下N個(gè)就是e^-N\Gamma，針對(duì)不同的硬件有不同的噪聲模型。

　　對(duì)于后者來說，量子計(jì)算做到更多比特，這里指的是通用的甚至容錯(cuò)的量子計(jì)算，而不是特指像退火那種。問題或許可以拆成幾部分，一個(gè)是怎么做到這么多比特，一個(gè)是怎么保證比特性質(zhì)，不同系統(tǒng)有不同的答案，總體來說像超導(dǎo)比特/離子阱在這方面現(xiàn)在是走在前列的，其他的如原子陣列（很多方面跟離子阱蠻像的……）、光學(xué)平臺(tái)、量子點(diǎn)、半導(dǎo)體缺陷等也各有千秋。

　　以超導(dǎo)比特為例，如何做到這么多比特？去年谷歌公司用53個(gè)比特實(shí)現(xiàn)了所謂的量子霸權(quán)，即在采樣問題上對(duì)經(jīng)典的超越。很多人會(huì)說從50+到更高沒有什么基礎(chǔ)性的困難，更多的是工程上的問題，但這“工程上的問題”已經(jīng)足夠艱巨了： 比特?cái)?shù)目多了用什么來布局？稀釋制冷機(jī)空間夠不夠？比特之間的相互干擾怎么解決？由遠(yuǎn)至近的交互怎么控制？還有單獨(dú)控制需要的任意波形發(fā)生器、合成器、放大器、交換機(jī)之類的東西就夠放滿一屋子了…，這些還只是談到怎么造出這么多比特而沒有談?wù)摫忍氐男再|(zhì)如何。

　　而說到比特的性質(zhì)，最值得關(guān)心的就是退相干。T1（Relaxation）/T2（Dephasing）這些關(guān)系到電路深度、關(guān)系到可以增加多少運(yùn)算。T1/T2目前最高的大概是幾百us，而尺寸增加幾十個(gè)的話一般T1/T2也就幾十us。像目前IBM Quantum Experience online的單比特性能最好是T1/T2大約150us。超導(dǎo)系統(tǒng)相干性質(zhì)更好的其實(shí)是空穴模型，把邏輯比特給編碼到空穴的玻色子態(tài)上，然后利用一些對(duì)稱性來做量級(jí)糾錯(cuò)（QEC），進(jìn)而實(shí)現(xiàn)其相干時(shí)間的延長（比如從~150us到300+us），到達(dá)所謂的臨界點(diǎn)。但問題是做幾個(gè)邏輯比特還好，但是3D腔這種東西太大了怎么增加尺寸？不大的話噪音又大且性質(zhì)又不好。

　　即使有了尺寸增大且控制還好，要實(shí)現(xiàn)容錯(cuò)計(jì)算的話，對(duì)保真度要求很高，畢竟不想在糾錯(cuò)的過程中又出錯(cuò)。目前別說容錯(cuò)量子計(jì)算機(jī)了，事實(shí)上連一個(gè)容錯(cuò)的邏輯比特都還很難實(shí)現(xiàn)。超導(dǎo)方面單比特的控制做到99.9%沒問題，兩比特門的話可以做到99%，但是再往上實(shí)在太困難了（多比特的裝置）。

　　還有一個(gè)挑戰(zhàn)是理論和實(shí)踐雙方怎么更好地合作的問題，雙方隔閡比較大，關(guān)注的問題不同，也許某個(gè)方向上理論上的進(jìn)展并不適合實(shí)踐方的工程實(shí)現(xiàn)，雙方目標(biāo)不同、努力的方向也存在一定分歧。

　　綜上，挑戰(zhàn)和困難太多以至于很多人不看好，但是如果真能有一天做到很多比特，那意義極大。這種誘惑就像要你一個(gè)人穿越一片沙漠，穿過去是幾輩子花不完的財(cái)富，穿不過去也能積累經(jīng)驗(yàn)探索未知，因此激勵(lì)著大家瘋狂投入?yún)⑴c其中。

　　四

　　量子計(jì)算機(jī)給密碼算法帶來的威脅

　　量子計(jì)算這種超大規(guī)模的并行計(jì)算能力，對(duì)于處理日常任務(wù)其實(shí)沒什么用。沒有人認(rèn)為量子計(jì)算機(jī)會(huì)顛覆文字處理和 email等日常應(yīng)用，但對(duì)于需要同時(shí)探索無數(shù)條路徑的算法，還有對(duì)海量數(shù)據(jù)庫的搜索，量子計(jì)算能極大地提高速度。它能被用來尋找新的化學(xué)催化劑、對(duì)加密數(shù)據(jù)的海量數(shù)字作因子分解（factoring），或許還能模擬黑洞和其他物理現(xiàn)象。

　　雖然量子計(jì)算的理論在 1980 年代就開始出現(xiàn)，直到 1995 年才有了第一次實(shí)驗(yàn)。貝爾實(shí)驗(yàn)室的數(shù)學(xué)家 Peter Shor，向人們展示量子計(jì)算機(jī)可以對(duì)大量數(shù)字快速因子分解—一旦實(shí)現(xiàn)，這會(huì)使現(xiàn)代密碼學(xué)的公鑰過時(shí)。Peter Shor 和其他人還展示了使用臨近量子比特修正錯(cuò)誤，讓脆弱的量子比特永遠(yuǎn)保持穩(wěn)定狀態(tài)在理論上是可能的。

　　1、Shor算法

　　1994年，美國麻省理工學(xué)院的彼得？肖爾（Peter Shor）發(fā)表了一篇論文，題為《量子計(jì)算機(jī)上的質(zhì)因數(shù)分解和離散對(duì)數(shù)的多項(xiàng)式時(shí)間算法》（Polynomial Time Algorithms for Prime Factorisation and Discrete Logarithms on a Quantum Computer）。這篇論文被認(rèn)為是一劑催化劑，催生了一場延續(xù)至今的建造量子計(jì)算機(jī)的競賽。本質(zhì)上說，通過使用量子并行處理，肖爾算法（Shor's Algorithm）使量子計(jì)算機(jī)上的大整數(shù)的因式分解比在經(jīng)典計(jì)算中使用已知最快的算法還要快出很多。更精確地說，肖爾算法差不多可以在多項(xiàng)式時(shí)間內(nèi)因式分解N比特整數(shù)，與此相比，在經(jīng)典計(jì)算中最有效的算法（稱作廣義數(shù)域篩法，縮寫為GNFS）則差不多需要指數(shù)級(jí)的更長時(shí)間。

　　Shor算法的效率歸因于量子傅立葉變換的效率，以及通過重復(fù)平方的模冪運(yùn)算。如果具有足夠數(shù)量的量子位的量子計(jì)算機(jī)可以在解決了量子噪聲和其他量子退相干現(xiàn)象的情況下運(yùn)行，那么Shor的算法可以用于打破公鑰加密方案，例如廣泛使用的RSA。

　　在肖爾算法使用量子計(jì)算的性質(zhì)之前，來自經(jīng)典數(shù)論的一些結(jié)果已經(jīng)被用來恰當(dāng)?shù)靥幚磉@個(gè)問題。肖爾算法的特別之處在于，它使用模運(yùn)算中的周期性的概念--對(duì)我們要因式分解的數(shù)N進(jìn)行模運(yùn)算，一個(gè)數(shù)x必須被自身乘多少次a才能得出答案是（也就是xamod N =1），找到這個(gè)周期就使我們能對(duì)N進(jìn)行分解。

　　確定這個(gè)函數(shù)的周期正是量子計(jì)算的性質(zhì)發(fā)揮作用的地方，特別是準(zhǔn)確地引入量子并行處理這一概念。我們使用兩個(gè)量子存儲(chǔ)寄存器--第一個(gè)被放置在所有a（a的范圍是從0到q，其中q是2的指數(shù)倍，并且滿足N2< q < 2N2）的可能值的疊加態(tài)上。注意，這個(gè)寄存器必須有足夠的量子比特來表示這個(gè)大小的整數(shù)，比如說，如果N是一個(gè)2048比特?cái)?shù)（RSA模數(shù)的典型大?。俏覀兙托枰蠹s4000個(gè)量子比特。在第一個(gè)寄存器中，會(huì)用到以N為模的函數(shù)xa，而結(jié)果會(huì)被存儲(chǔ)在第二個(gè)寄存器中（在這一步中，我們利用了量子并行處理的性質(zhì)）。

　　接下來，第二個(gè)寄存器會(huì)被測量，這意味著第二個(gè)寄存器從疊加態(tài)塌縮到某個(gè)值k。第一個(gè)寄存器也隨之塌縮，和第二個(gè)寄存器保持一致--但是對(duì)a的每個(gè)值，進(jìn)行相等的疊加使得xamod N = k。最終，一個(gè)叫作離散傅里葉變換的運(yùn)算被應(yīng)用到第一個(gè)寄存器上，得到的m就有很大可能性是這個(gè)周期的倍數(shù)。一旦得到m，在經(jīng)典計(jì)算機(jī)上使用一些相關(guān)的簡單數(shù)論就可以先找到這個(gè)周期，然后是N的因式分解。

　　簡而言之，Shor算法由兩步組成，該算法的第一步是將大數(shù)分解問題轉(zhuǎn)化為尋找函數(shù)周期的問題，并且可以經(jīng)典地實(shí)現(xiàn)。第二步是使用量子傅立葉變換找到周期，并負(fù)責(zé)量子加速。

　　2、Grover算法

　　1996 年，同在麻省理工貝爾實(shí)驗(yàn)室的格羅弗提出了格羅弗搜索算法（Grover's Algorithm），格羅弗算法的實(shí)現(xiàn)基于概率幅度放大。與其他的量子算法相同，格羅弗算法亦是概率性的。該算法為數(shù)據(jù)庫搜索算法，數(shù)據(jù)庫相當(dāng)于是一張存有未知函數(shù)的所有輸出值的表，以對(duì)應(yīng)的輸入值為索引。

　　量子計(jì)算的格羅弗搜索算法遠(yuǎn)超出了經(jīng)典計(jì)算機(jī)的數(shù)據(jù)搜索速度，但不像其他的量子算法可能會(huì)比相應(yīng)的經(jīng)典算法有指數(shù)級(jí)的加快，格羅弗算法對(duì)許多計(jì)算問題的傳統(tǒng)算法呈現(xiàn)平方加速。即便如此，加速程度也相當(dāng)可觀！對(duì)格羅弗算法舉一個(gè)例子來理解如下：假如我們有10000個(gè)盒子，并且隨機(jī)地把一個(gè)物品藏在其中一個(gè)盒子里。如果我們讓某個(gè)人去找到這個(gè)物品，那么他們將最多不得不打開所有10000個(gè)盒子才能確定找到這個(gè)物品（這個(gè)物品也許正好被藏在他們決定最后一個(gè)打開的盒子里）。平均來說，我們可能不得不打開盒子數(shù)量的一半才能找到被藏起來的物品，也就是找5000次。然而，使用格羅弗算法，我們實(shí)際上可以在0.758圖片次運(yùn)算中就找到結(jié)果。在這個(gè)例子中，這意味著我們找75.8次（0.758 * 圖片）就可以找到這個(gè)物品！

　　這種算法的力量與窮舉搜索攻擊有關(guān)。正如我們可以回想起來的，窮舉搜索攻擊就是檢查每一個(gè)密鑰的單值來看看那個(gè)密鑰是否解碼了一條信息。使用格羅弗算法，我們可以極大地加速窮舉搜索攻擊的過程——例如對(duì)于一個(gè)長度為128比特的密鑰來說，使用格羅弗算法的話，一次窮舉搜索攻擊可以在 圖片= 264次內(nèi)完成。同樣，一臺(tái)可以運(yùn)行格羅弗算法的量子計(jì)算機(jī)將意味著某些標(biāo)準(zhǔn)的密鑰長度需要增加，特別是AES 128比特不再被認(rèn)為是安全的，而是需要AES 256比特的密鑰。

　　一個(gè)很自然的問題是，我們距離一臺(tái)有能力大規(guī)模運(yùn)行肖爾算法或者格羅弗算法的量子計(jì)算機(jī)有多遠(yuǎn)呢？目前，在建最強(qiáng)大的通用量子計(jì)算機(jī)的數(shù)量級(jí)在100量子比特以內(nèi)。而正如我們?cè)谟懻撔査惴〞r(shí)看到的那樣，一臺(tái)量子計(jì)算機(jī)大概需要4000個(gè)邏輯量子比特才能因式分解一個(gè)2048比特的RSA數(shù)。

　　五

　　密碼界面對(duì)威脅的應(yīng)對(duì)

　　面對(duì)量子計(jì)算突飛猛進(jìn)的威脅，密碼學(xué)界以美國國家標(biāo)準(zhǔn)與技術(shù)研究院（NIST）為首，早早就開始了應(yīng)對(duì)布局，全面開展了一種公開的程序挑選一個(gè)或多個(gè)公鑰密碼算法的進(jìn)程。這些新的公鑰密碼標(biāo)準(zhǔn)將為數(shù)字簽名、公鑰密碼以及密鑰建立算法規(guī)定一個(gè)或多個(gè)另外的算法。新標(biāo)準(zhǔn)將對(duì)FIPS 186-4（數(shù)字簽名標(biāo)準(zhǔn)（DSS））以及特別出版物800-56A版本3（使用離散對(duì)數(shù)密碼的雙序密鑰建立方案建議）和SP 800-56B（使用整數(shù)因子分解的雙序密鑰建立方案建議）進(jìn)行擴(kuò)充。NIST的意圖是，在可以預(yù)見的未來，包括量子計(jì)算機(jī)出現(xiàn)之后，這些算法將能夠保護(hù)美國政府的敏感信息，這個(gè)競賽過程稱為NIST PQC（后量子密碼）標(biāo)準(zhǔn)化進(jìn)程。

　　PQC標(biāo)準(zhǔn)化進(jìn)程是NIST對(duì)量子計(jì)算機(jī)技術(shù)發(fā)展的響應(yīng)。量子計(jì)算機(jī)利用了量子力學(xué)現(xiàn)象來求解困難的或傳統(tǒng)計(jì)算機(jī)難以處理的難題。如果大容量規(guī)模的量子計(jì)算機(jī)被建造出來了，它們將能夠破解NIST目前標(biāo)準(zhǔn)化的這些公鑰密碼系統(tǒng)，包括數(shù)字簽名和密鑰建立方案。量子計(jì)算機(jī)對(duì)對(duì)稱密碼系統(tǒng)也有一定的影響，但其影響并不強(qiáng)烈。后量子密碼的目標(biāo)，是發(fā)展對(duì)量子計(jì)算機(jī)和經(jīng)典計(jì)算機(jī)都安全的密碼系統(tǒng)，并且能夠與現(xiàn)有協(xié)議和網(wǎng)絡(luò)互操作。

　　在啟動(dòng)PQC標(biāo)準(zhǔn)化進(jìn)程之前，NIST于2015年4月就成立了一個(gè)工作組，討論與后量子密碼以及未來可能的標(biāo)準(zhǔn)化相關(guān)的問題。一年之后，NIST發(fā)布了后量子密碼報(bào)告NISTIR，共享了NIST對(duì)量子計(jì)算和后量子密碼的狀態(tài)的理解，概括了NIST推進(jìn)該領(lǐng)域的初始計(jì)劃。NIST于PQCrypto 2016會(huì)議上以報(bào)告形式宣布了PQC標(biāo)準(zhǔn)化進(jìn)程的初步細(xì)節(jié)。

　　2016年8月，NIST以一個(gè)聯(lián)邦注冊(cè)公告的方式，公布了對(duì)后量子密碼的公開注釋建議的要求和評(píng)估判斷準(zhǔn)則。此后，又基于公開的反饋意見，對(duì)這些要求和評(píng)估判斷準(zhǔn)則進(jìn)行了更新，并且稍后將它們包含在2016年12月20日的第二次聯(lián)邦注冊(cè)公告（FRN-Dec16）內(nèi)。該公告正式征集關(guān)于后量子密碼算法的公開提案，標(biāo)志著NIST開始了PQC標(biāo)準(zhǔn)化的進(jìn)程。

　　候選提案的最后期限預(yù)定在2017年11月30日，在那個(gè)時(shí)日，NIST接收到了82個(gè)提案包。這是世界范圍內(nèi)密碼社區(qū)（在1998年為高級(jí)加密標(biāo)準(zhǔn)競賽提出過21個(gè)候選算法，在2008年為安全哈希算法3（SHA-3）競賽提交過64個(gè)文件包）作出的強(qiáng)烈反應(yīng)，NIST于2017年12月20日宣布接受了滿足提交要求和最小接受判斷準(zhǔn)則的69個(gè)第一輪候選算法。這69個(gè)提案包含了20個(gè)數(shù)字簽名方案和49個(gè)公鑰密碼（PKE）或密鑰封裝機(jī)制（KEM）。第一輪候選算法的提交包都被在線張貼在https://www.nist.gov/pqcrypto網(wǎng)頁上，征求公開的評(píng)論和注釋。

　　NIST于2018年4月11-13日在佛羅里達(dá)Lauderdale組織了第一次PQC標(biāo)準(zhǔn)化會(huì)議，其研究成果收錄在PQCrypto 2018中。獲得接受的第一輪候選算法的提交者被邀請(qǐng)到會(huì)上介紹他們的算法。NIST還討論了其縮小候選算法池、聚焦整個(gè)社區(qū)的關(guān)注點(diǎn)以及啟動(dòng)第二輪標(biāo)準(zhǔn)化進(jìn)程的計(jì)劃。在第一輪競賽中，NIST接收到密碼社區(qū)的大量反饋?；趯?duì)第一輪候選算法的公開反饋和內(nèi)部評(píng)估，NIST于2019年1月30日宣布挑選出26個(gè)算法作為第二輪候選算法，進(jìn)入該標(biāo)準(zhǔn)化進(jìn)程的第二階段。2019年7月20日宣布挑選出其中的7個(gè)算法作為第三輪最終候選算法PK，另外8個(gè)算法作為后補(bǔ)。

　　最終入選7算法如下：

　　1）CRYSTALS-KYBER

　　Kyber為一簇密鑰封裝機(jī)制，它基于模誤差學(xué)習(xí)（MLWE）問題的后量子困難問題假設(shè)，提供選擇性的密文安全性（即IND-CCA）。Kyber包含了一個(gè)標(biāo)準(zhǔn)的帶誤差學(xué)習(xí)（LWE）風(fēng)格的CPA安全的公鑰密碼方案，其基礎(chǔ)的代數(shù)目標(biāo)是在2的冪次的圓分割環(huán)上的一個(gè)模。通過對(duì)這個(gè)參數(shù)的精選，使其能夠采用數(shù)論變換（NTT）進(jìn)行效率非常高的計(jì)算。其噪聲按照一個(gè)有中心的二項(xiàng)式分布來進(jìn)行采樣。CCA安全性是通過Fujisaki-Okamoto變換的一種著名的變體來達(dá)到，其中會(huì)話密鑰是基于一種加密的方法來傳送的。

　　對(duì)Kyber的安全性強(qiáng)度水平的調(diào)整十分簡單。一種調(diào)整是僅僅改變底層模的秩（在{2,3,4}的范圍內(nèi)），并且調(diào)整其噪聲分布參數(shù)（分別在{5,4,3}的范圍內(nèi)）。對(duì)于密鑰交換而言，Kyber的性能為最具競爭力的密鑰交換設(shè)計(jì)之一。

　　Kyber的安全性依賴于一個(gè)已深入研究問題的變體。其提交文檔提供了一種基于隨機(jī)預(yù)言模型（ROM）的嚴(yán)密安全性證明，以及一種基于量子隨機(jī)預(yù)言機(jī)模型（QROM）的非嚴(yán)密安全性證明，二者都是基于MLWE假設(shè)。我們注意到一個(gè)潛在的問題是，這個(gè)安全性證明并不直接應(yīng)用于Kyber自身，而是應(yīng)用于該方案的一個(gè)不壓縮公鑰的改進(jìn)版本。如果沒有這種改進(jìn)，Kyber實(shí)際上是依賴于一個(gè)不同的（或附加的）類似取整的假設(shè)。如果是這樣的話，將帶來密碼分析上的擔(dān)憂，因?yàn)樵贛LWE和模取整學(xué)習(xí)（MLWR）之間進(jìn)行的那些已知的縮減設(shè)計(jì)，可能并不要求Kyber選取的那些參數(shù)。

　　2）NTRU（NTRUEncrypt與NTRU-HRSS-KEM的合并）

　　NTRU密碼為一種基于格的單向CPA安全（OW-CPA）的公鑰密碼方案，它大約發(fā)明于1996年。經(jīng)過了數(shù)十年的研究，NTRU密碼的安全性已經(jīng)得到了相當(dāng)好的理解和深入的研究審查。已經(jīng)發(fā)展出該方案的許多變體及其派生出的密鑰封裝機(jī)制，包括NTRUEncrypt和NTRU-HRSS-KEM提案。這兩個(gè)提案已經(jīng)宣布合并為一種方案，稱之為NTRU。

　　NTRU的安全性基礎(chǔ)是比LWE或RLWE稍微強(qiáng)一點(diǎn)的一種假設(shè)，有時(shí)稱之為“NTRU假設(shè)” 。在這個(gè)合并中，KEM為一種嚴(yán)密的IND-CCA2安全性轉(zhuǎn)換，源自于量子隨機(jī)預(yù)言模型的一種確定性O(shè)W-CPA安全的公鑰密碼方案。該提案對(duì)于KEM中的確定性PKE具有兩個(gè)選項(xiàng)。其派生的KEM沒有解密失敗問題，同時(shí)避免了密鑰產(chǎn)生期間的“對(duì)1值的評(píng)估”和可逆校驗(yàn)這兩個(gè)問題。

　　該方案以三個(gè)環(huán)結(jié)構(gòu)實(shí)例詳細(xì)說明了三個(gè)參數(shù)集。KEM產(chǎn)生的密鑰和密文都具有良好的尺寸，其封裝和解封效率看起來都很高。雖然它沒有形成已知的安全薄弱點(diǎn)，在具有相似效率的RLWE和MLWE密碼系統(tǒng)中，NTRU的構(gòu)造產(chǎn)生的結(jié)構(gòu)稍多一些（由于其矢量比期望的矢量更短）。這個(gè)方面需要進(jìn)一步研究。

　　3）SABER

　　SABER是一個(gè)基于格的PKE和KEM簇，它基于取整的模學(xué)習(xí)量子困難問題來達(dá)到CPA和CCA安全性。該方案使用在一個(gè)2的冪次的分圓環(huán)上具有固定維度和模數(shù)的不同秩的多個(gè)模塊，其安全級(jí)別分別為1、3以及5。其MLWR秘密分布為有中心的二項(xiàng)式分布，其會(huì)話密鑰哈希值再由公鑰進(jìn)行哈希運(yùn)算，以實(shí)現(xiàn)多目標(biāo)防護(hù)。其多項(xiàng)式相乘按照Toom-Cook和Karatsuba的詳細(xì)描述進(jìn)行。該方案通過Fujisaki-Okamoto變換的一個(gè)變量來達(dá)到CCA安全性。其會(huì)話密鑰使用一種基于帶噪聲的密鑰一致性協(xié)調(diào)的密碼方法來傳送。

　　在所有后量子密鑰交換中，SABER的性能優(yōu)勢具有非常強(qiáng)的競爭力。在每個(gè)安全級(jí)別中，它的帶寬代價(jià)都是比較低的。

　　關(guān)于SABER安全性的最明顯擔(dān)憂，是它是否過分?jǐn)U展了（模）取整學(xué)習(xí)的實(shí)際難度。雖然尚未有已知的利用所選參數(shù)的與（M）LWR相關(guān)的攻擊，在取整樣本MLWE和MLWR之間仍然存在很寬泛的縮減空間，并且還沒有應(yīng)用到SABER中。NIST將SABER當(dāng)作一個(gè)機(jī)遇，以突出對(duì)具有較小參數(shù)和取整樣本的（M）LWR進(jìn)行深入分析的需求，有利于推進(jìn)該方面的研究工作，繼續(xù)全面增強(qiáng)對(duì)該假設(shè)的信心。

　　4）Classic McEliece

　　Classic McEliece是一種IND-CCA2安全級(jí)別的密鑰封裝機(jī)制（KEM）。該提案以有名的McEliece密碼系統(tǒng)為基礎(chǔ)，McEliece密碼系統(tǒng)為1978年公布的第一個(gè)基于編碼的公鑰密碼系統(tǒng)。該KEM的公鑰機(jī)制確定一個(gè)隨機(jī)二元Goppa碼，通過在碼字上加入誤差來產(chǎn)生密文，通過解碼來實(shí)現(xiàn)解封。其安全性基于解碼一個(gè)常規(guī)線性碼的難度，并且假設(shè)一個(gè)隨機(jī)二元Goppa碼不能通過一個(gè)隨機(jī)線性碼來辨別。

　　其安全問題已經(jīng)具有很長的分析研究歷史，但并沒有顯著改變其攻擊復(fù)雜度。Classic McEliece也具有產(chǎn)生的密文非常短的特點(diǎn)，大概200個(gè)字節(jié)左右，看起來具有良好的封裝和解封性能。

　　McEliece類型的密碼系統(tǒng)的主要缺點(diǎn)是具有很大的公鑰尺寸，超過了一百萬個(gè)字節(jié)。該提案僅僅包含了第5類安全性的參數(shù)集，因而希望提交者生成其它安全類別的參數(shù)集。

　　5）CRYSTALS-DILITHIUM

　　Dilithium為一種格基簽名方案，采用了Fiat-Shamir啟發(fā)方法來構(gòu)造，其安全性是依賴于MLWE的困難問題。Dilithium與密鑰交換機(jī)制Kyber都是CRYSTALS的組成部分。Dilithium的主要新穎性在于通過忽略一些低階bit來減小其公鑰尺寸；為了進(jìn)行補(bǔ)償，每個(gè)簽名都包含了一個(gè)額外的“線索”，允許驗(yàn)證者對(duì)簽名進(jìn)行核對(duì)。Dilithium提供了相當(dāng)良好的性能，其實(shí)現(xiàn)也相對(duì)簡單。

　　對(duì)Dilithium的最知名的攻擊是基于格的偏移縮減，這種攻擊沒有有效利用MLWE問題的代數(shù)結(jié)構(gòu)。Dilithium的參數(shù)選擇以對(duì)這些攻擊代價(jià)的保守估計(jì)為基礎(chǔ)。Dilithium具有一個(gè)基于經(jīng)典隨機(jī)預(yù)言機(jī)模型的形式化的安全性證明。這個(gè)證明是極不平凡的，它突破了量子隨機(jī)預(yù)言機(jī)模型；但是還沒有任何已知攻擊的實(shí)例。NIST鼓勵(lì)對(duì)這個(gè)方案的所有方面都進(jìn)行的深入分析研究。

　　6）FALCON

　　FAlCON為一種格基簽名方案，它基于GPV（Gentry-Peikert-Vaikuntanathan）高斯取樣，應(yīng)用了NTRU格。其主要的創(chuàng)新性在于，它應(yīng)用了一種樹形的數(shù)據(jù)結(jié)構(gòu)（即“FAlCON樹”），使其成為對(duì)高斯采樣的一種非?？斓倪f歸算法。

　　對(duì)FAlCON方案的最知名的攻擊是基于格的偏移縮減，這種攻擊沒有有效利用NTRU格的特殊結(jié)構(gòu)。FAlCON具有一個(gè)基于經(jīng)典隨機(jī)預(yù)言機(jī)模型的形式化的安全性證明。

　　FAlCON提供了非常優(yōu)良的性能，但是其實(shí)現(xiàn)相當(dāng)復(fù)雜，因?yàn)樗鼑?yán)重依賴于數(shù)域的“多域塔”結(jié)構(gòu)，并且需要雙精度浮點(diǎn)算法。該方案還需要進(jìn)行更多的研究工作，確保其簽名算法面對(duì)邊信道攻擊時(shí)是安全的。

　　7）Rainbow

　　Rainbow是一種多變量數(shù)字簽名方案，它是UOV結(jié)構(gòu)的一種推廣，允許進(jìn)行參數(shù)優(yōu)化，使其以增加代數(shù)結(jié)構(gòu)的代價(jià)獲得更高的效率。Rainbow簽名方案所提交的格式已經(jīng)具有長達(dá)15年的針對(duì)各種參數(shù)的研究歷程。Rainbow方案聲稱，由于使用了隨機(jī)加鹽的一種哈希構(gòu)造，因而具備EUF-CMA安全性。

　　Rainbow參數(shù)譜允許在各種各樣的大量應(yīng)用場景中進(jìn)行優(yōu)化。Rainbow的另一優(yōu)勢是它已經(jīng)在其它包括輕量級(jí)應(yīng)用在內(nèi)的場景中得到了研究。

　　Rainbow提案針對(duì)NIST號(hào)召建議中的所有安全級(jí)別，提供了若干個(gè)參數(shù)集。作為一種入選第二輪的候選算法，期望能夠?qū)⒀芯恐攸c(diǎn)聚焦于一組更窄的細(xì)節(jié)規(guī)格上面。此外，還希望能激發(fā)針對(duì)Rainbow密鑰以文獻(xiàn)中已有的、而Rainbow提案中并未考慮的那些優(yōu)化技術(shù)開展更多的研究，最終使研究社區(qū)在方案的可行性上面取得一致。此外，Rainbow的實(shí)現(xiàn)也可能得到很大的改進(jìn)。

　　實(shí)際上我們并不處在建造一臺(tái)有能力破譯目前公鑰密碼（學(xué)）的量子計(jì)算機(jī)的中期階段（例如5年）內(nèi)。執(zhí)行肖爾算法所需的量子比特的數(shù)量，遠(yuǎn)遠(yuǎn)超過今天我們制造的最強(qiáng)大的量子計(jì)算機(jī)的能力，而且肖爾算法大規(guī)模的可靠的應(yīng)用還沒有被展示出來。今天，我們并不清楚諸如量子比特的退相干和管理噪聲以減少量子系統(tǒng)中的差錯(cuò)等面臨的挑戰(zhàn)能否被解決。正因?yàn)槿绱?，在短期或者中期?nèi)建造這樣一臺(tái)可規(guī)模化的擴(kuò)展的量子計(jì)算機(jī)似乎不太現(xiàn)實(shí)。

　　然而，放眼較長的時(shí)間（20年），忽視量子計(jì)算機(jī)對(duì)于目前的現(xiàn)代密碼學(xué)標(biāo)準(zhǔn)的威脅將會(huì)是錯(cuò)誤的。正如美國國家標(biāo)準(zhǔn)與技術(shù)研究院的描述：“一些人預(yù)測在接下來的20年左右，足夠規(guī)模的量子計(jì)算機(jī)會(huì)被制造出來，基本上可以打破目前使用中的所有公鑰方案。在歷史上，我們花了差不多20年時(shí)間去配置現(xiàn)代公鑰密碼基礎(chǔ)架構(gòu)。因此，不論我們能否準(zhǔn)確估計(jì)量子計(jì)算時(shí)代到來的時(shí)間，我們都必須現(xiàn)在開始準(zhǔn)備我們的信息安全系統(tǒng)，使之能夠?qū)沽孔佑?jì)算”。

　　六

　　結(jié)　語

　　對(duì)量子計(jì)算的研究如火如荼，以美國為首的國家已經(jīng)將量子計(jì)算作為其未來科技發(fā)展戰(zhàn)略的核心和重點(diǎn)之一，總體說來，當(dāng)前量子計(jì)算研究狀況是：

　　1、物理平臺(tái)探索發(fā)展迅速，但技術(shù)路線仍未收斂

　　量子計(jì)算研究始于上世紀(jì)八十年代，目前已進(jìn)入工程實(shí)驗(yàn)驗(yàn)證和原理樣機(jī)攻關(guān)階段。量子計(jì)算包含量子處理器、量子編碼、量子算法、量子軟件等關(guān)鍵技術(shù)，量子處理器的物理實(shí)現(xiàn)是當(dāng)前階段的核心瓶頸，包含超導(dǎo)、離子阱、硅量子點(diǎn)、中性原子、光量子和拓?fù)涞榷喾N技術(shù)路線，近期均取得一定進(jìn)展。超導(dǎo)路線方面，Google 在2018年推出72位量子比特處理器，Rigetti正在構(gòu)建更強(qiáng)大的128量子比特處理器。我國中科大在2019年已實(shí)現(xiàn)24位超導(dǎo)量子比特處理器，并進(jìn)行多體量子系統(tǒng)模擬；同時(shí)，清華大學(xué)利用單量子比特實(shí)現(xiàn)了精度為98.8%的量子生成對(duì)抗網(wǎng)絡(luò)，未來可應(yīng)用于圖像生成等領(lǐng)域。離子阱路線方面，IonQ已實(shí)現(xiàn)79位處理量子比特和160位存儲(chǔ)量子比特。光量子路線方面，中科大已實(shí)現(xiàn)18位光量子的糾纏操控，處于國際領(lǐng)先地位。硅量子點(diǎn)路線方面，新南威爾士大學(xué)報(bào)道了保真度為99.96%的單比特邏輯門，以及保真度為98%的雙比特邏輯門。目前，量子計(jì)算物理平臺(tái)中的超導(dǎo)和離子阱路線相對(duì)領(lǐng)先，但尚無任何一種路線能夠完全滿足量子計(jì)算技術(shù)實(shí)用化條件實(shí)現(xiàn)技術(shù)收斂。為充分利用每種技術(shù)的優(yōu)勢，未來的量子計(jì)算機(jī)也可能是多種路線并存的混合體系。

　　2、“量子霸權(quán)”突破里程碑，但實(shí)用化尚有距離

　　量子霸權(quán)（Quantum Supremacy）的概念由MIT的John Preskill教授首先提出，指量子計(jì)算在某一個(gè)計(jì)算問題上，相比于經(jīng)典計(jì)算機(jī)可實(shí)現(xiàn)指數(shù)量級(jí)運(yùn)算能力的加速，從而真正體現(xiàn)量子計(jì)算技術(shù)的原理性優(yōu)勢。2019年10月，Google公司在《自然》雜志報(bào)道了實(shí)現(xiàn)量子霸權(quán)的研究成果，基于53位量子比特的超導(dǎo)處理器，在解決隨機(jī)量子線路采樣特定計(jì)算問題時(shí)，具有遠(yuǎn)超過現(xiàn)有超級(jí)計(jì)算機(jī)的處理能力。Google的此項(xiàng)研究成果是證明量子計(jì)算原理優(yōu)勢和技術(shù)潛力的首個(gè)實(shí)際案例，具有重要的里程碑意義，這一熱點(diǎn)事件所引發(fā)的震動(dòng)和關(guān)注，將進(jìn)一步推動(dòng)全球各國在量子計(jì)算領(lǐng)域的研發(fā)投入、工程實(shí)踐和應(yīng)用探索，為加快量子計(jì)算機(jī)的研制和實(shí)用化注入新動(dòng)力。

　　現(xiàn)階段量子計(jì)算的發(fā)展水平距離實(shí)用化仍有較大距離。量子計(jì)算系統(tǒng)非常脆弱，極易受到材料雜質(zhì)、環(huán)境溫度和噪聲等外界因素影響而引發(fā)退相干效應(yīng)，使計(jì)算準(zhǔn)確性受到影響，甚至計(jì)算能力遭到破壞。同時(shí)，可編程通用量子計(jì)算機(jī)需要大量滿足容錯(cuò)閾值的物理量子比特進(jìn)行糾錯(cuò)處理，克服退相干效應(yīng)影響，獲得可用的邏輯量子比特?，F(xiàn)有研究報(bào)道中的物理量子比特?cái)?shù)量和容錯(cuò)能力與實(shí)際需求尚有很大差距，邏輯量子比特仍未實(shí)現(xiàn)。通用量子計(jì)算機(jī)的實(shí)用化，業(yè)界普遍預(yù)計(jì)將需十年以上時(shí)間。

　　3、生態(tài)鏈不斷壯大、應(yīng)用探索全面展開

　　在量子計(jì)算領(lǐng)域，美國近年來持續(xù)大力投入，已形成政府、科研機(jī)構(gòu)、產(chǎn)業(yè)和投資力量多方協(xié)同的良好局面，并建立了在技術(shù)研究、樣機(jī)研制和應(yīng)用探索等方面的全面領(lǐng)先優(yōu)勢。歐（含英國）、日、澳等國緊密跟隨，且領(lǐng)先國家之間通過聯(lián)合攻關(guān)和成果共享，形成并不斷強(qiáng)化聯(lián)盟優(yōu)勢。我國近年來取得系列先進(jìn)成果，但與美歐仍有一定差距。此外，印度、韓國、俄羅斯、以色列等國也開始將量子計(jì)算技術(shù)列入國家技術(shù)計(jì)劃加大投入。

　　科技巨頭間的激烈競爭，推動(dòng)量子計(jì)算技術(shù)加速發(fā)展。Google、IBM、英特爾、微軟在量子計(jì)算領(lǐng)域布局多年，霍尼韋爾隨后加入，產(chǎn)業(yè)巨頭基于雄厚的資金投入、工程實(shí)現(xiàn)和軟件控制能力積極開發(fā)原型產(chǎn)品、展開激烈競爭，對(duì)量子計(jì)算成果轉(zhuǎn)化和加速發(fā)展助力明顯。Google在2018年實(shí)現(xiàn)72位超導(dǎo)量子比特，在2019年證明量子優(yōu)越性。IBM在2019年1月展示具有20位量子比特的超導(dǎo)量子計(jì)算機(jī)，并在9月將量子比特?cái)?shù)量更新為53位。微軟在2019年推出量子計(jì)算云服務(wù)，可以與多種類型的硬件配合使用?；裟犴f爾的離子阱量子比特裝置已進(jìn)入測試階段。我國阿里巴巴、騰訊、百度和華為近年來通過與科研機(jī)構(gòu)合作或聘請(qǐng)具有國際知名度的科學(xué)家成立量子實(shí)驗(yàn)室，在量子計(jì)算云平臺(tái)、量子軟件及應(yīng)用開發(fā)等領(lǐng)域進(jìn)行布局。阿里與中科大聯(lián)合發(fā)布量子計(jì)算云平臺(tái)并在2018年推出量子模擬器“太章”。騰訊在量子AI、藥物研發(fā)和科學(xué)計(jì)算平臺(tái)等應(yīng)用領(lǐng)域展開研發(fā)。百度在2018年成立量子計(jì)算研究所，開展量子計(jì)算軟件和信息技術(shù)應(yīng)用等業(yè)務(wù)研究。華為在2018年發(fā)布HiQ量子云平臺(tái)，并在2019年推出昆侖量子計(jì)算模擬一體原型機(jī)。我國科技企業(yè)進(jìn)入量子計(jì)算領(lǐng)域相對(duì)較晚，在樣機(jī)研制及應(yīng)用推動(dòng)方面與美國存在差距。

　　初創(chuàng)企業(yè)是量子計(jì)算技術(shù)產(chǎn)業(yè)發(fā)展的另一主要推動(dòng)力量。初創(chuàng)企業(yè)大多脫胎于科研機(jī)構(gòu)或科技公司，近年來，來自政府、產(chǎn)業(yè)巨頭和投資機(jī)構(gòu)的創(chuàng)業(yè)資本大幅增加，初創(chuàng)企業(yè)快速發(fā)展。目前，全球有超過百余家初創(chuàng)企業(yè)，涵蓋軟硬件、基礎(chǔ)配套及上層應(yīng)用各環(huán)節(jié)。

　　盡管量子計(jì)算目前仍處于產(chǎn)業(yè)發(fā)展的初期階段，但軍工、氣象、金融、石油化工、材料科學(xué)、生物醫(yī)學(xué)、航空航天、汽車交通、圖像識(shí)別和咨詢等眾多行業(yè)已注意到其巨大的發(fā)展?jié)摿?，開始與科技公司合作探索潛在用途，生態(tài)鏈不斷壯大。Google聯(lián)合多家研究機(jī)構(gòu)將量子退火技術(shù)應(yīng)用于圖像處理、蛋白質(zhì)折疊、交通流量優(yōu)化、空中交通管制、海嘯疏散等領(lǐng)域。JSR和三星嘗試使用量子計(jì)算研發(fā)新材料特性。埃森哲、Biogen和1Qbit聯(lián)合開發(fā)量子化分子比較應(yīng)用，改善分子設(shè)計(jì)加速藥物研究。德國HQS開發(fā)的算法可以在量子計(jì)算機(jī)和經(jīng)典計(jì)算機(jī)上有效地模擬化學(xué)過程。摩根大通、巴克萊希望通過蒙特卡洛模擬加速來優(yōu)化投資組合。硅谷量子計(jì)算軟件開發(fā)商QCware編寫量子算法，以提高量化交易和基金管理策略的調(diào)整能力，優(yōu)化資產(chǎn)定價(jià)及風(fēng)險(xiǎn)對(duì)沖。在達(dá)到通用量子計(jì)算所需的量子比特?cái)?shù)量、量子容錯(cuò)能力和工程化條件等要求之前，專用量子計(jì)算機(jī)或量子模擬器將成為量子計(jì)算發(fā)展的下一個(gè)重要里程碑，在量子體系模擬、分子結(jié)構(gòu)解析、大數(shù)據(jù)集優(yōu)化和機(jī)器學(xué)習(xí)算法加速等領(lǐng)域開發(fā)出能夠有效發(fā)揮量子計(jì)算處理優(yōu)勢的典型應(yīng)用，打開量子計(jì)算實(shí)用化之門。

　　4、密碼界未雨綢繆，網(wǎng)絡(luò)空間安全基石必將發(fā)生根本性改變

　　在量子計(jì)算被引入后，盡管還不能確切得知實(shí)用化的破譯用量子計(jì)算機(jī)何時(shí)誕生，但密碼界早早就開展了深入研究，畢竟量子計(jì)算誕生的基礎(chǔ)和前提中十分重要的一點(diǎn)就是沖著密碼破譯而來，密碼學(xué)界提前啟動(dòng)了后量子密碼學(xué)的實(shí)用化進(jìn)程。

　　后量子密碼學(xué)以數(shù)學(xué)方法為基礎(chǔ)定義了一系列新的密碼學(xué)標(biāo)準(zhǔn)，其中主要是針對(duì)公鑰密碼學(xué)。這些方法很強(qiáng)大，足以抵擋來自量子計(jì)算機(jī)的攻擊。美國國家標(biāo)準(zhǔn)與技術(shù)研究院帶頭著手實(shí)施一項(xiàng)計(jì)劃來發(fā)展這些新的標(biāo)準(zhǔn)。他們通過階段性的招標(biāo)流程，收集學(xué)術(shù)界和工業(yè)界對(duì)新的密碼算法的建議，當(dāng)前學(xué)術(shù)界抗量子計(jì)算熱點(diǎn)集中于：

　　基于格的密碼（Lattice Based Cryptography）--格是N維空間中帶有周期性結(jié)構(gòu)的點(diǎn)集，它和N維的有斑點(diǎn)圖案的壁紙有些相似。某些數(shù)學(xué)上的格點(diǎn)問題被認(rèn)為解決起來非常困難，比如最短向量問題（Shortest Vector Problem），就是給定一個(gè)特定的基矢，然后找出一些最短的非零向量。這樣的格點(diǎn)問題已經(jīng)被用來作為構(gòu)建一些密碼學(xué)方法的基礎(chǔ)。

　　基于編碼的密碼（Code Based Cryptography）--這類方法是以糾錯(cuò)碼為基礎(chǔ)的加密系統(tǒng)。這些算法以解碼線性代碼的困難為基礎(chǔ)，算法中的私鑰與一個(gè)糾錯(cuò)碼相聯(lián)系，公鑰與加擾版本相聯(lián)系。

　　多變量多項(xiàng)式（Multivariant Polynomials）--在有限域上包含多變量多項(xiàng)式的數(shù)學(xué)問題已經(jīng)被建議用來作為新的加密方法的基礎(chǔ)。

　　基于哈希的簽名（Hash-Based Signatures）--這是一種提供數(shù)字簽名的方法，其中的數(shù)字簽名來自一種叫作哈希函數(shù)的數(shù)學(xué)函數(shù)的復(fù)用。

　　目前對(duì)公鑰界威脅最大的Shor算法的運(yùn)行瓶頸在于量子模冪，它遠(yuǎn)比量子傅立葉變換和經(jīng)典的預(yù)處理/后處理慢很多。有幾種方法可以構(gòu)造和優(yōu)化用于模冪的電路，最簡單（當(dāng)前）的最實(shí)用方法是模仿具有可逆門的常規(guī)算術(shù)電路，該方法從帶紋波的加法器開始，知道指數(shù)的基數(shù)和模數(shù)有助于進(jìn)一步優(yōu)化?？赡骐娐肥褂昧孔颖忍亻T來實(shí)現(xiàn)，替代技術(shù)通過使用量子傅立葉變換來漸進(jìn)地提高門數(shù)，但由于常數(shù)較高，不足600量子位不具有實(shí)際破譯能力。

　　目前，抗量子密碼算法已經(jīng)進(jìn)入最終遴選階段，未來1-2年內(nèi)一旦最終選定就能快速得到全面應(yīng)用，隨著抗量子計(jì)算的算法普及，網(wǎng)絡(luò)空間安全的基石即將發(fā)生變革。

　　5、基礎(chǔ)研究是重點(diǎn)，多樣混合也許是出路

　　毫無疑問量子計(jì)算是當(dāng)前一項(xiàng)十分重要和熱門的基礎(chǔ)性的研究領(lǐng)域，基礎(chǔ)研究的極端重要性是一個(gè)老生常談的話題，在涉及基礎(chǔ)性、全局性、顛覆性和長久性的科學(xué)研究領(lǐng)域，不存在什么彎道超車的僥幸，而只能是實(shí)實(shí)在在的進(jìn)行布局。四十年前第一代公鑰密碼算法引發(fā)的現(xiàn)代密碼學(xué)革命并不是來自于極少數(shù)國家級(jí)科研機(jī)構(gòu)，而是得益于美國大學(xué)自由的科研氛圍，這足以說明問題。

　　最近佐治亞理工學(xué)院的博士生Swamit Tannu和Moinuddin Qureshi教授開發(fā)了一種新技術(shù)--多樣映射集合，它依賴于使用不同的量子比特來創(chuàng)建錯(cuò)誤的多樣化。

　　與傳統(tǒng)計(jì)算機(jī)不同，基于量子的計(jì)算機(jī)中的處理過程是有噪聲的，因此產(chǎn)生的錯(cuò)誤率大大高于基于硅的計(jì)算機(jī)。為此，量子運(yùn)算要重復(fù)數(shù)千次，以使正確的答案在統(tǒng)計(jì)上從所有錯(cuò)誤的答案中脫穎而出。

　　但是，在相同的量子比特集上一次又一次地運(yùn)行相同的操作可能會(huì)生成相同的錯(cuò)誤答案，從統(tǒng)計(jì)學(xué)上看，這些錯(cuò)誤答案似乎是正確的答案。佐治亞理工學(xué)院的研究人員認(rèn)為，解決方案是對(duì)具有不同錯(cuò)誤特征的不同量子比特集重復(fù)操作，因此不會(huì)產(chǎn)生相同的相關(guān)錯(cuò)誤。

　　未來的量子計(jì)算機(jī)很可能是一個(gè)混合體，也許會(huì)出現(xiàn)這樣一種量子計(jì)算機(jī)：由超快的超導(dǎo)體量子比特對(duì)算法進(jìn)行運(yùn)算，然后把結(jié)果扔給更穩(wěn)定的離子存儲(chǔ)；與此同時(shí)，光子在機(jī)器的不同部件之間傳遞信息，或者在量子網(wǎng)絡(luò)的節(jié)點(diǎn)之間傳遞信息。微軟研究員 Krysta Svore 說：“能夠想象，將來不同類型的量子比特會(huì)同時(shí)存在，并在不同任務(wù)中扮演不同的角色”。