Analisis

Sekarang kita akan menganalisis algoritma Grover untuk memahami cara kerjanya. Kita akan mulai dengan apa yang bisa disebut sebagai analisis simbolik, di mana kita menghitung bagaimana operasi Grover $G$ bertindak pada keadaan tertentu, kemudian kita akan menghubungkan analisis simbolik ini dengan gambaran geometris yang membantu untuk memvisualisasikan cara kerja algoritma.

Solusi dan bukan-solusi

Mari kita mulai dengan mendefinisikan dua himpunan string.

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

Himpunan $A_1$ berisi semua solusi untuk masalah pencarian kita sementara $A_0$ berisi string yang bukan solusi (yang bisa kita sebut sebagai bukan-solusi bila perlu). Kedua himpunan ini memenuhi $A_0 \cap A_1 = \varnothing$ dan $A_0 \cup A_1 = \Sigma^n,$ yang artinya ini adalah bipartisi dari $\Sigma^n.$

Selanjutnya kita akan mendefinisikan dua vektor satuan yang mewakili superposisi seragam atas himpunan solusi dan bukan-solusi.

$$\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 didefinisikan ketika himpunan yang bersesuaian tidak kosong, tetapi mulai sekarang kita akan fokus pada kasus di mana $A_0$ maupun $A_1$ tidak kosong. Kasus di mana $A_0 = \varnothing$ dan $A_1 = \varnothing$ mudah ditangani secara terpisah, dan kita akan melakukannya nanti.

Sebagai catatan tambahan, notasi yang digunakan di sini umum: setiap kali kita memiliki himpunan $S$ yang hingga dan tidak kosong, kita dapat menulis $\vert S\rangle$ untuk menyatakan vektor keadaan kuantum yang seragam atas elemen-elemen $S.$

Mari kita juga mendefinisikan $\vert u \rangle$ sebagai keadaan kuantum seragam atas semua string $n$-bit:

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

Perhatikan bahwa

$$\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 punya bahwa $\vert u\rangle = H^{\otimes n} \vert 0^n \rangle,$ sehingga $\vert u\rangle$ mewakili keadaan register $\mathsf{Q}$ setelah inisialisasi pada langkah 1 algoritma Grover.

Ini berarti tepat sebelum iterasi $G$ terjadi pada langkah 2, keadaan $\mathsf{Q}$ terkandung dalam ruang vektor dua-dimensi yang dibentangkan oleh $\vert A_0\rangle$ dan $\vert A_1\rangle,$ dan selain itu koefisien vektor-vektor ini adalah bilangan nyata. Seperti yang akan kita lihat, keadaan $\mathsf{Q}$ akan selalu memiliki sifat-sifat ini — artinya keadaan adalah kombinasi linear nyata dari $\vert A_0\rangle$ dan $\vert A_1\rangle$ — setelah sejumlah iterasi operasi $G$ pada langkah 2.

Observasi tentang operasi Grover

Sekarang kita akan beralih perhatian ke operasi Grover

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

dimulai dengan observasi menarik tentangnya.

Bayangkan sebentar kita menggantikan fungsi $f$ dengan komposisi $f$ dengan fungsi NOT — atau dengan kata lain, fungsi yang kita dapatkan dengan membalik bit keluaran $f$. Kita akan menyebut fungsi baru ini $g,$ dan kita dapat mengekspresikannya menggunakan simbol dengan 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 bahwa

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

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

$$Z_g = - Z_f.$$

Ini berarti jika kita menggantikan fungsi $f$ dengan fungsi $g,$ algoritma Grover tidak akan berfungsi secara berbeda — karena keadaan yang kita peroleh dari algoritma dalam dua kasus tersebut pasti setara sampai fase global.

Ini bukan masalah! Secara intuitif, algoritma tidak peduli string mana yang merupakan solusi dan mana yang bukan — ia hanya perlu mampu membedakan solusi dan bukan-solusi agar bekerja dengan benar.

Aksi operasi Grover

Sekarang mari kita pertimbangkan aksi $G$ pada vektor keadaan kuantum $\vert A_0\rangle$ dan $\vert A_1\rangle.$

Pertama, mari kita amati bahwa operasi $Z_f$ memiliki aksi yang sangat sederhana pada $\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 memiliki operasi $H^{\otimes n} Z_{\mathrm{OR}} H^{\otimes n}.$ Operasi $Z_{\mathrm{OR}}$ didefinisikan 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}$$

lagi untuk setiap string $x\in\Sigma^n,$ dan cara alternatif yang nyaman untuk mengekspresikan operasi ini adalah seperti ini:

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

