Bagaimana cara oracle dalam algoritma pencarian Grover diimplementasikan?

Algoritma pencarian Grover menyediakan kecepatan kuadratik yang dapat dibuktikan untuk pencarian basis data yang tidak disortir. Algoritma biasanya diekspresikan oleh rangkaian kuantum berikut:

Dalam sebagian besar representasi, bagian penting dari protokol adalah "gerbang oracle" $U_\omega$ , yang "ajaib" melakukan operasi $|x\rangle\mapsto(-1)^{f(x)}|x\rangle$ . Namun seringkali dibiarkan tanpa disadari betapa sulitnya mewujudkan gerbang seperti itu sebenarnya. Memang, bisa jadi penggunaan "oracle" seperti ini hanyalah cara untuk menyapu kesulitan di bawah karpet.

Bagaimana kita tahu apakah operasi oracle seperti itu memang bisa diwujudkan? Dan jika demikian, apa kompleksitasnya (misalnya dalam hal kompleksitas dekomposisi gerbang)?

Fungsi $f$ hanyalah fungsi boolean sembarang dari string bit: $f\colon \{0,1\}^n \to \{0,1\}$ . Untuk aplikasi untuk memecahkan kriptografi, seperti [1] , [2] , atau [3] , ini sebenarnya bukan 'pencarian basis data', yang mengharuskan penyimpanan seluruh basis data sebagai rangkaian kuantum, melainkan fungsi seperti

$$\begin{equation*} x \mapsto \begin{cases} 1, & \text{if $\operatorname{SHA-256}(x) = y$;} \\ 0, & \text{otherwise,} \end{cases} \end{equation*}$$

untuk fixed $y$ , yang tidak memiliki struktur kita dapat mengeksploitasi untuk pencarian klasik, tidak seperti, katakanlah, fungsi

$$\begin{equation*} x \mapsto \begin{cases} 1, & \text{if $2^x \equiv y \pmod{2^{2048} - 1942289}$}, \\ 0, & \text{otherwise}, \end{cases} \end{equation*}$$

yang memiliki struktur yang dapat dieksploitasi untuk membalikkannya lebih cepat bahkan pada komputer klasik.

Pertanyaan tentang biaya tertentu tidak dapat dijawab secara umum karena $f$ dapat berupa sirkuit apa pun — itu hanya masalah membuat sirkuit kuantum dari sirkuit klasik . Tetapi biasanya, seperti pada contoh di atas, fungsi $f$ sangat murah untuk dievaluasi pada komputer klasik, sehingga seharusnya tidak menimbulkan beban yang sangat berat pada komputer kuantum yang segala sesuatu tentang algoritma Grover sesuai anggaran Anda.

Satu-satunya biaya umum di atas $f$ adalah gerbang BUKAN bersyarat ekstra

$$C\colon \left|a\right> \left|b\right> \to \left|a\right> \left|a \oplus b\right>$$ mana $\oplus$ adalah xor, dan qubit ekstra tambahan untuk itu. Khususnya, jika kita memiliki sirkuit $$F\colon \left|x\right> \left|a\right> \lvert\text{junk}\rangle \mapsto \left|x\right> \left|a \oplus f(x)\right> \lvert\text{junk}'\rangle$$ dibangun dari $C$ dan sirkuit untuk $f$ , maka jika kita menerapkannya ke $\left|x\right>$ bersama-sama dengan qubit tambahan awalnya di negara bagian $\left|-\right> = H\left|1\right> = (1/\sqrt{2})(\left|0\right> - \left|1\right>)$di mana$H$adalah gerbang Hadamard, maka kita mendapatkan

$$\begin{align*} F\left|x\right> \left|-\right> \lvert\text{junk}\rangle &= \frac{1}{\sqrt{2}}\bigl( F\left|x\right> \left|0\right> \lvert\text{junk}\rangle - F\left|x\right> \left|1\right> \lvert\text{junk}\rangle \bigr) \\ &= \frac{1}{\sqrt{2}}\bigl( \left|x\right> \left|f(x)\right> \lvert\text{junk}'\rangle - \left|x\right> \left|1 \oplus f(x)\right> \lvert\text{junk}'\rangle \bigr). \end{align*}$$

