Memilih jumlah iterasi

Kita telah menetapkan bahwa vektor keadaan register $\mathsf{Q}$ dalam algoritma Grover tetap berada dalam subruang dua-dimensi yang dibentangkan oleh $\vert A_0\rangle$ dan $\vert A_1\rangle$ setelah langkah inisialisasi dilakukan.

Tujuannya adalah menemukan elemen $x\in A_1$, dan tujuan ini akan tercapai jika kita bisa mendapatkan keadaan $\vert A_1\rangle$ — karena jika kita mengukur keadaan ini, kita dijamin mendapatkan hasil pengukuran $x\in A_1$. Mengingat bahwa keadaan $\mathsf{Q}$ setelah $t$ iterasi pada langkah 2 adalah

$$G^t \vert u \rangle = \cos\bigl((2t + 1)\theta\bigr) \vert A_0\rangle + \sin\bigl((2t + 1)\theta\bigr) \vert A_1\rangle,$$

kita harus memilih $t$ sedemikian sehingga

$$\langle A_1 \vert G^t \vert u \rangle = \sin((2t + 1)\theta)$$

sedekat mungkin dengan $1$ dalam nilai absolut, untuk memaksimalkan probabilitas mendapatkan $x\in A_1$ dari pengukuran. Untuk sudut $\theta \in (0,2\pi)$ manapun, nilai $\sin((2t + 1)\theta)$ berosilasi seiring $t$ meningkat, meskipun tidak harus periodik — tidak ada jaminan kita akan pernah mendapatkan nilai yang sama dua kali.

Secara alami, selain membuat probabilitas mendapatkan elemen $x\in A_1$ dari pengukuran besar, kita juga ingin memilih $t$ sekecil mungkin, karena $t$ aplikasi operasi $G$ memerlukan $t$ kueri ke fungsi $f$. Karena kita ingin membuat $\sin( (2t + 1) \theta)$ mendekati $1$ dalam nilai absolut, cara alami untuk melakukannya adalah memilih $t$ sehingga

$$(2t + 1) \theta \approx \frac{\pi}{2}.$$

Memecahkan untuk $t$ menghasilkan

$$t \approx \frac{\pi}{4\theta} - \frac{1}{2}.$$

Tentu saja, $t$ harus bilangan bulat, sehingga kita tidak selalu bisa mencapai nilai ini tepat — tetapi yang bisa kita lakukan adalah mengambil bilangan bulat terdekat dengan nilai ini, yaitu

$$t = \Bigl\lfloor \frac{\pi}{4\theta} \Bigr\rfloor.$$

Ini adalah jumlah iterasi yang direkomendasikan untuk algoritma Grover. Saat kita melanjutkan analisis, kita akan melihat bahwa kedekatan bilangan bulat ini dengan nilai target secara alami mempengaruhi kinerja algoritma.

(Sebagai catatan tambahan, jika nilai target $\pi/(4\theta) - 1/2$ kebetulan tepat di tengah antara dua bilangan bulat, ekspresi $t$ ini adalah yang kita dapatkan dengan membulatkan ke atas. Kita bisa secara alternatif membulatkan ke bawah, yang masuk akal karena berarti satu kueri lebih sedikit — tetapi ini bersifat sekunder dan tidak penting untuk keperluan pelajaran.)

Mengingat bahwa nilai sudut $\theta$ diberikan oleh rumus

$$\theta = \sin^{-1}\biggl(\sqrt{\frac{\vert A_1\vert}{N}}\biggr),$$

kita melihat bahwa jumlah iterasi yang direkomendasikan $t$ bergantung pada jumlah string di $A_1$. Ini menimbulkan tantangan jika kita tidak tahu berapa banyak solusi yang kita miliki, seperti yang akan kita bahas nanti.

Pencarian unik

Pertama, mari kita fokus pada situasi di mana ada satu string $x$ sedemikian sehingga $f(x)=1$. Cara lain untuk menyatakannya adalah bahwa kita sedang mempertimbangkan contoh masalah Pencarian Unik. Dalam kasus ini kita memiliki

$$\theta = \sin^{-1}\biggl( \sqrt{\frac{1}{N}} \biggr),$$

yang dapat didekati secara nyaman sebagai

$$\theta = \sin^{-1}\biggl( \sqrt{\frac{1}{N}} \biggr) \approx \sqrt{\frac{1}{N}}$$

ketika $N$ menjadi besar. Jika kita substitusi $\theta = 1/\sqrt{N}$ ke dalam ekspresi

$$t = \Bigl\lfloor \frac{\pi}{4\theta} \Bigr\rfloor$$

kita mendapatkan

$$t = \Bigl\lfloor \frac{\pi}{4}\sqrt{N} \Bigr\rfloor.$$

