Memilih bilangan iterasi

Kita telah menetapkan bahawa vektor keadaan daftar $\mathsf{Q}$ dalam algoritma Grover kekal dalam subruang dua dimensi yang dijangkau oleh $\vert A_0\rangle$ dan $\vert A_1\rangle$ setelah langkah inisialisasi dilakukan.

Matlamatnya adalah untuk mencari unsur $x\in A_1$, dan matlamat ini akan dicapai jika kita dapat memperoleh keadaan $\vert A_1\rangle$ — kerana jika kita mengukur keadaan ini, kita dijamin mendapat hasil ukuran $x\in A_1$. Memandangkan keadaan $\mathsf{Q}$ selepas $t$ iterasi dalam 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$ supaya

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

sedekat mungkin kepada $1$ dalam nilai mutlak, untuk memaksimumkan kebarangkalian memperoleh $x\in A_1$ daripada pengukuran. Untuk mana-mana sudut $\theta \in (0,2\pi)$, nilai $\sin((2t + 1)\theta)$ berosilasi apabila $t$ meningkat, walaupun ia tidak semestinya berkala — tiada jaminan kita akan mendapat nilai yang sama dua kali.

Sudah tentu, selain daripada menjadikan kebarangkalian memperoleh unsur $x\in A_1$ daripada pengukuran besar, kita juga ingin memilih $t$ sekecil mungkin, kerana $t$ penggunaan operasi $G$ memerlukan $t$ pertanyaan kepada fungsi $f$. Kerana kita bertujuan untuk menjadikan $\sin( (2t + 1) \theta)$ hampir kepada $1$ dalam nilai mutlak, cara semula jadi untuk melakukan ini adalah dengan memilih $t$ supaya

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

Menyelesaikan untuk $t$ menghasilkan

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

Sudah tentu, $t$ mesti berupa integer, jadi kita tidak semestinya dapat mencapai nilai ini dengan tepat — tetapi apa yang boleh kita lakukan adalah mengambil integer yang paling hampir dengan nilai ini, iaitu

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

Ini adalah bilangan iterasi yang disyorkan untuk algoritma Grover. Apabila kita meneruskan analisis, kita akan lihat bahawa kedekatan integer ini dengan nilai sasaran secara semula jadi mempengaruhi prestasi algoritma.

(Sebagai catatan tambahan, jika nilai sasaran $\pi/(4\theta) - 1/2$ kebetulan tepat di tengah-tengah antara dua integer, ungkapan $t$ ini adalah apa yang kita dapat dengan membundarkan ke atas. Kita boleh membundarkan ke bawah sebagai alternatif, yang masuk akal dilakukan kerana ia bermakna satu pertanyaan lebih sedikit — tetapi ini adalah perkara kedua dan tidak penting untuk tujuan pelajaran.)

Dengan mengingat bahawa nilai sudut $\theta$ diberikan oleh formula

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

kita melihat bahawa bilangan iterasi yang disyorkan $t$ bergantung kepada bilangan rentetan dalam $A_1$. Ini menimbulkan cabaran jika kita tidak tahu berapa banyak penyelesaian yang ada, seperti yang akan kita bincangkan kemudian.

Carian unik

Pertama, mari kita fokus pada situasi di mana terdapat satu rentetan tunggal $x$ sedemikian rupa sehingga $f(x)=1$. Cara lain untuk menyatakannya ialah kita sedang mempertimbangkan suatu contoh masalah carian Unik. Dalam kes ini kita ada

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

yang boleh dianggarkan secara mudah sebagai

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

apabila $N$ menjadi besar. Jika kita gantikan $\theta = 1/\sqrt{N}$ ke dalam ungkapan

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

kita memperoleh

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

Dengan mengingat bahawa $t$ bukan sahaja bilangan kali operasi $G$ dilakukan, tetapi juga bilangan pertanyaan kepada fungsi $f$ yang diperlukan oleh algoritma, kita melihat bahawa kita sedang menuju kepada algoritma yang memerlukan $O(\sqrt{N})$ pertanyaan.

Sekarang kita akan menyiasat seberapa baik pilihan $t$ yang disyorkan berfungsi. Kebarangkalian bahawa pengukuran akhir menghasilkan penyelesaian unik boleh dinyatakan secara eksplisit sebagai

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

Hujah pertama, $N,$ merujuk kepada bilangan item yang kita cari, dan hujah kedua, yang merupakan $1$ dalam kes ini, merujuk kepada bilangan penyelesaian. Sedikit kemudian kita akan menggunakan notasi yang sama secara lebih umum, di mana terdapat pelbagai penyelesaian.

