如何用 IT 業者能聽懂的話介紹量子計算的原理？

11-16

量子的不可測性質很容易從維基百科等地方做一些了解，但是這一性質如何能夠運用於可計算理論？

量子退火和量子比特的基本原理都是什麼？數學問題是如何轉換為依辛模型的求解問題的？依辛模型的求解又是如何轉換為量子過程的？

假設讀者只是一般的IT技術人員，請用讀者能看懂的語言進行介紹，謝謝！

本問題已收錄進圓桌：動態 - 將科學研究進行到底
更多討論歡迎關注: ）

謝邀。

量子計算/量子計算機的概念是著名物理學家費曼於1981年首先提出的。
後來大家試了試才知道，原來真的可以這麼玩。
【費曼還首先在Tiny Machine的課堂上首先提出了納米科學這一個概念，他課堂的學生某種意義是人類第一批納米科學家。然後又一個新領域誕生了。所以現在美國的納米科學領域的獎叫做費曼納米技術獎。

類似的，薛定諤有一個一系列講座叫《What is life》。他在《生命是什麼》里用物理思想詮釋了自己對生命的理解。他把信息、負熵等思想（食物就是負熵）引入了生命科學，然後分子生物學（生命科學最重要的領域之一）誕生。】

這些行走在人類能力圈邊緣的天才物理學家們總是有著這夢幻般的的創作力。所思所想皆對人類做出巨大貢獻。

量子計算的原理實際上應該分為兩部分。一部分是量子計算機的物理原理和物理實現；另一部分是量子演算法。
關於物理部分，我直接上郭光燦院士的文章吧。他是我國量子光學的泰斗級人物。我自認為不會比他講的更好。
【USTC物理的強大實力差不多有一半來自於潘建偉院士和郭光燦院士領導的量子物理領域。郭院士是一位非常和藹的老人。我本科期間還向他請教過量子物理相關的問題。：）】

量子計算

　　量子比特可以製備在兩個邏輯態0和1的相干疊加態，換句話講，它可以同時存儲0和1。考慮一個 N個物理比特的存儲器，若它是經典存儲器，則它只能存儲2^N個可能數據當中的任一個，若它是量子存儲器，則它可以同時存儲2^N個數，而且隨著 N的增加，其存儲信息的能力將指數上升，例如，一個250量子比特的存儲器（由250個原子構成）可能存儲的數達2^250,比現有已知的宇宙中全部原子數目還要多。

　　由於數學操作可以同時對存儲器中全部的數據進行，因此，量子計算機在實施一次的運算中可以同時對2^N個輸入數進行數學運算。其效果相當於經典計算機要重複實施2^N次操作，或者採用2^N個不同處理器實行並行操作。可見，量子計算機可以節省大量的運算資源（如時間、記憶單元等）。

【這部分就是最基本的原理了。關於基本原理，IT人士看這段應該就夠了。】

為開拓出量子計算機巨大的並行處理能力，必須尋找適用於這種量子計算的有效演算法。 Shor於1994年發現第一個量子演算法，它可以有效地用來進行大數因子分解。大數因子分解是現在廣泛用於電子銀行、網路等領域的公開密鑰體系 R SA安全性的依據。採用現有計算機對數 N（二進位長度為 l ogN）做因子分解，其運算步驟（時間）隨輸入長度（ l ogN）指數增長。迄今在實驗上被分解的最大數為129位，1994年在世界範圍內同時使用1600個工作站花了8個月時間才成功地完成了這個分解。若用同樣計算功能來分解250位的數則要用80萬年，而對於1000位的數，則要有10^25年。

與此相反，量子計算機採用 Shor演算法可以在幾分之一秒內實現1000位數的因子分解，而且操作時間僅隨輸入數的3次方增長。可見 Shor量子演算法將這類「難解」問題變成「易解」問題。在量子計算機面前，現有公開密鑰 R SA體系將無密可保！

　　Shor的開創性工作有力地刺激了量子計算機和量子密碼術的發展，成為量子信息科學發展的重要里程碑之一。

【第一個(有實用價值的)量子演算法。】

　1997年Grover發現了另一種很有用的量子演算法，即所謂的量子搜尋演算法，它適用於解決如下問題：從 N個未分類的客體中尋找出某個特定的客體。經典演算法只能是一個接一個地搜尋，直到找到所要的客體為止，這種演算法平均地講要尋找 N／2次，成功幾率為1／2,而採用Grover的量子演算法則只需要 Nkk√次。例如，要從有著100萬個號碼的電話本中找出某個指定號碼，該電話本是以姓名為順序編排的。經典方法是一個個找，平均要找50萬次，才能以 1／2幾率找到所要電話號碼。 G rover的量子演算法是每查詢一次可以同時檢查所有100萬個號碼。由於100萬量子比特處於疊加態，量子干涉的效應會使前次的結果影響到下一次的量子操作，這種干涉生成的操作運算重複1000（即 N √）次後，獲得正確答案的幾率為1／2。但若再多重複操作幾次，那麼找到所需電話號碼的幾率接近於1。

