Deskripsi algoritma Grover

Di bagian ini, kita akan mendeskripsikan algoritma Grover. Kita akan mulai dengan mendiskusikan Gate query fase dan cara membuatnya, diikuti dengan deskripsi algoritma Grover itu sendiri. Terakhir, kita akan secara singkat mendiskusikan bagaimana algoritma ini secara alami diterapkan untuk pencarian.

Gate query fase

Algoritma Grover menggunakan operasi yang dikenal sebagai Gate query fase. Berbeda dengan Gate query biasa $U_f,$ yang didefinisikan untuk fungsi $f$ tertentu dengan cara biasa yang dijelaskan sebelumnya, Gate query fase untuk fungsi $f$ didefinisikan sebagai

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

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

Operasi $Z_f$ bisa diimplementasikan menggunakan satu Gate query $U_f$ seperti yang disarankan diagram ini:

Implementasi ini memanfaatkan fenomena phase kickback, dan membutuhkan satu qubit ruang kerja, diinisialisasi ke state $\vert -\rangle$, untuk tersedia. Qubit ini tetap dalam state $\vert - \rangle$ setelah implementasi selesai, dan bisa digunakan kembali (untuk mengimplementasikan Gate $Z_f$ berikutnya, misalnya) atau sekadar dibuang.

Selain operasi $Z_f,$ kita juga akan menggunakan Gate query fase untuk fungsi OR $n$-bit, yang didefinisikan sebagai berikut untuk setiap string $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 query fase 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 memperjelas, inilah cara $Z_{\mathrm{OR}}$ beroperasi pada state basis standar; perilakunya pada state sembarang ditentukan dari ekspresi ini oleh linearitas.

Operasi $Z_{\mathrm{OR}}$ bisa diimplementasikan sebagai Circuit kuantum dengan dimulai dari Circuit Boolean untuk fungsi OR, kemudian membangun operasi $U_{\mathrm{OR}}$ (yaitu, Gate query standar untuk fungsi OR $n$-bit) menggunakan prosedur yang dijelaskan di pelajaran Quantum algorithmic foundations, dan akhirnya operasi $Z_{\mathrm{OR}}$ menggunakan fenomena phase kickback seperti yang dijelaskan di atas. Perhatikan bahwa operasi $Z_{\mathrm{OR}}$ tidak memiliki ketergantungan pada fungsi $f$ dan karenanya bisa diimplementasikan oleh Circuit kuantum yang tidak memiliki Gate query.

Deskripsi algoritma

Sekarang kita sudah memiliki dua operasi $Z_f$ dan $Z_{\mathrm{OR}},$ kita bisa mendeskripsikan algoritma Grover.

Algoritma ini mengacu pada angka $t,$ yaitu jumlah iterasi yang dilakukan (dan karenanya jumlah query ke fungsi $f$ yang diperlukan). Angka $t$ ini tidak ditentukan oleh algoritma Grover seperti yang kita deskripsikan, dan kita akan membahas nanti dalam pelajaran bagaimana cara memilihnya.

Grover's algorithm

1. Inisialisasi register $n$ qubit $\mathsf{Q}$ ke state all-zero $\vert 0^n \rangle$ lalu terapkan operasi Hadamard ke setiap qubit dari $\mathsf{Q}.$
2. Terapkan $t$ kali operasi uniter $G = H^{\otimes n} Z_{\mathrm{OR}} H^{\otimes n} Z_f$ ke register $\mathsf{Q}$
3. Ukur qubit-qubit dari $\mathsf{Q}$ berdasarkan pengukuran basis standar dan keluarkan string yang dihasilkan.

Operasi $G = H^{\otimes n} Z_{\mathrm{OR}} H^{\otimes n} Z_f$ yang diiterasi di langkah 2 akan disebut operasi Grover sepanjang sisa pelajaran ini. Berikut adalah representasi Circuit kuantum dari operasi Grover ketika $n=7\!:$

Dalam diagram ini, operasi $Z_f$ digambarkan lebih besar dari $Z_{\mathrm{OR}}$ sebagai petunjuk visual informal untuk menyarankan bahwa operasi itu kemungkinan merupakan operasi yang lebih mahal biayanya. Secara khusus, ketika kita bekerja dalam model query, $Z_f$ membutuhkan satu query sementara $Z_{\mathrm{OR}}$ tidak membutuhkan query. Jika sebaliknya kita memiliki Circuit Boolean untuk fungsi $f,$ dan kemudian mengubahnya menjadi Circuit kuantum untuk $Z_f,$ kita bisa dengan wajar mengharapkan bahwa Circuit kuantum yang dihasilkan akan lebih besar dan lebih rumit dari satu untuk $Z_{\mathrm{OR}}.$

Berikut adalah diagram Circuit kuantum untuk seluruh algoritma ketika $n=7$ dan $t=3.$ Untuk nilai $t$ yang lebih besar kita cukup menyisipkan instance tambahan dari operasi Grover tepat sebelum pengukuran.

Aplikasi untuk pencarian

Algoritma Grover bisa diterapkan pada masalah Search sebagai berikut:

• Pilih angka $t$ di langkah 2. (Ini dibahas nanti dalam pelajaran.)
• Jalankan algoritma Grover pada fungsi $f,$ menggunakan pilihan yang kita buat untuk $t,$ untuk mendapatkan string $x\in\Sigma^n.$
• Query fungsi $f$ pada string $x$ untuk melihat apakah itu solusi yang valid:
  • Jika $f(x) = 1,$ maka kita telah menemukan solusi, jadi kita bisa berhenti dan mengeluarkan $x.$
  • Jika tidak, jika $f(x) = 0,$ maka kita bisa menjalankan prosedur lagi, mungkin dengan pilihan berbeda untuk $t,$ atau kita bisa memutuskan untuk menyerah dan mengeluarkan "tidak ada solusi."

Setelah kita menganalisis bagaimana algoritma Grover bekerja, kita akan melihat bahwa dengan mengambil $t = O(\sqrt{N}),$ kita mendapatkan solusi untuk masalah pencarian kita (jika ada) dengan probabilitas tinggi.