在 IBM Bluemix 云平臺上開發并部署您的下一個應用。

現在就開始免費試用

Alan Turing 在 1936 年發明可編程計算機（請參閱?參考資料）是作為一種思想實驗以證明某些數學問題不可計算。在他的論證中，隱含的觀點是一臺裝有足夠資源的計算機能實現任何合理的算法。

從那時起，計算機工業不僅得以建造可編程計算機器，而且還通過每十八個月左右就使能力加倍，從而超越了它們自身。雖然計算機技術瘋狂的向前發展，但是現代計算機仍無法在難題方面取得顯著進展。需要指數資源的問題（同問題本身的大小相比）在當今仍然同 1936 年時一樣棘手。

1982 年 Richard Feynman 提出，值得尊敬的 Turing 機器的功能也許并沒有人們所想的那么強大。當時 Feynman 正在試圖用量子力學模擬 N 粒子之間的相互作用。盡管他很努力，但他沒能找到不使用指數資源的一般性解法。

然而不知為什么，大自然能僅使用 N 粒子模擬這一數學問題。結論是不可避免的：大自然具有建造非常高級的計算設備的能力，這說明 Turing 機器還不是人們從前所認為的全能計算機。

使量子計算問題形象化

QC 算法涉及就概率因子進行思考，對于現在的程序員而言，這是概念上的變化。在某些方面，這就象第一次卷入使用 OOP（面向對象編程方法）、結構化編程或多線程時概念上的轉變。從另一種角度來看，這種轉變更為重要，因為這使全新的一類（有可能）沒有替代物的問題開始出現了。

讓我們想象一下下面這個問題。我們要找一條路穿過一個復雜的迷宮。每次我們沿著一條路走，很快就會碰到新的岔路。即使知道出去的路，還是容易迷路。換句話說，有一個著名的走迷宮算法就是右手法則 － 順著右手邊的墻走，直到出去（包括繞過絕路）。這條路也許并不很短，但是至少您不會反復走相同的過道。以計算機術語表述，這條規則也可以稱作遞歸樹下行。

現在讓我們想象另外一種解決方案。站在迷宮入口，釋放足夠數量的著色氣體，以同時充滿迷宮的每條過道。讓一位合作者站在出口處。當她看到一縷著色氣體出來時，就向那些氣體粒子詢問它們走過的路徑。她詢問的第一個粒子走過的路徑最有可能是穿過迷宮的所有可能路徑中最短的一條。

當然，氣體顆粒絕不會給我們講述它們的旅行。但是 QC 以一種同我們的方案非常類似的方式運作。即，QC 先把整個問題空間填滿，然后只需費心去問問正確的解決方案（把所有的絕路排除在答案空間以外）。

回頁首

qcl 量子計算機模擬器

在一臺傳統的經典計算機上模擬量子計算機是個難題。需要的資源隨被模擬的量子內存數量增加呈指數增長，以致于連模擬一臺只有幾十個量子位（quantum bit，qubit）的 QC 也遠遠超出了現在制造的任何一臺計算機的能力范圍。

qcl 只模擬非常小的量子計算機，但幸運的是，它的效力剛好足夠大，可以展示一些有用的 QC 算法背后的概念。

和過去的超級計算機一樣，未來的第一臺 QC 的核心很可能由一些存儲和控制量子態機器的奇特硬件組成。其外圍將會是生命支持硬件以支援核心并把適當的編程環境呈現給用戶。qcl 通過為經典程序結構提供量子數據類型及對其執行操作的特殊函數來模擬這樣一種環境。

讓我們從一些經典計算中常見的運算開始使用 qcl。由于 qcl 是語法上模糊的類似于 C 的交互式解釋器，所以我們只要啟動它就可以往里面輸入命令。為了使我們的示例更具可讀性，我們把被模擬的量子位數目限制為 5 位。

清單 1. 初始化 qcl 并轉存一個量子位

$ qcl --bits=5 [0/8] 1 |00000> qcl> qureg a[1]; qcl> dump a : SPECTRUM a: |....0> 1 |0>

此處我們在 qcl 量子堆中為一個 1 量子位（布爾型）變量分配空間。機器的量子態（?|00000>?）被初始化為全 0。符號?|>?表示這是量子態（有時也叫做 ket），而 5 個 0 的字符串（一個 0 代表量子堆中的一位）就形成該狀態的標簽。這叫做量子力學的 Dirac 標記法（也可以稱做 bra-ket）。同線性代數傳統的數學標記法相比，其主要優點是更易于輸入。

