量子オラクルについて

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\ket{x}=\ket{f(x)}$するように$O$を定義することもできますが、このメソッドにはいくつかの問題があります。 第 1 に、$f$ の入力と出力のサイズは異なる可能性があります ($n \ne m$)。そのため、$O$ を適用すると、レジスタ内の量子ビットの数が変わります。 第 2 に、$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 には隣接する操作を定義する必要があります。

計算基底状態への影響によってオラクルを定義する

これらの両方の問題に対処するには、 $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{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}\\& =\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 et al. 1711.00465 のディスカッションを参照してください。

関連するコンテンツ

• グローバーのアルゴリズム
• 量子中間表現
• ベクトルと行列
• T ゲートと T ファクトリ