0
Tugas 4 Komputasi Quantum (Quantum Computation)
Posted by Chalvin Julian
on
06.28
Pada kesempatan kali ini, penulis akan mereview materi mengenai "Algoritma Grover" yang merupakan salah satu Algoritma Komputasi Quantum.
Referensi :
http://informatika.stei.itb.ac.id/~rinaldi.munir/Stmik/2005-2006/Makalah2006/MakalahStmik2006-04.pdf
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 = 2n = 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