Catatan
Akses ke halaman ini memerlukan otorisasi. Anda dapat mencoba masuk atau mengubah direktori.
Akses ke halaman ini memerlukan otorisasi. Anda dapat mencoba mengubah direktori.
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}}\otimes\ket{x_{1}}\otimes\cdots\otimes\ket{x_{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 orakel harus memiliki adjoint yang sudah didefinisikan.
Tentukan oracle berdasarkan efeknya pada keadaan dasar komputasional
Anda dapat menangani kedua masalah ini dengan memperkenalkan register kedua $m qubits$ untuk menyimpan jawabannya.
Kemudian, tentukan efek dari oracle pada semua keadaan basis komputasional: untuk semua
$$ \begin{ \begin{align} O(\ket{x}\otimes\ket{y}) =\ket{x}\otimes\ket{y \oplus f(x)}. \end{align} $$
Sekarang $O = O^\dagger$ secara konstruksi dan Anda sudah menyelesaikan kedua masalah sebelumnya.
Petunjuk
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, adalah linier dalam keadaan yang diterapkannya. 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}) =\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} $$
Saat menentukan oracle $O$, Anda juga dapat menggunakan fakta bahwa keadaan $\ket{\psi}$ apa pun pada $n + m$ qubit dapat ditulis sebagai
$$ \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} $$
Di sini, : \$\alpha0, 1\{^n } \\times0, 1\{^m }\toC\mathbb{ mewakili koefisien status }$. $\ket{\psi}$ 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}\\& =\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} $$
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 yang awalnya berada dalam keadaan basis komputasi $\ket{x}$, maka fase ini adalah fase global dan karenanya tidak dapat diamati. Oracle semacam itu dapat menjadi sumber daya yang kuat jika diterapkan pada superposisi atau sebagai operasi terkontrol. Misalnya, pertimbangkan suatu oracle fase $O_f$ untuk fungsi qubit tunggal $f$. Kemudian, $$\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} $$
Catatan
Perhatikan bahwa $Z^{-1}=Z^{\dagger}=Z$ dan oleh karena itu $Z^{f(0)-f(1)}=Z^{f(1)-f(0)}.$
Secara lebih umum, kedua pandangan tentang 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.