1.4　10分鐘看懂量子比特、量子計(jì)算和量子算法

宏觀世界的生活經(jīng)驗(yàn)很多都是表象。例如，你可能認(rèn)為世界的運(yùn)行是確定的、可預(yù)測的；一個(gè)物體不可能同時(shí)處于兩個(gè)相互矛盾的狀態(tài)。在微觀世界中，這種表象被一種叫作量子力學(xué)的規(guī)律打破了。

什么是量子？

前面已經(jīng)講過，量子是物理世界里最小的、不可分割的基本單元，是能量的最基本攜帶者。它是光子、質(zhì)子、中子、電子、介子等基本粒子的統(tǒng)稱。可以說，整個(gè)世界都是由量子組成的。例如，日常生活中的光，就由大量光量子組成。

量子力學(xué)指出，世界的運(yùn)行并不確定，人們最多只能預(yù)測各種結(jié)果出現(xiàn)的概率；一個(gè)物體可以同時(shí)處于兩個(gè)相互矛盾的狀態(tài)中。

量子計(jì)算，就是直接利用量子力學(xué)的現(xiàn)象（例如量子疊加態(tài)）操縱數(shù)據(jù)的過程。下面簡單地介紹什么是量子、量子疊加態(tài)、量子比特、量子測量和一種實(shí)現(xiàn)隨機(jī)數(shù)據(jù)庫搜索的量子算法。

量子有不同于宏觀物理世界的奇妙現(xiàn)象，例如波粒二象性，還有最為著名的量子疊加和量子糾纏。

1.4.1　波粒二象性

波粒二象性（Wave-particle duality）是量子粒子的特征，它是指微觀粒子基于不同的環(huán)境，有時(shí)會表現(xiàn)出波動性，而有時(shí)表現(xiàn)出粒子性。

微觀世界的奇異性在于“波粒二象性”，即微粒不再像以往以為的那樣，是個(gè)小小的實(shí)體球一樣的東西，而且可以沿著一條確定的軌跡運(yùn)動。它實(shí)際上已沒有什么確切的大小、形狀、位置、軌跡可言，這些經(jīng)典概念統(tǒng)統(tǒng)不適于描述微觀世界及其運(yùn)動。微粒已變得像波那樣彌散于廣闊的空間里。所有微粒都具有波粒二象性——它既像顆粒狀分離的粒子，又像云霧狀彌散的波動，而且粒子的動量直接與波動的波長成反比。

例如光就具有粒子和波的雙重性質(zhì)，圖解如圖1-8所示。

量子理論的特點(diǎn)是找到給定點(diǎn)x在空間中存在的概率，而不是它的確切位置。

1.4.2　量子糾纏

量子糾纏指的是量子粒子之間的相互作用。即使粒子間相隔甚遠(yuǎn)，它們依然相互作用、相互參照，而不是獨(dú)立的。

量子糾纏也是量子疊加的一種表現(xiàn)，兩個(gè)處在糾纏態(tài)的量子一旦分開，不論分開多遠(yuǎn)，如果對其中的一個(gè)粒子測量，另一個(gè)粒子就會立即發(fā)生變化，且是不需要時(shí)間的變化。

為了說明這個(gè)復(fù)雜的問題再舉個(gè)例子：你工作需要去上海出差了，你太太懷孕10個(gè)月被送進(jìn)北京協(xié)和醫(yī)院婦產(chǎn)科，突然肚子疼，被送進(jìn)產(chǎn)房，30分鐘后你的兒子出生了。那又怎么樣呢？在你兒子誕生的那一剎那，你在北京的太太成了媽媽，在上海的你成了爸爸！這是不是可以增加你對“糾纏”一詞的理解，不知道我說清楚了沒有？

這兩個(gè)糾纏在一起的量子就好比是一對有心電感應(yīng)的雙胞胎，不論兩人距離多遠(yuǎn)，千米量級或者更遠(yuǎn)，只要當(dāng)其中一個(gè)人的狀態(tài)發(fā)生變化時(shí)，另一個(gè)人的狀態(tài)也會跟著發(fā)生一樣的變化。愛因斯坦稱之為“幽靈般的超距作用”。量子糾纏所體現(xiàn)的這種非定域性是量子力學(xué)最神奇的現(xiàn)象之一。

在測量時(shí)，如果一對糾纏的量子被決定處于箭頭向下↓的自旋態(tài)（能量最低狀態(tài)），則當(dāng)電子與它的磁場保持一致時(shí)，這個(gè)狀態(tài)就會被傳遞到另一個(gè)相關(guān)的箭頭向上↑的相對自旋態(tài)的粒子上。量子糾纏允許相隔很遠(yuǎn)的量子比特彼此之間及時(shí)相互作用。