Berikut adalah jadual kebarangkalian kejayaan untuk nilai $N = 2^n$ yang semakin 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 bahawa kebarangkalian ini tidak meningkat secara ketat. Khususnya, kita mempunyai anomali menarik apabila $N=4$, di mana kita mendapat penyelesaian dengan kepastian. Namun, secara umum boleh dibuktikan bahawa

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

untuk semua $N$, jadi kebarangkalian kejayaan menuju kepada $1$ dalam had apabila $N$ menjadi besar, seperti yang dicadangkan oleh nilai di atas. Ini bagus!

Tapi perhatikan, walau bagaimanapun, bahawa walaupun sempadan lemah seperti $p(N,1) \geq 1/2$ membuktikan kegunaan algoritma Grover. Untuk apa jua hasil ukuran $x$ yang kita peroleh daripada menjalankan prosedur, kita sentiasa boleh menyemak sama ada $f(x) = 1$ menggunakan satu pertanyaan kepada $f$. Dan jika kita gagal memperoleh rentetan unik $x$ yang $f(x) = 1$ dengan kebarangkalian paling banyak $1/2$ dengan menjalankan prosedur sekali, maka selepas $m$ jalan bebas prosedur kita akan gagal memperoleh rentetan unik $x$ ini dengan kebarangkalian paling banyak $2^{-m}$. Iaitu, menggunakan $O(m \sqrt{N})$ pertanyaan kepada $f$, kita akan memperoleh penyelesaian unik $x$ dengan kebarangkalian sekurang-kurangnya $1 - 2^{-m}$. Menggunakan sempadan yang lebih baik $p(N,1) \geq 1 - 1/N$ mendedahkan bahawa kebarangkalian untuk mencari $x\in A_1$ menggunakan kaedah ini sebenarnya sekurang-kurangnya $1 - N^{-m}$.

Pelbagai penyelesaian

Apabila bilangan unsur dalam $A_1$ berubah, begitu juga sudut $\theta$, yang boleh memberi kesan ketara kepada kebarangkalian kejayaan algoritma. Untuk ringkas, mari kita tulis $s = \vert A_1 \vert$ untuk menandakan bilangan penyelesaian, dan seperti sebelum ini kita akan anggap bahawa $s\geq 1$.

Sebagai contoh motivasi, mari kita bayangkan kita mempunyai $s = 4$ penyelesaian berbanding satu penyelesaian tunggal, seperti yang kita pertimbangkan di atas. Ini bermakna

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

yang kira-kira dua kali ganda sudut yang kita ada dalam kes $\vert A_1 \vert = 1$ apabila $N$ besar. Andaikan kita tidak tahu lebih baik, dan memilih nilai $t$ yang sama seperti dalam tetapan penyelesaian unik:

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

Kesannya akan menjadi bencana seperti yang ditunjukkan oleh jadual kebarangkalian berikut.

$$\begin{array}{ll} N & \text{Kebarangkalian kejayaan}\\ \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 kebarangkalian kejayaan menuju kepada $0$ apabila $N$ menuju kepada infiniti. Ini berlaku kerana kita secara efektifnya berputar dua kali lebih cepat berbanding apabila terdapat penyelesaian unik, jadi kita terlepas sasaran $\vert A_1\rangle$ dan mendarat berhampiran $-\vert A_0\rangle$.

Namun, jika sebaliknya kita menggunakan pilihan $t$ yang disyorkan, iaitu

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

untuk

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

maka prestasinya akan lebih baik. Untuk lebih tepat, menggunakan pilihan $t$ ini membawa kepada kejayaan dengan kebarangkalian 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}$$

Mengeneralisasikan apa yang dituntut sebelum ini, boleh dibuktikan bahawa

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

di mana kita menggunakan notasi yang dicadangkan sebelum ini: $p(N,s)$ menandakan kebarangkalian bahawa algoritma Grover yang dijalankan selama $t$ iterasi mendedahkan satu penyelesaian apabila terdapat $s$ penyelesaian secara keseluruhan daripada $N$ kemungkinan.

Sempadan bawah $1 - s/N$ pada kebarangkalian kejayaan ini agak pelik dalam erti kata bahawa lebih banyak penyelesaian bermakna sempadan bawah yang lebih lemah — tetapi dengan andaian bahawa $s$ jauh lebih kecil daripada $N$, kita tetap menyimpulkan bahawa kebarangkalian kejayaan agak tinggi. Seperti sebelum ini, hakikat semata-mata bahawa $p(N,s)$ agak besar menyiratkan kegunaan algoritma.

Ia juga berlaku bahawa

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

Sempadan bawah ini menerangkan kebarangkalian bahawa rentetan $x\in\Sigma^n$ yang dipilih secara rawak seragam adalah satu penyelesaian — jadi algoritma Grover selalu melakukan sekurang-kurangnya sebaik meneka secara rawak. (Sebenarnya, apabila $t=0$, algoritma Grover adalah meneka secara rawak.)

