如何解释 Grover 算法中的相位反冲

Question

对于 Grover 算法的预言，有一个解释是我们使用如下的相位反冲。

也就是说，我们可以判断 f(|x>) 是否为 1，因为它会改变输出 |x>。

我的问题是，

1. 我们如何确定系数 (-1)^f(x) 附加到 |x>，而不是附加到辅助位 (|y>)？

2. 为什么这种解释有用？我没有看到这个辅助位在实现 Grover 算法中有任何用途。

我期待以上两个问题的答案。

Answer 1

我们来一一解答您的疑问。

1. 我们如何知道相位变化 (-1)^f(x) 附加到 |x>，而不是附加到辅助位 (|y>)？

• 我们知道相位变化与输入状态 |x> 相关的原因 （而不是辅助位 |y>）是由于量子预言机的设计 和相位反冲机制。 在格罗弗的算法中，预言机通常作为一个单一的系统运行 联合状态 |x>|y> 上的变换 U_f，其中 |x> 是输入状态 （我们想要搜索的状态），|y> 是辅助位。这 构造酉变换 U_f，使其执行 以下操作：

  • U_f : ∣x>∣y> → ∣x>∣y ⊕ f(x)∣

  这里，f(x) 是二元函数。如果 f(x) = 1，则辅助位 |y> 为 翻转（即 |y> ⊕ 1），如果 f(x) = 0，则保持不变。

  这里的关键观察是当我们将 |y> 初始化为像 |-> = rac{1}{\sqrt{2}} (|0> - |1>) 这样的叠加态时会发生什么。通过此初始化，翻转辅助位会导致相变而不是翻转。以下步骤解释了为什么会出现这种情况：

  • 当 f(x) = 0 时，|y> 仍为 |->。
  • 当 f(x) = 1 时，|y> 翻转为 -|->。

  这里的关键在于，运算的结果是在状态|x>上加上了(-1)^f(x)的相位因子，而辅助位又回到原来的叠加状态。

2. 为什么这个解释有用？为什么 Grover 算法中需要辅助位？

• 辅助位的这种解释和使用很有用，因为它允许我们将函数 f(x) 编码为 |x> 上的相位变化。这种相变是格罗弗算法的基础，该算法依靠量子干涉来放大正确答案的概率，同时抑制错误答案。

• 辅助位提供了一种“查询”函数 f(x) 的机制，而无需永久更改 |x> 的状态。相反，它将结果编码在一个阶段中，允许格罗弗的算法使用量子干涉和幅度放大来找到正确的答案。这种基于阶段的操作对于保持量子操作的单一性和可逆性至关重要，这是量子计算的基石。

• 因此，辅助位有助于确保 Grover 的预言机执行所需的转换，而不会永久改变计算状态，同时还促进作为许多量子算法核心的基于相位的逻辑。