量子計算/量子計算機的概念是著名物理學家費曼於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 optimizationproblems) 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的時候更快地穿過局域極值點旁的勢壘。

例如你在迷宮入口，一次只能選擇一條路徑探索，考慮到迷宮複雜度，你的每次選擇失敗的機率都很大，也許經過很多很多次才能找到出口。但是現在考慮你有分身術，在每個轉折點都有很多分身，並不斷分身，這樣總有一個分身一次就找到出口。這就是量子計算機的優勢，越多量子位元位分身能力越強，效率越高，用時越短。

上述內容如果不能理解，那麼下面這個解釋你會理解的。

考慮你是一個量子，具有同時穿越無限多平行宇宙的能力，每個平行宇宙代表一個你的探索路徑。因此，不論多麼複雜的迷宮，總有一個你的分身在某個平行宇宙一次性就找到出口！

對於你來講，這都不是事兒！甚至都無所謂時間。然而對於外界觀察者來說，究竟哪一個平行分身坍塌為可觀測的現實是不確定的！但是身為量子的你，明確的知道他們測量的只是你的分身之一，那不是整個的你！