Cara sederhana untuk memverifikasi bahwa ekspresi ini sesuai dengan definisi $Z_{\mathrm{OR}}$ adalah dengan mengevaluasi aksinya pada keadaan basis standar.

Operasi $H^{\otimes n} Z_{\mathrm{OR}} H^{\otimes n}$ oleh karena itu dapat 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 atas semua string $n$-bit.

Dan sekarang kita memiliki apa yang kita butuhkan untuk menghitung aksi $G$ pada $\vert A_0\rangle$ dan $\vert A_1\rangle.$ Pertama mari kita hitung aksi $G$ pada $\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 hitung aksi $G$ pada $\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 kasus 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 ekspresi

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

yang mengikutinya.

Singkatnya, kita memiliki

$$\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 sudah kita catat, keadaan $\mathsf{Q}$ tepat sebelum langkah 2 terkandung dalam ruang dua-dimensi yang dibentangkan oleh $\vert A_0\rangle$ dan $\vert A_1\rangle,$ dan kita baru saja membuktikan bahwa $G$ memetakan setiap vektor dalam ruang ini ke vektor lain dalam ruang yang sama. Ini berarti, untuk keperluan analisis, kita dapat memusatkan perhatian sepenuhnya pada subruang ini.

Untuk lebih memahami apa yang terjadi dalam ruang dua-dimensi ini, mari kita ekspresikan aksi $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},$$

yang baris dan kolomnya pertama dan kedua masing-masing bersesuaian dengan $\vert A_0\rangle$ dan $\vert A_1\rangle.$ Sejauh ini dalam seri ini, kita selalu menghubungkan baris dan kolom matriks dengan keadaan klasik suatu sistem, tetapi matriks juga bisa digunakan untuk mendeskripsikan aksi pemetaan linear pada basis yang berbeda seperti yang kita miliki di sini.

Meskipun tidak terlihat jelas pada pandangan pertama, matriks $M$ adalah yang kita peroleh dengan mengkuadratkan matriks yang tampak lebih sederhana.

$$\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 matriks rotasi, yang dapat kita ekspresikan 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 peran yang sangat penting dalam analisis berikut, jadi penting untuk menekankan pentingnya di sini saat kita melihatnya untuk pertama kali.

Berdasarkan ekspresi matriks ini, kita amati bahwa

$$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 karena merotasi dengan sudut $\theta$ dua kali setara dengan merotasi dengan sudut $2\theta.$ Cara lain untuk melihat ini adalah dengan menggunakan ekspresi alternatif

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

bersama dengan rumus sudut ganda dari trigonometri:

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

Singkatnya, keadaan register $\mathsf{Q}$ pada awal 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 efek menerapkan $G$ pada keadaan ini adalah merotasinya dengan sudut $2\theta$ dalam ruang yang dibentangkan oleh $\vert A_0\rangle$ dan $\vert A_1\rangle.$ Jadi, misalnya, kita memiliki

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

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

Sekarang mari kita hubungkan analisis yang baru saja kita lakukan dengan gambaran geometris. Idenya adalah bahwa operasi $G$ adalah hasil kali dari dua refleksi, $Z_f$ dan $H^{\otimes n} Z_{\mathrm{OR}} H^{\otimes n}.$ Dan efek bersih dari melakukan dua refleksi adalah melakukan rotasi.

Mari kita mulai dengan $Z_f.$ Seperti yang sudah kita amati sebelumnya, kita memiliki

$$\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 dibentangkan oleh $\vert A_0\rangle$ dan $\vert A_1\rangle,$ ini adalah refleksi terhadap garis yang sejajar dengan $\vert A_0\rangle,$ yang kita sebut $L_1.$ Berikut adalah gambar yang menggambarkan aksi refleksi ini pada vektor satuan hipotetis $\vert\psi\rangle,$ yang kita asumsikan sebagai kombinasi linear nyata dari $\vert A_0\rangle$ dan $\vert A_1\rangle.$

Kedua kita memiliki operasi $H^{\otimes n} Z_{\mathrm{OR}} H^{\otimes n},$ yang sudah kita lihat dapat ditulis sebagai

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

Ini juga merupakan refleksi, kali ini terhadap garis $L_2$ yang sejajar dengan vektor $\vert u\rangle.$ Berikut adalah gambar yang menggambarkan aksi refleksi ini pada vektor satuan $\vert\psi\rangle.$

Ketika kita mengkomposisikan dua refleksi ini, kita mendapatkan rotasi — sebesar dua kali sudut antara garis-garis refleksi — seperti yang diilustrasikan gambar ini.

Ini menjelaskan, dalam istilah geometris, mengapa efek operasi Grover adalah merotasi kombinasi linear dari $\vert A_0\rangle$ dan $\vert A_1\rangle$ dengan sudut $2\theta.$