Sekarang mari kita lihat bilangan iterasi (dan seterusnya bilangan pertanyaan)

$$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]$, adalah benar bahawa $\sin^{-1}(\alpha)\geq \alpha$, dan oleh itu

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

Ini menyiratkan bahawa

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

Ini diterjemahkan kepada penjimatan dalam bilangan pertanyaan apabila $s$ bertumbuh. Khususnya, bilangan pertanyaan yang diperlukan adalah

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

Bilangan penyelesaian yang tidak diketahui

Jika bilangan penyelesaian $s = \vert A_1 \vert$ adalah tidak diketahui, maka pendekatan yang berbeza diperlukan, kerana dalam situasi ini kita tidak mempunyai pengetahuan tentang $s$ untuk memaklumkan pilihan $t$ kita. Sebenarnya, terdapat pelbagai pendekatan.

Satu pendekatan mudah adalah dengan memilih

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

secara rawak seragam. Memilih $t$ dengan cara ini sentiasa menemukan penyelesaian (dengan mengandaikan terdapat satu) dengan kebarangkalian lebih daripada 40%, walaupun ini tidak jelas dan memerlukan analisis yang tidak akan dimasukkan di sini. Namun ia masuk akal, terutamanya apabila kita memikirkan gambaran geometri: memutar keadaan $\mathsf{Q}$ beberapa kali secara rawak seperti ini tidak jauh berbeza daripada memilih vektor unit rawak dalam ruang yang dijangkau oleh $\vert A_0\rangle$ dan $\vert A_1\rangle$, yang berkemungkinan besar pekali $\vert A_1\rangle$ agak besar. Dengan mengulangi prosedur ini dan menyemak hasilnya dengan cara yang sama seperti yang dihuraikan sebelum ini, kebarangkalian untuk mencari penyelesaian boleh dijadikan sangat hampir kepada $1$.

Terdapat kaedah yang lebih halus yang menemukan penyelesaian apabila terdapat satu menggunakan $O(\sqrt{N/s})$ pertanyaan, walaupun apabila bilangan penyelesaian $s$ tidak diketahui, dan memerlukan $O(\sqrt{N})$ pertanyaan untuk menentukan bahawa tiada penyelesaian apabila $s=0$.

Idea asasnya adalah memilih $t$ secara rawak seragam daripada set $\{1,\ldots,T\}$ secara berulang, untuk nilai $T$ yang semakin meningkat. Khususnya, kita boleh mulakan dengan $T = 1$ dan meningkatkannya secara eksponen, sentiasa menamatkan proses sebaik sahaja penyelesaian ditemui dan mengehadkan $T$ supaya tidak membuang pertanyaan apabila tiada penyelesaian. Proses ini memanfaatkan hakikat bahawa lebih sedikit pertanyaan diperlukan apabila lebih banyak penyelesaian wujud. Namun diperlukan sedikit kehati-hatian untuk mengimbangi kadar pertumbuhan $T$ dengan kebarangkalian kejayaan untuk setiap iterasi. (Mengambil $T \leftarrow \lceil \frac{5}{4}T\rceil$ berfungsi, misalnya, seperti yang ditunjukkan oleh analisis. Menggandakan $T$, walau bagaimanapun, tidak — ini ternyata terlalu cepat untuk meningkat.)

Kes-kes remeh

Sepanjang analisis yang baru kita lalui, kita telah mengandaikan bahawa bilangan penyelesaian adalah bukan sifar. Memang, dengan merujuk kepada vektor-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 tersirat mengandaikan bahawa $A_0$ dan $A_1$ kedua-duanya tidak kosong. Di sini kita akan mempertimbangkan secara ringkas apa yang berlaku apabila salah satu daripada set ini kosong.

Sebelum kita sibuk dengan analisis, mari kita perhatikan yang jelas: jika setiap rentetan $x\in\Sigma^n$ adalah penyelesaian, maka kita akan melihat penyelesaian apabila kita mengukur; dan apabila tiada penyelesaian, kita tidak akan melihat satu. Dalam sesetengah hal tidak perlu pergi lebih jauh daripada ini.

Namun, kita boleh mengesahkan matematik untuk kes-kes remeh ini dengan cepat. Situasi di mana salah satu daripada $A_0$ dan $A_1$ kosong berlaku apabila $f$ adalah malar; $A_1$ kosong apabila $f(x) = 0$ untuk setiap $x\in\Sigma^n,$ dan $A_0$ kosong apabila $f(x) = 1$ untuk setiap $x\in\Sigma^n.$ Ini bermakna

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

dan oleh 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, tanpa mengira bilangan iterasi $t$ yang kita lakukan dalam kes-kes ini, pengukuran akan sentiasa mendedahkan rentetan rawak seragam $x\in\Sigma^n$.