　　Grover演算法的用途很廣，可以尋找最大值、最小值、平均值等，也可以用於下棋。最有趣的是可有效地攻擊密碼體系，如 D ES體系，這個問題的實質是從256＝7×1016個可能的密鑰中尋找一個正確的密鑰。若以每秒100萬密鑰的運算速率操作，經典計算需要1000年，而採用Grover演算法的量子計算機則只需小於4分鐘的時間。難怪 G rover以「量子力學可以幫助在稻草堆中尋找一根針」這樣的題目在 P RL上公布他的演算法。

【非常有用的Grover搜索演算法。】

　　Feynman最先（1981年）指出，採用經典計算機不可能以有效方式來模擬量子系統的演化。我們知道，經典計算機與量子系統遵從不同的物理規律，用於描述量子態演化所需要的經典信息量，遠遠大於用來以同樣精度描述相應的經典系統所需的經典信息量。量子計算則可以精確而方便地實現這種模擬。採用少數量子比特的量子計算機可以進行有效的量子模擬，事實上人們已採用這種方法在簡單情況下預言了量子體系的行為。

　　一般地說，量子模擬可以按下列步驟來完成：①根據所研究的量子體系的哈密頓量，設計出能夠實現相應的幺正變換的量子網路；②將 N―量子比特按照要求製備為特定初態；③操作計算機進行模擬運算。計算機的終態就是所需的量子態。因此，一旦人們有了量子模擬計算機，就無需求解薛定諤方程或者採用蒙特卡羅方法在經典計算機上做數值運算，便可精確地研究量子體系的特性。

　　有許多量子體系可以用這種方法來研究。例如：①高溫高密度等離子體；②採用格點規範理論描述的體系，如量子色動力學；③晶體固態模型，包括諸如 H ubbard模型的固體費米系統，其量子對稱性使得它們難以採用蒙特卡羅技術來模擬；④固體模型，包括諸如高溫超導體的長程關聯；⑤分子行為的量子模型等等。

　　然而，量子計算的實現在技術上遇到嚴重的挑戰。實現量子計算必須解決三個方面的問題：一是量子演算法，它是提高運算速度的關鍵，目前已研究成功 S hor量子並行演算法、 G rover量子搜尋演算法等；二是量子編碼，它是克服消相干的有效辦法，目前已有量子糾錯、量子避錯和量子防錯三種不同原理；三是實現量子計算的物理體系（即多個量子比特的量子邏輯網路），目前在腔 Q ED、離子阱、核磁共振、量子點等系統已實現少數量子比特，但距實現有效量子計算的需求相差甚遠。各國科學家正從不同途徑來探索實現可擴展的量子邏輯網路的方法，雖然不斷取得進展，在《自然》、《科學》上每年都有許多重要進展發表，但仍未根本上突破。這個領域仍處於基礎性的探索階段。

【上面是技術上的問題。】

最後我覺得必須要補充的是：人類第一個商用量子計算機Dwave和另一個非常重要的演算法——量子退火（說不定是目前為止最重要的量子演算法）。
量子退火演算法已經在超級計算機上被笨拙地模擬過了，下一步是拿到真正的量子計算機上運行。
Google和NASA合建的量子人工智慧實驗室用的就是這種計算機。
量子退火演算法的提出者是西森教授。
【接下來的兩年里應該會和導師經常去拜訪他。：）】

但很可惜的是，Dwave並不是通用型量子計算機，只能運行量子退火（Quantum Annealing）演算法這一種演算法而已。因為它的構造就是為基於量子退火設計的，沒辦法做其他量子計算。
所以很多人並不覺得這是真正的量子計算機，只認為這是一種具有特定計算功能的量子結構。

不過量子退火演算法實在是太有用了。所以Dwave還是很有吸引力的。找global minimum是機器學習等領域繞不開且相當費時一個過程。而量子退火可以極好地提速。

Quantum annealing (QA) is a general method for finding the global minimum of a given objective function over a given set of candidate solutions (candidate states), by a process using quantum fluctuations.
It is used mainly for problems where the search space is discrete (combinatorial optimization problems) with many local minima; such as finding the ground state of a spin glass employing quantum tunneling (across the barriers separating the global minimum from the local minima or spin configurations).

--------------------------------------------
量子退火演算法是模擬退火演算法的進階。模擬退火演算法用的是熱力學的退火思想找minimum。而量子退火的中心思想是，量子力學的隧穿效應可以在尋找global minimum的時候更快地穿過局域極值點旁的勢壘。

來自wiki:

來自wiki:Quantum annealing

更新了！~更新了！稍微寫的更詳細一點。我覺得這樣應該能懂了。

請專家指正。下面論述是我個人的理解。這裡是談量子計算所以和糾纏瞬間塌縮關係不大。(當然我們也知道不能超光速傳遞信息。) 當然這是一種委婉的說法其實就是沒有關係。量子通信是另外一個問題與這個問題無關。

量子比特的基本原理：這一部分我們會闡述二進位，二進位序列和對二進位序列的操作。

我們首先來看計算機是怎麼保存數據的。計算機中，用0和1二進位序列保存數據。抽象的來看，二進位0和1分別代表了系統的兩種「狀態」。也就是說，我們只要能夠找到一個有兩個可以區分的狀態的系統，就可以抽象的實現計算機的二進位。因此我們首先討論如何在系統中實現二進位。

