Analisis

Sekarang kita akan menganalisis algoritma Grover untuk memahami cara ia berfungsi. Kita akan mulakan dengan apa yang boleh dihuraikan sebagai analisis simbolik, di mana kita mengira bagaimana operasi Grover $G$ bertindak ke atas keadaan-keadaan tertentu, kemudian kita akan menghubungkan analisis simbolik ini dengan gambaran geometri yang berguna untuk menvisualisasikan cara algoritma berfungsi.

Penyelesaian dan bukan penyelesaian

Mari kita mulakan dengan mentakrifkan dua set rentetan.

$$\begin{aligned} A_0 &= \bigl\{ x\in\Sigma^n : f(x) = 0\bigr\} \\ A_1 &= \bigl\{ x\in\Sigma^n : f(x) = 1\bigr\} \end{aligned}$$

Set $A_1$ mengandungi semua penyelesaian kepada masalah carian kita, manakala $A_0$ mengandungi rentetan yang bukan penyelesaian (yang boleh kita rujuk sebagai bukan penyelesaian apabila sesuai). Kedua-dua set ini memenuhi $A_0 \cap A_1 = \varnothing$ dan $A_0 \cup A_1 = \Sigma^n,$ yang bermakna ini adalah sebuah bipartisi daripada $\Sigma^n.$

Seterusnya kita akan takrifkan dua vektor unit yang mewakili superposisi seragam ke atas set penyelesaian dan bukan penyelesaian.

$$\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}$$

Secara formal, setiap vektor ini hanya ditakrifkan apabila set yang bersamaannya tidak kosong, tetapi mulai sekarang kita akan fokus pada kes di mana $A_0$ mahupun $A_1$ tidak kosong. Kes $A_0 = \varnothing$ dan $A_1 = \varnothing$ mudah dikendalikan secara berasingan, dan kita akan lakukan itu kemudian.

Sebagai catatan tambahan, notasi yang digunakan di sini adalah lazim: setiap kali kita ada set $S$ yang terhingga dan tidak kosong, kita boleh tulis $\vert S\rangle$ untuk merujuk kepada vektor keadaan kuantum yang seragam ke atas unsur-unsur $S.$

Mari kita juga takrifkan $\vert u \rangle$ sebagai keadaan kuantum seragam ke atas semua rentetan $n$-bit:

$$\vert u\rangle = \frac{1}{\sqrt{N}} \sum_{x\in\Sigma^n} \vert x\rangle.$$

Perhatikan bahawa

$$\vert u\rangle = \sqrt{\frac{\vert A_0 \vert}{N}} \vert A_0\rangle + \sqrt{\frac{\vert A_1 \vert}{N}} \vert A_1\rangle.$$

Kita juga ada $\vert u\rangle = H^{\otimes n} \vert 0^n \rangle,$ jadi $\vert u\rangle$ mewakili keadaan daftar $\mathsf{Q}$ selepas inisialisasi dalam langkah 1 algoritma Grover.

Ini bermakna tepat sebelum iterasi $G$ berlaku dalam langkah 2, keadaan $\mathsf{Q}$ terkandung dalam ruang vektor dua dimensi yang dijangkau oleh $\vert A_0\rangle$ dan $\vert A_1\rangle,$ dan tambahan pula pekali vektor-vektor ini adalah nombor nyata. Seperti yang akan kita lihat, keadaan $\mathsf{Q}$ akan sentiasa mempunyai sifat-sifat ini — bermakna keadaan adalah gabungan linear nyata $\vert A_0\rangle$ dan $\vert A_1\rangle$ — selepas sebarang bilangan iterasi operasi $G$ dalam langkah 2.

Pemerhatian tentang operasi Grover

Sekarang kita akan menumpukan perhatian kepada operasi Grover

$$G = H^{\otimes n} Z_{\mathrm{OR}} H^{\otimes n} Z_f,$$