Mengingat bahwa $t$ bukan hanya jumlah kali operasi $G$ dilakukan, tetapi juga jumlah kueri ke fungsi $f$ yang diperlukan oleh algoritma, kita melihat bahwa kita sedang menuju untuk mendapatkan algoritma yang memerlukan kueri $O(\sqrt{N})$.

Sekarang kita akan menyelidiki seberapa baik pilihan $t$ yang direkomendasikan bekerja. Probabilitas bahwa pengukuran akhir menghasilkan solusi unik dapat diekspresikan secara eksplisit sebagai

$$p(N,1) = \sin^2 \bigl( (2t + 1) \theta \bigr).$$

Argumen pertama, $N,$ mengacu pada jumlah item yang dicari, dan argumen kedua, yang dalam hal ini adalah $1,$ mengacu pada jumlah solusi. Sedikit kemudian kita akan menggunakan notasi yang sama secara lebih umum, di mana ada beberapa solusi.

Berikut adalah tabel probabilitas keberhasilan untuk nilai $N = 2^n$ yang meningkat.

$$\begin{array}{ll} N & p(N,1)\\ \hline 2 & 0.5000000000\\ 4 & 1.0000000000\\ 8 & 0.9453125000\\ 16 & 0.9613189697\\ 32 & 0.9991823155\\ 64 & 0.9965856808\\ 128 & 0.9956198657\\ 256 & 0.9999470421\\ 512 & 0.9994480262\\ 1024 & 0.9994612447\\ 2048 & 0.9999968478\\ 4096 & 0.9999453461\\ 8192 & 0.9999157752\\ 16384 & 0.9999997811\\ 32768 & 0.9999868295\\ 65536 & 0.9999882596 \end{array}$$

Perhatikan bahwa probabilitas ini tidak meningkat secara ketat. Khususnya, kita memiliki anomali menarik ketika $N=4$, di mana kita mendapatkan solusi dengan kepastian. Namun, dapat dibuktikan secara umum bahwa

$$p(N,1) \geq 1 - \frac{1}{N}$$

untuk semua $N$, sehingga probabilitas keberhasilan mendekati $1$ dalam batas ketika $N$ menjadi besar, seperti yang tampaknya disarankan nilai-nilai di atas. Ini bagus!

Tapi perhatikan, bagaimanapun, bahwa bahkan batas lemah seperti $p(N,1) \geq 1/2$ menetapkan kegunaan algoritma Grover. Untuk hasil pengukuran $x$ apapun yang kita peroleh dari menjalankan prosedur, kita selalu bisa memeriksa apakah $f(x) = 1$ menggunakan satu kueri ke $f$. Dan jika kita gagal mendapatkan string unik $x$ di mana $f(x) = 1$ dengan probabilitas paling banyak $1/2$ dengan menjalankan prosedur sekali, maka setelah $m$ jalankan independen dari prosedur kita akan gagal mendapatkan string unik $x$ ini dengan probabilitas paling banyak $2^{-m}$. Artinya, menggunakan kueri $O(m \sqrt{N})$ ke $f$, kita akan mendapatkan solusi unik $x$ dengan probabilitas setidaknya $1 - 2^{-m}$. Menggunakan batas yang lebih baik $p(N,1) \geq 1 - 1/N$ mengungkapkan bahwa probabilitas menemukan $x\in A_1$ menggunakan metode ini sebenarnya setidaknya $1 - N^{-m}$.

Beberapa solusi

Saat jumlah elemen di $A_1$ bervariasi, begitu pula sudut $\theta$, yang bisa memiliki efek signifikan pada probabilitas keberhasilan algoritma. Untuk singkatnya, mari kita tulis $s = \vert A_1 \vert$ untuk menyatakan jumlah solusi, dan seperti sebelumnya kita akan asumsikan bahwa $s\geq 1$.

Sebagai contoh motivasi, bayangkan kita memiliki $s = 4$ solusi daripada solusi tunggal, seperti yang kita pertimbangkan di atas. Ini berarti bahwa

$$\theta = \sin^{-1}\biggl( \sqrt{\frac{4}{N}} \biggr),$$

yang kira-kira dua kali lipat sudut yang kita miliki dalam kasus $\vert A_1 \vert = 1$ ketika $N$ besar. Misalkan kita tidak tahu lebih baik, dan memilih nilai $t$ yang sama seperti dalam pengaturan solusi unik:

$$t = \Biggl\lfloor \frac{\pi}{4\sin^{-1}\bigl(1/\sqrt{N}\bigr)}\Biggr\rfloor.$$

Efeknya akan bencana seperti yang diungkapkan tabel probabilitas berikut.

