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

了解量子 oracle

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

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

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

可以通过引入第二个 m来保存答案来处理这两个问题。 然后,定义 oracle 在所有计算基础上的效果:对于所有 x \0、1\}^ny \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=O,注意 O2=1,因为对于所有 a,b0,1abb=a。 因此 O|x|yf(x)=|x|yf(x)f(x)=|x|y

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

$$\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使n+m 量子比特上\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} $$

此处, α{01}n×{01}mC 表示状态 |ψ的系数。 因此,

$$\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,将 foracleO$$。 例如,可以定义 O,以便 $$\begin{align}\begin{O \ket{x}= (-1)^{f(x)}\ket{x}。 \end{align} $$

如果阶段 Oracle 作用于最初处于计算基态 |x 的寄存器,则此阶段是全局阶段,因而不可观察。 但是,如果应用于叠加或作为受控操作,此类 Oracle 可能是一种强大的资源。 例如,考虑一下单量子比特函数 f 的阶段 Oracle Of。 然后, $$\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} $$

备注

请注意 Z1=Z=Z,因此 Zf(0)f(1)=Zf(1)f(0)

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

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

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