在經典計算機中，01由不同的電壓實現，0代表低電壓信號，1代表高電壓信號。
在量子力學中，我們有很多天然的雙態系統來實現這種兩個可區分的狀態(不需要太糾結量子力學的態表示什麼)。比如自旋1/2系統，這在量子力學中對應自旋向上/向下兩種狀態的系統；或者更經典的光子的極化，比如一束光具有不同的偏振狀態(比如左旋/右旋偏振光)。總之，我們能夠在量子力學中找到實現二進位的系統。

在實現二進位之後，我們的下一步是需要得到二進位序列。

在經典計算機中，二進位序列由一個高低電壓交錯的脈衝實現。比如001對應於一個低電壓-低電壓-高電壓的信號。在量子力學中，我們通過糾纏態實現二進位序列。具體而言，比如某個光子處於態 $| psi angle$ 上，我們可以把這個光子和其它光子糾纏起來得到一個N光子糾纏態 $| phi angle = | psi angle ^{otimes N}$ ，這樣我們就實現了一個二進位的序列。

在這裡，量子世界和經典世界出現了不同。在經典世界中，我們只能同時擁有一個狀態。比如，如果我們擁有了001態，我們就不能同時擁有010態，這是因為兩個態的電壓會疊加，如果同時擁有這兩個態的話我們只能夠得到011態。但是在量子世界中，我們可以得到疊加態。具體來說，系統的狀態可以同時處於 $| psi_0 angle= a|001 angle + b |010 angle$ 態。其中疊加係數a,b的模方表示我們在測量中得到相應態的概率。比如，我們得到 $| 001 angle$ 的概率是 $|a|^2$ 。當然概率歸一化要求 $|a|^2 + |b|^2 =1$ 。

我們闡述的態疊加原理會導致什麼後果呢？比如我們通過Hadamard門製備了一個態， $| psi angle = frac{1}{sqrt 2} (|0 angle + |1 angle)$ 並用這個態製備一個N光子糾纏態 $| phi angle = | psi angle ^{otimes N}$ , 那麼我們看到，這個態就同時處於 $|000cdots 0 angle$ 到 $|111cdots 1 angle$ 的等概率疊加態。(最簡單的例子，比如 $| psi angle ^{otimes 2} = frac{1}{2} (|0 angle + |1 angle ) otimes (|0 angle + |1 angle ) = frac{1}{2} (|00 angle + |01 angle +|10 angle+ |11 angle)$ )

這個事實說明了什麼呢？與經典演算法不同，我們的操作可以同時對上面的所有態進行。因此，如果我們能夠找到一種有效的演算法來同時處理這些態，那麼我們就能夠進行並行計算，因此我們演算法的速度比起經典就大大提高了。這個並行與經典的並行演算法的區別在於，經典的並行是把任務分成小的部分(比如算一個加法12+34，我們可以同時加十位和加各位然後最後加上兩個結果)，量子並行是同時處理了很多不一樣的狀態(同時計算了12+34，23+45, ...)。

比如Grover 演算法。

量子退火：我們先要看看經典退火演算法是如何實現的。經典退火演算法是一種加入概率的貪心演算法。通常搜索極值的最簡單的方法就是將某一點的值與附近的點的值比較，如果我們找到一點它的值比附近的點的值都大或者都小的話那麼我們就找到了局部極值。但是這樣搜索的話有可能不能得到整體的極值點。經典退火演算法對上述過程進行了修正，它以一定的概率 $p(E)$ 使得系統在處於局部極值時可以移動到附近一個不是局部極值的點。為了系統最後能夠得到穩定解，隨著時間推移，這個概率必須逐漸趨近於0。這個過程與物理中的玻爾茲曼分布類似。在玻爾茲曼分布中， $p(Delta E) sim e^{-Delta E/kT}$ ，其中 $Delta E$ 是兩個不同狀態的能量差，這裡能量對應各點的函數值。如果我們漸漸降低溫度，那麼我們看到只要 $Delta E eq 0$ 那麼概率就會趨向於0。上述降低溫度的過程在人類製造金屬的歷史上稱為「退火」。

量子退火的核心思想也是這樣。我們需要讓系統具有一個遠離局部極值點的概率(這樣才能走向最值點)，並讓這個概率最終趨於0(才能穩定在最值點)。與經典退火不同的是，我們發現在物理的量子力學系統中具有隧穿效應，因此量子力學系統本身就具有一個自然的偏離局部極值點到達全局極值點的概率。不太嚴格的說，這個隧穿概率 $P(E) sim e^{- sqrt E x/hbar}$ ，其中x為兩點的距離， $hbar$ 為一個參數。因此我們看出系統的總能量越高，隧穿概率越大。因此，我們的退火演算法對應著一開始系統具有一個很大的總能量，在給定初始位置的情況下就是系統的初動能很大，在這個情況下系統有比較大的概率從局部極值移動到不是局部極值的點。隨著時間增加，我們把系統的動能減小，相應的總能量減小，隧穿概率減小，隨後我們就能夠達到一個穩定的極值點。

