Memahami oracles kuantum
Oracle, $O$, adalah operasi yang tidak terekspos yang digunakan sebagai input ke algoritma lain. Seringkali, operasi tersebut didefinisikan menggunakan fungsi $klasik f: \{0, 1\}^n \to \{0, 1\}^m$, yang mengambil $input biner n-bit$ dan menghasilkan $output biner m-bit$. Untuk melakukannya, pertimbangkan input biner tertentu $x = (x_{0}, x_{1}, \dots, x_{n-1})$. Anda dapat memberi label status qubit sebagai $\ket{\vec{x=\ket{}}x_{0}}\ket{{\otimesx_\otimes{1}}\otimes\ket{\cdotsx_{n-1.}}$
Anda mungkin terlebih dahulu mencoba menentukan $O$ sehingga $O\ket{x\ket{}=f(x)}$, tetapi metode ini memiliki beberapa masalah. Pertama, $f$ mungkin memiliki ukuran input dan output yang berbeda ($n \ne m$), sehingga menerapkan $O$ akan mengubah jumlah qubit dalam register. Kedua, bahkan jika $n = m$, fungsi mungkin tidak dapat dibalik: jika $f(x) = f(y)$ untuk beberapa $x \ne y$, maka $O\ket{x=} O\ket{y}$ tetapi $O^\dagger O\ket{x}\ne O^\dagger O\ket{y}$. Ini berarti Anda tidak dapat membuat operasi $adjoint O^\dagger$, dan oracles harus memiliki adjoint yang ditentukan untuk mereka.
Tentukan oracle berdasarkan efeknya pada status dasar komputasional
Anda dapat menangani kedua masalah ini dengan memperkenalkan register $kedua m qubits$ untuk memegang jawabannya. Kemudian, tentukan efek oracle pada semua status dasar komputasi: untuk semua x \0, 1\}^n$ dan $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} $$
Sekarang $O O = ^\dagger$ dengan konstruksi dan Anda menyelesaikan kedua masalah sebelumnya.
Tip
Untuk melihat $O = O^{\dagger}$, perhatikan bahwa $O^2 =\mathbf{1}$ karena $a \oplus b \oplus b = a$ untuk semua $a, b \in{0, 1}$. Akibatnya, $O \ket{x}\ket{y \oplus f(x)}=\ket{x}\ket{y \oplus f(x) \oplus f(x)}=\ket{x}\ket{y}$.
Yang penting, penentuan oracle dengan cara ini untuk tiap status dasar komputasional $\ket{x}\ket{y}$ juga mendefinisikan bagaimana $O$ bertindak untuk status lain. Perilaku ini mengikuti segera dari fakta bahwa $O$, seperti semua operasi kuantum, linier dalam keadaan yang ditindaklanjutinya. Pertimbangkan operasi Hadamard, misalnya, yang didefinisikan $H \ket{0}=\ket{+}$ dan $H \ket{1}=\ket{-}$. Jika Anda ingin tahu bagaimana $H$ bertindak pada $\ket{+}$, Anda dapat menggunakan $H$ itu linier,
$$\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{- ) . =\ket{{1}\ket{{0} \end{align} $$
Saat menentukan oracle $O$, Anda juga dapat menggunakan bahwa status $\ket{\psi}$ apa pun pada $n + m$ qubit dapat ditulis sebagai
$$\begin{\begin{align}\ket{\psi}&Amp; =\sum_{x \in \{0, 1\}^n, y \in \{0, 1\}^m}\alpha(x, y) \ket{x}\ket{y}. \end{align} $$
Di sini, : \{0, 1\}^n \times \{0, 1\}^m \to\mathbb{C}$ mewakili koefisien status $\ket{\psi}$. $\alpha Dengan demikian,
$$\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 fase
Atau, Anda dapat mengodekan $f$ ke oracle $O$ dengan menerapkan fase berdasarkan input ke $O$. Misalnya, Anda dapat mendefinisikan $O$ sehingga\begin{$$\begin{align} O \ket{x=} (-1)^{f(x)}\ket{x.} \end{align} $$
Jika oracle fase bertindak pada register awalnya dalam status $\ket{dasar komputasi x}$, maka fase ini adalah fase global dan karenanya tidak dapat diamati. Tetapi oracle semacam itu dapat menjadi sumber daya yang kuat jika diterapkan pada superposisi atau sebagai operasi yang dikontrol. Misalnya, pertimbangkan oracle fase $O_f$ untuk fungsi qubit tunggal $f$. Kemudian, $$\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)} Z^{f(0) - f(1)}\ket{+.} \end{align} $$
Catatan
Perhatikan bahwa $Z^{-1}=Z^{\dagger}=Z$ dan oleh karena itu $Z^{f(0)-f(1)}=Z^{f(1)-f(0)}.$
Lebih umumnya, kedua tampilan oracle dapat diperluas untuk mewakili fungsi klasik, yang mengembalikan angka riil alih-alih hanya satu bit.
Memilih cara terbaik untuk mengimplementasikan oracle sangat tergantung pada bagaimana oracle ini digunakan dalam algoritma tertentu. Misalnya, algoritma Deutsch-Jozsa bergantung pada oracle yang diimplementasikan dengan cara pertama, sementara algoritma Grover bergantung pada oracle yang diimplementasikan dengan cara kedua.
Untuk informasi selengkapnya, lihat diskusi di Gilyén 1711.00465.