预言机

经典预言机

预言机本质上是一个黑箱函数，用于抽象算法中的某些部分。计算机科学家使用预言机来隐藏复杂的逻辑和实现细节，从而专注于所分析算法的可计算性或时间/空间复杂度。形式上，我们可以将一个预言机表示为一个函数。该函数接收一个 $n$ 维输入 $x$，并产生一个 $m$ 维输出 $y$。

$f(x) = y$

例如，可以有一个函数接收五个数字作为输入，并返回它们的和。此时，输入 $x$ 是五维的，而输出 $y$ 只有一维。

量子预言机

从经典预言机的例子中，你可能会注意到该操作是不可逆的。输入和输出的维度不一致，仅凭输出无法确定原始输入。我们之前讨论过，为了保持可逆性，必须使用酉操作。本质上，量子预言机是一种可逆的黑箱函数，其用途与经典预言机在研究经典算法时相同。相同的输入和输出维度使得量子预言机能够应用于量子计算和量子比特的场景。我们可以将量子预言机定义为一个酉算子 $O$，它对一组量子比特系统施加所需的黑箱函数。

$O|x\rangle = |f(x)\rangle$

这个定义的问题在于，当函数的输出 $y$ 所需的量子比特数与输入 $x$ 不同时，该定义无法适用。为了解决这个问题，我们可以引入一个额外的 $m$ 位量子比特寄存器 $y$，也称为辅助量子比特。此时，酉算子可以被定义为：以 $n$ 维 $x$ 和 $m$ 维 $y$ 的组合作为输入，通过 $CNOT$ 操作（即量子等价的异或操作）将函数 $f(x)$ 的结果写入辅助寄存器，同时保持原始输入 $x$ 不变。关键点在于，所有操作都是可逆的。

$O(|x\rangle \otimes |y\rangle) = |x\rangle \otimes |y \oplus f(x)\rangle$

示例

我们可以将这些预言机看作一个大型量子门，从一端接收量子态，应用酉算子来实现 $f(x)$，并将所需结果存储在额外的量子比特中。

下图展示了一个记为 $U_f$ 的预言机示例。

在上述电路中，$U_f$ 接收 $x=|0^{\otimes n}\rangle$ 和 $y = |1\rangle$ 作为输入，输出时保持 $x$ 不变，但将 $y \oplus f(x)$ 输出，即 $y$ 与 $f(x)$ 的模 2 加法（或异或）。其中 $f(x)$ 是预言机作用于数据量子比特上的函数，而 $y = |1\rangle$ 是我们的辅助量子比特（简称辅助）。需要注意的是，输出中保留了足够的信息，确保不会违反量子计算的基本原理。

相位预言机

上述量子预言机的定义提供了一种在量子算法中使用预言机的可逆方案，但需要额外的量子比特，带来了额外开销。另一种量子预言机的定义称为相位预言机，可以帮助我们克服这一开销。

那么相位预言机是如何工作的？它会对量子态施加一个相位。其定义如下：

$O|x\rangle = (-1)^{f(x)}|x\rangle$

这在处理叠加态时特别有用，因为正如我们在前面课程中看到的，相位差异可以通过干涉来促进计算。对于普通状态，它会施加一个全局相位，这种相位可以忽略，因此在这种情况下没有实际意义。

$O|+\rangle = \frac{1}{\sqrt{2}}|0\rangle + \frac{1}{\sqrt{2}}|1\rangle$

$O|+\rangle = \frac{1}{\sqrt{2}}(-1)^{f(0)}|0\rangle + \frac{1}{\sqrt{2}}(-1)^{f(1)}|1\rangle$

函数的结果被编码在量子态的相对相位中。这将根据新相位值的变化改变量子态。

为什么需要量子预言机？

在后续学习量子算法的过程中，我们将需要定义量子预言机和相位预言机，以抽象出某些经典逻辑。这有助于我们聚焦于算法的量子特性，并深入理解为何特定的量子算法在解决相同问题时比经典算法具有渐近优势。