dimulakan dengan pemerhatian menarik mengenainya.

Bayangkan sebentar kita menggantikan fungsi $f$ dengan komposisi $f$ dengan fungsi NOT — atau dengan kata lain, fungsi yang kita dapat dengan membalikkan bit output $f.$ Kita akan panggil fungsi baru ini $g,$ dan kita boleh ungkapkannya menggunakan simbol dalam beberapa cara alternatif.

$$g(x) = \neg f(x) = 1 \oplus f(x) = 1 - f(x) = \begin{cases} 1 & f(x) = 0\\[1mm] 0 & f(x) = 1 \end{cases}$$

Perhatikan bahawa

$$(-1)^{g(x)} = (-1)^{1 \oplus f(x)} = - (-1)^{f(x)}$$

untuk setiap rentetan $x\in\Sigma^n,$ dan oleh itu

$$Z_g = - Z_f.$$

Ini bermakna jika kita menggantikan fungsi $f$ dengan fungsi $g,$ algoritma Grover tidak akan berfungsi secara berbeza — kerana keadaan yang kita dapat daripada algoritma dalam kedua-dua kes adalah semestinya setara sehingga satu fasa global.

Ini bukan masalah! Secara intuitif, algoritma tidak mengambil berat yang mana rentetan adalah penyelesaian dan yang mana bukan — ia hanya perlu dapat membezakan penyelesaian dan bukan penyelesaian untuk berfungsi dengan betul.

Tindakan operasi Grover

Sekarang mari kita pertimbangkan tindakan $G$ ke atas vektor keadaan kuantum $\vert A_0\rangle$ dan $\vert A_1\rangle.$

Pertama, mari kita perhatikan bahawa operasi $Z_f$ mempunyai tindakan yang sangat mudah ke atas $\vert A_0\rangle$ dan $\vert A_1\rangle.$

$$\begin{aligned} Z_f \vert A_0\rangle & = \vert A_0\rangle \\[1mm] Z_f \vert A_1\rangle & = -\vert A_1\rangle \end{aligned}$$

Kedua, kita ada operasi $H^{\otimes n} Z_{\mathrm{OR}} H^{\otimes n}.$ Operasi $Z_{\mathrm{OR}}$ ditakrifkan sebagai

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

sekali lagi untuk setiap rentetan $x\in\Sigma^n,$ dan cara alternatif yang mudah untuk mengungkapkan operasi ini adalah seperti berikut:

$$Z_{\mathrm{OR}} = 2 \vert 0^n \rangle \langle 0^n \vert - \mathbb{I}.$$

Cara mudah untuk mengesahkan bahawa ungkapan ini bersetuju dengan definisi $Z_{\mathrm{OR}}$ adalah dengan menilai tindakannya ke atas keadaan asas piawai.

Operasi $H^{\otimes n} Z_{\mathrm{OR}} H^{\otimes n}$ oleh itu boleh ditulis seperti ini:

$$H^{\otimes n} Z_{\mathrm{OR}} H^{\otimes n} = 2 H^{\otimes n} \vert 0^n \rangle \langle 0^n \vert H^{\otimes n} - \mathbb{I} = 2 \vert u \rangle \langle u \vert - \mathbb{I},$$

menggunakan notasi yang sama, $\vert u \rangle,$ yang kita gunakan di atas untuk superposisi seragam ke atas semua rentetan $n$-bit.

Dan kini kita ada apa yang diperlukan untuk mengira tindakan $G$ ke atas $\vert A_0\rangle$ dan $\vert A_1\rangle.$ Pertama mari kita kira tindakan $G$ ke atas $\vert A_0\rangle.$