總結一下，兩種演算法都是簡單的貪心演算法加入了一個移動概率。量子退火演算法的移動概率天然的是系統的隧穿概率。量子演算法的好處是由於系統能夠往全局最值隧穿因此不像經典演算法那樣我們在翻越勢壘的時候有一定的概率接受當前的局部極值因此可能好一些。

根據上面的討論，我們看出，優化函數對應量子力學中的勢能，優化的過程是給系統加入一個衰減的初始很大的動能項。最後系統的態就處於勢能的最值位置。

由於隧穿概率是正比於距離的，因此我們看出量子退火的有效性與局部極值和全局最值的距離很有關係。另一方面由於躍遷概率與能量差相關，所以經典退火的有效性和局部極值和全局最值中間的勢壘高度很有關係。

有的物理文獻是通過絕熱定理來討論的。這裡略去。參考Science的文章。 doi: 10.1126/science.1057726
.

另外好像實際上因為一般沒有(買不起)量子計算機(退火專用)我們實際上使用的是路徑積分蒙特卡羅來做模擬的。

另外似乎沒有量子演算法優於經典演算法的證明或者證據。在某些具體問題中經典退火更快。

數學問題轉為伊辛模型：通常在這裡說的伊辛模型是隨機場伊辛模型(random field ising model)。待續。

伊辛模型轉化為量子過程：伊辛模型本身就是量子的。物理上的所有統計都是量子的。因為伊辛模型就是描述很多個自旋(理解為有很多個雙態，也就是01)的相互作用的最簡單模型。

IT技術人員學習演算法的時候會學到隨機尋優演算法。具體說來有這樣一個問題：請找出一座大山中最高的山峰。

普通青年看，這是一個線性複雜度O(N)的問題，遍歷整座山之後能夠準確得出哪個山峰最高的答案。

2B青年想偷個懶，就隨便找個地兒，開始一根筋往上爬，爬到最高處就宣布這就是最高峰了。2B青年的演算法叫做Hill Climbing登山演算法。這種演算法可以快速得出局部最優解。

文藝青年不像普通青年那麼勤奮，也不想2B青年那麼一根筋往上爬，在爬山過程中會不斷溜號去抓個蝴蝶采朵花，經常會爬到其他山峰上去，他可以根據爬過的多個山峰大概判斷出來哪個山峰是最高的。這就是Simulated Annealing模擬退火法。

NB青年開著滑翔機在山中隨風飄動，在山中繞來繞去，很快目測出最高峰是哪個。這個就是量子退火演算法。其實跟模擬退火演算法類似，只是利用量子隧穿效應代替隨機數跨越不同山峰，避免局部最優解。跟傳統模擬退火演算法不同的是，量子退火演算法不是「量」出來的，而是「看」出來的。這是DWave最終被Google定性為量子計算機的重要依據。

最後是土豪青年高帥富，直接開著飛機從天上往下看，雖然沒有通過近距離測量，他還是一眼就看出了哪個山峰是最高的。這就是量子演算法，整座山就可以類比波函數的波峰波谷疊加。

看了幾個答案，我的理解如下：
比方說我們求解一個問題，一個 1公斤的鐵球，從3米高的地方丟下來，多久接觸地面？
經典計算機的演算法，就是用公式，用演算法計算，而量子計算就是搞個鐵球，實際丟幾次，測量結果。

量子有種特性叫疊加態，假設有狀態 A，狀態 B。疊加態就是 AB 的疊加，用二進位的說法就是同時表示 0和1.

於是，如果有5個量子他們都處於疊加態，那麼就包含了 00000~11111 (二進位) 所有數字的疊加，我們想要的答案，當然在裡面。而我們使用的量子演算法，類似於一種實驗過程，讓他們發揮物理特性，按我們設計的演算法退出疊加態，退出疊加態的量子，有些退成了A，有些成B。我們最後測量到的 ABBAA (01100) 就是計算結果。

由於量子演算法利用了量子的物理特性，所以我們可以讓疊加態的量子高概率的塌陷到我們想要的結果上。

換句話說，我們並非是去計算結果，而是按我們的要求去觀測，直接看到結果。

也不知道我這樣的理解是否正確。

初學者寫了一篇關於量子計算的小文章，請多指教：量子計算（一）

進入公司之後第一次聽到「量子計算」這個概念，一直覺得十分神秘。從維基百科或者知乎上看量子計算機利用量子來提升效率，有極強的並行能力，可以加速很多演算法等。但是個人還是對這個方向了解甚少。直到前幾天聽完組裡面大神的講座，並用《Quantum Computing: From Linear Algebra to Physical Realizations》一書的作為量子計算的入門讀物。讀後豁然開朗，雖然也對這個方向了解也不夠深入，不過還是略做筆記作為分享。作為一個量子計算的初學者，還是有很多理解不夠到位之處，希望大家指正。