$$\begin{array}{ll} N & \text{Probabilitas keberhasilan}\\ \hline 4 & 1.0000000000\\ 8 & 0.5000000000\\ 16 & 0.2500000000\\ 32 & 0.0122070313\\ 64 & 0.0203807689\\ 128 & 0.0144530758\\ 256 & 0.0000705058\\ 512 & 0.0019310741\\ 1024 & 0.0023009083\\ 2048 & 0.0000077506\\ 4096 & 0.0002301502\\ 8192 & 0.0003439882\\ 16384 & 0.0000007053\\ 32768 & 0.0000533810\\ 65536 & 0.0000472907 \end{array}$$

Kali ini probabilitas keberhasilan mendekati $0$ saat $N$ mendekati tak hingga. Ini terjadi karena kita secara efektif berputar dua kali lebih cepat dari yang kita lakukan saat ada solusi unik, sehingga kita melewati target $\vert A_1\rangle$ dan mendarat di dekat $-\vert A_0\rangle$.

Namun, jika sebaliknya kita menggunakan pilihan $t$ yang direkomendasikan, yaitu

$$t = \Bigl\lfloor \frac{\pi}{4\theta}\Bigr\rfloor$$

untuk

$$\theta = \sin^{-1}\biggl( \sqrt{\frac{s}{N}} \biggr),$$

maka kinerjanya akan lebih baik. Lebih tepatnya, menggunakan pilihan $t$ ini mengarah pada keberhasilan dengan probabilitas tinggi.

$$\begin{array}{ll} N & p(N,4)\\ \hline 4 & 1.0000000000\\ 8 & 0.5000000000\\ 16 & 1.0000000000\\ 32 & 0.9453125000\\ 64 & 0.9613189697\\ 128 & 0.9991823155\\ 256 & 0.9965856808\\ 512 & 0.9956198657\\ 1024 & 0.9999470421\\ 2048 & 0.9994480262\\ 4096 & 0.9994612447\\ 8192 & 0.9999968478\\ 16384 & 0.9999453461\\ 32768 & 0.9999157752\\ 65536 & 0.9999997811 \end{array}$$

Menggeneralisasi apa yang diklaim sebelumnya, dapat dibuktikan bahwa

$$p(N,s) \geq 1 - \frac{s}{N},$$

di mana kita menggunakan notasi yang disarankan sebelumnya: $p(N,s)$ menyatakan probabilitas bahwa algoritma Grover yang dijalankan untuk $t$ iterasi mengungkapkan solusi ketika ada $s$ solusi dari $N$ kemungkinan secara total.

Batas bawah $1 - s/N$ pada probabilitas keberhasilan ini sedikit aneh karena lebih banyak solusi berarti batas bawah yang lebih buruk — tetapi dengan asumsi bahwa $s$ jauh lebih kecil dari $N$, kita tetap menyimpulkan bahwa probabilitas keberhasilan cukup tinggi. Seperti sebelumnya, fakta sederhana bahwa $p(N,s)$ cukup besar menyiratkan kegunaan algoritma.

Kebetulan juga berlaku bahwa

$$p(N,s) \geq \frac{s}{N}.$$

Batas bawah ini mendeskripsikan probabilitas bahwa string $x\in\Sigma^n$ yang dipilih secara seragam acak adalah solusi — jadi algoritma Grover selalu setidaknya sebaik tebakan acak. (Faktanya, ketika $t=0$, algoritma Grover adalah tebakan acak.)

Sekarang mari kita lihat jumlah iterasi (dan karenanya jumlah kueri)

$$t = \Bigl\lfloor \frac{\pi}{4\theta}\Bigr\rfloor,$$

untuk

$$\theta = \sin^{-1}\biggl(\sqrt{\frac{s}{N}}\biggr).$$

Untuk setiap $\alpha \in [0,1]$, berlaku bahwa $\sin^{-1}(\alpha)\geq \alpha$, sehingga

$$\theta = \sin^{-1}\left(\sqrt{\frac{s}{N}}\right) \geq \sqrt{\frac{s}{N}}.$$

Ini berarti bahwa

$$t \leq \frac{\pi}{4\theta} \leq \frac{\pi}{4}\sqrt{\frac{N}{s}}.$$

Ini diterjemahkan menjadi penghematan dalam jumlah kueri seiring $s$ meningkat. Khususnya, jumlah kueri yang diperlukan adalah

$$O\biggl(\sqrt{\frac{N}{s}}\biggr).$$

Jumlah solusi yang tidak diketahui

Jika jumlah solusi $s = \vert A_1 \vert$ tidak diketahui, maka diperlukan pendekatan yang berbeda, karena dalam situasi ini kita tidak memiliki pengetahuan tentang $s$ untuk menginformasikan pilihan $t$ kita. Sebenarnya ada beberapa pendekatan.

