了解量子 oracle

oracle $O$ 是一个未公开的操作，用作另一种算法的输入。 通常，此类操作使用经典函数 $f：\{0、1{\}}^n\to \{0、1{\}}^m$ 定义，后者采用 $n$ 位二进制输入并生成 $m$ 位二进制输出。 为此，请考虑一个特殊的二进制输入 $x=(x_0,x_1,\dots ,x_{n-1})$。 可以将量子比特状态$\ket{\vec{标记为 x=\ket{}}x_{0}}\ket{{\otimesx_\otimes{1}}\otimes\ket{\cdotsx_{n-1。}}$

可能首先尝试定义 $O$ 以便 $O|x|⟩=f（x），⟩$但此方法存在几个问题。 首先， $f$ 的输入和输出大小可能不同（$n\ne m$），以便应用 $O$ 会更改寄存器中的量子比特数。 其次，即使 n m，函数可能不可逆：如果$\mathrm{某}\mathrm{些}$x \ne y$\mathrm{的}f（x）=f（y），$则 $O x=} O\ket{y 但 $O|{}^{O}x\ne ⟩O^{†}†O||y。⟩\$⟩$$=$ 这意味着无法构造相邻操作 $O^{†}$，oracle 必须为其定义相邻操作。

通过对计算基态的影响定义 Oracle

可以通过引入第二个 m$\mathrm{量}\mathrm{子}\mathrm{比}\mathrm{特}\mathrm{寄}\mathrm{存}\mathrm{器}$来保存答案来处理这两个问题。 然后，定义 oracle 在所有计算基础上的效果：对于所有 x \0、1\}^n$\mathrm{和}$y \in \{0、1\}^m$、{\in $

$$\begin{\begin{align} O(\ket{x}\otimes\ket{y}) =\ket{x}\otimes\ket{y \oplus f(x)}. \end{align} $$

现在 $\mathrm{通}\mathrm{过}\mathrm{构}\mathrm{造}O{=}^{†}$ 解决了这两个问题。

提示

对于 $O=O^{†}$，注意 $O^2=\mathbf{1}$，因为对于所有 $a,b\in 0,1$，$a\oplus b\oplus b=a$。 因此 $O|x⟩|y\oplus f(x)⟩=|x⟩|y\oplus f(x)\oplus f(x)⟩=|x⟩|y⟩$。

重要的是，如果以这种方式为每一种计算基态定义 Oracle，$|x⟩|y⟩$ 还会定义 $O$ 如何作用于所有其他状态。 此行为紧 $\mathrm{随}O$（与所有量子操作一样）处于线性状态，其作用状态是线性的。 考虑 Hadamard 运算，例如，定义 $H|0⟩|=+⟩$ 和 $H。|1⟩=|-⟩$ 如果想要知道 H 如何$\mathrm{作}\mathrm{用}$\ket{+}$，\mathrm{则}\mathrm{可}\mathrm{以}\mathrm{使}\mathrm{用}\mathrm{该}$H$\mathrm{是}\mathrm{线}\mathrm{性}\mathrm{的}，$

$$\begin{align}H\ket{+}& =\frac{1}{\sqrt{{2}}H（\ket{0} + \ket{{1}） ={2}}\frac{1}{\sqrt{（H\ket{0} + H\ket{1}） \& =\frac{1}{\sqrt{2}}（\ket{+ + \ket{}{-}） =\frac12 （\ket{{0} + \ket{{1} +{0} \ket{-{1}\ket{ ） 。 =\ket{{0} \end{align} $$

定义 oracle $O\mathrm{时}，\mathrm{同}\mathrm{样}\mathrm{可}\mathrm{以}\mathrm{使}\mathrm{用}n+m$ 量子比特上$\mathrm{的}\mathrm{任}\mathrm{何}\mathrm{状}\mathrm{态}$\ket{\psi}$$编写为

$$\begin{\begin{align}\ket{\psi}&放大 器; =\sum_{x \in \{0、1\}^n、y \in \{0、1\}^m}\alpha（x、y） \ket{x}\ket{y}。 \end{align} $$

此处， $\alpha ：\{0、1{\}}^n\times \{0、1{\}}^m\to \mathbb{C}$ 表示状态 $|\psi ⟩$的系数。 因此，

$$\begin{\begin{align}O \ket{\psi}& =O \sum_{x \in \{0， 1\}^n， y \in \{0， 1\}^m\alpha}（x， y） \ket{x\ket{}y\&}amp; =\sum_{x \in \{0， 1\}^n， y \in \{0， 1\}^m}\alpha（x， y） O \ket{x}\ket{y\&}amp; =\sum_{x \in \{0， 1\}^n， y \in \{0， 1\}^m\alpha}（x， y） \ket{x}\ket{y \oplus f（x）}. \end{align} $$

阶段 Oracle

或者，可以通过将基于输入的阶段应用于 O，将 f$\mathrm{编}\mathrm{码}$为 $oracle$O$$。 例如，可以定义 $O$，以便 $$\begin{align}\begin{O \ket{x}= （-1）^{f（x）}\ket{x}。 \end{align} $$

如果阶段 Oracle 作用于最初处于计算基态 $|x⟩$ 的寄存器，则此阶段是全局阶段，因而不可观察。 但是，如果应用于叠加或作为受控操作，此类 Oracle 可能是一种强大的资源。 例如，考虑一下单量子比特函数 $f$ 的阶段 Oracle $O_f$。 然后， $$\begin{align} O_f \ket{+}& =O_f （\ket{0} +{1}\ket{ ） /\&\sqrt{{2} amp; =（（-1）^{f（0）}\ket{0} + （-1）^{f（1）\ket{1}}） /&\sqrt{2}\ amp; =（-1）^{f（0）} （{0}\ket{ + （-1）^{f（1） - f（0）{1}\ket{}） /\{2}&\sqrt{ amp; = （-1）^{f（0）} -{ f（1）}\ket{+.} \end{align} $$

备注

请注意 $Z^{-1}=Z^{†}=Z$，因此 $Z^{f(0)-f(1)}=Z^{f(1)-f(0)}。$

更普遍的是，可以扩大 oracle 的这两种视图来表示经典函数，后者返回实数，而不是只返回一位。

选择实现 oracle 的最佳方式在很大程度上取决于如何在给定算法中使用此 oracle。 例如，Deutsch-Jozsa 算法依赖于以第一种方法实现的 Oracle，而 Grover 的算法依赖于以第二种方法实现的 Oracle。

有关详细信息，请参阅 Gilyén 1711.00465 中的讨论。

相关内容

• Grover 算法
• 量子中间表示形式
• 矢量和矩阵
• T 门和 T 工厂