Pengenalan

Algoritma Grover adalah algoritma kuantum untuk masalah pencarian tanpa struktur yang menawarkan peningkatan kuadratik berbanding algoritma klasik. Maksudnya, algoritma Grover memerlukan bilangan operasi pada tahap punca kuasa dua daripada bilangan operasi yang diperlukan untuk menyelesaikan pencarian tanpa struktur secara klasik — yang bersamaan dengan mengatakan bahawa algoritma klasik untuk pencarian tanpa struktur mesti mempunyai kos sekurang-kurangnya pada tahap kuasa dua kos algoritma Grover.

Algoritma Grover, bersama dengan sambungan dan metodologinya yang mendasari, ternyata boleh digunakan secara meluas, memberikan kelebihan kuadratik untuk banyak tugas pengiraan yang menarik yang mungkin pada awalnya tidak kelihatan seperti masalah pencarian tanpa struktur di permukaan.

Walaupun kebolehgunaan teknik pencarian Grover yang luas adalah menarik, perlu diakui di awal pelajaran ini bahawa kelebihan kuadratik yang ditawarkannya nampaknya tidak mungkin membawa kepada kelebihan praktikal kuantum berbanding klasik dalam masa terdekat. Perkakasan pengiraan klasik jauh lebih maju daripada perkakasan pengiraan kuantum — dan kelebihan kuantum berbanding klasik yang kuadratik yang ditawarkan oleh algoritma Grover pasti akan hilang oleh kelajuan jam komputer klasik moden yang luar biasa untuk sebarang masalah pencarian tanpa struktur yang mungkin dijalankan dalam masa terdekat.

Namun, seiring kemajuan teknologi pengiraan kuantum, algoritma Grover mungkin mempunyai potensi. Memang, beberapa algoritma klasik yang paling penting dan berpengaruh yang pernah ditemui, termasuk jelmaan Fourier cepat dan pengisihan cepat (contohnya, quicksort dan merge sort), menawarkan sedikit kurang daripada kelebihan kuadratik berbanding pendekatan naif untuk masalah yang mereka selesaikan. Perbezaan utama di sini, tentu saja, adalah bahawa teknologi yang sepenuhnya baharu (bermaksud pengiraan kuantum) diperlukan untuk menjalankan algoritma Grover. Walaupun teknologi ini masih sangat awal berbanding pengiraan klasik, kita tidak seharusnya terlalu meremehkan potensi kemajuan teknologi yang boleh membolehkan kelebihan kuadratik kuantum berbanding klasik suatu hari nanti menawarkan manfaat praktikal yang nyata.

Video pelajaran

Dalam video berikut, John Watrous membimbing kamu melalui kandungan dalam pelajaran tentang algoritma Grover ini. Sebagai alternatif, kamu boleh membuka video YouTube untuk pelajaran ini dalam tetingkap berasingan. Muat turun slaid untuk pelajaran ini.