　　普通計算機一個比特（bit）可以表示 0 或者 1。而量子具有不確定性，這使得一個量子比特（qubit）需要被描述成 α0|0?+α1|1?（量子比特的 0 狀態記作 |0?，1 狀態記作 |1?），其中 |α0|^2+|α1|^2=1。也就是表示了這個量子比特有 |α0|^2 的概率是 |0?，有 |α1|^2 的概率是 |1?。這裡面的 α0 和 α1 都是複數，所以要先取模再平方才是其概率。可以記作 p(0)=|α0|^2, p(1)=|α1|^2, p(0)+p(1)=1。舉例說明：

參見原文：量子計算（一）

2016年3月

－－－－－－－－－－－－－－－－－－－－－－－－－－

時隔一年多，重新整理了一份量子計算的PPT，量子計算（一）

2017年10月21日

其實很好理解，
最最基礎的傅立葉變換，普通計算機儲存的是數據，量子計算機儲存的直接就是分解後的結果，這一步不需要任何計算成本。你直接想像大因數分解，量子計算機在做分解的時候其實就是儲存過程，每個正交狀態對應一個素數，存儲的過程天然就分解了這個數。最好不要把1，0這些傳統概念套上去，這樣不好理解。比如21怎麼在量子態下表示？首先我們得找到對應的正交態，這自然是素數了，21=3×7,那麼 |21&> = |3&> + |7&>就可以了，這裡的正交態對應的就是傳統的1，0.。同樣的道理也用在矩陣計算上，直接儲存的就是正交矢量

作為一名CS的學生，看了知乎關於量子計算原理這方面的好幾個問題以及好多回答，然後又跑去網上聽中科大郭光燦院士的公開課。但是並沒有明白量子態是怎麼用於計算的，直到看到這篇文章
量子計算機編程原理簡介和機器學習
希望對想科普量子計算的朋友有幫助

我不是來回答的，我是來提問的。
我的理解可能跟大家不一樣。

我對量子存儲的理解疑惑最大。
它的存儲是疊加態，那麼一個比特能夠疊加多少次？
我的理解是多少次跟比特位有關，N位量子比特的話每個比特位就可以疊加2^N次，這樣才能說是存儲了2^N個數，是這樣嗎？
寫入和讀取每個數的方式又是怎樣的？
其實我的關鍵疑問是——量子比特如何容納那麼大信息量，怎樣進行存取操作，一個量子比特位究竟有多少個狀態？

本人是程序員，在知乎上拜讀@Summer Clover 關於量子計算機的介紹，對量子計算有了一定的了解，下面就用程序員的語言試著分析一下量子計算機的優勢

在我看來量子計算機有兩大優勢：

1.存儲能力超強

電子計算機中的數據是以二進位存儲的，而量子計算機存儲的是四進位數。
為什麼這樣說？
電子計算機中的寄存器具有兩個可以相互轉換的穩定狀態，人們利用這兩種狀態分別表示0和1。因此，電子計算機存儲的基本數據單元是bit也就是一位二進位數0或1。假如我有十個晶體管就可以表示 $2^{10}$ 種不同的狀態。
量子計算機中的寄存器具有【兩對】兩個可以相互轉化的穩定狀態，這兩對狀態可以分別表示兩位二進位數。量子計算機中的一個基本數據單元就是一位四進位數。十個量子存儲單元可以表示 $4^{10}$ 種不同狀態。
可能聽起來比較繞，可以嘗試抽象到面向對象的思想中：
把「電子計算機的bit」看作一個類，它具有一個屬性，這個屬性是bool類型的。
而「量子計算機的bit」類有兩個屬性，兩個屬性同樣都是bool類型。

$4^{10}$ / $2^{10}$ = $2^{10}$ 具有等量的存儲單元的情況下，量子計算機的存儲能力是電子計算機的 $2^{n}$ 倍！
這是什麼概念？
電子計算機中1Kb的數據在量子計算機中相當於10byte
1Mb相當於100byte
1Gb相當於1000byte
……………………
而現在絕對算的上是「大數據」的1Pb數據量僅僅相當於量子計算機中的0.1Mb
媽媽再也不用擔心我的硬碟不夠大了……

2.運算能力超強

當我們在計算機下編程時，不管是使用何種語言，最終都要轉化為機器碼進行運算。也就是對寄存器中的二進位數進行運算。

下面出一道程序題：a=1,b=0,c=0,d=1; 求 a+b, c+d 的值。

在電子計算機中要這樣做：
x=a+b;
y=c+d;

而在量子計算機中，一個「量子計算機byte」有兩個屬性，可以把一個量子byte對象看做是一個向量。上面那道題就變成了：x=(a,b), =y(c,d);求x+y
解：
z = x+y;

在此時，一次量子計算相當於兩次電子計算。在電子計算機中需要計算 $2^{n}$ 次的問題在量子計算時只需要n次！

看到這裡只要是懂點演算法的同學就應該精神了，這就是說，那些O( $2^{n}$ )的「難解問題」現在都成了線性的，隨著n的增加，運算量不再呈指數級飆升，而僅僅是線性增加！

突然發現許多從前認為不可能的事變得很近。比如應用廣泛的TSP旅行商問題，如果能夠使用量子計算機解決，就能隨時規劃一條拼車線路，駕駛員可以在上班路上在不增加路程的前提下順便帶上幾名乘客，或者為快遞員找到最快捷最節能的快遞路徑。而這僅僅是在一類問題下的應用。