$$\begin{aligned} G \vert A_0 \rangle & = \bigl( 2 \vert u\rangle \langle u \vert - \mathbb{I}\bigr) Z_f \vert A_0\rangle \\ & = \bigl( 2 \vert u\rangle \langle u \vert - \mathbb{I}\bigr) \vert A_0\rangle \\ & = 2 \sqrt{\frac{\vert A_0\vert}{N}} \vert u\rangle -\vert A_0 \rangle\\ & = 2 \sqrt{\frac{\vert A_0\vert}{N}} \biggl( \sqrt{\frac{\vert A_0\vert}{N}} \vert A_0\rangle + \sqrt{\frac{\vert A_1\vert}{N}} \vert A_1\rangle\biggr) -\vert A_0 \rangle \\ & = \biggl( \frac{2\vert A_0\vert}{N} - 1\biggr) \vert A_0 \rangle + \frac{2 \sqrt{\vert A_0\vert \cdot \vert A_1\vert}}{N} \vert A_1 \rangle \\ & = \frac{\vert A_0\vert - \vert A_1\vert}{N} \vert A_0 \rangle + \frac{2 \sqrt{\vert A_0\vert \cdot \vert A_1\vert}}{N} \vert A_1 \rangle \end{aligned}$$

Dan kedua, mari kita kira tindakan $G$ ke atas $\vert A_1\rangle.$

$$\begin{aligned} G \vert A_1 \rangle & = \bigl( 2 \vert u\rangle \langle u \vert - \mathbb{I} \bigr) Z_f \vert A_1\rangle \\ & = - \bigl( 2 \vert u\rangle \langle u \vert - \mathbb{I} \bigr) \vert A_1\rangle \\ & = - 2 \sqrt{\frac{\vert A_1\vert}{N}} \vert u\rangle + \vert A_1 \rangle \\ & = - 2 \sqrt{\frac{\vert A_1\vert}{N}} \biggl(\sqrt{\frac{\vert A_0\vert}{N}} \vert A_0\rangle + \sqrt{\frac{\vert A_1\vert}{N}} \vert A_1\rangle\biggr) + \vert A_1 \rangle \\ & = - \frac{2 \sqrt{\vert A_1\vert \cdot \vert A_0\vert}}{N} \vert A_0 \rangle + \biggl( 1 - \frac{2\vert A_1\vert}{N} \biggr) \vert A_1 \rangle \\ & = - \frac{2 \sqrt{\vert A_1\vert \cdot \vert A_0\vert}}{N} \vert A_0 \rangle + \frac{\vert A_0\vert - \vert A_1\vert}{N} \vert A_1 \rangle \end{aligned}$$

Dalam kedua-dua kes kita menggunakan persamaan

$$\vert u\rangle = \sqrt{\frac{\vert A_0 \vert}{N}} \vert A_0\rangle + \sqrt{\frac{\vert A_1 \vert}{N}} \vert A_1\rangle$$

bersama dengan ungkapan

$$\langle u \vert A_0\rangle = \sqrt{\frac{\vert A_0 \vert}{N}} \qquad\text{dan}\qquad \langle u \vert A_1\rangle = \sqrt{\frac{\vert A_1 \vert}{N}}$$

yang mengikutinya.

Secara ringkasnya, kita ada

$$\begin{aligned} G \vert A_0 \rangle & = \frac{\vert A_0\vert - \vert A_1\vert}{N} \vert A_0 \rangle + \frac{2 \sqrt{\vert A_0\vert \cdot \vert A_1\vert}}{N} \vert A_1 \rangle\\[2mm] G \vert A_1 \rangle & = - \frac{2 \sqrt{\vert A_1\vert \cdot \vert A_0\vert}}{N} \vert A_0 \rangle + \frac{\vert A_0\vert - \vert A_1\vert}{N} \vert A_1 \rangle. \end{aligned}$$

Seperti yang telah kita perhatikan, keadaan $\mathsf{Q}$ tepat sebelum langkah 2 terkandung dalam ruang dua dimensi yang dijangkau oleh $\vert A_0\rangle$ dan $\vert A_1\rangle,$ dan kita baru sahaja menetapkan bahawa $G$ memetakan sebarang vektor dalam ruang ini ke vektor lain dalam ruang yang sama. Ini bermakna, untuk tujuan analisis, kita boleh menumpukan perhatian kita secara eksklusif pada subruang ini.

