Pencarian tanpa struktur

Ringkasan

Kita akan mulakan dengan penerangan masalah yang diselesaikan oleh algoritma Grover. Seperti biasa, kita akan biarkan $\Sigma = \{0,1\}$ menandakan abjad binari sepanjang perbincangan ini.

Andaikan bahawa

$$f:\Sigma^n \rightarrow \Sigma$$

adalah fungsi daripada rentetan binari panjang $n$ kepada bit. Kita akan anggap bahawa kita boleh mengira fungsi ini dengan cekap, tetapi selain daripada itu ia adalah sewenang-wenang dan kita tidak boleh bergantung padanya yang mempunyai struktur khas atau pelaksanaan tertentu yang sesuai dengan keperluan kita.

Apa yang dilakukan oleh algoritma Grover adalah mencari rentetan $x\in\Sigma^n$ di mana $f(x) = 1.$ Kita akan merujuk kepada rentetan seperti ini sebagai penyelesaian kepada masalah pencarian. Jika terdapat berbilang penyelesaian, maka mana-mana satu daripadanya dianggap sebagai output yang betul, dan jika tiada penyelesaian, maka jawapan yang betul memerlukan kita melaporkan bahawa tiada penyelesaian.

Tugas ini digambarkan sebagai masalah pencarian tanpa struktur kerana kita tidak boleh bergantung pada $f$ yang mempunyai sebarang struktur tertentu untuk memudahkan kerja. Kita tidak mencari dalam senarai tersusun, atau dalam beberapa struktur data yang direka khas untuk memudahkan pencarian, kita pada dasarnya mencari jarum dalam timbunan jerami.

Secara intuitif, kita boleh bayangkan bahawa kita mempunyai litar Boolean yang sangat rumit yang mengira $f,$ dan kita boleh menjalankan litar ini dengan mudah pada rentetan input yang dipilih jika kita mahu. Tetapi kerana litar itu sangat rumit, kita tidak mungkin dapat memahami litar itu dengan memeriksa (selain daripada mempunyai keupayaan untuk menilainya pada rentetan input yang dipilih).

Salah satu cara untuk melakukan tugas pencarian ini secara klasik adalah dengan hanya mengulangi semua rentetan $x\in\Sigma^n,$ menilai $f$ pada setiap satu untuk memeriksa sama ada ia adalah penyelesaian atau tidak. Seterusnya, mari tulis

$$N = 2^n$$

untuk kemudahan. Terdapat $N$ rentetan dalam $\Sigma^n,$ jadi mengulangi semuanya memerlukan $N$ penilaian $f.$ Dengan andaian bahawa kita terhad kepada menilai $f$ pada input yang dipilih, ini adalah yang terbaik yang boleh kita lakukan dengan algoritma deterministik jika kita mahu menjamin kejayaan. Dengan algoritma probabilistik, kita mungkin berharap dapat menjimatkan masa dengan memilih rentetan input kepada $f$ secara rawak, tetapi kita masih memerlukan $O(N)$ penilaian $f$ jika kita mahu kaedah ini berjaya dengan kebarangkalian yang tinggi.

Algoritma Grover menyelesaikan masalah pencarian ini dengan kebarangkalian yang tinggi dengan hanya $O(\sqrt{N})$ penilaian $f.$ Untuk jelaskan, penilaian fungsi ini mesti berlaku dalam superposisi, serupa dengan algoritma pertanyaan yang dibincangkan dalam pelajaran Algoritma pertanyaan kuantum, termasuk algoritma Deutsch, algoritma Deutsch-Jozsa, dan algoritma Simon. Tidak seperti algoritma tersebut, algoritma Grover mengambil pendekatan lelaran: ia menilai $f$ pada superposisi rentetan input dan menyisipkan penilaian ini dengan operasi lain yang mempunyai kesan mewujudkan corak interferens, membawa kepada penyelesaian dengan kebarangkalian yang tinggi (jika ada) selepas $O(\sqrt{N})$ lelaran.

Pernyataan masalah formal

Kita akan memformalkan masalah yang diselesaikan oleh algoritma Grover menggunakan model pertanyaan pengiraan. Iaitu, kita akan anggap bahawa kita mempunyai akses kepada fungsi $f:\Sigma^n\rightarrow\Sigma$ melalui gate pertanyaan yang ditakrifkan dengan cara biasa:

$$U_f \bigl( \vert a\rangle \vert x\rangle \bigr) = \vert a \oplus f(x) \rangle \vert x \rangle$$

untuk setiap $x\in\Sigma^n$ dan $a\in\Sigma.$ Ini adalah tindakan $U_f$ pada keadaan asas standard, dan tindakannya secara umum ditentukan oleh kelelurusan.

Seperti yang dibincangkan dalam pelajaran Asas algoritmik kuantum, jika kita mempunyai litar Boolean untuk mengira $f,$ kita boleh mengubah penerangan litar Boolean itu kepada litar kuantum yang melaksanakan $U_f$ (menggunakan beberapa Qubit ruang kerja yang memulakan dan mengakhiri pengiraan dalam keadaan $\vert 0\rangle$). Jadi, walaupun kita menggunakan model pertanyaan untuk memformalkan masalah yang diselesaikan oleh algoritma Grover, ia tidak terhad kepada model ini; kita boleh menjalankan algoritma Grover pada mana-mana fungsi $f$ yang kita mempunyai litar Boolean untuknya.

Berikut ialah pernyataan tepat masalah itu, yang dinamakan Carian kerana kita mencari penyelesaian, bermaksud rentetan $x$ yang menyebabkan $f$ menilai kepada $1.$

Carian

Input: fungsi $f:\Sigma^n\rightarrow\Sigma$
Output: rentetan $x\in\Sigma^n$ yang memenuhi $f(x) = 1,$ atau "tiada penyelesaian" jika tiada rentetan $x$ sedemikian wujud

Perhatikan bahawa ini bukan masalah janji — fungsi $f$ adalah sewenang-wenang. Namun, akan berguna untuk mempertimbangkan varian janji berikut bagi masalah ini, di mana kita dijamin bahawa terdapat tepat satu penyelesaian. Masalah ini muncul sebagai contoh masalah janji dalam pelajaran Algoritma pertanyaan kuantum.

Carian unik

Input: fungsi berbentuk $f:\Sigma^n \rightarrow \Sigma$
Janji: terdapat tepat satu rentetan $z\in\Sigma^n$ di mana $f(z) = 1,$ dengan $f(x) = 0$ untuk semua rentetan $x\neq z$
Output: rentetan $z$

Perhatikan juga bahawa masalah Or yang disebutkan dalam pelajaran yang sama berkait rapat dengan Carian. Untuk masalah itu, matlamatnya adalah hanya untuk menentukan sama ada penyelesaian wujud atau tidak, berbanding dengan benar-benar mencari penyelesaian.