Grover 搜索算法#

背景与理论#

Grover 搜索算法（Grover, 1996）为非结构化搜索提供了二次加速。 给定一个预言机 \(f : \{0,1\}^n \to \{0,1\}\)，满足 \(f(x) = 1\) 当且仅当 \(x\) 是目标态 \(|w\rangle\)， Grover 算法只需 \(O(\sqrt{N})\) 次预言机调用即可找到 \(|w\rangle\)， 而非经典算法所需的 \(O(N)\) 次，其中 \(N = 2^n\)。

核心组件#

1. 预言机 \(U_\omega\) 相位翻转预言机，将目标态的振幅乘以 \(-1\)：

\[U_\omega |x\rangle = (-1)^{f(x)} |x\rangle\]

标准构造使用一个处于魔术态 \(|-\rangle = (|0\rangle - |1\rangle)/\sqrt{2}\) 的辅助比特：

\[U_\omega |x\rangle |-\rangle = |x\rangle \otimes (-1)^{f(x)} |-\rangle\]

2. 扩散算子 \(D\) 也称为振幅放大算子：

\[D = 2|s\rangle\langle s| - I\]

其中 \(|s\rangle = H^{\otimes n}|0\rangle^{\otimes n}\) 是均匀叠加态。 \(D\) 将任意向量关于 \(|s\rangle\) 做反射，将非目标态的振幅转移到目标态。

3. Grover 迭代 组合的预言机 + 扩散步：

\[G = D \cdot U_\omega\]

对 \(|s\rangle\) 施加 \(R \approx \frac{\pi}{4}\sqrt{N}\) 次后，振幅将集中于目标态。

状态演化#

从 \(|s\rangle = \frac{1}{\sqrt{N}} \sum_x |x\rangle\) 出发：

经过一次 Grover 迭代后，状态处于由 \(\{|w\rangle, |s'\rangle\}\) 张成的二维子空间中， 其中 \(|s'\rangle\) 是所有非目标态的叠加。

\(|w\rangle\) 上的振幅按 \(\sin((2R+1)\theta)\) 增长，其中 \(\sin\theta = 1/\sqrt{N}\)。

代码解析#

build_oracle#

def build_oracle(n_qubits, marked_state):

为给定目标态构建相位翻转预言机：

  1. 辅助比特准备：将辅助比特初始化为 \(|-\rangle = X \cdot H |0\rangle\)

  2. 目标态编码：翻转目标态中处于 \(|0\rangle\) 的数据比特

  3. 相位回踢：从数据比特到辅助比特施加多控 Z（CCZ）

  4. 逆计算：恢复之前翻转的比特

build_diffusion#

实现 \(D = H^{\otimes n} \cdot Z^{\otimes n} \cdot H^{\otimes n}\)：

  1. 施加 \(H^{\otimes n}\) 将 \(|s\rangle \to |0\rangle^{\otimes n}\)

  2. 施加 \(Z^{\otimes n}\) 翻转 \(|0\rangle^{\otimes n}\) 的相位

  3. 再次施加 \(H^{\otimes n}\)——净效果是关于 \(|s\rangle\) 的反射

run_grover#

端到端的 Grover 搜索：

  1. 将数据比特初始化为 \(|+\rangle\)（对 \(|0\rangle\) 施加 Hadamard）

  2. 施加最优迭代次数 \(R = \lfloor \frac{\pi}{4}\sqrt{N} \rfloor\) 次 Grover 迭代

  3. 测量所有数据比特

运行示例#

# 基本运行：3 个比特，目标态 = 5
python examples/algorithms/grover.py --n-qubits 3 --marked-state 5

# 更大的搜索空间
python examples/algorithms/grover.py --n-qubits 4 --marked-state 10 --shots 8192

预期输出：

 Grover's Search — 3 data qubits
 Marked state: 5 (101)
 Search space: 8 states

 Results (top 5 most probable states):
   |101⟩  95.2% ← TARGET
   |010⟩   1.8%
   |000⟩   1.2%
   |110⟩   0.8%
   |001⟩   0.6%

 Target probability: 95.2%
 Expected (ideal): ~95.0% (after optimal iterations)

设计说明#

  • 辅助比特：预言机使用一个额外的辅助比特来实现相位回踢。这是标准的”辅助比特”方法，适用于任意数量的比特。

  • 多控 Z 门：对于 2 比特情况，使用 ccx（Toffoli）加末尾的 Z 门实现 CCZ。对于超过 2 个比特，使用线性深度的 CNOT 级联配合目标比特上的 H 门来实现 MCZ。

  • 最优迭代次数：迭代次数 \(R = \lfloor \frac{\pi}{4}\sqrt{N} \rfloor\) 可最大化成功概率。对于较小的 \(N\)，取整和上限可以防止过冲。

  • 测量：仅测量数据比特（辅助比特不测量）。

扩展方向#

  • 多目标 Grover：将单个目标替换为 \(M\) 个目标态；最优迭代次数变为 \(\frac{\pi}{4}\sqrt{N/M}\)

  • 非均匀 Grover：对每个状态使用不同的预言机强度

  • 振幅估计：使用 state_tomography 表征测量前的状态，并解析地估计成功概率

References#