Apakah ada penjelasan orang awam mengapa algoritma Grover bekerja?

Posting blog ini oleh Scott Aaronson adalah penjelasan yang sangat berguna dan sederhana tentang algoritma Shor .

Saya ingin tahu apakah ada penjelasan seperti itu untuk algoritma kuantum kedua yang paling terkenal: Algoritma Grover untuk mencari basis data ukuran tidak berurutan dalam waktu .O ( $O(n)$$O(\sqrt{n})$

Secara khusus, saya ingin melihat beberapa intuisi yang dapat dimengerti untuk hasil awal yang mengejutkan dari waktu berjalan!

Ada penjelasan yang bagus dari Craig Gidney di sini (ia juga memiliki konten hebat lainnya, termasuk simulator rangkaian, di blog-nya ).

Pada dasarnya, algoritma Grover berlaku ketika Anda memiliki fungsi yang mengembalikan Trueuntuk salah satu input yang mungkin, dan Falseuntuk semua yang lain. Tugas algoritma adalah menemukan yang kembali True.

Untuk melakukan ini, kami menyatakan input sebagai string bit, dan menyandikannya menggunakan status dan dari string qubit. Jadi string bit akan dikodekan dalam empat negara qubit , misalnya.$|0\rangle$$|1\rangle$0011$|0011\rangle$

Kita juga harus bisa mengimplementasikan fungsi menggunakan gerbang kuantum. Secara khusus, kita perlu menemukan urutan gerbang yang akan mengimplementasikan kesatuan sehingga$U$

$U | a \rangle = - | a \rangle, \,\,\,\,\,\,\,\,\,\,\,\,\, U | b \rangle = | b \rangle$

di mana adalah bit string yang fungsi akan kembali dan adalah setiap yang akan kembali .$a$True$b$False

Jika kita mulai dengan superposisi dari semua string bit yang mungkin, yang cukup mudah dilakukan dengan hanya Hadamarding segalanya, semua input dimulai dengan amplitudo yang sama dari (di mana adalah panjang string bit yang kita cari, dan karena itu jumlah qubit yang kita gunakan). Tetapi jika kita menerapkan oracle , amplitudo status yang kita cari akan berubah menjadi .$\frac{1}{\sqrt{2^n}}$$n$$U$$-\frac{1}{\sqrt{2^n}}$

Ini bukan perbedaan yang mudah diamati, jadi kita perlu memperkuatnya. Untuk melakukan ini kita menggunakan Grover Difusi Operator , . Efek dari operator ini pada dasarnya adalah untuk melihat bagaimana setiap amplitudo berbeda dari amplitudo rata-rata, dan kemudian membalikkan perbedaan ini. Jadi jika amplitudo tertentu adalah jumlah tertentu lebih besar dari amplitudo rata-rata, itu akan menjadi jumlah yang sama kurang dari rata-rata, dan sebaliknya.$D$

Khususnya, jika Anda memiliki superposisi string bit , operator difusi memiliki efek$b_j$

$D: \,\,\,\, \sum_j \alpha_j \, | b_j \rangle \,\,\,\,\,\, \mapsto \,\,\,\,\,\, \sum_j (2\mu \, - \, \alpha_j) \, | b_j \rangle$

di mana adalah amplitudo rata-rata. Jadi amplitudo apa pun akan berubah menjadi . Untuk melihat mengapa itu memiliki efek ini, dan bagaimana menerapkannya, lihat catatan kuliah ini .$\mu = \sum_j \alpha_j$$\mu + \delta$$\mu - \delta$

Sebagian besar amplitudo akan menjadi sedikit lebih besar dari rata-rata (karena efek dari single ), sehingga mereka akan menjadi sedikit lebih kecil dari rata-rata melalui operasi ini. Bukan perubahan besar.$-\frac{1}{\sqrt{2^n}}$

Keadaan yang kita cari akan sangat terpengaruh. Amplitudo-nya jauh lebih sedikit daripada rata-rata, sehingga akan menjadi jauh lebih besar rata-rata setelah operator difusi diterapkan. Karena itu, efek akhir dari operator difusi adalah menyebabkan efek interferensi pada status yang memotong amplitudo dari semua jawaban yang salah dan menambahkannya ke jawaban yang benar. Dengan mengulangi proses ini, kita dapat dengan cepat mencapai titik di mana solusi kita sangat menonjol dari kerumunan sehingga kita dapat mengidentifikasinya.$\frac{1}{\sqrt{2^n}}$

Tentu saja, ini semua menunjukkan bahwa semua pekerjaan dilakukan oleh operator difusi. Pencarian hanyalah sebuah aplikasi yang dapat kita sambungkan.

Lihat jawaban atas pertanyaan lain untuk perincian tentang bagaimana fungsi dan operator difusi diimplementasikan.

Saya menemukan pendekatan grafis yang cukup baik untuk memberikan beberapa wawasan tanpa terlalu teknis. Kami membutuhkan beberapa input:

• kita bisa menghasilkan keadaan$|\psi\rangle$ with non-zero overlap with the 'marked' state $|x\rangle$: $\langle x|\psi\rangle\neq 0$.
• we can implement an operation $U_1=-(\mathbb{I}-2|\psi\rangle\langle\psi|)$
• we can implement an operation $U_2=\mathbb{I}-2|x\rangle\langle x|$.

This last operation is the one that can mark our marked item with a -1 phase. We can also define a state $|\psi^\perp\rangle$ to be orthonormal to $|x\rangle$ such that the $\{|x\rangle,|\psi^\perp\rangle\}$ forms an orthonormal basis for the span of $\{|x\rangle,|\psi\rangle\}$. Both the operations that we have defined preserve this space: you start with some state in the span of $\{|x\rangle,|\psi^\perp\rangle\}$, and they return a state within the span. Moreover, both are unitary, so the length of the input vector is preserved.

A vector of fixed length within a two-dimensional space can be visualised as the circumference of a circle. So, let's set up a circle with two orthogonal directions corresponding to $|\psi^\perp\rangle$ and $|x\rangle$.

Our initial state $|\psi\rangle$ will have small overlap with $|x\rangle$ and large overlap with $|\psi^\perp\rangle$. If it were the other way around, search would be easy: we'd just prepare $|\psi\rangle$, measure, and test the output using the marking unitary, repeating until we got the marked item. It wouldn't take long. Let's call the angle between $|\psi\rangle$ and $|\psi^\perp\rangle$ the angle $\theta$.

Now let's take a moment to think about what our two unitary actions do. Both have a -1 eigenvalue, and all other eigenvalues +1. In our two-dimensional subspace, that reduces to a +1 eigenvalue and a -1 eigenvalue. Such an operation is a reflection in the axis defined by the +1 eigenvector. So, $U_1$ is a reflection in the $|\psi\rangle$ axis, while $U_2$ is a reflection in the $|\psi^\perp\rangle$ axis.

Now, take an arbitrary vector in this space, and apply $U_2$ followed by $U_1$. The net effect is that the vector is rotated by an angle $2\theta$ towards the $|x\rangle$ axis.

So, if you start from $|\psi\rangle$, you can repeat this sufficiently many times, and get to within an angle $\theta$ of $|x\rangle$. Thus, when we measure that state, we get the value $x$ with high probability.

Now we need a little care to find the speed-up. Assume that the probability of finding $|x\rangle$ in $|\psi\rangle$ is $p\ll 1$. So, classically, we'd need $O(1/p)$ attempts to find it. In our quantum scenario, we have that $\sqrt{p}=\sin\theta\approx\theta$ (since $\theta$ is small), and we want a number of runs $r$ such that $\sin((2r+1)\theta)\approx 1$. So, $r\approx \frac{\pi}{2\theta}\approx \frac{\pi}{2\sqrt{p}}$. You can see the square-root speed-up right there.

The simple explanation for how (and hence why) Grover's algorithm works is that a quantum gate can only reshuffle (or otherwise distribute) probability amplitudes. Using an initial state with equal probability amplitudes for all states of the computational basis, one starts with an amplitude of $1/\sqrt{N}$. This much can be "added" to the desired (solution) state in each iteration, such that after $\sqrt{N}$ iterations one arrives at a probability amplitude of $1$ meaning the desired state has been distilled.