“qureg a[1]”為量子堆中的 1 位變量?a?分配空間。?dump a?命令給了我們一些關于?a?的信息。?SPECTRUM?行告訴我們在量子堆中分配給?a?的量子位的位置；在這種情況下，?a?的 0 位是堆中右面第一位的量子位。下面一行告訴我們，如果我們要測量?a?，那么我們認為“0”的概率為“1”。

當然，因為 qcl 是一個模擬器，所以只是有可能能窺到量子內存。只有不可撤回的改變值才能觀察到真正的量子位。后面還有更多這方面的內容。

qcl 提供的基本量子運算符中有許多在經典計算中很常見。例如，?Not()?函數會把一位的值取反。

清單 2. 對一個量子位使用布爾型函數

qcl> Not(a); [2/8] 1 |00001>

再次對同一量子位使用?Not()?將撤消第一次的結果，這正是我們在經典計算中所預期的。

CNot(x,y)?運算符測試 y 的值，如果是“1”，則對 x 的值取反。等價于 C 中的?x^=y?語句。

清單 3. 其它一些量子位運算符（CNot）

qcl> qureg b[2]; qcl> Not(b[1]); [3/8] 1 |00100> qcl> CNot(b[0], b[1]); [3/8] 1 |00110> qcl> dump b[0]; : SPECTRUM b[0]: |...0.> 1 |1> qcl> dump b[1]; : SPECTRUM b[1]: |..0..> 1 |1>

CNot()?運算符同?Not()?運算符一樣，是它本身的逆。第二次應用時，它會把第一次的結果反過來，使您回到同開始時一樣的狀態。

可逆性觀點是理解量子計算的關鍵。理論物理學告訴我們對量子位進行的所有操作（除了測量以外）必須可撤消。我們必須一直保留足夠的信息以復原任何操作。這意味著象賦值（x=y）、AND（?x&=y?）和 OR（?x|=y?）（在經典計算中我們認為這些運算是理所當然的）就必須為能在 QC 中使用而修改了。幸運的是，有一個簡單的方案可以把不可逆的經典運算轉換成量子運算。

首先，除了要把量子位初始化為“0”，我們絕不重寫它。因此在我們本來可以進行賦值（x=y）的地方，我們沒有這么做，而是把目標初始化（x=0）并如同上面的示例一樣使用異或（x^=y）。

清單 4. 對布爾型 AND 進行可逆模擬

nomadic$ qcl --bits=5 [0/8] 1 |00000> qcl> qureg c[3]; qcl> Not(c[1]); [3/8] 1 |00010> qcl> Not(c[2]); [3/8] 1 |00110> qcl> dump c : SPECTRUM c: |..210> 1 |110> qcl> CNot(c[0], c[1] & c[2]); [3/8] 1 |00111> qcl> dump c : SPECTRUM c: |..210> 1 |111>

如果 y 和 z 的值都是“1”，?CNot(x, y & z)?會對 x 的值取反。因此如果在開始前我們就把?x?初始化成“0”，那么這就象計算?y & z?并把值存到?x里。這是一個細微的區別，但卻是量子計算中的一個重要區別。

現在讓我們看看一些無經典類似情況的運算。最引人注目的，同時也是最有用的其中之一就是 Hadamard 函數，qcl 把它恰當的標記為?Mix()。?Mix()?把計算基態，如?|0>?或?|1>?，變成量子疊加。下面一個量子位的示例：

清單 5. 用 Mix() 進行狀態疊加

[0/8] 1 |00000> qcl> qureg a[1]; qcl> dump a; : SPECTRUM a: |....0> 1 |0> qcl> Mix(a); [1/8] 0.707107 |00000> + 0.707107 |00001> qcl> dump a; : SPECTRUM a: |....0> 0.5 |0> + 0.5 |1>

本例中，我們利用了量子力學的疊加原理。根據?dump a?，如果我們要測量?a?，我們會認為“0”或“1”的概率都等于 0.5（0.707107?2）。

如果您以前從未接觸過疊加這個概念，那么它可能有點兒令人困惑。量子力學告訴我們，小粒子，比如電子，可以同時處于兩個位置。同樣，一個量子位可以同時有兩個不同的值。理解這一切的關鍵在于向量算術。

