Analisis Jurnal dengan Tema Komputasi Kuantum

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