ps:
我從前沒有接觸過量子知識，本條回答中關於量子部分的認識是通過閱讀知乎中的回答和百度詞條的概念形成的。歡迎對量子物理學有研究的同學探討、斧正。

特定的協處理器。以後實用了 API 就叫 OpenQL。

量子計算的過程一般是這樣的，創建一組量子態的 bit（qbits）。然後用量子演算法調整 qbits 的狀態。因為 qbits 可以疊加多個狀態，所以量子演算法可以很快。然後讀取 qbits，qbits 隨機塌陷到一個經典態。你會說：我靠，開玩笑，隨機塌陷？那存儲多個狀態的好處是什麼？是這樣，隨機塌陷的概率是不一樣的。中間的量子演算法就是讓正確結果的塌陷概率越來越高。但是再高也達不到 100%。所以最後還是得用經典方法驗證一下。

一本書上說，一台量子計算機背後是它在眾多平行宇宙的眾多分支計算機在同時運行，所以速度快。

原文：

但是，在本節的最後，我們還是回到多宇宙解釋上來。我們如何去解釋量子計算機那神奇的計算能力呢？德義奇聲稱，唯一的可能是它利用了多個宇宙，把計算放在多個平行宇宙中同時進行，最後匯總那個結果。拿肖的演算法來說，我們已經提到，當它分解一個250 位數的時候，同時進行著10^500 個計算。在他的著作中，德義奇憤憤不平地請求那些不相信MWI 的人解釋這個事實：如果不是把計算同時放到10^500 個宇宙中進行的話，它哪來的資源可以進行如此驚人的計算？
他特別指出，整個宇宙也不過
包含大約10^80 個粒子而已。但是，雖然把計算放在多個平行宇宙中進行是一種可能的說法，MWI 也並不是唯一的解釋。基本上，量子計算機所依賴的只是量子論的基本方程，而不是某個解釋。它的模型是從數學上建築起來的，和你如何去解釋它無干。你可以把它想像成10^500 個宇宙中的每一台計算機在進行著計算，但也完全可以按照哥本哈根解釋，想像成未觀測（輸出結果）前，在這個宇宙中存在著10^500 台疊加的計算機在同時幹活！至於這是如何實現的，我們是沒有權利去討論的，正如我們不知道電子如何同時穿過了雙縫，貓如何同時又死又活一樣。這聽起來不可思議，但在許多人看來，比起瞬間突然分裂出了10^500 個宇宙，其古怪程度也半斤八兩。

這個回答，會先講一點量子力學，然後講一些量子計算，最後來說具體的物理實現方法。

一、量子力學

為了方便討論，需要引入狄拉克符號

$|A>$

這稱作狄拉克符號，A代表某種狀態。

量子力學裡面有個重要的概念，叫做測量，在測量某個物理量之前，你是無法確定系統的該物理量的。比如說，對於著名的薛定諤的貓，貓放在箱子裡面，箱子裡面的放射性元素是否衰變決定著貓的死活，但是在你打開箱子之前（或者任何嘗試測量貓死活狀態、放射性元素是否衰變的舉動），你無法確定。這時有

$|mao>=a|sile>+b|meisi>$

其中a代表死了的概率幅，b代表沒死的概率幅。概率幅（概率幅是個複數）乘以概率幅的共軛，是該狀態的概率。

這個式子表示貓處於在一個疊加的狀態，又死又活。當你進行測量之後，才會具體的變成 $|sile>$ 或者 $|meisi>$ （測量之後變成的這個特定的狀態稱作基）。而假設你製備完全相同的若干個此系統，都進行測量，那麼死活的統計結果就是式子裡面的概率幅算出的概率。

你可能會說，這看起來就只是個數學技巧而已。但其實不是，又死又活的疊加態是真實的物理，這一點，實驗可以證明，比如單光子的楊氏干涉實驗。

二、量子計算

大家知道，電子計算機其實基於一些基礎的邏輯門，比如或門，與門，非門。換句話說，只要你通過物理方法實現了這些門，那麼原則上就可以做出電子計算機了（暫時忽略時序電路的實現）。

量子計算機也有類似的性質。基於某些證明，有了受控非門和單量子比特門就可以原則上實現所有量子門（定義在後面給出）。下面我會一個個介紹

單量子比特門，顧名思義，就是對於單個量子比特進行操作的門。由於我們剛才說，量子力學裡面存在疊加態這種狀態，所以這個門相當於

$(|psi>=a|0>+b|1>)mapsto(|psiprime>=aprime|0>+bprime|1>)$ 的映射

也就是

$egin{pmatrix}abend{pmatrix}U=egin{pmatrix}aprimebprimeend{pmatrix}$

為了滿足物理意義（變換之後， $|0>$ 和 $|1>$ 的概率和還是1），還要求U是個酉矩陣。

比如

$U:|0>mapstofrac{1}{sqrt2}(|0>+|1>),|1>mapstofrac{1}{sqrt2}(|0>-|1>)$

（給出了單個 $|0>$ 和 $|1>$ 的變換，也就是給出了 $|psi>$ 到 $|psiprime>$ 的）

