5.1 什麼讓量子演算法更快#

概念說明#

要談「快」，先把問題標準化。量子演算法理論多用黑箱模型（oracle / query model）：問題由一個函式 \(f:\{0,1\}^n \to \{0,1\}\) 定義，但 \(f\) 的內容藏在黑箱裡，我們只能詢問「 \(f(x)\) 是多少？」。查詢複雜度（query complexity）就是所需詢問次數。它最大的好處是：可以證明下界——「任何古典演算法都至少要問幾次」。

量子黑箱是一個么正算子 \(U_f\) ：

量子演算法的標準套路（被 Deutsch–Jozsa、BV、Grover、Shor 共用）：

1. 疊加：Hadamard 把 \(|0\rangle^{\otimes n}\) 變成所有 \(2^n\) 個輸入的均勻疊加；
2. 一次黑箱查詢： \(U_f\) 把 \(f\) 的資訊「編碼進相位」——這一步稱為 phase kickback：若標的位元先被 H 置於 \(|-\rangle\) ，則 \(U_f|x\rangle|-\rangle = (-1)^{f(x)}|x\rangle|-\rangle\) ；
3. 干涉：再用 H（或其他么正）讓不同路徑的振幅相加或相消；
4. 測量：讀出被干涉放大出來的資訊。

三個必須破除的迷思：

• 「 \(2^n\) 個振幅 = 平行計算 \(2^n\) 個值」：測量只能取一個結果；加速來自干涉，不是平行。
• 「量子可以解 NP 完全問題」：目前沒有證據，Grover 只有平方加速。
• 「量子對所有問題都快」：絕大多數問題的最佳量子演算法與古典差不多。

Python 範例：相位 kickback 的觀察#

import numpy as np

ket0 = np.array([1,0], dtype=complex)
ket1 = np.array([0,1], dtype=complex)
minus = (ket0 - ket1)/np.sqrt(2)
H = np.array([[1,1],[1,-1]], dtype=complex)/np.sqrt(2)

def f_oracle_Uf(f, n):
    """建構 U_f：|x>|y> -> |x>|y xor f(x)>，2n 位元矩陣"""
    N = 2**(2*n)
    U = np.zeros((N, N), dtype=complex)
    for x in range(2**n):
        for y in range(2):
            col = (x << 1) | y                    # 高 n 位是 x，低位是 y
            row = (x << 1) | (y ^ f(x))
            U[row, col] = 1
    return U

# 例：f(x) = x 的第 0 位
f = lambda x: x & 1
Uf = f_oracle_Uf(f, 1)

for inp, name in [(ket0, "|0>"), (ket1, "|1>"), (minus, "|->")]:
    out = Uf @ np.kron(inp, ket1)      # 標的先放 |1>
    out_input = out[:2]                # 輸入位元的部分
    print(f"輸入 {name}: 輸出輸入位元部分 = {np.round(out_input,3)}")
# 注意：|1>|-> 與 |0>|-> 經 Uf 後，輸入部分完全相同（f 已被踢進相位）：
# Uf|x>|-> = (-1)^{f(x)} |x>|->

複雜度分析#

查詢模型下： - 判斷 \(n\) 位元函式 \(f\) 是否全為 0：古典最壞 \(2^n\) 次查詢，量子（相位估計式方法） \(O(\sqrt{2^n})\) ； - Deutsch–Jozsa 的常數/平衡判別：古典 \(2^{n-1}+1\) ，量子 1 次（指數差距，但問題本身是人造的）； - 模擬成本：構造完整 \(U_f\) 矩陣需 \(O(4^n)\) ，實作上應以「逐項更新」的方式在 \(O(2^n)\) 內套用。

練習#

1. 證明 \(U_f|x\rangle|-\rangle = (-1)^{f(x)}|x\rangle|-\rangle\) 。
2. 說明為什麼「測量取得一個結果」不與「 \(2^n\) 振幅」矛盾，量子加速從哪裡來？
3. （程式）擴充 f_oracle_Uf 支援 \(n=2\) ，並驗證 \(U_f^2 = I\) （黑箱是么正且自逆的）。