一

　　前　言

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

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

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

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

　　那么，讓我們仔細看看這個神奇的量子計算吧。

　　二

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

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

　　１、為什么會誕生量子計算？

　?。幔┚w管進入原子級尺寸極限

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

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

　　ｂ）對海量計算的加速需求

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

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

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

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

　　2）、生物分子運動

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

　　分子模擬問題（Chemistry:化學Nitrogenase enzyme…：參與氮氣（N2）轉化為銨根（NH4）過程的固氮酶Simulating this cluster…：模擬該簇已經(jīng)是傳統(tǒng)計算機運算能力的上限）。

　　3）、密碼分析破譯

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

　　量子計算基礎原理

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

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

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

　　經(jīng)典比特

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

　　量子比特

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

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

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

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

　　２、量子計算發(fā)展歷程

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

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

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

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

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

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

　?。玻┝孔佑嬎愕陌l(fā)展史

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

　　一）20世紀80年代

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

　　第一個問題：經(jīng)典計算機是否能夠有效的模擬量子系統(tǒng)？雖然在量子理論中，仍用微分方程來描述量子系統(tǒng)的演化，但變量的數(shù)目卻遠遠多于經(jīng)典物理系統(tǒng)。所以費曼針對這個問題的結論是：不可能。因為目前沒有任何可行的方法，可以求解出這么多變量的微分方程。

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

　　1985年，David Deutsch描述了通用量子計算機，使得量子計算機的構建更加清晰。

　　二）20世紀90年代

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

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

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

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

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

　　三）21世紀

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

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

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

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

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

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

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

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

　　2019年1月，IBM展示了具有20位量子比特的超導量子計算機，并在9月將量子比特數(shù)量更新為53位。

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

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

　　三

　　量子計算機工作原理及實現(xiàn)模式

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

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

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

　　量子計算的基礎和核心是量子比特的實現(xiàn)，量子比特相比傳統(tǒng)計算機比特更強大，是因為它利用了兩個獨特的量子現(xiàn)象：疊加（superposition）和糾纏（entanglement）。量子疊加使量子比特能夠同時具有 0 和 1 的數(shù)值，可進行“同步計算”（simultaneous computation）。量子糾纏使分處兩地的兩個量子比特能共享量子態(tài)，創(chuàng)造出超疊加效應：每增加一個量子比特，運算性能就翻一倍。

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

　　當前實現(xiàn)量子比特的幾個典型物理方法有：

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

　　當前已知的量子計算主流實現(xiàn)方式方法有：超導、離子囚禁、量子退火、硅量子點、量子光學、拓撲量子計算等等幾種。

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

　　1）超導

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

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

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

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

　　2）離子囚禁

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

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

　　3）量子退火

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

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

　　4）半導體量子點

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

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

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

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

　　5）量子光學

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

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

　　6）拓撲量子

　　拓撲量子計算建立在全新的計算思路之上，應用任意子的交換相位、交換過程的“編辮”程序實現(xiàn)量子計算的信息處理。拓撲學研究幾何形象在幾何元素的連續(xù)變形下保持不變的性質。如果構成量子比特的元素是拓撲不變的，基于這些量子比特的運算結果也具有拓撲不變性。由此構造的量子計算對環(huán)境干擾、噪音、雜質有很大的抵抗能力。但拓撲量子計算尚停留在理論層面，實際上還未把這些理論付諸成器件化的現(xiàn)實。

　　拓撲量子是微軟的選擇路線，它基于非阿貝爾任意子（nonabelian anyons）的拓撲量子比特（topological qubits）。這些根本就不是物體，它們是沿著不同物質邊緣游動的準粒子（quasiparticles）。量子態(tài)由不同交叉路線（braiding Paths）來表現(xiàn)。因為交叉路線的形狀導致了量子疊加，它們會受到拓撲保護（topologically protected）而不至于崩潰，這類似于打結的鞋帶不會散開一樣。。

　　理論上拓撲量子計算機不需要在錯誤修正上花費那么多量子比特。早在2005年，微軟帶領的一支研究團隊就提出了一種在半導體-超導體混合結構中建造拓撲保護量子比特的方法。微軟已經(jīng)投資了數(shù)個團隊進行嘗試，他們近期的論文還有貝爾實驗室的一項獨立研究都展示了關鍵的任意子以電路中電流的模式進行移動的“征兆”，這已經(jīng)很接近展示真正的量子比特了?？茖W家Preskill 說：“我認為在一兩年內，我們就可以看到結果--拓撲量子比特確實存在”。

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

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

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

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

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

　　2）無誤差量子計算需要量子錯誤校正

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

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

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

　　4）量子算法設計難度較大

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

　　5）量子計算機將需要一個全新的軟件棧

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

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

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

　　7）從理論到工程跨域實現(xiàn)困難

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

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

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

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

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

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

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

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

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

　　四

　　量子計算機給密碼算法帶來的威脅

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

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

　　1、Shor算法

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

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

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

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

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

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

　　2、Grover算法

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

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

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

　　一個很自然的問題是，我們距離一臺有能力大規(guī)模運行肖爾算法或者格羅弗算法的量子計算機有多遠呢？目前，在建最強大的通用量子計算機的數(shù)量級在100量子比特以內。而正如我們在討論肖爾算法時看到的那樣，一臺量子計算機大概需要4000個邏輯量子比特才能因式分解一個2048比特的RSA數(shù)。

　　五

　　密碼界面對威脅的應對

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

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

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

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

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

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

　　最終入選7算法如下：

　　1）CRYSTALS-KYBER

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

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

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

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

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

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

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

　　3）SABER

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

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

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

　　4）Classic McEliece

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

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

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

　　5）CRYSTALS-DILITHIUM

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

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

　　6）FALCON

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

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

　　FAlCON提供了非常優(yōu)良的性能，但是其實現(xiàn)相當復雜，因為它嚴重依賴于數(shù)域的“多域塔”結構，并且需要雙精度浮點算法。該方案還需要進行更多的研究工作，確保其簽名算法面對邊信道攻擊時是安全的。

　　7）Rainbow

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

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

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

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

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

　　六

　　結　語

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

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

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

　　2、“量子霸權”突破里程碑，但實用化尚有距離

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

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

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

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

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

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

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

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

　　在量子計算被引入后，盡管還不能確切得知實用化的破譯用量子計算機何時誕生，但密碼界早早就開展了深入研究，畢竟量子計算誕生的基礎和前提中十分重要的一點就是沖著密碼破譯而來，密碼學界提前啟動了后量子密碼學的實用化進程。

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

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

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

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

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

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

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

　　5、基礎研究是重點，多樣混合也許是出路

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

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

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

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

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