量子計算是一種運算模型，它利用量子物理來以不同的方式計算，做到古典電腦做不到的事——例如有效率地攻破 RSA 與橢圓曲線密碼學。

但量子電腦不是一台超快的普通電腦。

事實上，量子電腦無法解決任何對古典電腦而言太難的問題，例如暴力搜尋或 NP-complete 問題。

兩個量子現象#

量子電腦建立在量子力學之上——研究次原子粒子行為的物理學分支，那些粒子的行為是真正隨機的。

疊加#

古典電腦操作的位元非 0 即 1；量子電腦則建立在量子位元（qubit）之上，它能同時既是 0 又是 1——這種模稜兩可的狀態稱為疊加（superposition）。

物理學家發現在這個微觀世界裡，電子與光子這類粒子的行為極度違反直覺：

• 在你觀測一個電子之前，它並不位於空間中某個確定的位置，而是同時在好幾個位置（也就是處於疊加態）。
• 一旦你觀測它（量子物理中稱為測量），它就停在一個固定的、隨機的位置，不再處於疊加態。

這個量子魔法，正是量子電腦中能創造出 qubit 的原因。

糾纏#

但量子電腦之所以能運作，靠的是一個更瘋狂的現象——糾纏（entanglement）：

這個行為由 EPR 悖論（Einstein–Podolsky–Rosen paradox）所闡明，也是愛因斯坦（Albert Einstein）當初否定量子力學的原因。

量子位元#

要解釋量子電腦如何運作，我們該區分實際的量子電腦（硬體，由量子位元組成）與量子演算法（跑在其上的軟體，由量子閘組成）。

量子位元（或其群組）由稱為振幅（amplitude）的數所刻畫。振幅類似機率但不完全是機率：

• 機率是 0 到 1 之間的數。
• 振幅是形如 a + bi 的複數，其中 a 與 b 是實數，i 是虛數單位（i² = −1）。

實數可以看成屬於一條線；複數則可以看成屬於一個平面（二維空間）：x 軸對應 a + bi 中的 a，y 軸對應 b。

用畢氏定理可以算出從原點到點 a + bi 之連線的長度：

|a + bi| = √(a² + b²)

這稱為複數 a + bi 的模（modulus），可以當成該複數的長度。

單一 qubit 的振幅#

單一個 qubit 由兩個振幅刻畫（記為 α 與 β），狀態可表示為：

α|0⟩ + β|1⟩

其中 | ⟩ 記法用來表示量子態中的向量。這個記法的意思是：當你觀測這個 qubit，它會以機率 |α|² 呈現為 0、以機率 |β|² 呈現為 1。

為了讓它們是真正的機率，|α|² 與 |β|² 必須是 0 到 1 之間的數，且：

|α|² + |β|² = 1

例一：qubit Ψ（psi），振幅 α = 1/√2、β = 1/√2：

|Ψ⟩ = (1/√2)|0⟩ + (1/√2)|1⟩ = (|0⟩ + |1⟩)/√2

計算實際機率：取 1/√2 的模（等於 1/√2，因為沒有虛部），再平方得 (1/√2)² = 1/2。觀測 Ψ 時，看到 0 與看到 1 的機率各為 1/2。

例二：qubit Φ（phi），振幅 α = i/√2（正的虛數）、β = −1/√2（負的實數）：

|Φ⟩ = (i/√2)|0⟩ + (−1/√2)|1⟩

Φ 與 Ψ 從根本上不同——Ψ 的兩個振幅相等，Φ 的則相異。

但若你觀測 Φ，看到 0 或 1 的機率仍是 1/2，與 Ψ 相同：

|i/√2|² = (√(0² + (1/√2)²))² = (1/√2)² = 1/2

這告訴我們，看到 0 或 1 的實際機率只部分刻畫了一個 qubit——就像你觀察牆上某個物體的影子，影子的形狀讓你知道物體的寬與高，卻不知道它的深度。

對 qubit 而言，這個隱藏的維度就是其振幅的值：它是正的還是負的？它是實數還是虛數？

為了簡化記法，一個 qubit 常常直接寫成它的振幅對 (α, β)。前例可寫成 |Ψ⟩ = (1/√2, 1/√2)。

多個 qubit 的振幅#

一個量子位元組可以由 8 個 qubit 構成，此時這 8 個 qubit 的量子態以某種方式彼此連結（我們說它們糾纏了）。這樣的量子位元組可以描述為：

α₀|00000000⟩ + α₁|00000001⟩ + α₂|00000010⟩ + ... + α₂₅₅|11111111⟩

其中各 α 是與這 8 個 qubit 之 256 個可能值各自關聯的振幅，且必須滿足：

