Welcome to Chalv'Jr Blog

Pada kesempatan kali ini, penulis akan mereview materi mengenai "Algoritma Grover" yang merupakan salah satu Algoritma Komputasi Quantum.

A. Latar Belakang

   Komputer yang saat ini kita gunakan tampak bisa mengerjakan banyak tugas pada saat bersamaan, namun kenyataannya adalah prosessor hanya beralih secara cepat dari satu tugas ke tugas selanjutnya. Komputer paralel yang sesungguhnya akan sanggup melakukan banyak operasi pada saat yang bersamaan secara simultan, mencari solusi secara cepat dari sekian banyak kemungkinan. Para ilmuwan menyebutnya komputer kuantum, karena komputer ini bekerja menurut kaidah-kaidah ganjil dalam mekanika kuantum. Kaidah yang memicu timbulnya komputer kuantum adalah bahwa partikel elementer seperti proton, neutron, dan elektron dapat berada dalam dua atau lebih stata pada saat bersamaan. Partikel-partikel ini (secara teoritis) dapat merepresentasikan prosessing unit dalam suatu mesin sehingga lebih efisien dibandingkan komputer ‘klasik’ konvensional. Lov Grover (1996) telah menemukan algoritma kuantum (dikenal juga dengan algoritma Grover) untuk mencari di dalam suatu daftar tak terurut lebih cepat daripada komputer klasik. Dengan algoritma pencarian pada komputer klasik, suatu daftar dengan N item membutuhkan rata-rata N/2 langkah untuk menemukan solusi, sedangkan dengan komputer kuantum hanya dibutuhkan √N langkah untuk melakukan hal yang sama. Untuk daftar dengan jumlah item yang sangat besar, perbedaan ini sangat signifikan.

  Quantum komputer adalah alat untuk perhitungan yang menggunakan langsung dari kuantum mekanik fenomena, seperti superposisi dan belitan. Yang dimana untuk melakukan operasi data. Dalam komputasi mode klasik, jumlah data dihitung dengan bit dalam komputer  kuantum hal ini dilakukan dengan qubit yang artinya jika dikomputer basa hanya mengenal 0 atau 1, dengan qubit sebuah komputer quantum mengenal keduanya secara bersamaan dan itu  membuat kerja dari komputer quantum itu lebih cepat dari komputer konvensuional pada banyak masalah, salah satunya memiliki sifat seperti berikut:

 - Satu-satunya cara adalah menembak dan mengecek jawabannya berkali-kali.

 - Terdapat n jumlah jawaban yang mungkin.

 - Setiap kemungkinan jawaban membutuhkan waku yang sama untuk mengeceknya.

 - Tidak ada petunjuk jawaban mana yang kemungkinan benarnya lebih besar memberi jawaban dengan asal tidak berbeda dengan mengeceknya dengan urutan tertentu.

   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.

   Perbedaan antara komputer kuantum dengan komputer klasik adalah komputer klasik bergantung pada prinsip aljabar boolean, operasi dengan prinsip gerbang logika. Data diproses dalam biner (0 dan 1) dan hanya bisa dikerjakan satu bit (0 saja atau 1 saja) dalam satu waktu. Sedangkan komputer kuantum dapat bekerja dengan 2 model gerbang logika: XOR dan Q01 (kemampuan untuk berganti dari 0 ke superposisi dari 0 atau 1, gerbang logika yang tidak bisa muncul di komputasi klasik). Dalam komputer klasik, jumlah data dihitung dengan bit, sedangkan pada komputer kuantum hal ini dilakukan dengan qubit (quantum bit). Prinsip dasar komputasi kuantum adalah bahwa sifat kuantum dari partikel dapat digunakan untuk mewakili data dan struktur data, dan bahwa prinsip mekanika kuantum dapat digunakan untuk melakukan operasi dengan data ini.

B. Metode Penelitian

   Metode penelitian yang digunakan adalah dari komponen – komponen pada Algoritma Quantum. Pada umumnya algoritma yang menghasilkan proses iterasi yang tidak lebih besar dari pangkat polinomial masukan datanya, dalam hal ini N, bisa dikatakan sudah efisien. Seperti yang telah diketahui bahwa proses pencarian data secara klasik berada dalam , jadi bisa dikatakan sudah efisien. Pencarian data dalam indeks takterurut dapat dibuat lebih efisien menggunakan komputer quantum dengan algoritma Grover yang secara umum. Algoritma Grover memanfaatkan informasi atau data dalam bentuk qubit atau quantum bit yang merupakan state dari ruang Hilbert dimensi dua. Qubit sendiri memiliki sifat-sifat khas yang tidak dimiliki bit pada umumnya, yaitu superposisi dan paralelisme Pada umumnya algoritma-algoritma quantum menggunakan sifat-sifat tersebut untuk mempercepat penyelesaian masalah yang tidak dapat dikerjakan oleh algoritma digital biasa. Salah satu algoritma yang terkenal adalah algoritma Shor yang digunakan untuk mencari faktorisasi bilangan prima dari sebuah bilangan bulat.

C. Analisis dan Pembahasan

   Hasil simulasi dari penelitian menggunakan algoritma Grover dengan jumlah N = 2ⁿ = 8 (n = 3 qubit) dan indeks dari data yang akan dicari adalah 4 0 = x 

D. Kelebihan dan Kekurangan

   Untuk kelebihan, komputer kuantum memiliki potensi untuk melaksanakan berbagai perhitungan secara simultan sehingga jauh lebih cepat dari komputer digital dan lebih cepat dari pada komputer konvensiaonal karena melalukan proses secara simultan tidak secara linear seperti komputer konvensional.

  Sedangkan kekurangan nya adalah algoritma Grover membutuhkan kelengkapan dari hampir seluruh perangkat keras dari komputer quantum untuk dapat diimplementasikan, hal ini dikarenakan sulitnya mengimplementasikan oracle yang bekerja secara paralel dalam sebuah operator inversi.

E. Kesimpulan

  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). Meski masih dalam bentuk kertas kerja, prospek komputer kuantum sangat menggiurkan, contohnya, suatu algoritma yang dapat memfaktorkan bilangan sepanjang 140 digit dengan kecepatan semilyar (10^9) kali lebih cepat dibanding yang ditawarkan oleh metode nonkuantum terbaik yang kita kenal sekarang, sebuah search engine yang sanggup memeriksa setiap ‘sudut dan celah’ di Internet dalam waktu kurang dari setengah jam, atau sebuah pemecah kode ‘brute-force’ yang dapat memecahkan transmisi DES dalam tempo 5 menit.

Referensi :
http://informatika.stei.itb.ac.id/~rinaldi.munir/Stmik/2005-2006/Makalah2006/MakalahStmik2006-04.pdf