就是一個單量子比特門（這個門叫做Hadamard門）。

（單量子比特門其實又可以分成幾種獨立的操作的結合，也就是 $2 imes2$ 酉矩陣的所有基對應的操作）

受控非門，是對於多量子比特來說的，下面以雙量子比特為例。

我們用 $|AB>$ 或者 $|A,B>$ 表示 $|A>$ 和 $|B>$ 兩個單量子比特

受控非門是如下的映射

$|A,B>mapsto|A,Aoplus B>$

其中A為控制比特，B為目標比特。控制比特為0時，目標比特不變，為1時，目標比特翻轉。

$|00>mapsto|00>,|01>mapsto|01>,|10>mapsto|11>,|11>mapsto|10>$

（和之前類似，給出了單個的基的變換，也就是給出了任意雙量子比特，包括疊加態，的受控非門操作。順便一提，受控非門也是酉矩陣）

任意量子門，也就是任意n個量子比特到n個量子比特之間，滿足概率總和不變（也就要求是酉矩陣）的操作，都可以由單量子比特門和受控非門實現。

好了，說了這麼多，在量子比特上進行的計算，到底和經典比特有什麼不同呢？

下面會說到量子並行性特點

先忽略物理實現的方法，假設我們存在一個量子邏輯門，可以實現映射

$|x,y>mapsto|x,yoplus f(x)>$

其中f(x)是一個對我們有用的函數 $f:{0,1}mapsto{0,1}$ ，而當輸入的x為兩個量子比特時（這個時候大概是 $|x,z,y>mapsto|x,z,yoplus f(x,z)>$ ）， $f:{00,01,10,11}mapsto{0,1}$ 。特別的，當y=0時，有

$|x,0>mapsto|x,f(x)>$

想像一個黑箱子，有兩個輸入比特，兩個輸出比特

現在我們輸入兩個量子比特，一個 $|0>$ ，一個 $|x>$ （注意，這個地方x可能是疊加態）

那麼黑箱子就會返回給我們兩個量子比特， $|f(x)>$ 和 $|x>$

關於這個黑箱子的實現方法，很長，我就不細說了。大概的邏輯就是，我們可以構造一個量子門（Fredkin門），以多用一些比特的代價，實現經典邏輯門（量子門可逆，而經典邏輯門不可逆）。然後找到f(x)的經典邏輯門實現方法，用Fredkin門替換，也就是f(x)的量子門實現了。

現在我們對輸入的 $|x>$ 做一些操作，比如讓 $|0>$ 通過Hadamard門變換成 $frac{1}{sqrt2}(|0>+|1>)$ 。

也就是說現在黑箱子輸入的兩個量子比特，一個是 $|0>$ ，一個是 $frac{1}{sqrt2}(|0>+|1>)$

那麼我們會發現，輸出的 $|f(x)>$ 量子比特變成了

$frac{1}{sqrt2}(|f(0)>+|f(1)>)$

而另一個輸出的 $|x>$ 自然是

$frac{1}{sqrt2}(|0>+|1>)$

因為輸出的是 $|x,f(x)>$ ，所以把兩個寫一起，此時輸出就是

$frac{1}{sqrt2}(|0,f(0)>+|1,f(1)>)$

如果輸入x是兩個量子比特,那麼同理，輸出是

$frac{1}{2}(|00,f(00)>+|01,f(01)>+|10,f(10)>+|11,f(11)>)$

這說明了什麼？

我們的量子比特只通過了一個計算f(x)的量子門，就同時計算了 $2^n$ 個f(x)的值（其中假設x輸入的是n個量子比特。當然，還是有些額外開銷，比如n個Hadamard門，和Fredkin門實現f(x)量子門時的額外開銷，但這些都是n量級的。）

