你当前正在访问 Microsoft Azure Global Edition 技术文档网站。 如果需要访问由世纪互联运营的 Microsoft Azure 中国技术文档网站，请访问 https://docs.azure.cn。

使用和定义量子 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\ket{x=}\ket{f (x) }$，但此方法存在一些问题。 第一，$f$ 的输入和输出大小可能不同 ($n \ne m$)，因此，应用 $O$ 可能会改变寄存器中量子比特的数量。 第二，即使 $n = m$，该函数也可能不可逆：如果对于某些 $x \ne y$，$f(x) = f(y)$，则 $O\ket{x}= O\ket{y}$，但 $O^\dagger O\ket{x}\ne O^\dagger O\ket{y}$。 这意味着无法构造相邻操作 $O^\dagger$，并且 Oracle 必须为其定义一个相邻操作。

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

可以通过引入第二个 m$ 量子比特寄存器$来保存答案来处理这两个问题。 然后，定义 oracle 对所有计算基础状态的影响：对于所有 x \0、1\}^n$ 和 $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} $$

现在 $O = O^\dagger$ 通过构造，你已经解决了两个以前的问题。

提示

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

重要的是，如果以这种方式为每一种计算基态定义 Oracle，$\ket{x}\ket{y}$ 还会定义 $O$ 如何作用于所有其他状态。 与所有量子运算一 $样，O$ 在作用状态中是线性的，这一行为紧随其后。 例如，考虑由 H +}$ 和 $H=\ket{0}\ket{-}$=\ket{1}\ket{ 定义的 $Hadamard 操作。 如果希望了解 H$ 如何$作用于 $\ket{+}$，可以使用 H $$ 是线性的，

$$\begin{align}H\ket{+}& =\frac{1}{\sqrt{{2}}H (\ket{0} +{1}\ket{) =\frac{1}{\sqrt{{2}} (H\ket{0} +\ket{1} H) \\& =\frac{1}{\sqrt{2}} (\ket{+} + \ket{{-}) \frac= 12 (\ket{{0} + \ket{{1} +{0}\ket{-{1}\ket{) 。=\ket{{0} \end{align} $$

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

$$\begin{align}\ket{\psi}&放大 器; =\sum_{x \in \{0， 1\}^n， y \in \{0， 1\}^m}\alpha (x， y) \ket{x}\ket{y}\end{\end{align}$$

其中，$\alpha : \{0, 1\}^n \times \{0, 1\}^m \to\mathbb{C}$ 表示状态 $\ket{\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$ 编码$为 $Oracle $O$。 例如，可以定义 $O$，使 $$\begin{align}\begin{O \ket{x=} (-1) ^{f (x) }\ket{x}。 \end{align} $$

如果相位预言作用于最初处于计算基础状态 $\ket{x}$ 的寄存器，则此相位是全局相位，因而不可观察。 但是，如果应用于叠加或作为受控操作，此类 oracle 可能是一种功能强大的资源。 例如，考虑一下单量子比特函数 $f$ 的阶段 Oracle $O_f$。 然后， $$\begin{align} O_f \ket{+}& =\ket{0} O_f (+{1}\ket{) / \sqrt{{2}\\& = ( (-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) } Z^{f (0) - f (1) }\ket{+。} \end{align} $$

注意

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

更一般地，可以扩大 oracle 的两个视图，以表示经典函数，这些函数返回实数，而不是只返回一个位。

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

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

后续步骤