使用和定義量子 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}}\otimes\ket{{x_x_{1}}\otimes\ket{\cdots\otimes{n-1。}}$

您可以先嘗試定義 O，讓 O\ket{x f (x\ket{=}) }$，但此方法有幾個問題。$$$ 首先，$f$ 可能會有不同的輸入與輸出大小 ($n \ne m$)，因此套用 $O$ 會變更暫存器中的量子位元數目。 其次，即使 $n = m$，函式可能是不可逆的：如果 $f(x) = f(y)$，而某些 $x \ne 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 = ^\dagger$ 已解決上述兩個問題。

提示

若要查看 $O = O^{\dagger}$，請注意 $O^2 =\mathbf{1}$ 因為 $a \oplus b \oplus b = a$ 是針對所有的 $a, b \in{0, 1}$。 因此，$O \ket{x}\ket{y \oplus f(x)}=\ket{x}\ket{y \oplus f(x) \oplus f(x)}=\ket{x}\ket{y}$

重要的是，以這種方式為每個計算基礎狀態 $\ket{x}\ket{y}$ 定義 Oracle，也會定義 $O$ 對任何其他狀態運作的方式。 此行為會緊接在 O$ 就像所有量子作業一樣的事實$中，其作用狀態為線性。 例如，請考慮由 H\ket{\ket{0}= +}$ 和 $H \ket{1}\ket{-}$=定義的 $Hadamard 作業。 如果您想要知道 H$ 在 +}$上$\ket{的運作方式$，可以使用該 $H$ 是線性的，

$$\begin{align}H\ket{+}& =\frac{1}{\sqrt{{2}}H (\ket{0} +) ({2}}\frac{1}{\sqrt{= H\ket{0} + \ket{{1} H\ket{1}) &\\ amp; =\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{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

或者，您可以將 f 編碼$$為 Oracle $O$，方法是根據輸入將階段套用至 $O$。 例如，您可以定義 $O$，$$\begin{align}\begin{讓 O \ket{x}= (-1) ^{f (x) }\ket{x。} \end{align} $$

如果階段 Oracle 一開始是在計算基礎狀態 $\ket{x}$ 中對暫存器採取動作，則此階段是全域階段，因此無法觀察。 但是，如果套用至迭加或控制作業，這類 Oracle 可能是功能強大的資源。 例如，針對單一量子位元函式 $f$ 考慮階段 Oracle $O_f$。 然後， $$\begin{align} O_f \ket{+}& =\ket{0} O_f (+ \ket{{1}) /\\&{2}\sqrt{ amp; = ( (-1) ^{f (0) }\ket{0} + (-1) ^{f (1) \ket{1}}) / \sqrt{2}\\& = (-1) ^{f (0) } (\ket{{0} + (-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 的討論。

下一步