和經典計算機機器狀態只是唯一的一串 1 和 0 不同，QC 的狀態是一個向量，其分量包括所有可能的 1 和 0 組成的字符串。換一種方式來說，這些 1 和 0 組成的字符串構成了我們的機器狀態生存的向量空間的基礎。我們可以通過寫出如下的和來把 QC 的狀態寫下來：

清單 6. 量子計算機的向量態

a|X> + b|Y> + ...

此處?X?、?Y?等是 1 和 0 組成的字符串，?a?、?b?等是分量 X、Y 等的振幅。?|X>?標記正是物理學家們表示“名叫 X 的向量（或狀態）”的方式。

Mix()?運算符（Hadamard 運算符）用于處于?|0>?狀態的位時，將會象上面的例子一樣把狀態轉變成?sqrt(0.5)(|0>+|1>)?。但是如果我們把Mix()?用于處于?|1>?狀態的位，我們會得到?sqrt(0.5)(|0>-|1>)?。因此如果我們對任意量子位（處于任何狀態）應用兩次?Mix()?，我們就回到了開始的地方。換句話說，?Mix()?是它本身的逆。

如果我們有兩個量子位?a?與?b?（初始化成 0）并對?a?執行了一系列量子運算，然后對?b?執行同樣的運算，我們應當預期結束時?a?和?b?的值相同，確實是這樣。

清單 7. 獨立疊加的量子位

qcl> qureg a[1]; qcl> Not(a); [1/8] 1 |00001> qcl> Mix(a); [1/8] 0.707107 |00000> + -0.707107 |00001> qcl> qureg b[1]; qcl> Not(b); [2/8] 0.707107 |00010> + -0.707107 |00011> qcl> Mix(b); [2/8] 0.5 |00000> + -0.5 |00010> + -0.5 |00001> + 0.5 |00011> qcl> dump a : SPECTRUM a: |....0> 0.5 |0> + 0.5 |1> qcl> dump b : SPECTRUM b: |...0.> 0.5 |0> + 0.5 |1>

在這個示例中，?a?和?b?是完全獨立的。如果我們測量其中一個，那么不應當對另外一個造成任何影響。

清單 8. 獨立測量的量子位

qcl> measure a; [2/8] -0.707107 |00001> + 0.707107 |00011> qcl> dump b : SPECTRUM b: |...0.> 0.5 |0> + 0.5 |1>

正如我們所預期的，?b?的頻譜并沒有因測量?a?而改變。

如果運算比簡單的?Not();Mix()?要復雜，那么我們可能很想只對?a?執行一次這些運算，然后把值從?a?拷貝到?b?。不錯，雖然我們無法真的進行拷貝（因為拷貝不是可逆運算），但是我們可以把?b?初始化為 0，然后用?CNot(b,a)?會達到相同的目的。

很可惜，它所做的并不是我們所預期的。但還是讓我們嘗試一下看看會得到什么結果：

清單 9. 嘗試量子位拷貝運算

qcl> qureg a[1]; qcl> Not(a); [1/8] 1 |00001> qcl> Mix(a); [1/8] 0.707107 |00000> + -0.707107 |00001> qcl> qureg b[1]; qcl> CNot(b,a); [2/8] 0.707107 |00000> + -0.707107 |00011> qcl> dump a; : SPECTRUM a: |....0> 0.5 |0> + 0.5 |1> qcl> dump b; : SPECTRUM b: |...0.> 0.5 |0> + 0.5 |1>

a?和?b?的頻譜看起來是正確的。而且事實上如果我們只對?a?或?b?中的一個進行測量，我們就會得到和上面一樣的結果。區別在于我們對 a 和 b 都進行測量時所發生的事。

請記住測量結果是隨機的，因此如果您正反復做這個實驗，您的結果可能會有所不同。

清單 10. 測量使量子位疊加坍縮

qcl> measure a; [2/8] -1 |00011> qcl> dump b : SPECTRUM b: |...0.> 1 |1>

通過測量?a?，我們使?b?的疊加坍縮了。這是因為?a?與?b?糾纏在物理學家們所說的 EPR 對中，繼 Einstein 之后，Podolsky 和 Rosen 都試圖用它來說明量子力學是一個不完整的理論。然而，John Bell 后來通過實驗反駁 Bell 不等式（正是它使 EPR 思維實驗正式化）證明了真實粒子間的糾纏。