|α₀|² + |α₁|² + ... + |α₂₅₅|² = 1

我們這組 8 個 qubit 可以看成一組 2^8 = 256 個振幅，因為它有 256 種可能組態，每種都有自己的振幅。

但在物理現實中，你只有八個物理物件，不是 256 個。 那 256 個振幅是這組 8 個 qubit 的隱含特徵，而這 256 個數中的每一個都能取無限多種不同的值。

一般化：一組 n 個 qubit 由 2^n 個複數刻畫——這個數量隨 qubit 數呈指數成長。

「以指數多的高精度複數編碼」正是古典電腦無法模擬量子電腦的核心原因：要做到這件事，它需要深不可測的大量記憶體（約 2^n 大小），才能儲存僅僅 n 個 qubit 所含的等量資訊。

量子閘#

古典電腦用暫存器、記憶體與微處理器對資料執行一連串指令；量子電腦則藉由套用一系列量子閘可逆地變換一組 qubit，然後測量一個或多個 qubit 的值。

量子電腦之所以承諾更強的計算能力，是因為只用 n 個 qubit，它們就能處理 2^n 個數（qubit 的振幅）。

從數學角度看，量子演算法本質上是一個量子閘電路，它在最終測量之前變換一組複數（振幅）。你也會看到量子演算法被稱為量子閘陣列或量子電路。

量子閘就是矩陣乘法#

與古典電腦的布林閘（AND、XOR 等）不同，量子閘作用於一組振幅的方式，就如同一個矩陣與一個向量相乘。

例如最簡單的量子閘——單位閘 I——套用到 qubit Φ 上：

     ⎡ 1  0 ⎤ ⎡  i/√2 ⎤   ⎡ 1×(i/√2) + 0×(−1/√2) ⎤   ⎡  i/√2 ⎤
I|Φ⟩=⎢      ⎥ ⎢       ⎥ = ⎢                      ⎥ = ⎢       ⎥ = |Φ⟩
     ⎣ 0  1 ⎦ ⎣ −1/√2 ⎦   ⎣ 0×(i/√2) + 1×(−1/√2) ⎦   ⎣ −1/√2 ⎦

矩陣—向量乘法的結果是另一個兩元素的行向量：上方的值等於矩陣第一列與輸入向量的內積，下方的值同理。

實務上量子電腦不會明確計算矩陣—向量乘法，因為那些矩陣會大到不行（這正是量子計算無法被古典電腦模擬的原因）。

量子電腦是把 qubit 當成物理粒子，透過等價於矩陣乘法的物理變換來變換它們。

覺得困惑嗎？費曼（Richard Feynman）是這麼說的：「如果你沒有被量子力學徹底搞糊塗，你就是沒理解它。」

Hadamard 閘#

單位閘 I 什麼都不做，相當無用。現在來看最有用的量子閘之一——Hadamard 閘（記為 H）：

    ⎡ 1/√2   1/√2 ⎤
H = ⎢             ⎥      （注意右下角的負值）
    ⎣ 1/√2  −1/√2 ⎦

套用到 |Ψ⟩ = (1/√2, 1/√2)：

H|Ψ⟩ = ⎡ 1/√2 + 1/√2 ⎤ = ⎡ 1 ⎤ = |0⟩
       ⎣ 1/√2 − 1/√2 ⎦   ⎣ 0 ⎦

我們得到 qubit |0⟩——|0⟩ 的振幅是 1、|1⟩ 的振幅是 0。

這告訴我們該 qubit 會確定性地行動：觀測它永遠會看到 0，絕不會看到 1。換句話說，我們失去了初始 qubit |Ψ⟩ 的隨機性。

再套用一次到 |0⟩：

H|0⟩ = ⎡ 1/√2 ⎤ = |Ψ⟩
       ⎣ 1/√2 ⎦

這把我們帶回 |Ψ⟩ 與隨機化的狀態。

事實上，Hadamard 閘在量子演算法中常被用來從確定性狀態走向均勻隨機狀態。

不是所有矩陣都是量子閘#

儘管量子閘可以看成矩陣乘法，並非所有矩陣都對應到量子閘。

回想一個 qubit 的振幅 α 與 β 必須滿足 |α|² + |β|² = 1。

若把一個 qubit 乘上某矩陣後得到的兩個振幅不滿足這個條件，結果就不可能是一個 qubit。

量子閘只能對應到那些保持 |α|² + |β|² = 1 性質的矩陣，滿足這個條件的矩陣稱為么正矩陣（unitary matrices）。

么正矩陣（依定義也就是量子閘）是可逆的——給定一次操作的結果，你可以套用反矩陣算回原本的 qubit。

這正是**量子計算被稱為一種「可逆計算」**的原因。