量子オラクルについて
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_{1}}\otimes\cdots\otimes\ket{x_{n-1}}$ というラベルを付けることができます。
最初に $O$ を定義して、 $O\ket{x}=\ket{f(x)}$するようにすることもできますが、このメソッドにはいくつかの問題があります。 まず、 $f$ の入出力のサイズが異なる場合があります ($n \ne m$)、 $O を適用すると$ レジスタ内の量子ビット数が変更されます。 2 つ目$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 には隣接する操作を定義する必要があります。
計算基底状態への影響によってオラクルを定義する
これらの両方の問題に対処するには、 $m$ 量子ビットの 2 つ目のレジスタを導入して、回答を保持します。 次に、すべての$x \in \{0、1\}^n$ および $y \in \{0、1\}^m) に対して、oracle の効果を定義します$
$$\begin{\begin{align} O(\ket{x}\otimes\ket{y}) =\ket{x}\otimes\ket{y \oplus f(x)}。 \end{align} $$
$O^\dagger$を構築によって=し、以前の両方の問題を解決しました。
ヒント
$O = O^{\dagger}$ であることを確認するには、すべての $a, b \in{0, 1}$ に対して $a \oplus b \oplus b = a$ であるため、$O^2 =\mathbf{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}$ に対してオラクルをこのように定義すると、他の任意の状態に対して $O$ がどのように作用するかも定義されることです。 この動作は、 $O$は、すべての量子演算と同様に、動作する状態で直線的であるという事実に直ちに従います。 たとえば、 $H \ket{0}=\ket{+}$ と $H \ket{1}=\ket{-}$で定義されている Hadmard 操作について考えてみましょう。 $H$が$\ket{+}$にどのように作用するかを知りたい場合は、その$H$線形を使用できます。
$$\begin{align} H\ket{+ }& =\frac{1}{\sqrt{{2}} H(\ket{0} + \ket{{1}) =\frac{1}{\sqrt{{2}} (H\ket{0} + H\ket{1}) \\& =\frac{1}{\sqrt{2}} (\ket{ + } + \ket{{-}) =\frac12 (\ket{{0} + \ket{{1} + \ket{{0} - \ket{{1}) =\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} $$
ここで、 $\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}\\& =\sum_{x \in \{0,1\}^n, y \in \{0, 1\}^m}\alpha(x, y) O \ket{x}\ket{y}\\& =\sum_{x \in \{0,1\}^n, y \in \{0, 1\}^m}\alpha(x, y) \ket{x}\ket{y \oplus f(x)}. \end{align} $$
位相オラクル
または、$O$ への入力に基づいてフェーズを適用することで$$f$を oracle $O にエンコードすることもできます。 たとえば、O \ket{x}= (-1)^{f(x)}\ket{x} を$$\begin{\begin{align}するような$$O を定義できます。 \end{align} $$
位相オラクルが最初に計算基底状態 $\ket{x}$ でレジスタに作用する場合、このフェーズはグローバル フェーズであるため、監視できません。 しかし、このようなオラクルは、重ね合わせまたは制御された操作として適用される場合、強力なリソースになる可能性があります。 たとえば、1 量子ビット関数 $f$ の位相オラクル $O_f$ について考えてみましょう。 次に、 $$\begin{align} O_f \ket{ + }& = O_f (\ket{0} + \ket{{1}) / \sqrt{{2}\\& = ((-1)^{f(0)}\ket{0} + (-1)^{f(1)}\ket{1}) / \sqrt{2}\\& = (-1)^{f(0)} (\ket{{0} + (-1)^{f(1) - f(0)}\ket{{1}) / \sqrt{{2}\\& = (-1)^{f(0)} Z^{f(0) - f(1)}\ket{+}。 \end{align} $$
Note
$Z^{-1}=Z^{\dagger}=Z$ であるため、$Z^{f(0)-f(1)}=Z^{f(1)-f(0)} であることに注意してください。$
より一般的には、オラクルの両方のビューを広げて古典的な関数を表すことができます。これは、1 ビットではなく実数を返します。
Oracle を実装する最適な方法の選択は、特定のアルゴリズム内でこのオラクルを使用する方法によって大きく異なります。 たとえば、Deutsch-Jozsa アルゴリズムは、最初の方法で実装されたオラクルに依存しますが、グローバーのアルゴリズムは、2 番目の方法で実装されたオラクルに依存します。
詳細については、 Gilyén 1711.00465のディスカッションを参照してください。