您試圖把一個量子變量拷貝到另一個上時發生了什么事？您以最終得到的是糾纏，而非真正的拷貝。

回頁首

Deutsch 問題

假定我們有一個函數，它有一個參數是一個二進制位，返回的也是一個二進制位。為了使事情向好的方向發展，讓我們要求這是一個偽經典函數。如果我們傳給它一個經典的二進制位（0 或 1）作參數，它將返回一個經典二進制位。

確切地說，有 4 種可能的函數滿足這一要求。

清單 11. 共 4 種可能的布爾型一元函數

f(x) -> 0# constant zero result f(x) -> 1# constant one result f(x) -> x# identity function f(x) -> ~x# boolean negation

前兩個是常量，也就是說，不管輸入如何，它們總是輸出相同的值。后兩個是對稱的，即一半時間輸出 0 ，一半時間輸出 1。經典意義上，要確定?f()?是常量還是對稱的只有對該函數進行兩次計算。

Deutsch 問題要我們只對?f()?進行一次計算就確定?f()?是常量還是對稱的。以下是其工作原理。

首先，我們得用 qcl 構造一個偽經典運算符來對?f(x)?進行計算。我們將定義一個帶輸入輸出參數的量子函數來構造該函數。例如：

清單 12. 用 qcl 語言定義一個量子函數

qufunct F(qureg out, quconst in) {CNot(out, in);Not(out);print "f(x)= ~x"; }

如果 out 被初始化成“0”，調用這個函數就會把 out 變成?f(x)=~x?。您可以把?CNot()?或?Not()?代碼行注釋掉得到其它三種可能的函數中的一種。我們把上面的代碼片斷放在一個叫做 f_def.qcl 的文件中以后，我們就可以測試?F()?以確保它所做的正是我們想要的：

清單 13. 交互導入并測試 F()

qcl> include "f_def.qcl"; qcl> qureg in[1]; qcl> qureg out[1]; qcl> F(out,in); : f(x)= ~x [2/8] 1 |00010> qcl> dump out; : SPECTRUM out: |...0.> 1 |1> qcl> reset [2/8] 1 |00000> qcl> Not(in); [2/8] 1 |00001> qcl> dump in : SPECTRUM in: |....0> 1 |1> qcl> F(out,in); : f(x)= ~x [2/8] 1 |00001> qcl> dump out : SPECTRUM out: |...0.> 1 |0>

現在讓我們重置量子內存并運行 Deutsch 算法。它首先要把 in 和 out 位放到四種基態的疊加中去才能工作。

清單 14. Deutsch 算法（加上了行號）

(01) qcl> reset; (02) qcl> int result; (03) qcl> Not(out); (04) [2/8] 1 |00010> (05) qcl> Mix(out); (06) [2/8] 0.707107 |00000> + -0.707107 |00010> (07) qcl> Mix(in); (08) [2/8] 0.5 |00000> + 0.5 |00001> + -0.5 |00010> + -0.5 |00011> (09) qcl> F(out,in); (10) : f(x)= ~x (11) [2/8] 0.5 |00010> + 0.5 |00001> + -0.5 |00000> + -0.5 |00011> (12) qcl> Mix(in); (13) [2/8] 0.707107 |00011> + -0.707107 |00001> (14) qcl> Mix(out); (15) [2/8] -1 |00011> (16) qcl> measure in, result; (17) [2/8] -1 |00011> (18) qcl> if (result == 0) { print "constant"; } else { print "balanced"; } (19) : balanced

1-7 行我們把 in/out 位放入四種基態的一個疊加中，其中“out=0”狀態為正振幅 +0.5，而“out=1”狀態為負振幅 -0.5。請注意即使我們有四個非 0 振幅，這些振幅絕對值的平方和總能達到 1。

第 9 行我們運行量子函數?F()?，它把?f(in)?的值 XOR 到?out?量子位。函數?F()?是偽經典的，意味著它交換基本向量，但是不會對任何振幅作更改。因此應用?F()?后我們仍有兩個振幅的值為“+0.5”，兩個振幅的值為“-0.5”。

通過對疊加態應用?F()?函數，我們一下子就對所有的四種基態有效的應用了?F()?。這就是所謂的“量子并行性”，它是 QC 的一個重要元素。當然我們的模擬器不得不輪流在每種基態應用?F()?，但真正的 QC 是把?F()?作為一步運算應用到組合態。

