Penerangan algoritma Grover

Dalam bahagian ini, kita akan menerangkan algoritma Grover. Kita akan mulakan dengan membincangkan gate pertanyaan fasa dan cara membinanya, diikuti dengan penerangan algoritma Grover itu sendiri. Akhirnya, kita akan membincangkan secara ringkas bagaimana algoritma ini secara semulajadi digunakan untuk pencarian.

Gate pertanyaan fasa

Algoritma Grover menggunakan operasi yang dikenali sebagai gate pertanyaan fasa. Berbeza dengan gate pertanyaan biasa $U_f$, yang ditakrifkan untuk fungsi $f$ yang diberikan dengan cara biasa yang telah diterangkan sebelum ini, gate pertanyaan fasa untuk fungsi $f$ ditakrifkan sebagai

$$Z_f \vert x\rangle = (-1)^{f(x)} \vert x\rangle$$

untuk setiap rentetan $x\in\Sigma^n$.

Operasi $Z_f$ boleh dilaksanakan menggunakan satu gate pertanyaan $U_f$ seperti yang dicadangkan oleh rajah ini:

Pelaksanaan ini menggunakan fenomena tendangan fasa, dan memerlukan satu qubit ruang kerja tambahan yang diinisialisasi kepada keadaan $\vert -\rangle$. Qubit ini kekal dalam keadaan $\vert - \rangle$ selepas pelaksanaan selesai, dan boleh digunakan semula (untuk melaksanakan gate $Z_f$ berikutnya, misalnya) atau hanya dibuang.

Selain operasi $Z_f$, kita juga akan menggunakan gate pertanyaan fasa untuk fungsi OR $n$-bit, yang ditakrifkan seperti berikut untuk setiap rentetan $x\in\Sigma^n$.

$$\mathrm{OR}(x) = \begin{cases} 0 & x = 0^n\\[0.5mm] 1 & x \neq 0^n \end{cases}$$

Secara eksplisit, gate pertanyaan fasa untuk fungsi OR $n$-bit beroperasi seperti ini:

$$Z_{\mathrm{OR}} \vert x\rangle = \begin{cases} \vert x\rangle & x = 0^n \\[0.5mm] - \vert x\rangle & x \neq 0^n. \end{cases}$$

Untuk jelaskan, inilah cara $Z_{\mathrm{OR}}$ beroperasi pada keadaan asas standard; tingkah lakunya pada sebarang keadaan ditentukan daripada ungkapan ini melalui kelinearan.

Operasi $Z_{\mathrm{OR}}$ boleh dilaksanakan sebagai litar kuantum dengan memulakan dengan litar Boolean untuk fungsi OR, kemudian membina operasi $U_{\mathrm{OR}}$ (iaitu gate pertanyaan standard untuk fungsi OR $n$-bit) menggunakan prosedur yang diterangkan dalam pelajaran Asas algoritmik kuantum, dan akhirnya operasi $Z_{\mathrm{OR}}$ menggunakan fenomena tendangan fasa seperti yang diterangkan di atas. Perhatikan bahawa operasi $Z_{\mathrm{OR}}$ tidak bergantung pada fungsi $f$ dan oleh itu boleh dilaksanakan oleh litar kuantum tanpa gate pertanyaan.

Penerangan algoritma

Sekarang kita sudah mempunyai kedua-dua operasi $Z_f$ dan $Z_{\mathrm{OR}}$, kita boleh menerangkan algoritma Grover.

Algoritma ini merujuk kepada nombor $t$, iaitu bilangan lelaran yang dilakukan (dan oleh itu bilangan pertanyaan kepada fungsi $f$ yang diperlukan). Nombor $t$ ini tidak ditetapkan oleh algoritma Grover seperti yang kita terangkan di sini, dan kita akan membincangkan kemudian dalam pelajaran ini bagaimana ia boleh dipilih.

Algoritma Grover

1. Inisialisasi daftar $n$ qubit $\mathsf{Q}$ kepada keadaan semua-sifar $\vert 0^n \rangle$ kemudian gunakan operasi Hadamard pada setiap qubit dalam $\mathsf{Q}$.
2. Gunakan $t$ kali operasi uniter $G = H^{\otimes n} Z_{\mathrm{OR}} H^{\otimes n} Z_f$ pada daftar $\mathsf{Q}$
3. Ukur qubit dalam $\mathsf{Q}$ berkenaan dengan pengukuran asas standard dan keluarkan rentetan yang terhasil.

Operasi $G = H^{\otimes n} Z_{\mathrm{OR}} H^{\otimes n} Z_f$ yang diulang dalam langkah 2 akan dipanggil operasi Grover sepanjang baki pelajaran ini. Berikut ialah representasi litar kuantum bagi operasi Grover apabila $n=7\!:$

Dalam rajah ini, operasi $Z_f$ digambarkan lebih besar daripada $Z_{\mathrm{OR}}$ sebagai petunjuk visual tidak formal untuk mencadangkan bahawa ia kemungkinan besar merupakan operasi yang lebih mahal. Khususnya, apabila kita bekerja dalam model pertanyaan, $Z_f$ memerlukan satu pertanyaan manakala $Z_{\mathrm{OR}}$ tidak memerlukan sebarang pertanyaan. Sebaliknya, jika kita mempunyai litar Boolean untuk fungsi $f,$ dan kemudian menukarnya kepada litar kuantum untuk $Z_f,$ kita boleh menjangka bahawa litar kuantum yang terhasil akan lebih besar dan lebih rumit berbanding litar untuk $Z_{\mathrm{OR}}.$

Berikut ialah rajah litar kuantum untuk keseluruhan algoritma apabila $n=7$ dan $t=3$. Untuk nilai $t$ yang lebih besar, kita hanya perlu memasukkan salinan tambahan operasi Grover tepat sebelum pengukuran.

Aplikasi untuk pencarian

Algoritma Grover boleh digunakan untuk masalah Carian seperti berikut:

• Pilih nombor $t$ dalam langkah 2. (Ini dibincangkan kemudian dalam pelajaran.)

• Jalankan algoritma Grover pada fungsi $f$, menggunakan pilihan yang kita buat untuk $t$, untuk mendapatkan rentetan $x\in\Sigma^n$.

• Tanya fungsi $f$ pada rentetan $x$ untuk melihat sama ada ia adalah penyelesaian yang sah:

  • Jika $f(x) = 1$, maka kita telah menemui penyelesaian, jadi kita boleh berhenti dan mengeluarkan $x$.

  • Jika tidak, jika $f(x) = 0$, maka kita boleh sama ada menjalankan prosedur sekali lagi, mungkin dengan pilihan yang berbeza untuk $t$, atau kita boleh memutuskan untuk berhenti dan mengeluarkan "tiada penyelesaian."

Setelah kita menganalisis cara algoritma Grover berfungsi, kita akan lihat bahawa dengan mengambil $t = O(\sqrt{N})$, kita mendapat penyelesaian kepada masalah pencarian kita (jika ada) dengan kebarangkalian yang tinggi.