量子計算

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

量子計算的發展史

1、概念的提出

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

2、中期發展

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

3、發展前景

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

量子計算的應用

1、解決經典計算難題

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

2、量子搜索

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

3、密碼學

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