0
雷峰網(wǎng)(公眾號：雷峰網(wǎng))按：本文作者James Zhu ，本文為你介紹了1）量子計算機(jī)的發(fā)展歷史；2）量子計算機(jī)較傳統(tǒng)計算機(jī)的優(yōu)越之處；3）量子算法與我們的關(guān)系；4）IBM量子在線體驗服務(wù)介紹。
量子計算機(jī)真的不只存在在科幻小說里嗎？它和普通計算機(jī)有何區(qū)別？和咱普通程序員又有何關(guān)系。本篇文章專治不明覺厲，希望帶你一探量子計算機(jī)的究竟！
2001年的時候，IBM發(fā)表文章說“在未來的幾十年里，量子計算機(jī)很可能會走出科幻小說與科研實驗室（主要在IBM）進(jìn)入實際應(yīng)用。”
現(xiàn)在這句話已經(jīng)成為了現(xiàn)實，并且只用了十幾年的時間。在本周三，IBM的科學(xué)家首次將該公司的量子計算機(jī)接入云端服務(wù)向大眾公開?？萍嫉陌l(fā)展總是令人震驚不已。并且IBM希望幾年之內(nèi)就能開發(fā)出可用于量子計算機(jī)的實驗芯片。目前，IBM還沒有正式公開量子計算服務(wù)，但是有興趣的朋友可以登錄IBM Quantum申請試用。
IBM正在研發(fā)的是基于超導(dǎo)效應(yīng)的量子邏輯門架構(gòu)的通用量子計算機(jī)。對于量子計算機(jī)，國內(nèi)媒體報道轉(zhuǎn)載的很多，不過大多基本停留在翻譯英文媒體的水平。而且互相轉(zhuǎn)發(fā)，鮮有原創(chuàng)或者類似電子產(chǎn)品的試用評測。本文作者者恰好做過量子加密的研究和實驗，對于量子計算也有興趣，而且作者的專業(yè)之一光子學(xué)(Photonics)恰好也是量子加密/量子計算的物理實現(xiàn)途徑之一。
所以我們特約了一篇從淺入深，老少咸宜的科普介紹，來給大家解說量子計算機(jī)的原理，和普通計算機(jī)的區(qū)別，與咱們程序員有什么關(guān)系，并且作者還利用IBM的開放服務(wù)做了一些評測。希望沒有任何專業(yè)背景的讀者能從本文管窺全豹，同時對于擁有相關(guān)背景知識（主要是大學(xué)物理、量子力學(xué)和數(shù)字電路/模擬電路）的讀者也能有所收獲。
史蒂芬·威斯納在1969年最早提出“基于量子力學(xué)的計算設(shè)備”。1980年代一系列的研究使得量子計算機(jī)的理論變得豐富起來。在1981年五月的MIT物理學(xué)和計算機(jī)技術(shù)的一次會議上，1918年出生的美國物理學(xué)家理查德·費(fèi)曼，作了一個“Simulating Physics With Computers”的報告，揭開了研究發(fā)展量子計算機(jī)的新篇章。
費(fèi)曼在報告中提出：經(jīng)典的圖靈計算機(jī)可以用來模擬量子物理嗎？答案是否定的，用傳統(tǒng)計算機(jī)來模擬量子力學(xué)，計算量將隨著系統(tǒng)（微觀粒子數(shù)）的增大而指數(shù)增加。費(fèi)曼認(rèn)為微觀世界的本質(zhì)是量子的，想要模擬它，就得用和自然界的工作原理一樣的方式，也就是量子的方式才行。費(fèi)曼首先將物理學(xué)和計算機(jī)理論聯(lián)系到一起，他在MIT會上精彩的演講，使得計算機(jī)科學(xué)家開始關(guān)注物理學(xué)的進(jìn)展，關(guān)注量子力學(xué)。
1994年，貝爾實驗室的專家彼得·秀爾（Peter Shor）證明量子計算機(jī)能做出離散對數(shù)運(yùn)算，而且速度遠(yuǎn)勝傳統(tǒng)電腦。
2011年5月11日，加拿大的D-Wave 系統(tǒng)公司發(fā)布了一款號稱“全球第一款商用型量子計算機(jī)”的計算設(shè)備“D-Wave One”。
2013年5月，谷歌和NASA在加利福尼亞的量子人工智能實驗室發(fā)布D-Wave Two。
量子計算是一門理論科學(xué)。它是研究如何直接應(yīng)用量子力學(xué)現(xiàn)象（例如量子疊加態(tài)和量子糾纏態(tài)）對數(shù)據(jù)進(jìn)行操作的計算系統(tǒng)的科學(xué)。在最終的運(yùn)算結(jié)果上，量子計算機(jī)和現(xiàn)有計算機(jī)沒有任何不同（否則一定是有一方算錯了，那算錯的一方也就沒有什么實用價值了）。它們最大的不同之處在于運(yùn)算的過程有著天壤之別，后文將會詳細(xì)解釋。
量子計算模型，主要有3種：
● 量子電路模型
● 單向量子計算模型
● 絕熱量子計算模型
量子電路模型（Quantum circuit model）是把量子計算過程化成像經(jīng)典計算一樣有不同的“邏輯門”（當(dāng)然是quantum operation）作用在量子態(tài)上，最后得到所期待的量子態(tài)。
單向量子計算模型 （one-way quantum computation model） 是把量子計算，化成通過傳輸（teleportatio）和測量二維簇態(tài)（two dimensional cluster state），使得我們可以得到我們想要的量子門操作（quantum gates）。
絕熱量子計算模型（adiabatic quantum computation model）是通過先把問題劃歸成復(fù)雜的漢密爾頓量的基態(tài)（Hamiltonian ground state）的問題（即找到基態(tài)就可以找到最終結(jié)果），然后開始與一個簡單的漢密爾頓量，通過絕熱過程最后得到所需要的基態(tài)。
量子計算機(jī)造出來了，依然需要優(yōu)秀的算法。就像我們?nèi)粘Ｋ玫碾娮佑嬎銠C(jī)中的排序問題，寫得好的算法基本可以做到O（n*log（n））的時間復(fù)雜度，而差的算法很可能就是O(n^2)了。
舉一個非常實用的例子：快速傅立葉變換（FFT）在信號處理和圖像處理中是十分常見也非常有用的函數(shù)。它的時間復(fù)雜度是O（n*long(n))。借助量子計算機(jī)，F(xiàn)FT 的復(fù)雜度可以降低到 O((log(n))^2)，甚至連讀一遍數(shù)據(jù)的 O(n) 時間都不用，因為只要 log(n) 個量子比特就可以描述 n 維向量了。利用高性能的 FFT，因子分解的復(fù)雜度可以達(dá)到亞指數(shù)時間（sub-exponential time）。
目前量子計算機(jī)已經(jīng)以可擴(kuò)展的方式，使用 Shor's Algorithm 完成了對15的素數(shù)分解。有人表示：用 Shor 算法實現(xiàn)素數(shù)分解這一件事情，可以與經(jīng)典計算機(jī)中的 "Hello World!" 相提并論。 除了贊嘆它的開創(chuàng)性地位之外，也從一個側(cè)面說明目前量子計算還處在起步階段。
有了上面的介紹，有心的讀者應(yīng)該已經(jīng)了然于胸了：數(shù)據(jù)量越大，量子算法在時間復(fù)雜度上的優(yōu)勢就越明顯：n＝1000時，O（n^2)的傳統(tǒng)算法需要運(yùn)算一百萬步，而O(n*log(n))稍好，也得幾千步。而量子計算只需要幾步就完成整個運(yùn)算拿到最終結(jié)果了。
在大數(shù)據(jù)時代，n＝10000000是家常便飯，那么上邊的對比就成了10^12 vs 10^6 vs 10^2，在耗時上的差距是幾個數(shù)量級。
上面僅僅是以FFT為例子，實際上一旦找到實用的算法可以實現(xiàn)O(n)甚至O(1)的效率，那在大數(shù)據(jù)領(lǐng)域里就可以給常規(guī)電子計算機(jī)畫上句號了。
懂得量子算法的程序員，就會和目前熟悉深度學(xué)習(xí)算法以及大數(shù)據(jù)架構(gòu)的程序員一樣，變得格外搶手。
所以現(xiàn)在投入必要的時間精力學(xué)習(xí)一點量子計算的知識，是自我提高的一個不錯的選擇。而IBM量子體驗的網(wǎng)站，正好也提供了這個平臺和機(jī)會。
量子算法對云存儲行業(yè)，則多少會有些打擊。目前各個有能力的大國政府都在靜悄悄的研究量子計算以便即時破解重要的加密文件。而只要這個技術(shù)成熟可用，那么任何存儲在第三方的云數(shù)據(jù)都變得不安全了。因為哪怕是加密存儲，也可以在轉(zhuǎn)眼間被破解。
有了量子計算的威脅，用戶會更加保守的將敏感數(shù)據(jù)保存在只有自己能接觸到的物理環(huán)境，而不再會大大咧咧的加密上傳到第三方云存儲服務(wù)商。當(dāng)然，量子計算一定能同時帶動加密技術(shù)的發(fā)展。但是目前來看這對矛與盾的較量，在政府大機(jī)構(gòu)的影響下，應(yīng)該是解密技術(shù)占上風(fēng)且更容易流入民用。量子加密技術(shù)則主要還是有政府機(jī)構(gòu)掌握。所以從一點來看，量子計算的出現(xiàn)，對提供云存儲服務(wù)行業(yè)并不是一個利好消息。當(dāng)然，作為程序員，如果能理解甚至設(shè)計可靠的量子加密算法，也許很快就會成為IT業(yè)內(nèi)的搶手當(dāng)紅辣子雞，甚至被政府特工追殺也不是沒有可能。
量子計算研究的終極目標(biāo)之一是制造并應(yīng)用通用量子計算機(jī)（Universal Quantum computer）。以當(dāng)前的設(shè)計構(gòu)想，至少要能夠處理上百量子比特位（qubit）才有意義，目前IBM開放的5-qubit計算服務(wù)離這一目標(biāo)還差得很遠(yuǎn)。通用量子計算機(jī)的具體指標(biāo)可以參考《The Physical Implementation of Quantum Computation》（http://arxiv.org/abs/quant-ph?0002077 ）
而硬件上的具體物理實現(xiàn)有很多，比如通過：
● 光子學(xué)
● 核磁共振
● QED腔
● 量子點
● Redberg atom
● ion trap
● Josephson junction
等等來實現(xiàn)。
比較出名的D-wave 1代和2代使用的都是Josephson junction 。
NASA、CIA、Google都購買了D-wave進(jìn)行相關(guān)研究。牛津大學(xué)則和洛克馬丁、諾基亞合建了一個基于D-wave模型的量子人工智能的研究中心。D-Wave受到質(zhì)疑的地方在于其應(yīng)用場景受限，目前的設(shè)計并不是通用量子計算機(jī)。
而IBM正在研發(fā)的是基于量子邏輯門的通用型量子計算機(jī)，所以通用性沒有問題，所有的量子算法都能運(yùn)行。
此外，IBM還完成了兩個很重要的突破。
一是同時檢測兩種量子誤差（quantum errors）：1. bit-flip， 2. phase-flip。從而大大增強(qiáng)量了子計算機(jī)的穩(wěn)定性。
最簡單的單個量子比特的狄拉克表示： |Psi>=a|0>+b|1> ，其中a，b是兩個基態(tài)的系數(shù)。其他量子比特基態(tài)對還有|+>和|->, |spin+>和|spin->等。所以也可記為|Psi>=a|+>+b|->或者|Psi>=a|spin+>+b|spin->，采用何種正交基主要取決于量子系統(tǒng)的物理實現(xiàn)，例如光子的偏振態(tài)、粒子的自旋等等，這里就不再深入。
一個量子比特是兩個標(biāo)準(zhǔn)正交比特0和1的任意疊加。a和b滿足歸一化條件即可，所以a和b之間有一個相位自由度。如果相位在量子計算過程中被干擾，這個flip就是就是phase-flip。 bit-flip就是運(yùn)算操作過程中0意外變成1，或者1意外變成0了。理想情況下，量子計算不會有誤差。 但實際上由于環(huán)境噪音（主要是熱和電磁輻射），量子系統(tǒng)會受到環(huán)境干擾。只有在零場強(qiáng)和絕對零度的環(huán)境里，才能有理想狀態(tài)下的量子計算。D-wave是在20mk（零下273.13度）工作的，IBM用的也是超導(dǎo)芯片，工作溫度是15mk（零下273.135度，僅比絕對零度-273.15度高0.015度）。
之前的研究只能測量兩個error中的一個，也就無法做到EC（error correction）。如今IBM解決了這個問題(http://spectrum.ieee.org/tech-talk/computing/hardware/ibm-shows-first-full-error-detection-for-quantum-computers)。
二是IBM提供了有史以來最好的可擴(kuò)展性。當(dāng)然落實在實際硬件開發(fā)應(yīng)該還會有新的問題。IBM接下來的目標(biāo)應(yīng)該是把量子比特加到50至100。再往后就需要更多的研發(fā)資源了。
在這里附帶澄清一下很多媒體對量子比特的普遍誤解，以及連帶到對量子計算的誤解：對于量子計算的優(yōu)勢，媒體上常見的解釋是，相比較我們常用的電子計算機(jī)采用的0，1二進(jìn)制值，量子計算機(jī)每一個量子位都能存儲0到1之間的信息。這是一個想當(dāng)然的解釋，這根本不是量子計算機(jī)的本質(zhì)優(yōu)勢：
因為很明顯我們用電阻電容組成的模擬電路一樣可以表征0到1之間的任何連續(xù)值。所以說本質(zhì)區(qū)別不是比特位所攜帶數(shù)值的無窮可能性，而是比特信息的量子疊加態(tài)特性。對于多比特位的運(yùn)算，量子計算機(jī)的優(yōu)勢才得以明顯體現(xiàn)：所有的比特位可以同時完成邏輯運(yùn)算，這一點是傳統(tǒng)電子計算機(jī)根本做不到的。
對于多比特位的量子系統(tǒng)，整個系統(tǒng)的量子比特位狀態(tài)是可定量預(yù)測的，而單個量子比特位是不能確定的。
舉一個簡單的例子來說明這種量子態(tài)的疊加關(guān)聯(lián)性——在IBM量子計算服務(wù)的教程里也用到的十分常見的Hadamard Gate:
Hadamard Gate的功能就是將輸入 α0|0?+α1|1?，轉(zhuǎn)換成輸出 2^{-1/2}(α0+α1)|0?+2^{-1/2}(α0-α1)|1? 。換言之，Hadamard Gate 就是把經(jīng)典的狀態(tài) |0? 和 |1? 轉(zhuǎn)換成 |0? 和 |1? 的“halfway" 狀態(tài)。
關(guān)鍵之處在于：這個操作，即使是僅對 n 個量子比特中的第一位進(jìn)行Hadamard gate 運(yùn)算，所有的 2^{n} 個系數(shù)都會改變。這里的“并行”運(yùn)算是量子力學(xué)的物理本質(zhì)確保的，而不是很多媒體中不明就里的多核多設(shè)備的”并行/多線程“。
回到IBM 量子計算的實驗室硬件，下面放了兩張從官方網(wǎng)站視頻中的截圖：
圖一是開放式稀釋冰箱（ open dilution refrigerator）。冰箱底部的溫度最低，低到僅比絕對零度高15mK，以便維持芯片中超導(dǎo)材料的超導(dǎo)狀態(tài)，用來處理量子信息 。
圖二 是冰箱的氣體處理系統(tǒng)。面板顯示的是閥門以及泵的開關(guān)情況。冰箱里使用的氣體是氦的同位素氦氣-3（Helium-3） 。
看完這么多高大上高冷貴的東西，再來看看IBM為愛好者提供了什么試用服務(wù)。
下圖是申請到的試用帳號，下面按照他們的教程（User Guide）嘗試的幾個實驗。
第一部分（The IBM Quantum Experience）是面向所有人介紹世界上第一個基于云端的量子計算服務(wù)。
第二部分（The Weird and Wonderful World of the Qubit）是介紹基本的量子比特常識
第三部分（Multiple Qubits, Gates, and Entangled States）通過四個小課程演示多量子比特的復(fù)雜性和精巧之處。
第四部分（Quantum Algorithms）更深入的介紹量子世界的奇妙之處，介紹可用于編程的量子算法。
第五部分（Quantum Error Correction）介紹如何利用量子糾纏態(tài)糾錯
第六部分（FAQ）就是常見問題的回答。
頁面右下端還有一個小蟲子的圖標(biāo)，方便用戶反饋各種bu
IBM官方介紹視頻里用的是Grover's Search算法做例子，這里我就以Deutsch-Jozsa 算法再舉一個例子。畢竟這個例子的物理模型可以對應(yīng)于光學(xué)中雙縫干涉，看上去格外親切。
Deutsch-Jozsa Algorithm簡介
Deutsch-Jozsa 量子算法是第一個證明量子算法能繞過經(jīng)典算法困境的例子。這個算法演示允許量子振幅取正值和負(fù)值，而不像傳統(tǒng)的概率必須總是非負(fù)的。
Deutsch-Jozsa量子問題定義如下?？紤]一個函數(shù)f（x）對輸入的n比特位x返回0或1。
假設(shè)我們確保f（x）或者是一個常數(shù)函數(shù)，它的返回值是常數(shù)c，對所有輸入x有c∈{0,1}，或者f（x）是平衡函數(shù)，對任何0，1輸入他都取半值。我們的目標(biāo)是通過盡可能少的嘗試來確定f（x）到底是常數(shù)函數(shù)還是平衡函數(shù)。傳統(tǒng)算法在最壞情況下需要進(jìn)行2^(n-1) + 1次計算。而使用Deutsch-Jozsa量子算法，這個問題可以只用一次運(yùn)算來解答。
要了解Deutsch-Jozsa量子算法是如何工作的，讓我們先考慮一個典型的干涉實驗：其行為類似波的粒子，如光子，可以從源頭上檢測器陣列通過兩個或多個路徑行進(jìn)。觀察到粒子出現(xiàn)概率大的區(qū)域是入射波在到達(dá)時具有相同的相位的區(qū)域。
設(shè)想我們可以建立一個干擾實驗，具有2^n個探測器和從源到每個探測器的2^n個可能的路徑。我們將其分別標(biāo)記為n比特輸入x和n比特探測器y。進(jìn)一步假設(shè)x與探測器y沿路徑累積的相位等于C（-1）^(f(x)+x+y)，其中
x?y=Σi= xiyi
是二進(jìn)制的內(nèi)積（點乘），C是歸一化系數(shù)。觀察檢測器y中的粒子出現(xiàn)的概率可以通過累加所有路徑的幅值x到達(dá)y時的絕對值平方來計算：
PR（y）= |CΣx（-1）^(f（x）+x?y)| ^2
歸一化條件ΣyPr（y）= 1，則使C = 2^(-n)。接下來計算檢測器Y = 0^N觀察粒子的概率譜（Y = 0^n）（全零字符串）。我們有Pr（Y = 0^n）= | 2^(-n)Σ（-1）f（x）|^ 2
如果函數(shù)f（x）= c是常數(shù)函數(shù)，我們將得到譜Pr（Yy= 0^n）= |（-1）^c |^ 2 = 1。而當(dāng)f（x）是一個平衡函數(shù)時，我們會得到Pr（y = 0^n）= 0，因為所有的總和超過x的項彼此抵消。
因此，我們可以只用一次實驗判斷是否f（x）是常數(shù)還是平衡函數(shù)。
當(dāng)然，以光學(xué)手段進(jìn)行這個實驗不太實際，因為它需要一個非常大的光學(xué)平臺！但是，我們可以用量子計算機(jī)模擬這個實驗，僅用n量子比特和訪問Oracle電路Uf就能實現(xiàn)。
事實上，考慮下面的算法：
第1步：初始化n的全零狀態(tài)量子比特| 0，...，0>。
第2步 應(yīng)用Hagamard門H至每個量子位。
第3步. 應(yīng)用Oracle電路Uf。
第4步：重復(fù)步驟2。
第5步：測量每個量子位。設(shè)y =（y1，...，yn）是測量結(jié)果的列表。
如果f是一個常數(shù)函數(shù)，那么將會觀測到y(tǒng)是全零字符串。Hagamard門將輸入|0>映射到均勻疊加的|0>和|1>。 第二步之后系統(tǒng)的狀態(tài)是2^(-n/2)Σ|x>。
接著Oracle電路將此狀態(tài)映射到2^(-n /2)Σ（-1）^f(x)|x>。第4步再次應(yīng)用Hadamards門，它將基態(tài)|x>映射到一個疊加態(tài)2^(-n/2)Σ（-1)^(xy)|y>。第4步完成后系統(tǒng)的狀態(tài)是|ψ>=Σψ（y）|y>，其中ψ（y）= 2^(-n)Σ（-1）^(f（x）+x?y)。
這正是我們需要的干擾實驗。
在步驟5的測量起著檢測粒子的作用。如上結(jié)果表明，如果概率y=0^n值為1，則f是一個常數(shù)函數(shù)。為零，則f是一個平衡函數(shù)。因此，我們只通過一次運(yùn)算就解決了Deutsch-Jozsa量子問題的確切解答。
拉拉雜雜扯這么多，沒有量子力學(xué)基礎(chǔ)的讀者可能有點暈。那么下面就是實際量子線路的設(shè)計：
一 n=3，函數(shù)為常數(shù)函數(shù)時的模擬：
結(jié)果跟理論分析預(yù)測的是一樣的，即輸出為1
二 n=3，函數(shù)為平衡函數(shù)時的模擬：
輸出跟理論分析預(yù)測的是一樣的，即輸出為0
從外界的評價來看：“……IBM所做的是對的。該服務(wù)的界面易于使用，“任何對量子計算機(jī)有所了解的學(xué)生都知道如何與這個設(shè)備交互?！?/p>
Cory周末對IBM這個新服務(wù)進(jìn)行了試用，讓他吃驚的是：這個系統(tǒng)相當(dāng)穩(wěn)定——每一次測試它幾乎都得到了相同的結(jié)果。這在傳統(tǒng)計算機(jī)中是個尋常的現(xiàn)象，但在基本都是圍繞捕獲概率展開的量子計算機(jī)世界中，結(jié)果的穩(wěn)定一致就意味著標(biāo)志性的進(jìn)步。 ”
IBM的確用他的量子計算平臺證明了他的突破之一：對雙誤差同時測量來大大提高系統(tǒng)的穩(wěn)定性。此外能對公眾開放5qubit的平臺，也給大家留下了想象的空間——IBM到底能在短期內(nèi)將qubit推進(jìn)到多少位？
IBM提供的這個平臺，看上去是為自己的研發(fā)成果和企業(yè)品牌打廣告，事實也的確起到了廣而告之的作用。
但是如果你真的認(rèn)為就只有這么點兒信息，那說明你還沒有親自嘗試網(wǎng)頁上的各種量子計算和算法。
如果你稍有嘗試，應(yīng)該不難發(fā)現(xiàn)，IBM提供的其實是一個雙向?qū)W習(xí)的平臺：嘗試用戶可以從中學(xué)習(xí)了解量子計算的各項基本知識和常見算法，IBM則可以從中統(tǒng)計用戶的大致認(rèn)知水平。
既然每個用戶都是用郵箱注冊，又在平臺上擺弄了一番。IBM的研究團(tuán)隊也會從試用用戶中發(fā)現(xiàn)具備相關(guān)背景知識、能熟練實用的“高級用戶”，說不定這些用戶在不久就能從注冊郵箱收到IBM的招聘挖人郵件呢——這只是yy而已，不過既然人家免費(fèi)提供了這個學(xué)習(xí)平臺，為什么不利用閑暇時間了解學(xué)習(xí)一下，提高一下作為程序員的未來職業(yè)素養(yǎng)呢。
雷鋒網(wǎng)注：本文轉(zhuǎn)自大數(shù)據(jù)雜談，如需轉(zhuǎn)載請聯(lián)系原作者。
雷峰網(wǎng)版權(quán)文章，未經(jīng)授權(quán)禁止轉(zhuǎn)載。詳情見轉(zhuǎn)載須知。
