IMPLEMENTASI PENCACAHAN KUANTUM DALAM PENCARIAN KUANTUM

Fikri Ramdan Algifari, Prof. Drs. Pekik Nurwantoro, M.S., Ph.D.

2025 | Skripsi | FISIKA

Banyak masalah pencarian melibatkan basis data tak terstruktur dengan elemen yang dicari harus ditemukan tanpa adanya informasi atau urutan yang jelas untuk membantu dalam pencarian. Dalam pencarian klasik, diperlukan pemeriksaan setiap elemen, yang membutuhkan waktu O(N). Algoritma Grover (1996) dikembangkan untuk mempercepat proses pencarian ini dengan memanfaatkan prinsip-prinsip kuantum sehingga hanya membutuhkan waktu O(?N). Namun, masih terdapat batasan, salah satunya tidak dapat melakukan pencarian untuk cacah elemen tertanda (m) yang belum diketahui. Konsep pencacahan kuantum (quantum counting) kemudian dicetuskan untuk mengatasi masalah tersebut dengan mengkombinasikan algoritma Grover dan algoritma estimasi fase kuantum atau Quantum Phase Estimation (QPE). Dalam penelitian ini, pencarian kuantum diimplementasikan pada program Qiskit melalui jaringan IBM Q. Pencarian satu elemen tertanda dan lebih dari satu elemen tertanda menggunakan algoritma Grover menghasilkan histogram distribusi probabilitas elemen tertanda. Algoritma Grover menunjukkan pola grafik sinusoidal dikarenakan fenomena superposisi dan interferensi kuantum. Dapat ditunjukkan terjadi percepatan kuadrat (quadratic speedup) terhadap pencarian klasik pada algoritma Grover dengan kompleksitas waktu O(?N). Dipaparkan juga pencarian untuk cacah elemen tertanda (m) yang belum diketahui serta hubungan t (ancillary qubit) terhadap ?m yang saling berbanding terbalik.

Many search problems involve unstructured databases with the searched elements must be identified without any clear information or order to assist in the search. In classical search algorithms, each element must be examined individually, resulting in a time complexity of O(N). The Grover algorithm (1996) was developed to accelerate this process by exploiting quantum principles, reducing the time complexity to O(?N). However, limitations remain, one of which is the inability to search for an unknown number of marked elements (m). To address this issue, the concept of quantum counting was introduced, combining the Grover algorithm with Quantum Phase Estimation (QPE). In this study, quantum search was implemented using Qiskit on the IBM Q network. Searching for a single marked element, as well as multiple marked elements, with the Grover algorithm results in a histogram representing the probability distribution of marked elements. The Grover algorithm shows a sinusoidal pattern in the probability distribution due to the quantum phenomena of superposition and interference. It can be shown that there’s a quadratic speedup over classical search in Grover algorithm with a time complexity of O(?N). The study also discusses the search for an unknown number of marked elements (m) and the relationship between t (ancillary qubits) and ?m, which are inversely proportional.

Kata Kunci : algoritma grover, pencacahan kuantum, qiskit.