Untuk lebih memahami apa yang berlaku dalam ruang dua dimensi ini, mari kita ungkapkan tindakan $G$ pada ruang ini sebagai matriks,

$$M = \begin{pmatrix} \frac{\vert A_0\vert - \vert A_1\vert}{N} & -\frac{2 \sqrt{\vert A_1\vert \cdot \vert A_0\vert}}{N} \\[2mm] \frac{2 \sqrt{\vert A_0\vert \cdot \vert A_1\vert}}{N} & \frac{\vert A_0\vert - \vert A_1\vert}{N} \end{pmatrix},$$

di mana baris/lajur pertama dan kedua berkaitan dengan $\vert A_0\rangle$ dan $\vert A_1\rangle,$ masing-masing. Setakat ini dalam siri ini, kita sentiasa menghubungkan baris dan lajur matriks dengan keadaan klasik sesebuah sistem, tetapi matriks juga boleh digunakan untuk menerangkan tindakan pemetaan linear ke atas asas yang berbeza seperti yang kita ada di sini.

Walaupun tidak jelas sama sekali pada pandangan pertama, matriks $M$ adalah apa yang kita peroleh dengan mengkuasakan dua matriks yang kelihatan lebih mudah.

$$\begin{pmatrix} \sqrt{\frac{\vert A_0\vert}{N}} & - \sqrt{\frac{\vert A_1\vert}{N}} \\[2mm] \sqrt{\frac{\vert A_1\vert}{N}} & \sqrt{\frac{\vert A_0\vert}{N}} \end{pmatrix}^2 = \begin{pmatrix} \frac{\vert A_0\vert - \vert A_1\vert}{N} & -\frac{2 \sqrt{\vert A_1\vert \cdot \vert A_0\vert}}{N} \\[2mm] \frac{2 \sqrt{\vert A_0\vert \cdot \vert A_1\vert}}{N} & \frac{\vert A_0\vert - \vert A_1\vert}{N} \end{pmatrix} = M$$

Matriks

$$\begin{pmatrix} \sqrt{\frac{\vert A_0\vert}{N}} & - \sqrt{\frac{\vert A_1\vert}{N}} \\[2mm] \sqrt{\frac{\vert A_1\vert}{N}} & \sqrt{\frac{\vert A_0\vert}{N}} \end{pmatrix}$$

adalah sebuah matriks putaran, yang boleh kita ungkapkan secara alternatif sebagai

$$\begin{pmatrix} \sqrt{\frac{\vert A_0\vert}{N}} & - \sqrt{\frac{\vert A_1\vert}{N}} \\[2mm] \sqrt{\frac{\vert A_1\vert}{N}} & \sqrt{\frac{\vert A_0\vert}{N}} \end{pmatrix} = \begin{pmatrix} \cos(\theta) & -\sin(\theta) \\[2mm] \sin(\theta) & \cos(\theta) \end{pmatrix}$$

untuk

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

Sudut $\theta$ ini akan memainkan peranan yang sangat penting dalam analisis yang berikut, jadi penting untuk menekankan kepentingannya di sini ketika kita melihatnya buat kali pertama.

Dengan mengambil kira ungkapan matriks ini, kita perhatikan bahawa

$$M = \begin{pmatrix} \cos(\theta) & -\sin(\theta) \\[2mm] \sin(\theta) & \cos(\theta) \end{pmatrix}^2 = \begin{pmatrix} \cos(2\theta) & -\sin(2\theta) \\[2mm] \sin(2\theta) & \cos(2\theta) \end{pmatrix}.$$

Ini kerana memutar sebanyak sudut $\theta$ dua kali adalah setara dengan memutar sebanyak sudut $2\theta.$ Cara lain untuk melihat ini ialah dengan menggunakan ungkapan alternatif

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

