15、量子计算中的 Deutsch–Jozsa 与 Grover 算法

量子计算中的 Deutsch–Jozsa 与 Grover 算法

1. Deutsch–Jozsa 算法

1.1 算法概述

Deutsch–Jozsa 算法是 Deutsch 算法在 n 自由度情况下的推广。该算法的分析主要是为了说明将 n 个量子比特表示为计算基态的叠加时所产生的振幅抵消现象。

1.2 具体步骤

考虑 n 个量子比特和一个辅助量子比特。对 |0⟩⊗n 应用 Hadamard 门，会得到所有可能的量子比特计算基的组合，且每个组合的振幅相等。展开式中有 2n 项，用 x = {0, 1, 2, …, 2n - 1} 对这些状态进行标记。

以下是算法的具体状态变化：
1. 初始状态：
- |ψ(t0)⟩ = |0⟩⊗n|1⟩
2. 应用 Hadamard 门后：
- |ψ(t1)⟩ = (H⊗n|0⟩⊗n)(H|1⟩) = $\frac{1}{\sqrt{N}}\sum_{x = 0}^{N - 1}|x⟩\frac{1}{\sqrt{2}}(|0⟩ - |1⟩)$，其中 N = 2n
3. 经过 Uf 变换后：
- |ψ(t2)⟩ = Uf|ψ(t1)⟩ = $\frac{1}{\sqrt{N}}\sum_{x = 0}^{N - 1}|x⟩\frac{1}{\sqrt{2}}(|0 ⊕ f(x)⟩ - |1 ⊕ f(x)⟩)$
- 利用 $\frac{1}{\sqrt{2}}[|f⟩ - |1 ⊕ f⟩] = (-1)^f\frac{1}{\sqrt{2}}(|0⟩ - |1⟩) = (-1)^fH|1⟩$，可得 |ψ(t2)⟩ = $\frac{