Jika $f(x) = 0$ maka $1 \oplus f(x) = 1$ , maka dengan menyederhanakan kita memperoleh

$$F\left|x\right> \left|-\right> \lvert\text{junk}\rangle = \left|x\right> \left|-\right> \lvert\text{junk}'\rangle,$$ sedangkan jika $f(x) = 1$ maka $1 \oplus f(x) = 0$ , maka $$F\left|x\right> \left|-\right> \lvert\text{junk}\rangle = -\left|x\right> \left|-\right> \lvert\text{junk}'\rangle,$$ dan dengan demikian secara umum $$F\left|x\right> \left|-\right> \lvert\text{junk}\rangle = (-1)^{f(x)} \left|x\right> \left|-\right> \lvert\text{junk}'\rangle.$$

Nah, makalah asli Grover, "mekanika kuantum membantu dalam mencari jarum di tumpukan jerami" dengan jelas menyatakan, ia mengasumsikan bahwa C (S) dapat dievaluasi dalam waktu yang konstan. Pencarian Grover tidak peduli tentang implementabilitas, tetapi pengurangan polinomial dalam apa yang disebut kompleksitas kueri (berapa kali Anda berkonsultasi dengan oracle, seperti database klasik)

Bahkan, konsep oracle dalam komputasi diusulkan oleh Alan Turing untuk menggambarkan konstruksi yang deskripsi tentang UTM mungkin tidak dapat diwujudkan (Wikipedia). Hal ini dalam arti magis.

Tapi tentu saja, kembali ke pertanyaan Anda, bagaimana kita kemudian benar-benar membuat sirkuit untuk algoritma pencarian Grover (atau oracle)? Apakah kita perlu mengetahui jawabannya terlebih dahulu untuk mencari hasilnya? Nah, dalam beberapa hal Anda perlu. Itulah tepatnya perbaikan pintar pada pencarian Grover mencoba untuk bekerja, sehingga, kita tidak perlu tahu jawaban yang tepat di muka, tetapi beberapa sifat itu. Biarkan saya ilustrasikan dengan sebuah contoh.

Untuk masalah pengenalan pola menggunakan pencarian Grover, jika saya memiliki 4 pola pada 2 qubit (00, 01, 10, 11) dan saya ingin menandai dan memperkuat 11, diagonal unitary oracle saya harus seperti (1,1,1 , -1) untuk menjaga pergeseran fase pi untuk solusi. Jadi, untuk implementasi sederhana ini, untuk membangun kesatuan, Anda perlu mengetahui jawaban lengkapnya terlebih dahulu.

Perbaikan yang cerdas dari penyelesaian pola jika diberikan dalam makalah "Pencocokan pola kuantum" oleh Mateas dan Omar. Intinya, itu membangun oracle tetap sebanyak ada huruf di set. Jadi untuk string biner kita, akan ada oracle yang menandai semua 1s, dan lainnya yang menandai semua 0s. Kata-kata itu dipanggil secara kondisional berdasarkan apa yang ingin saya cari. Jika saya ingin mencari 11, saya memanggil oracle 1 di LSqubit, dan oracle 1 lagi di MSqubit. Dengan oracle pertama, saya akan memperkuat negara (01, 11), yaitu negara dengan LSQ sebagai 1, dan dalam panggilan ke-2, itu akan menguatkan (10, 11). Jadi seperti yang Anda lihat, 11 adalah satu-satunya negara yang mendapatkan dua kali diperkuat, yang berakhir dengan probabilitas pengukuran yang lebih tinggi. Meskipun sirkuit kuantum yang dikompilasi akan berubah berdasarkan apa pola pencarian input saya, deskripsi tingkat tinggi dari algoritma kuantum tetap sama. Anda dapat menganggap nubuat sebagai pemanggilan fungsi berdasarkan sakelar alfabet yang digunakan untuk setiap karakter dalam string pencarian.