bersama-sama dengan formula sudut berganda daripada trigonometri:

$$\begin{aligned} \cos(2\theta) & = \cos^2(\theta) - \sin^2(\theta)\\[1mm] \sin(2\theta) & = 2 \sin(\theta)\cos(\theta). \end{aligned}$$

Secara ringkasnya, keadaan daftar $\mathsf{Q}$ pada permulaan langkah 2 adalah

$$\vert u\rangle = \sqrt{\frac{\vert A_0\vert}{N}} \vert A_0\rangle + \sqrt{\frac{\vert A_1\vert}{N}} \vert A_1\rangle = \cos(\theta) \vert A_0\rangle + \sin(\theta) \vert A_1\rangle,$$

dan kesan menggunakan $G$ ke atas keadaan ini adalah untuk memutarkannya sebanyak sudut $2\theta$ dalam ruang yang dijangkau oleh $\vert A_0\rangle$ dan $\vert A_1\rangle.$ Jadi, sebagai contoh, kita ada

$$\begin{aligned} G \vert u \rangle &= \cos(3\theta) \vert A_0\rangle + \sin(3\theta) \vert A_1\rangle\\[1mm] G^2 \vert u \rangle &= \cos(5\theta) \vert A_0\rangle + \sin(5\theta) \vert A_1\rangle\\[1mm] G^3 \vert u \rangle &= \cos(7\theta) \vert A_0\rangle + \sin(7\theta) \vert A_1\rangle \end{aligned}$$

dan secara umumnya

$$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.$$

Gambaran geometri

Sekarang mari kita hubungkan analisis yang baru kita lalui dengan gambaran geometri. Ideanya ialah operasi $G$ adalah hasil darab dua pantulan, $Z_f$ dan $H^{\otimes n} Z_{\mathrm{OR}} H^{\otimes n}.$ Dan kesan bersih daripada melakukan dua pantulan adalah melakukan sebuah putaran.

Mari kita mulakan dengan $Z_f.$ Seperti yang telah kita perhatikan sebelum ini, kita ada

$$\begin{aligned} Z_f \vert A_0\rangle & = \vert A_0\rangle \\[1mm] Z_f \vert A_1\rangle & = -\vert A_1\rangle. \end{aligned}$$

Dalam ruang vektor dua dimensi yang dijangkau oleh $\vert A_0\rangle$ dan $\vert A_1\rangle,$ ini adalah sebuah pantulan tentang garis yang selari dengan $\vert A_0\rangle,$ yang akan kita panggil $L_1.$ Berikut adalah rajah yang menggambarkan tindakan pantulan ini ke atas vektor unit hipotetikal $\vert\psi\rangle,$ yang kita anggap adalah gabungan linear nyata $\vert A_0\rangle$ dan $\vert A_1\rangle.$

Kedua kita ada operasi $H^{\otimes n} Z_{\mathrm{OR}} H^{\otimes n},$ yang telah kita lihat boleh ditulis sebagai

$$H^{\otimes n} Z_{\mathrm{OR}} H^{\otimes n} = 2 \vert u \rangle \langle u \vert - \mathbb{I}.$$

Ini juga satu pantulan, kali ini tentang garis $L_2$ yang selari dengan vektor $\vert u\rangle.$ Berikut adalah rajah yang menggambarkan tindakan pantulan ini ke atas vektor unit $\vert\psi\rangle.$

Apabila kita menggabungkan dua pantulan ini, kita memperoleh satu putaran — sebanyak dua kali sudut di antara garis-garis pantulan — seperti yang digambarkan dalam rajah ini.

Ini menjelaskan, dari segi geometri, mengapa kesan operasi Grover adalah untuk memutar gabungan linear $\vert A_0\rangle$ dan $\vert A_1\rangle$ sebanyak sudut $2\theta.$