Pencarian tak terstruktur

Ringkasan

Kita akan mulai dengan deskripsi masalah yang diselesaikan algoritma Grover. Seperti biasa, kita akan menggunakan $\Sigma = \{0,1\}$ untuk menunjukkan alfabet biner sepanjang diskusi ini.

Misalkan

$$f:\Sigma^n \rightarrow \Sigma$$

adalah fungsi dari string biner dengan panjang $n$ ke bit. Kita akan berasumsi bahwa kita bisa menghitung fungsi ini secara efisien, tapi selain itu fungsinya sembarang dan kita tidak bisa mengandalkannya memiliki struktur khusus atau implementasi tertentu yang sesuai dengan kebutuhan kita.

Yang dilakukan algoritma Grover adalah mencari string $x\in\Sigma^n$ yang memenuhi $f(x) = 1$. Kita akan menyebut string seperti ini sebagai solusi untuk masalah pencarian. Jika ada beberapa solusi, maka salah satunya dianggap sebagai output yang benar, dan jika tidak ada solusi, maka jawaban yang benar mengharuskan kita melaporkan bahwa tidak ada solusi.

Tugas ini disebut masalah pencarian tak terstruktur karena kita tidak bisa mengandalkan $f$ memiliki struktur tertentu untuk memudahkannya. Kita tidak mencari dalam daftar yang terurut, atau dalam struktur data yang dirancang khusus untuk memfasilitasi pencarian, kita pada dasarnya mencari jarum dalam tumpukan jerami.

Secara intuitif, kita mungkin membayangkan bahwa kita memiliki Circuit Boolean yang sangat rumit yang menghitung $f$, dan kita bisa dengan mudah menjalankan Circuit ini pada string input yang dipilih jika kita mau. Tapi karena Circuit-nya sangat rumit, mustahil bagi kita memahami Circuit tersebut hanya dengan memeriksanya (selain bahwa kita bisa mengevaluasinya pada string input yang dipilih).

Salah satu cara untuk melakukan tugas pencarian ini secara klasik adalah dengan mengiterasi semua string $x\in\Sigma^n$, mengevaluasi $f$ pada setiap satu untuk memeriksa apakah itu solusi atau bukan. Selanjutnya, mari kita tulis

$$N = 2^n$$

demi kepraktisan notasi. Ada $N$ string dalam $\Sigma^n$, sehingga mengiterasi semua string tersebut memerlukan $N$ evaluasi dari $f$. Dengan asumsi bahwa kita hanya bisa mengevaluasi $f$ pada input yang kita pilih, ini adalah yang terbaik yang bisa kita lakukan dengan algoritma deterministik jika kita ingin menjamin keberhasilan. Dengan algoritma probabilistik, kita mungkin berharap menghemat waktu dengan memilih string input ke $f$ secara acak, tapi kita masih memerlukan $O(N)$ evaluasi dari $f$ jika kita ingin metode ini berhasil dengan probabilitas tinggi.

Algoritma Grover menyelesaikan masalah pencarian ini dengan probabilitas tinggi hanya dengan $O(\sqrt{N})$ evaluasi dari $f$. Untuk memperjelas, evaluasi fungsi ini harus terjadi dalam superposisi, mirip dengan algoritma query yang dibahas di pelajaran Quantum query algorithms, termasuk algoritma Deutsch, algoritma Deutsch-Jozsa, dan algoritma Simon. Tidak seperti algoritma-algoritma itu, algoritma Grover mengambil pendekatan iteratif: mengevaluasi $f$ pada superposisi string input dan menyelingi evaluasi-evaluasi ini dengan operasi-operasi lain yang memiliki efek menciptakan pola interferensi, menghasilkan solusi dengan probabilitas tinggi (jika ada) setelah $O(\sqrt{N})$ iterasi.

Pernyataan masalah formal

Kita akan memformalisasi masalah yang diselesaikan algoritma Grover menggunakan model komputasi query. Yaitu, kita akan mengasumsikan bahwa kita memiliki akses ke fungsi $f:\Sigma^n\rightarrow\Sigma$ melalui Gate query yang didefinisikan dengan cara biasa:

$$U_f \bigl( \vert a\rangle \vert x\rangle \bigr) = \vert a \oplus f(x) \rangle \vert x \rangle$$

untuk setiap $x\in\Sigma^n$ dan $a\in\Sigma$. Ini adalah aksi dari $U_f$ pada state basis standar, dan aksinya secara umum ditentukan oleh linearitas.

Seperti yang dibahas di pelajaran Quantum algorithmic foundations, jika kita memiliki Circuit Boolean untuk menghitung $f$, kita bisa mengubah deskripsi Circuit Boolean tersebut menjadi Circuit kuantum yang mengimplementasikan $U_f$ (menggunakan sejumlah qubit ruang kerja yang memulai dan mengakhiri komputasi dalam state $\vert 0\rangle$). Jadi, meskipun kita menggunakan model query untuk memformalisasi masalah yang diselesaikan algoritma Grover, algoritma ini tidak terbatas pada model ini; kita bisa menjalankan algoritma Grover pada fungsi $f$ mana pun yang kita miliki Circuit Boolean-nya.

Berikut adalah pernyataan masalah secara presisi, yang diberi nama Search karena kita mencari solusi, maksudnya string $x$ yang membuat $f$ bernilai $1$.

Search

Input: sebuah fungsi $f:\Sigma^n\rightarrow\Sigma$
Output: sebuah string $x\in\Sigma^n$ yang memenuhi $f(x) = 1$, atau "tidak ada solusi" jika tidak ada string $x$ seperti itu yang ada

Perhatikan bahwa ini bukan masalah promise — fungsi $f$ adalah sembarang. Namun, akan sangat membantu untuk mempertimbangkan varian promise berikut dari masalah, di mana kita dijamin bahwa ada tepat satu solusi. Masalah ini muncul sebagai contoh masalah promise di pelajaran Quantum query algorithms.

Unique search

Input: sebuah fungsi berbentuk $f:\Sigma^n \rightarrow \Sigma$
Promise: ada tepat satu string $z\in\Sigma^n$ di mana $f(z) = 1$, dengan $f(x) = 0$ untuk semua string $x\neq z$
Output: string $z$

Perhatikan juga bahwa masalah Or yang disebutkan di pelajaran yang sama erat kaitannya dengan Search. Untuk masalah itu, tujuannya adalah sekadar menentukan ada atau tidaknya solusi, alih-alih benar-benar menemukan solusinya.