Satu pendekatan sederhana adalah memilih

$$t \in \Bigl\{ 1,\ldots,\bigl\lfloor\pi\sqrt{N}/4\bigr\rfloor \Bigr\}$$

secara seragam acak. Memilih $t$ dengan cara ini selalu menemukan solusi (dengan asumsi ada) dengan probabilitas lebih dari 40%, meskipun ini tidak jelas dan memerlukan analisis yang tidak akan disertakan di sini. Namun masuk akal, terutama ketika kita memikirkan gambaran geometris: merotasi keadaan $\mathsf{Q}$ sejumlah acak kali seperti ini tidak jauh berbeda dari memilih vektor satuan acak dalam ruang yang dibentangkan oleh $\vert A_0\rangle$ dan $\vert A_1\rangle$, yang kemungkinan besar koefisien $\vert A_1\rangle$ cukup besar. Dengan mengulangi prosedur ini dan memeriksa hasilnya dengan cara yang sama seperti yang dijelaskan sebelumnya, probabilitas menemukan solusi dapat dibuat sangat dekat dengan $1$.

Ada metode yang lebih baik yang menemukan solusi ketika ada satu menggunakan kueri $O(\sqrt{N/s})$, bahkan ketika jumlah solusi $s$ tidak diketahui, dan memerlukan kueri $O(\sqrt{N})$ untuk menentukan bahwa tidak ada solusi ketika $s=0$.

Ide dasarnya adalah memilih $t$ secara seragam acak dari himpunan $\{1,\ldots,T\}$ secara iteratif, untuk nilai $T$ yang meningkat. Khususnya, kita bisa mulai dengan $T = 1$ dan meningkatkannya secara eksponensial, selalu menghentikan proses segera setelah solusi ditemukan dan membatasi $T$ agar tidak membuang kueri ketika tidak ada solusi. Prosesnya memanfaatkan fakta bahwa lebih sedikit kueri diperlukan ketika lebih banyak solusi ada. Namun diperlukan kehati-hatian, untuk menyeimbangkan laju pertumbuhan $T$ dengan probabilitas keberhasilan setiap iterasi. (Mengambil $T \leftarrow \lceil \frac{5}{4}T\rceil$ misalnya, bekerja, seperti yang diungkapkan analisis. Menggandakan $T$, bagaimanapun, tidak — ini ternyata terlalu cepat peningkatannya.)

Kasus trivial

Sepanjang analisis yang baru saja kita lakukan, kita telah mengasumsikan bahwa jumlah solusi bukan nol. Memang, dengan mengacu pada vektor

$$\begin{aligned} \vert A_0\rangle &= \frac{1}{\sqrt{\vert A_0\vert}} \sum_{x\in A_0} \vert x\rangle \\ \vert A_1\rangle &= \frac{1}{\sqrt{\vert A_1\vert}} \sum_{x\in A_1} \vert x\rangle \end{aligned}$$

kita secara implisit telah mengasumsikan bahwa $A_0$ dan $A_1$ keduanya tidak kosong. Di sini kita akan secara singkat mempertimbangkan apa yang terjadi ketika salah satu dari himpunan ini kosong.

Sebelum kita repot-repot menganalisis, mari kita amati hal yang jelas: jika setiap string $x\in\Sigma^n$ adalah solusi, maka kita akan melihat solusi ketika kita mengukur; dan ketika tidak ada solusi, kita tidak akan melihat satu pun. Dalam arti tertentu tidak perlu lebih jauh dari ini.

Namun, kita bisa dengan cepat memverifikasi matematika untuk kasus-kasus trivial ini. Situasi di mana salah satu dari $A_0$ dan $A_1$ kosong terjadi ketika $f$ konstan; $A_1$ kosong ketika $f(x) = 0$ untuk setiap $x\in\Sigma^n,$ dan $A_0$ kosong ketika $f(x) = 1$ untuk setiap $x\in\Sigma^n.$ Ini berarti bahwa

$$Z_f \vert u\rangle = \pm \vert u\rangle,$$

dan oleh karena itu

$$\begin{aligned} G \vert u \rangle & = \bigl( 2 \vert u\rangle \langle u \vert - \mathbb{I}\bigr) Z_f\vert u\rangle \\ & = \pm \bigl( 2 \vert u\rangle \langle u \vert - \mathbb{I}\bigr) \vert u\rangle \\ & = \pm \vert u\rangle. \end{aligned}$$

Jadi, terlepas dari jumlah iterasi $t$ yang kita lakukan dalam kasus-kasus ini, pengukuran akan selalu mengungkapkan string acak seragam $x\in\Sigma^n$.