量子計算

量子計算是一種遵循量子力學規(guī)律調(diào)控量子信息單元進行計算的新型計算模式。對照于傳統(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ù)學的基本型式。然而上述的量子計算研究多半局限于探討計算的物理本質(zhì)，還停留在相當抽象的層次，尚未進一步跨入發(fā)展算法的階段。

2、中期發(fā)展

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

3、發(fā)展前景

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

量子計算的應(yīng)用

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

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

2、量子搜索

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

3、密碼學

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