Saya akan menganalisis sebuah jurnal mengenai algoritma komputasi
kuantum. Jurnal ini berjudul “Algoritma Pencarian dalam Daftar Tak Terurut pada
Komputasi Kuantum (Algoritma Grover)”.
1.
Latar Belakang
Algoritma pencarian dalam suatu daftar
merupakan algoritma pencarian paling dasar. Tujuannya adalah mencari sebuah
elemen dari sebuah himpunan dengan suatu kunci (kemungkinan memuat informasi
yang terkait dengan kunci). Algoritma pencarian yang paling sederhana adalah
pencarian linear, yang mencari item secara berurutan. Kompleksitas algoritma
pencarian linear ini adalah O(n), dengan n adalah banyaknya item dalam daftar.
Algoritma Grover merupakan algoritma
pencarian kuantum yang memungkinkan percepatan kuadrat dibandingkan dengan
algoritma pencarian linear klasik untuk daftar tak terurut. Dengan demikian,
algoritma Grover memungkinkan untuk dapat mencari suatu nama pada buku telepon
yang berisi 1000.000 nama dengan 1000 kali percobaan saja, alih-alih 500 ribu
percobaan.
2.
Metode
Pada jurnal ini, peneliti membedakan
antara pencarian dengan probabilitas pada komputer klasik dan pencarian dengan
algoritma pencarian uantum (algoritma Grover). Perbedaan paling mendasar antara
pencarian probabilitas klasik dan algoritma pencarian kuantum adalah bahwa
pencarian probabilitas klasik menggunakan nilai peluang yang harus bernilai
positif, sedangkan pencarian kuantum menggunakan amplitudo, yang dapat bernilai
positif atau negatif. Berdasarkan prinsip mekanika kuantum, nilai amplitudo
adalah sebesar akar dari peluang, sehingga amplitudo untuk setiap status
menjadi sebesar akar dari 1/N, yaitu 1/√N. Pada algoritma pencarian kuantum
juga terdapat fungsi qrandom(N,r) yang merupakan fungsi pembangkit bilangan
random.
.
3.
Analisis
Pada jurnal ini peneliti melakukan contoh
penerapan algoritma Grover pada kasus ingin menemukan suatu nama dalam buku
telepon yang hanya memiliki empat aran (entri), maka N = 4. Pada umumnya, eta
(jumlah iterasi pada algoritma pencarian kuantum), berkisar antara 0.5√N and
0.8√N. Untuk N = 4, maka eta bernilai 1 sehingga iterasi hanya berlangsung satu
kali. Fungsi qrandom(4,r) akan membangkitkan bilangan q antara 0 sampai 3
dengan amplitudo bernilai ±1/√4 atau ±0.5. Berikut ini adalah daftar nilai
amplitudo untuk bilangan q dan r dengan tanda sesuai dengan perhitungan yang
telah dijelaskan sebelumnya:
Pada awalnya dengan fungsi qrandom(4,0)
amplitudo yang terbentuk untuk setiap nilai r adalah +0.5, sehingga himpunan
amplitudonya v = [0.5, 0.5, 0.5, 0.5]. Diasumsikan nilai r yang dihasilkan pada
langkah sebelumnya adalah 2, maka fungsi invert_phase() tereksekusi, dan v[2]
menjadi -0.5. Pada langkah ini diperoleh v = [0.5, 0.5, - 0.5, 0.5].
qrandom(4,r) tidak hanya membangkitkan
bilangan acak antara 0 sampai 3, tetapi juga menghitung amplitudo sesuai dengan
amplitudo sebelumnya. Bilangan yang dibangkitkan oleh qrandom(4,r), misalnya q,
bernilai antara 0 sampai 3. Maka untuk q = 0, amplitudonya adalah 0.25 + 0.25 -
0.25 + 0.25 = 0.5. Dengan melakukan perhitungan yang sama untuk q = 1, q = 2,
dan q = 3, diperoleh amplitudonya adalah -0.5, 0.5 dan 0.5. Sehingga diperoleh
v = [0.5, -0.5, 0.5, 0.5]. Diasumsikan nilai r yang dihasilkan pada langkah
sebelumnya adalah 0, maka fungsi invert_phase() tereksekusi, dan v[0] menjadi
-0.5. Pada langkah ini diperoleh v = [-0.5, -0.5, 0.5, 0.5].
kemudian menghitung kembali amplitudo
untuk semua kemungkinan bilangan yang dibangkitkan oleh fungsi qrandom(4,r). Sehingga
diperoleh v = [0.0, 0.0, -1.0, 0.0].
Dari himpunan amplitudo v yang diperoleh
pada langkah sebelumnya dapat diketahui peluang untuk:
Dari peluang di atas dapat dilihat bahwa
aran yang dicari terletak pada indeks ke-2.
4.
Kesimpulan/tanggapan
Berdasarkan jurnal di atas dapat diambil
kesimpulan bahwa Karena kecepatan dan kemampuannya, algoritma pencarian Grover
sangat mungkin menjadi komponen kunci dalam peranti lunak masa depan. Dengan
kompleksitas algoritma sebesar O(√N), jelas algoritma pencarian Grover yang
merupakan algoritma kuantum jauh lebih baik daripada algoritma pencarian klasik
dalam daftar tak terurut, dengan kompleksitas algoritma O(N).
5.
Referensi
http://informatika.stei.itb.ac.id/~rinaldi.munir/Stmik/2005-2006/Makalah2006/MakalahStmik2006-04.pdf