1.4.3　量子疊加

量子同時(shí)以0和1的形式存在，這種現(xiàn)象被稱為疊加。

雖然粒子能存在于多個(gè)量子態(tài)中，一旦確定了粒子的能量或位置，疊加至此消失，它只能存在一個(gè)狀態(tài)。

量子世界跟宏觀世界最大的區(qū)別，就是量子有多個(gè)可能狀態(tài)的疊加態(tài)。這種現(xiàn)象在宏觀世界中不存在且也無法維持。在宏觀的經(jīng)典世界中，1就是1，2就是2。而在微觀的量子世界中，一個(gè)狀態(tài)可以存在于1和2之間，它既不是1，也不是2，但它既是1，又是2。

這說起來有點(diǎn)懸，歷史上世界最著名的幾個(gè)科學(xué)家也吵了若干年，我們后面有足夠的章節(jié)講這個(gè)事情。先打個(gè)比方，這就好比孫悟空的分身術(shù)。一個(gè)孫悟空可以同時(shí)出現(xiàn)在多個(gè)地方，孫悟空的各個(gè)分身就像是他的疊加態(tài)。在日常生活中，一個(gè)人不可能同時(shí)出現(xiàn)在兩個(gè)地方。但在量子世界里，作為一個(gè)微觀的客體，它能夠同時(shí)出現(xiàn)在許多地方。

下面就一些比較復(fù)雜的概念進(jìn)行解釋，先大概描述一下粗淺的含義，以后的章節(jié)再進(jìn)一步詳細(xì)地解釋。

1. 量子疊加態(tài)

下面需要解釋一下量子疊加態(tài)。

夏天到了，烈日炎炎。當(dāng)你帶上偏振墨鏡時(shí)，從某種程度上講，你就已開始接觸量子計(jì)算了。偏振墨鏡就是我們了解量子疊加態(tài)的起始案例。

為什么這么說呢？因?yàn)楣獾钠裾谩巴瑫r(shí)處于兩個(gè)相互矛盾的狀態(tài)”中，也就是量子疊加態(tài)。在量子計(jì)算中，光子的偏振就可以用來實(shí)現(xiàn)量子比特。

首先，光是一種電磁波，組成它的粒子叫作光子。電磁波的振動就像繩子抖動一樣，可以朝這兒偏也可以朝那兒偏，形成各種各樣的偏振。

其次，偏振墨鏡就像一個(gè)篩子，只有跟篩子的縫隙方向一致，光子才能“鉆過去”。如果跟篩子的縫隙方向垂直，光子就被完全“攔住”了。

如果光子偏振方向跟縫隙方向既不垂直也不平行，而是呈一定角度，又會怎樣呢？

如果你在鉆過去的朝↗方向偏振的光子后面，再放一個(gè)只過濾↑光子的偏振鏡，就會發(fā)現(xiàn)一個(gè)非常詭異的量子力學(xué)現(xiàn)象：大約有一半兒↗偏振光子穿過了偏振鏡，而且偏振方向都變成了↑。這真是一個(gè)非常詭異的量子力學(xué)現(xiàn)象。

這個(gè)時(shí)候，運(yùn)用高中學(xué)過的矢量合成知識，我們可以試著解釋這個(gè)現(xiàn)象。由于光子的偏振既有方向又有大小，我們可以將每個(gè)光子的偏振看作一個(gè)矢量。于是，它們滿足矢量的加法。

由于↗方向的振動等于↑方向的振動加上→方向的振動，我們就可以說，↗偏振的光子可以看作是同時(shí)在朝↑和→方向振動。矢量既有長度又有方向，這時(shí)就是其矢量的相加（見圖1-9）。

矢量↗可以看作矢量↑加上矢量→：C=A+B。

而光子同時(shí)在進(jìn)行兩種振動的情況可以解釋如下：一種振動可以看作由兩種不同的振動相加而成，所以，光子可以看作是同時(shí)進(jìn)行兩種振動，即↗偏振的光子可以看作它同時(shí)進(jìn)行的↑振動和→振動的合成。

如果你不理解什么叫同時(shí)進(jìn)行兩種振動，想想你耳朵里的鼓膜，正是它同時(shí)進(jìn)行多種振動，你才能同時(shí)聽到各種各樣的聲音。

