6.1 疊加與相位反轉#

概念說明#

Grover 搜尋的問題設定：黑箱 \(f:\{0,1\}^n\to\{0,1\}\) ，滿足 \(f(x)=1\) 的解恰有 \(M\) 個（先設 \(M=1\) ）， \(N=2^n\) 。目標：用最少次呼叫 \(f\) 找到解。

第一步：均勻疊加

每個索引的振幅都是 \(1/\sqrt N\) 。此時測量，任何一點被抽到的機率都只有 \(1/N\) ——還沒有用。

**第二步：相位反轉 oracle \(O_f\) **

即「解」的振幅乘上 \(-1\) 。實作時不檢查相位（相位不可直接測量），而是靠**輔助位元放在 \(|-\rangle\) ** 的 phase kickback： \(U_f|x\rangle|-\rangle = (-1)^{f(x)}|x\rangle|-\rangle\) 。

相位反轉之後，機率分佈完全不變（ \(|{-a}|^2 = |a|^2\) ）——單獨使用 oracle 什麼都得不到。它的價值在於為下一步的干涉準備了「符號」。這是量子演算法最反直覺之處：先把資訊藏進相位，再用另一個操作把相位差轉換成可測量的機率差。

在二維子空間 \(\{|w\rangle, |r\rangle\}\) （解與其餘的均勻疊加）中，oracle 是對 \(|w\rangle\) 的反射。

Python 範例：相位反轉#

import numpy as np

def phase_oracle(f, n):
    """O_f|x> = (-1)^{f(x)}|x>，對角矩陣"""
    d = np.array([(-1)**f(x) for x in range(2**n)])
    return np.diag(d.astype(complex))

n = 3
w = 5                                   # 隱藏的解：x=5 (二進位 101)
f = lambda x: 1 if x == w else 0
O = phase_oracle(f, n)

plus = np.ones(2**n, dtype=complex)/np.sqrt(2**n)
after = O @ plus
print("oracle 前振幅:", np.round(plus[:8], 3))
print("oracle 後振幅:", np.round(after[:8], 3))    # 只有第 5 項是 -1
print("機率分佈變了嗎?", np.allclose(np.abs(plus)**2, np.abs(after)**2))
print("目標振幅:", after[w])                        # -0.3535，符號已翻轉

複雜度分析#

• oracle 的查詢成本記為 1 單位；電路實作上 \(O_f\) 需要 \(O(n)\) 個基本閘合成 \(f\) 的可逆電路（若 \(f\) 本身是多項式時間可計算）。
• 狀態向量模擬中，對角 oracle 可用 state *= signs 向量化， \(O(2^n)\) 。
• 單做疊加＋oracle 不改變測量分佈；干涉需要下一步的擴散算子。

練習#

1. 對 \(n=3\) 、 \(w=5\) ，寫出 oracle 作用後的完整振幅向量。
2. （程式）實作 phase kickback 版本的 oracle（3 位元 + 輔助 \(|-\rangle\) ），驗證與對角矩陣版本等效。
3. （觀念）為什麼「直接把解的振幅改成大數字」的閘不是合法的量子操作？（提示：么正性與振幅依賴態本身。）