14 行和 16 行的?Mix()?函數對機器狀態的疊加態取反回到計算基態（?|00011>?）。如果我們沒有運行第 9 行的?F()?，這會把我們帶回到第 4 行的狀態（因為?Mix()?是其本身的逆）。但是因為我們用?F()?交換了振幅，撤消疊加使我們處于一種不同于我們在第 9 行時的狀態。特別是?in量子位現在被設置成“1”而非“0”。

注意到在 15 行的振幅 -1 不重要也是很有益的。量子態是向量，我們并不關心其總長度（只要不是 0）。只有向量方向，即分振幅之間的比值，是重要的。通過保持量子態是單位向量，變換就都是幺正的。這不僅使理論數學容易的多了，而且還使經典計算機上數字計算中出現的錯誤不致于象滾雪球般失去控制。

回頁首

受控相位變換

量子計算最初的目標是使用很少一部分基本元素模擬變化多端的量子系統的行為。到目前為止，我們已經討論了?Not()?、?CNot()?和?Mix()?函數。要使集合完整并考慮普遍的量子計算，那么我們需要受控相位函數，?CPhase()?。

CPhase()?的第一個參數是（經典的）浮點數，第二個參數是一個量子位。?CPhase(a,x)?對機器的基態分量振幅的改變如下：

• x 是?|0>?的基態振幅沒有更改，而
• x 是?|1>?的基態振幅乘上了 exp(i*a)=cos(a)+i*sin(a)。

x=1 時的機器狀態系數在復平面內轉過了 a 弧度。例如：

清單 15. 演示 CPhase() 函數

$ qcl --bits=5 [0/5] 1 |00000> qcl> qureg a[1]; qcl> Mix(a); [1/5] 0.707107 |00000> + 0.707107 |00001> qcl> CPhase(3.14159265, a); [1/5] 0.707107 |00000> + -0.707107 |00001> qcl> reset [1/5] 1 |00000> qcl> Mix(a); [1/5] 0.707107 |00000> + 0.707107 |00001> qcl> CPhase(0.01, a); [1/5] 0.707107 |00000> + (0.707071,0.00707095) |00001> qcl> dump a : SPECTRUM a: |....0> 0.5 |0> + 0.5 |1>

由于 exp(i*pi)=-1，?CPhase(pi,x)?會對?|1>?分量的符號取反。?CPhase(0.01, x)?在復平面內使?|1>?分量的相位轉過了百分之一弧度。括弧里的元組（0.707071，0.00707095）是復數 exp(0.01*i)=0.707071+i*0.00707095 的 qcl 表達式。

回頁首

更大的問題及解決方案

Deutsch 問題及其 N 位泛化，即 Deutsch-Jozsa 問題，也許有趣，但是沒有太多的實際價值。幸運的是，另外還有一些量子算法讓人希望會有更大的收益。

例如 Shor 的算法能在多項式時間內找到一個 N 位函數的周期。雖然聽起來這并不是什么了不起的事，但分解并找到一個離散對數的困難形成了大部分公用密鑰密碼學系統的基礎，如果不是全部的話。

雖然不那么壯觀，但是用可以在 O(sqrt(N)) 時間內搜索一個無序的 N 項列表的 Grover 算法實現起來容易得多。要搜索這樣的列表，最好的經典算法平均要 N/2 次迭代。

回頁首

結論

自從經典計算機開始出現，模擬電子電路以促進更快的計算機的設計就一直是其任務之一。這一反饋循環一直在促進計算機工業半個世紀以來的爆炸式發展。量子計算機具有潛力把這一爆炸式的發展轉變的更具活力，如同 QC 用于創造更快更有力的量子計算元件一樣。

2000 年 8 月間，IBM Almaden Research Center 的 Isaac L. Chuang 宣布他和他的合作者們已經建造了一臺 5 量子位的機器，利用的是一個有 5 個氟原子的分子（請參閱?參考資料）。不幸的是，這一技術可能無法發展到可用的規模。

那么何時才能建成第一臺可伸縮的量子計算機呢？有一些存儲、操作和移動量子位的候選技術。完整的列表已超出了本文的范圍，但是還要再過一、二十年才會有第一個有用的 QC 的說法可能還是可靠的。

總結

以上是生活随笔為你收集整理的量子计算入门的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。