瞭解量子 Oracle

Oracle $O$ 是一項未公開的作業，可作為另一個演算法的輸入。 這類作業通常是使用傳統函 $\mathrm{式}f\mathrm{來}\mathrm{定}\mathrm{義}：\{0、1{\}}^n\to \{0、1{\}}^m$，它會接受 $n$ 位二進位輸入併產生 $m$ 位二進位輸出。 若要這樣做，請考慮特定的二進位輸入 $x（x_{、}{x}_{0}1、\cdots 、x_{n-1）。\$}=\mathrm{您}\mathrm{可}\mathrm{以}\mathrm{將}\mathrm{量}\mathrm{子}\mathrm{位}\mathrm{狀}\mathrm{態}$\ket{\vec{標記為 x\ket{}}=x_{0}}\otimes\ket{{x_x_{1}}\otimes\ket{\cdots\otimes{n-1。}}$

您可能先嘗試定義 $O$，讓 $O|xf（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

您可以引進第二個量子位緩存器$$來保存答案，以處理這兩個問題。 然後，在所有計算基礎狀態上定義 Oracle 的效果：針對所有 x \0、1\}^n$\mathrm{和}$y \in \{0、1\}^m、{\in $$

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

現在 $O{=}^{†}$ 建構，您解決了先前兩個問題。

提示

$\mathrm{若}\mathrm{要}\mathrm{查}\mathrm{看}O{O}^{，}\mathrm{請}\mathrm{注}\mathrm{意}$O=^{\dagger}$2=\mathbf{1}$，因為 $\oplus b\oplus b=$ a 代表所有 $a、b\in 0、1。$ 因此，O x}y \oplus f（x）}\ket{=x\ket{}y \oplus f（x） \oplus f（x） \oplus f（x）}=\ket{x}\ket{y。}$\ket{\ket{$

重要的是，針對每個計算基礎狀態 x y 以這種方式定義 Oracle，也會定義 O$\text{Extra close brace or missing open brace}$}\ket{$|\$\mathrm{此}\mathrm{行}\mathrm{為}\mathrm{緊}\mathrm{接}\mathrm{在}\$O\$，\mathrm{就}\mathrm{像}\mathrm{所}\mathrm{有}\mathrm{量}\mathrm{子}\mathrm{作}\mathrm{業}\mathrm{一}\mathrm{樣}，\mathrm{在}\mathrm{作}\mathrm{用}\mathrm{中}\mathrm{狀}\mathrm{態}\mathrm{是}\mathrm{線}\mathrm{性}\mathrm{的}。\mathrm{例}\mathrm{如}，\mathrm{假}\mathrm{設}\mathrm{已}\mathrm{定}\mathrm{義}\$H+⟩$ 和 $H|1⟩=|-⟩$\ket{0}=\ket{的 Hadamard 作業。 如果您想要知道 H$\text{Extra close brace or missing open brace}$上的$\ket{運作方式$，\mathrm{可}\mathrm{以}\mathrm{使}\mathrm{用}\mathrm{該}$H$ 是線性的，

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

定義 Oracle $O$ 時，您也可以同樣地使用 n + m$\mathrm{量}\mathrm{子}\mathrm{位}\mathrm{上}$的任何狀態$|\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

或者，您可以將 f 編碼為 Oracle $O$，方法是根據輸入將階段套用至 $O。$$$ 例如，您可以定義 $O$，\begin{\begin{align}$$\text{Missing begin{align} or extra end{align}}$$

如果階段 Oracle 一開始以計算基礎狀態 $|x⟩$ 執行緩存器，則此階段是全域階段，因此無法觀察。 但是，如果套用至迭加或做為受控制的作業，這類 Oracle 可以是強大的資源。 例如，請考慮單一量子位函$\mathrm{式}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{}） /&\sqrt{{2}\ amp; = （-1）^f（0） Z^{{f（0）} - f（1）}\ket{+。} \end{align} $$

注意

請注意，$\text{Double exponent: use braces to clarify}$，因此 $Z{}^{-1}=f（0）-f（1）=Z^{f（1）-f（0）}。$

更普遍地，可以擴大兩個 Oracle 檢視來表示傳統函式，以傳回實數，而不是只傳回單一位。

選擇實作 Oracle 的最佳方式，在很大程度上取決於此 Oracle 如何在指定的演算法內使用。 例如， Deutsch-Jozsa 演算法 依賴第一種方式實作的 Oracle，而 Grover 的演算法 則依賴以第二種方式實作的 Oracle。

如需詳細資訊，請參閱 Gilyén 1711.00465 中的討論。

相關內容

• Grover 的演算法
• 量子中繼表示法
• 向量和矩陣
• T 閘道和 T Factory