Pengantar

Algoritma Grover adalah algoritma kuantum untuk masalah yang disebut pencarian tak terstruktur yang menawarkan perbaikan kuadratik dibanding algoritma klasik. Yang dimaksud adalah bahwa algoritma Grover membutuhkan jumlah operasi pada orde akar kuadrat dari jumlah operasi yang diperlukan untuk menyelesaikan pencarian tak terstruktur secara klasik — yang ekuivalen dengan mengatakan bahwa algoritma klasik untuk pencarian tak terstruktur harus memiliki biaya setidaknya pada orde kuadrat dari biaya algoritma Grover.

Algoritma Grover, beserta ekstensi dan metodologinya yang mendasari, ternyata berlaku secara luas, menghasilkan keunggulan kuadratik untuk banyak tugas komputasi menarik yang mungkin awalnya tidak terlihat seperti masalah pencarian tak terstruktur pada permukaannya.

Meskipun penerapan teknik pencarian Grover yang luas cukup menarik, perlu diakui di awal pelajaran ini bahwa keunggulan kuadratik yang ditawarkannya tampaknya kecil kemungkinannya menghasilkan keunggulan praktis kuantum dibanding klasik dalam waktu dekat. Hardware komputasi klasik jauh lebih canggih dari hardware komputasi kuantum — dan keunggulan kuantum atas klasik secara kuadratik yang ditawarkan algoritma Grover pasti akan tersapu oleh kecepatan clock komputer klasik modern yang luar biasa untuk masalah pencarian tak terstruktur mana pun yang bisa dijalankan dalam waktu dekat.

Namun, seiring kemajuan teknologi komputasi kuantum, algoritma Grover bisa memiliki potensi. Memang, beberapa algoritma klasik terpenting dan paling berpengaruh yang pernah ditemukan, termasuk fast Fourier transform dan pengurutan cepat (misalnya, quicksort dan merge sort), menawarkan sedikit kurang dari keunggulan kuadratik dibanding pendekatan naif terhadap masalah yang mereka selesaikan. Perbedaan utama di sini, tentu saja, adalah bahwa teknologi yang sepenuhnya baru (maksudnya komputasi kuantum) diperlukan untuk menjalankan algoritma Grover. Meskipun teknologi ini masih sangat dalam masa pertumbuhannya dibandingkan komputasi klasik, kita tidak boleh terlalu cepat meremehkan potensi kemajuan teknologi yang suatu hari bisa memungkinkan keunggulan kuadratik kuantum atas klasik memberikan manfaat praktis yang nyata.

Video pelajaran

Di video berikut, John Watrous memandu kamu melalui konten di pelajaran ini tentang algoritma Grover. Atau, kamu bisa membuka video YouTube untuk pelajaran ini di jendela terpisah. Unduh slide untuk pelajaran ini.