量子計(jì)算

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

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

1、概念的提出

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

2、中期發(fā)展

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

3、發(fā)展前景

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

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

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

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

2、量子搜索

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

3、密碼學(xué)

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