這時(shí)，我們就可以試著解釋那個(gè)奇怪的量子現(xiàn)象了。如果把一個(gè)↗偏振的光子看作是一個(gè)光子同時(shí)進(jìn)行↑和→兩種振動，那么可以說，當(dāng)這個(gè)光子路過↑偏振鏡時(shí)，其中一半兒→振動被擋住了，另一半兒↑振動通過了。

2. 量子態(tài)測量的概率性

然而，這個(gè)上面的解釋并不完全正確。

如果朝這個(gè)偏振鏡發(fā)出一個(gè)↗光子，在偏振鏡之后，并不會接收到一個(gè)振動能量減弱一半兒的光子，而是有50%的概率接收到一個(gè)↑光子；50%的概率什么也沒接收到。也就是說，當(dāng)你測量一個(gè)量子疊加態(tài)時(shí)，總會得到概率性的結(jié)果。記住量子測量的概率性，這在后面的量子算法中會用到。

到這里你可能想起來了，這就是量子力學(xué)常說的“上帝擲骰子”。根據(jù)不同的偏振方向，得到的概率也是不同的，如圖1-10所示。

注解：雖然↗方向的光子處于兩種振動的疊加狀態(tài)，但當(dāng)你通過↑偏振鏡測量它時(shí)，它總會隨機(jī)地“擲骰子”，以一定概率得到↑方向或→方向的結(jié)果。“擲骰子”的概率與偏振方向的夾角有關(guān)。偏振方向跟↑方向的夾角有關(guān)。偏振方向跟↑方向的夾角越小，測量時(shí)得到↑偏振的光子的概率就越大。偏振方向與→方向的夾角也是同理。

1.4.4　量子比特和量子計(jì)算

1. 量子比特

如果把↑光子看作比特0，把→光子看作比特1，那么，一個(gè)↗光子就處于比特0和比特1光子的疊加狀態(tài)之中。

如果硬要用一個(gè)偏振鏡去測量它到底是比特0還是比特1，就會發(fā)現(xiàn)，測量結(jié)果有50%的概率是比特0，還有50%的概率是比特1。

↗光子所攜帶的這種詭異的“比特”就叫作量子比特。可以把比特0和比特1分別想象成一個(gè)虛擬的空間中的兩個(gè)相互垂直的坐標(biāo)軸。對于經(jīng)典比特來說，它要么處于比特0的軸上，要么處于比特1的軸上。

而量子比特可以在兩個(gè)軸之間的空間任意“轉(zhuǎn)動”，量子比特在兩個(gè)軸之間的空間任意“轉(zhuǎn)動”的結(jié)果，以一定比例得到比特0，一定比例得到比特1。

2. 量子計(jì)算

1）量子門

電子計(jì)算機(jī)所做的計(jì)算，就是操縱經(jīng)典比特。

同樣的道理，所謂量子計(jì)算機(jī)，就是在量子力學(xué)允許的范圍內(nèi)操縱量子比特。這時(shí)就需要可以操縱電子比特的量子門。

量子邏輯門是一個(gè)對特定的量子比特在一段時(shí)間間隔實(shí)現(xiàn)邏輯變換的量子邏輯線路，它是量子線路的基礎(chǔ)。與傳統(tǒng)邏輯門不同，量子邏輯門是可逆的。

量子邏輯門是量子計(jì)算與量子計(jì)算機(jī)實(shí)現(xiàn)的基礎(chǔ)，可用下列方法實(shí)現(xiàn)。

（1）量子點(diǎn)系統(tǒng)。

（2）超導(dǎo)約瑟夫森（Josephson）結(jié)系統(tǒng)。

（3）核磁共振量子系統(tǒng)。

（4）離子阱系統(tǒng)。

（5）腔量子電動力學(xué)系統(tǒng)等。

量子邏輯門按照其作用的量子比特的數(shù)目可分為單比特門、二比特門和三比特門等。

2）量子并行計(jì)算

不知道你發(fā)現(xiàn)了沒有，由于量子比特可以同時(shí)處于比特0和比特1的狀態(tài)，量子門操縱它時(shí)，實(shí)際上同時(shí)操縱了其中的比特0和比特1的狀態(tài)。

所以，操縱一量子比特的量子計(jì)算機(jī)可以同時(shí)操縱2個(gè)狀態(tài)。如果一個(gè)量子計(jì)算機(jī)可以同時(shí)操縱N量子比特，那么它實(shí)際上可以同時(shí)操縱2^N個(gè)狀態(tài)，其中每個(gè)狀態(tài)都是一個(gè)N位的經(jīng)典比特。這就是量子計(jì)算機(jī)傳說中的并行計(jì)算能力。

3）量子計(jì)算機(jī)算法