但這裡有個小小的問題，雖然所有的f(x)都被計算了，原則上，我們對輸出進行測量，如果 $|x,f(x)>$ 中x為x0，那麼就可以知道後面那個量子比特為f(x")的值。但是，我們測量，最終得到的只是一個 $|x,f(x)>$ ，不可能同時測量到所有的 $|x,f(x)>$ 。聽起來似乎相當的絕望，不過，好消息是，通過構造一些特別的量子演算法，可以間接的利用到量子並行性的額外信息，從而加快某些演算法。換句話說，如果需要量子計算機真的全面替代電子計算機，而不是只在某些特定的演算法上面加速，那麼需要一個通用的量子演算法。

三、物理實現

注意到之前的所有討論，其實可以看出物理實現有這麼幾個要求。

在需要測量（或者說是計算完成）之前，要保持量子比特的疊加態（疊加態使量子演算法具有優勢）。

需要實現基本的，單量子比特門和受控非門（這兩個是量子門的基礎）

要能產生基，也就是說產生 $|0>$ 和 $|1>$

現在有很多種實現量子計算的方法，因為我自己是做集成光學的，所以只對光子量子計算和光學共振腔量子電動力學兩種方法有些了解。。（而且推導哈密頓量好複雜啊。。。我就只給出基本的原理了）

在這之前，先提一下物理實現酉矩陣的原理。在量子力學中，測量被刻畫為一個算符，其中測量系統能量的算符為H，比如

$hat{H}|psi>=E|psi>$

就表示對 $|psi>$ 系統的能量測量，測量結果為E。

根據量子力學的另外一個結論， $|psi>$ 體系隨著時間的演化可以寫成

$|psi(t)>=e^{frac{-ihat{H}t}{hbar}}|psi(0)>$

如果我們找到H,使得 $e^{frac{-ihat{H}t}{hbar}}$ 的作用相當於酉矩陣的話，那麼量子比特在這系統中就相當於通過了對應的量子門。

光子量子計算

分束器和移相器可以實現單量子比特門

受控非門器件由Kerr介質來實現

Kerr介質中，折射率隨入射光的總光強變化

$n=n_1+n_2I$

允許兩束光之間的作用。通過Kerr介質長度的選取，就可以結合分束器實現受控非門。

光學共振腔量子電動力學

單量子比特的操作與之前一樣

不過這種方法通過光在共振腔中與一個雙能級原子互相作用，來實現兩個光子之間的作用。

在光子實現方法中，量子比特代表的可以是有無光子。產生初態，通過極弱的激光可以近似的產生單光子。測量時，通過光電倍增管。

這樣的話。。應該原理都說到了吧。。

順便推薦一本書

Nielsen的Quantum Computation and Quantum Information

物理系的同學學過量子力學就沒問題了。。

我的理解是這樣的，舉個例子：A到B有10000條路，哪條路最近呢？？傳統演算法就是一個人把10000條路都走一遍，然後得到答案,用時很多。量子演算法是直接分身10000個一起走，誰先到終點就把其他分身收了。那麼我們就會發現那個人總是走最近的路，然後收工。牛大了!

「對於量子之類的東西我連一塊錢的賭注都不會押的。」麻省理工學院的計算機科學家斯里尼·戴瓦達斯說，「這類東西聽起來那麼不現實。」

關於量子計算的入門請看我的博客，不管是技術人員還是非技術人員，基本都能看懂。專欄：量子計算機程序開發 - 博客頻道 - CSDN.NET，後面還會介紹量子計算機程序開發。

簡單的說一下，IT工作者可以了解的一些量子計算機物理底層的東西。其實最麻煩的問題就是量子退相干問題。

1、物理基礎：量子疊加干涉現象：計算機有並行計算能力。

2、經典的存儲器：N個比特——————01011100代表真實的數，一個數

量子存儲器：量子相干性，——————有2N次方個數。

3、費曼說過：採用經典計算機不可能以有效方式來模擬量子系統的演化。

4、量子密碼術：無法竊聽，不可克隆。但是相干性易受環境影響而破壞。

5、量子比特的物理實現：採用比較好控制的原子核自旋。

6、邏輯門的實現：原子核作載體，核磁共振。幺正變換

單比特量子門

這裡面用到一些離子阱的東西，用激光致冷束縛，來保持相干性。

小渣渣一枚。

我對量子態的理解是：
1.量子在未被觀察的時候，處於未知狀態，也就是各種可能狀態的混合體。比如一個品德相對良好的人，他撿到錢包會歸還的概率是80%。那麼在沒撿到錢包的時候，他是 80%歸還+20%不歸還的狀態。
2.而一旦觀察後，量子狀態會坍縮為某一特定狀態。也就是萬一那個人撿到了一個錢包，他當時的反應是歸還，就坍縮為歸還，否則是不歸還。
3.我能夠理解在比普朗克時間尺度更大的時間尺度上，一個東西的狀態可能是同時存在的。比如假設我一秒能移動2米，那麼在移動中的我就可以在1s內處於相距2米的兩個狀態（1個狀態是1s開始的，1個是1s結束時的）。再舉一個時間尺度更大的，比如我2016年往返於老家和工作地，那麼也可以說2016我同時存在在老家和工作地。
但我不知道有沒有理論是說粒子可以在普朗克時間尺度上同時存在兩個不同狀態。
4.對於量子計算，我的理解是，一個量子位可能有多個狀態，那麼進行計算後也可以有多個結果。比如因式分解15，1個量子位可能狀態有1，2，3.。。那麼計算結果可能同時有1*5, 2*5, 3*5。這其中會有一個是正解。但我無法理解的是，當你取結果的時候，量子會坍縮為哪一個結果是不確定的，難道不是有可能你取結果的時候，得到的是錯誤的那一個么（比如結果坍縮為2*5）？這樣的話，豈不是還要進行多次計算，那他相對普通計算有什麼優勢？？
難道有方法控制坍縮的結果狀態&>&>無法理解。

對量子理論並不十分了解，只是從大概概念上理解一下，也希望有大牛可以用科普的白話方式告知我的疑問。多謝。

看了大咖的一大堆話，是不是可以這樣理解，量子計算可以分為兩大領域，一是量子演算法，二是量子計算機本體。量子演算法雖然難，但是有諸多進展。量子計算機，毛都沒有摸到。

普通計算機是2^N種狀態（二進位），量子計算機是N^N種狀態。
這能懂了不？

量子計算概述_百度文庫
量子計算_百度文庫
文章是專門為那些不懂量子力學而又想了解量子計算機的計算機工作者而撰寫的