量子計算

量子計算是一種遵循量子力學規(guī)律調控量子信息單元進行計算的新型計算模式。對照于傳統(tǒng)的通用計算機，其理論模型是通用圖靈機；通用的量子計算機，其理論模型是用量子力學規(guī)律重新詮釋的通用圖靈機。從可計算的問題來看，量子計算機只能解決傳統(tǒng)計算機所能解決的問題，但是從計算的效率上，由于量子力學疊加性的存在，目前某些已知的量子算法在處理問題時速度要快于傳統(tǒng)的通用計算機。

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

1、概念的提出

量子計算（quantumcomputation）的概念最早由阿崗國家實驗室的P.Benioff于80年代初期提出，他提出二能階的量子系統(tǒng)可以用來仿真數(shù)字計算；稍后費曼也對這個問題產(chǎn)生興趣而著手研究，并在1981年于麻省理工學院舉行的FirstConferenceonPhysicsofComputation中給了一場演講，勾勒出以量子現(xiàn)象實現(xiàn)計算的愿景。1985年，牛津大學的D.Deutsch提出量子圖靈機（quantumTuringmachine）的概念，量子計算才開始具備了數(shù)學的基本型式。然而上述的量子計算研究多半局限于探討計算的物理本質，還停留在相當抽象的層次，尚未進一步跨入發(fā)展算法的階段。

2、中期發(fā)展

1994年，貝爾實驗室的應用數(shù)學家P.Shor指出，相對于傳統(tǒng)電子計算器，利用量子計算可以在更短的時間內將一個很大的整數(shù)分解成質因子的乘積。這個結論開啟量子計算的一個新階段：有別于傳統(tǒng)計算法則的量子算法（quantumalgorithm）確實有其實用性，絕非科學家口袋中的戲法。自此之后，新的量子算法陸續(xù)的被提出來，而物理學家接下來所面臨的重要的課題之一，就是如何去建造一部真正的量子計算器，來執(zhí)行這些量子算法。許多量子系統(tǒng)都曾被點名做為量子計算器的基礎架構，例如光子的偏振（photonpolarization）、腔量子電動力學（cavityquantumelectrodynamics，CQED）、離子阱（iontrap）以及核磁共振（nuclearmagneticresonance，NMR）等等。截止到2017年，考慮到系統(tǒng)的可擴展性和操控精度等因素，離子阱與超導系統(tǒng)走在了其它物理系統(tǒng)的前面。

3、發(fā)展前景

量子計算將有可能使計算機的計算能力大大超過今天的計算機，但仍然存在很多障礙。大規(guī)模量子計算所存在重要的問題是，如何長時間地保持足夠多的量子比特的量子相干性，同時又能夠在這個時間段之內做出足夠多的具有超高精度的量子邏輯操作。

量子計算的應用

1、解決經(jīng)典計算難題

大數(shù)質因子求解問題是公認的NP問題，如給定一個足夠大的數(shù)，可以驗證某個數(shù)是否是它的因子，但無法在有限的時間里找出它所有的因子。Shor的量子算法將大數(shù)質因子求解轉換為P問題，激發(fā)了人們尋找對其他NP問題可能存在的量子算法，但還不清楚量子計算是否可以將所有的NP問題轉換為P問題。量子計算解決NP問題的一個辦法是利用量子并行機制搜索問題的所有可能解。這種辦法并不能給出對所有NP問題進行有效解答的方法，但在NP問題中有可能存在更深層的結構，使得可以用量子計算快速求解。

2、量子搜索

量子搜索利用量子并行計算的優(yōu)勢在解空間進行完全搜索，并將目標振幅放大求解。Grover量子搜索算法的提出最初用于搜索非結構化數(shù)據(jù)庫問題，之后掀起了研究搜索的熱潮。經(jīng)過許多研究者的不斷完善和發(fā)展，Grover量子搜索算法已經(jīng)形成一個比較完整的搜索算法體系，能夠適應各種不同的搜索需求?，F(xiàn)實中許多問題都可以歸結為搜索問題，如最短路徑、排序、圖著色、數(shù)據(jù)庫搜索及密碼中的窮舉攻擊等均屬于這類問題。量子搜索能將這些問題中的部分NP類問題轉換為P類問題（如圖著色問題）或是對問題的求解進行加速。目前，各種量子搜索算法的具體應用正在不斷涌現(xiàn)。

3、密碼學

Shor提出的量子大數(shù)因子分解算法使得量子計算機可以輕易破譯RSA公開密匙體系，因此量子密碼受到了極大的關注。Wiesner在1970年寫了一篇很有創(chuàng)意的有關共軛編碼的文章，奠定了量子密碼學的基礎。因Wicsncr的想法太新奇，論文被拒絕刊登，直到1983年才得以發(fā)表。Bennet等繼續(xù)該課題的研究并取得了豐碩的成果。量子密碼學系統(tǒng)利用了Heisenberg的不確定性原理，原則上量子密碼學可以提供不可破譯、不可竊聽的保密通信體系。國內李傳鋒等在建立量子密碼體系方面也取得了一定成果。隨著時代的發(fā)展，出現(xiàn)了各式各樣的密碼形式，當今真正能夠成為主流加密技術的是大名鼎鼎的非對稱公鑰加密技術，正是有賴于這項上世紀70年代出現(xiàn)的公鑰加密系統(tǒng)，讓安全而且高效的互聯(lián)網(wǎng)傳輸成為可能。2016年3月2日，公鑰加密系統(tǒng)的兩位創(chuàng)始人因此獲得有“計算機界諾貝爾獎“之稱的圖靈獎！