1985年，英國牛津大學(xué)Deutsch研究了量子圖靈（Turing）機(jī)，引進(jìn)了量子計(jì)算線路模型和量子通用邏輯門組，突破了經(jīng)典計(jì)算布爾（Boole）邏輯的限制，實(shí)現(xiàn)了到量子演化的躍進(jìn)。在那之后，科學(xué)家們開始了對量子算法的研究。

（1）Shor算法。

Shor算法是由美國貝爾實(shí)驗(yàn)室的科學(xué)家彼得·秀爾（Peter Shor）在1994年提出的分解大數(shù)質(zhì)因子的量子方法。互聯(lián)網(wǎng)時(shí)代絕大多數(shù)的加密，都由RSA算法完成，目前支付寶、微信支付、微眾銀行等都在采用RSA 2048加密算法，但隨著量子計(jì)算的發(fā)展，RSA加密安全性受到了挑戰(zhàn)。例如，Shor分解大數(shù)質(zhì)因子時(shí)，傳統(tǒng)計(jì)算機(jī)與量子計(jì)算機(jī)使用的時(shí)間和硬件環(huán)境如表1-1所示。

（2）Grover算法。

Grover算法是由Grover于1996年提出的平方根加速的隨機(jī)數(shù)據(jù)庫量子搜索算法。搜索算法常用于從N個(gè)未分類的記錄中找出某個(gè)特定的記錄。

Grover量子搜索算法可以對隨機(jī)數(shù)據(jù)庫相對經(jīng)典搜索平方根加速，為了實(shí)現(xiàn)這樣的加速，Grover算法主要依賴于量子態(tài)的疊加。

假設(shè)有N個(gè)未經(jīng)排序的數(shù)據(jù)。如果使用經(jīng)典算法尋找其中的某個(gè)數(shù)據(jù)x，條件是它（并且只有它）滿足P（x）=TRUE，比方說x代表一個(gè)人的工號，P（x）是看這個(gè)人是不是現(xiàn)任CEO。那么你只能從第一個(gè)數(shù)據(jù)開始，一個(gè)一個(gè)地看它是不是CEO的工號。使用經(jīng)典算法尋找其中的某個(gè)數(shù)據(jù)x的方法是：對于未經(jīng)排序的數(shù)據(jù)，經(jīng)典的算法只能一個(gè)一個(gè)地找，運(yùn)氣最差的時(shí)候你得計(jì)算N次才能找到那個(gè)數(shù)據(jù)。

在這種算法中，計(jì)算復(fù)雜度是O（N）。

在Grover算法中，可以將N個(gè)數(shù)據(jù)同時(shí)存儲在log₂N量子比特中，然后同時(shí)計(jì)算N個(gè)函數(shù)P（）的取值，就相當(dāng)于同時(shí)在N個(gè)狀態(tài)上做了N次P（）的計(jì)算，也就是同時(shí)看它是不是CEO的工號。

在N個(gè)計(jì)算結(jié)果中，必然有一個(gè)結(jié)果是CEO的工號，其他結(jié)果都不是。但如果這個(gè)時(shí)候貿(mào)然去“讀取”結(jié)果就會發(fā)現(xiàn)，每個(gè)結(jié)果發(fā)生的概率都是1/N。這就好比你用↑偏振鏡去測量↗光子，得到↑和→的概率各為1/2。

Grover算法的思想是，同時(shí)計(jì)算N個(gè)P（）的取值后，先不要讀取，而是通過量子操作略微增加結(jié)果為CEO工號的那個(gè)數(shù)據(jù)發(fā)生的概率。

數(shù)學(xué)計(jì)算證明，反復(fù)重復(fù)以上過程（π）/4次之后，你要找的那個(gè)數(shù)據(jù)發(fā)生的概率就會達(dá)到最大。這個(gè)時(shí)候如果再去讀取數(shù)據(jù)，就會以極大的概率讀到你要找的數(shù)據(jù)。

所以，Grover的量子搜索加速算法，可以將搜索復(fù)雜度降低到O（），但你成功讀取那個(gè)數(shù)據(jù)的概率永遠(yuǎn)也不會達(dá)到100%，而是略小于100%。

從目前的情況看，量子計(jì)算只是在少數(shù)計(jì)算任務(wù)中表現(xiàn)得比經(jīng)典計(jì)算更快，例如大數(shù)質(zhì)因子（Shor算法）、隨機(jī)數(shù)據(jù)庫搜索（Grover算法），并且，這種快法不能掙脫量子力學(xué)的約束，達(dá)到十全十美。