BAB 2 LANDASAN TEORI 2.1
Teori Dasar/Umum
2.1.1
Pengertian Optimisasi Optimisasi (Wikipedia, Optimisasi, 2007) ialah suatu proses untuk mencapai
hasil yang ideal atau optimal (nilai efektif yang dapat dicapai). Dalam disiplin matematika, optimisasi merujuk pada studi permasalahan yang mencoba untuk mencari nilai minimal atau maksimal dari suatu fungsi nyata. Untuk dapat mencapai nilai optimal baik minimal atau maksimal tersebut, secara sistematis dilakukan pemilihan nilai variabel integer atau nyata yang akan memberikan solusi optimal. Permasalahan ini dapat direpresentasikan dalam notasi matematis sebagai berikut: Berdasarkan: fungsi dari himpunan A ke himpunan bilangan nyata. Cari: sebuah elemen x0 dalam A sedemikian sehingga : •
f(x0) ≤ f(x) untuk semua x dalam A, untuk proses minimalisasi.
•
f(x0) ≥ f(x) untuk semua x dalam A, untuk proses maksimalisasi. Formulasi yang telah diuraikan diatas adalah formulasi permasalahan optimisasi,
atau sering disebut juga permasalahan pemrograman matematis, salah satu bentuk dari pemrograman linear. Banyak masalah dalam dunia nyata yang dapat direpresentasikan dalam kerangka permasalahan ini. Pada umumnya A adalah himpunan bagian dari Ruang Euclid Rn. Biasanya juga ada syarat-syarat tertentu (constraint) berupa persamaan atau ketidaksamaan yang harus dipenuhi oleh elemen dari A. Elemen dari A biasa disebut sebagai solusi yang mungkin (feasible solution), sementara fungsi f biasa disebut sebagai fungsi objektif atau fungsi biaya. Diantara solusi yang mungkin,
12 terdapat solusi yang dapat meminimalkan atau memaksimalkan fungsi objektif, solusi yang demikian ini disebut sebagai solusi optimal. Domain dari A disebut sebagai ruang pencarian sementara elemen dari A disebut sebagai kandidat solusi atau solusi yang mungkin. 2.1.2
Waktu Akses Waktu akses (Wikipedia, Waktu akses, 2006) merupakan penundaan/selang
waktu antara permintaan untuk mengakses sistem dan pengembalian data sesuai dengan yang diminta. Dalam sistem telekomunikasi, waktu akses adalah selang waktu antara mulainya akses pencobaan dengan akses yang berhasil. Nilai waktu akses ini hanya diukur pada pencobaan akses yang berakibat pada akses yang berhasil. Dalam bidang komputer, waktu akses diartikan sebagai interval waktu antara unit pengontrol instruksi melakukan inisialisasi sebuah panggilan data atau permintaan untuk penyimpanan data dan proses pengiriman data secara lengkap atau penyimpanan dimulai. Sedangkan dalam magnetic disk drive, waktu akses merupakan waktu untuk mendapatkan track yang diinginkan dan penundaan rotasi disk dalam membawa sektor yang diperlukan di bawah mekanisme pembacaan-penulisan. Waktu akses juga kerap kali dideskripsikan sebagai tingkat kecepatan dari disk drive, dimana disk drive merupakan peralatan untuk membaca dari dan menulis ke disk. Waktu akses ini diukur dalam milisekon atau sering disingkat dengan ms. Untuk hard disk drives cepat bagi komputer (Personal Computer) memiliki waktu akses antara 9 sampai 15 milisekon, di mana waktu akses ini 200 kali lebih lambat dibandingkan dengan DRAM (Dynamic Random Access Memory). DRAM merupakan jenis/tipe
13 memory yang paling sering digunakan dalam komputer, sedangkan memory memiliki arti area penyimpanan internal dalam komputer. Jadi, waktu akses database dapat diartikan sebagai selang waktu antara user atau pengguna melakukan permintaan untuk mengakses ke database dan pengembalian data secara lengkap sesuai yang diminta. Definisi paling umum tentang waktu akses adalah (Kozierok, Charles. M, 2005): Access Time = Command Overhead Time + Seek Time + Settle Time + Latency
Command overhead merupakan waktu yang dibutuhkan terhitung dari sebuah perintah diberikan ke harddisk sampai terjadinya sesuatu yang memenuhi perintah. Dengan kata lain, sering disebut dengan waktu reaksi untuk disk. Sebagai contoh, ketika kita sedang menyetir mobil dan tiba-tiba lampu merah, “common overhead” kita adalah waktu antara ketika lampu berubah, sampai kaki kita mulai menginjak rem. Seperti halnya dengan settle time, command overhead merupakan komponen waktu akses dan bagian dari keseluruhan persamaan posisi tampilan secara acak. Command overhead ini umumnya kecil dan sekitar 0.5 ms, biasanya tidak dibedakan secara terpisah dari seek time. Waktu ini umumnya dipengaruhi oleh rancangan keseluruhan pengontrolan disk serta interface yang ada. Seek time adalah salah satu dari beberapa penundaan yang berhubungan dengan pembacaan dan penulisan data pada disk drive sebuah komputer. Sering pula disebut dengan penundaan rotasi atau waktu pemindahan. Untuk dapat membaca dan menulis data dalam tempat khusus sebuah disk, read/write head dari sebuah disk perlu
14 dipindahkan ke tempat yang sebenarnya. Proses seperti ini dikatakan sebagai “seeking”, dan waktu yang diperlukan dari head untuk memindahkan ke tempat yang sebenarnya dinamakan “seek time”. Settle time merupakan jumlah waktu yang dibutuhkan setelah penggerak memindahkan head selama pencarian dan waktu ketika head dalam menstabilkan data untuk dibaca. Umumnya, settle time sangat singkat sekitar 0.1 ms. Settle time serupa dengan seek time, yang merupakan fungsi karakteristik penggerak drive. Latency adalah waktu ketika drive menunggu datangnya sektor yang benar, di mana read/write head ditempatkan setelah penggerak selesai mencari track yang benar. penggerak telah selesai mencari track yang benar. Tabel di bawah ini menunjukkan kecepatan putaran harddisk yang umum : Tabel 2.1.2.1 Contoh latency waktu akses Spindle Speed (RPM)
Worst-Case Latency (Full Rotation) (ms)
Average Latency (Half Rotation) (ms)
3,600
16.7
8.3
4,200
14.2
7.1
4,500
13.3
6.7
4,900
12.2
6.1
5,200
11.5
5.8
5,400
11.1
5.6
7,200
8.3
4.2
10,000
6.0
3.0
12,000
5.0
2.5
15,000
4.0
2.0
Sumber: http://www.storagereview.com/map/lm.cgi/access (23/09/2006)
15 Latency hanya relevan dengan tipe akses tertentu. Untuk akses yang majemuk, pembacaan sektor dalam disk secara acak merupakan faktor penting. Dalam pembacaan data yang besar secara berkelanjutan, latency umumnya faktor minor karena hanya akan terjadi ketika menunggu pembacaan sektor pertama dari sebuah file. Penggunaan silinder dan head skewing dalam drive yang modern dirancang untuk mengurangi latency ketika perubahan antara consecutive heads atau silinder dalam pembacaan atau penulisan secara berurutan. Berikut adalah contoh waktu akses dari beberapa harddisk :
Gambar 2.1.2.1 Contoh perbandingan waktu akses Sumber: http://images.anandtech.com/graphs/wd1500%20king%20raptor_020506110228/10744.png (22/09/2006)
16 2.1.3
Database Data merupakan nilai/value yang turut merepresentasikan deskripsi dari suatu
objek atau kejadian. Informasi merupakan hasil dari pengolahan data dalam suatu bentuk yang lebih berguna dan lebih berarti bagi penerimanya yang menggambarkan suatu kejadian-kejadian (event) yang nyata (fact) yang digunakan untuk pengambilan keputusan. Database adalah (Irmansyah, Faried, 2003, p2) kumpulan dari item data yang saling berhubungan satu dengan yang lainnya yang diorganisasikan berdasarkan sebuah skema atau struktur tertentu, tersimpan di hardware komputer dan dengan software untuk melakukan manipulasi untuk kegunaan tertentu. Sedangkan sistem manajemen database adalah program komputer yang digunakan untuk mengatur dan melakukan permintaan dalam database. Data memiliki tingkat-tingkat tertentu yang dikenal sebagai jenjang data. Berikut ini adalah jenjang data dari yang paling sederhana ke paling kompleks : •
Characters merupakan bagian data yang terkecil, dapat berupa karakter numerik, huruf atau pun karakter-karakter khusus (special characters) yang membentuk suatu item data/field.
•
Field merepresentasikan suatu atribut dari record yang menunjukkan suatu item dari data. Kumpulan dari field membentuk suatu record. Jenis-jenis field: ¾ field name: harus diberi nama untuk membedakan field yang satu dengan lainnya. ¾ field representation: tipe field (karakter, teks, tanggal, angka, dsb), lebar field (ruang maksimum yang dapat diisi dengan karakter-karakter data). ¾ field value: isi dari field untuk masing-masing record.
17 •
Record adalah kumpulan dari field membentuk suatu record. Record menggambarkan suatu unit data individu yang tertentu. Kumpulan dari record membentuk suatu file. Misalnya: file personalia, tiap-tiap record dapat mewakili data tiap-tiap karyawan.
•
File terdiri dari record-record yang menggambarkan satu kesatuan data yang sejenis. Misalnya: file mata pelajaran berisi data tentang semua mata pelajaran yang ada.
•
Database merupakan kumpulan dari file/tabel.
Untuk lebih jelasnya, dapat dilihat pada contoh gambar di bawah ini (Irmansyah, Faried, 2003, p3):
Gambar 2.1.3.1 Contoh database Sumber: http://ilmukomputer.com/umum/faried-database.php (22/09/2006)
Menurut Schneiderman (1998), ada delapan aturan emas dalam merancang interface : a. Berusaha keras untuk konsisten. b. Memungkinkan frequent users menggunakan shortcuts. Dengan adanya peningkatan dalam penggunaan shortcut dapat mengurangi jumlah interaksi dan meningkatkan kecepatan tampilan. c. Memberikan umpan balik (feed back) yang informatif. d. Merancang dialog untuk menghasilkan keadaan akhir (sukses atau selesai). e. Memberikan penanganan kesalahan yang sederhana. f. Mengizinkan pembalikan aksi (undo) dengan mudah. Jika memungkinkan, aksi harus bisa dibalik. Hal ini dapat mengurangi kegelisahan user, karena kesalahan yang dilakukan oleh user dapat diperbaiki. g. Mendukung pusat kendali internal. Untuk mendukung user agar lebih berinisiatif dalam melakukan aksi daripada menunggu respon dari sistem untuk melakukan aksi. h. Mengurangi beban ingatan jangka pendek. Normalisasi (Irmansyah, Faried, 2003, p4) merupakan sebuah teknik dalam logical desain sebuah basis data/database, teknik pengelompokkan atribut dari suatu relasi sehingga membentuk struktur relasi yang baik (tanpa redudansi). •
Normalisasi Pertama Aturannya meliputi pendefinisikan atribut kunci, tidak adanya group berulang, semua atribut bukan kunci tergantung pada atribut kunci.
19 •
Normalisasi Kedua Aturannya meliputi sudah tidak ada ketergantungan parsial, di mana seluruh field hanya tergantung pada sebagian field kunci dan sudah normal pertama.
•
Normalisasi Ketiga Aturannya meliputi tidak ada ketergantungan transitif dan sudah normal kedua.
2.1.4
Teknik Searching Searching merupakan aktivitas untuk menemukan sesuatu. Terdapat 5 jenis
searching yang akan dibahas: •
List search Teknik pencarian ini merupakan teknik pencarian yang paling dasar. Tujuannya (Wikipedia, Search Algorithm, 2006) adalah untuk mendapatkan sebuah elemen dari himpunan dengan beberapa kunci (yang mungkin mengandung informasi lain yang berhubungan dengan kunci). Karena ini merupakan masalah yang umum dalam ilmu komputer, kompleksitas komputasi algoritma ini telah dipelajari. Algoritma termudah adalah pencarian linear, yang mencari masing-masing elemen dalam daftar secara berurutan. Teknik ini memiliki waktu akses O(n), tetapi dapat digunakan secara pada daftar yang tidak terproses. Teknik pencarian daftar yang lain adalah pencarian secara biner yang memiliki waktu akses O(log n). Teknik ini lebih baik dibandingkan teknik linear untuk daftar dalam jumlah besar, tetapi daftar ini perlu diurutkan terlebih dahulu dan merupakan akses secara acak. Pencarian interpolasi lebih baik dari pencarian biner untuk daftar tak terurut yang sangat besar. Algoritma Grover
20 merupakan algoritma kuantum yang menyediakan kecepatan akses akar dari pencarian secara linear dan untuk daftar tak terurut.
• Tree search Algoritma pencarian tree merupakan pusat teknik pencarian. Prinsip dasarnya adalah sebuah simpul diambil dari sebuah data, penggantinya diperiksa dan ditambahkan ke struktur data. Dengan memanipulasi struktur data, tree dieksplorasikan dalam urutan yang berbeda tingkat demi (Breadth First Search) atau mencapai sebuah simpul leaf dahulu kemudian backtracking (Depth First Search). Contoh lain dari pencarian tree ini meliputi Iterative Deepening Search, Depth Limited Search, Bidirectional Search dan Uniform Cost Search.
• Graph search Banyak permasalahan dari teori graph dapat diselesaikan dengan menggunakan algoritma pencarian (Wikipedia, Search Algorithm, 2006), seperti algoritma Djikstra, algoritma Kruskal, dan algoritma Prim. Algoritma ini merupakan kelanjutan dari algoritma tree.
• Informed search Dalam sebuah pencarian informed, heuristik yang spesifik ke masalah dijadikan
sebuah
pedoman.
Kebanyakan
algoritma
informed
ini
mengeksplorasikan tree. Pencarian ini meliputi Best First Search dan A*.
• Adversarial search Pencarian ini terdapat dalam permainan catur, di mana harus diperhitungkan langkah-langkah yang ada. Teknik ini sering menggunakan algoritma pencarian seperti algoritma Minimax dan Alpha Beta Pruning.
21 2.2
Teori Khusus yang Berhubungan dengan Algoritma Grover
2.2.1
Dasar Komputasi Kuantum
•
Bit Dalam komputasi klasik (Jr, Tarsem S. Purewall, 2004, p10), unit informasi
dasarnya berupa bit, yang bernilai 0 atau 1. Kebanyakan ilmu komputer klasik dipertimbangkan dengan merepresentasikan informasi sebagai string dari bit dan menampilkan operasi dalam bitstring yang mengubahnya ke bitstring lainnya. •
Qubit Qubit merupakan (Jr, Tarsem S. Purewall, 2004, p11) singkatan dari quantum
bit. Perbedaan antara bit dan qubit adalah bahwa qubit dapat merupakan kombinasi linear dari state
dan
. Perluasan kuantum dari sebuah bit adalah qubit, yang
merupakan sebuah unit vektor dalam ruang vektor dua dimensi:
State ini dikatakan sebagai superposisi dari state
dan
β, di mana α dan β adalah bilangan kompleks. State
ruang vektor 2 dimensi, di mana state dinamakan basis komputasi. State
dan
dengan amplitudo α dan adalah sebuah vektor dalam
membentuk basis ortonormal, yang
bukan merupakan vektor nol, tetapi merupakan
vektor pertama dalam basis. Untuk lebih jelasnya, (Jr, Tarsem S. Purewall, 2004, p1213) unit vektornya berupa:
22
Jika
dan
adalah peluang dan hanya ada 2 kemungkinan hasil, maka berlaku:
Untuk perhitungan norm dari
•
adalah:
Qubit Measurement
Dalam beberapa pengertian, (Jr, Tarsem S. Purewall, 2004, p14-15) sebuah qubit dalam state ini mengubah state 0 dan 1 secara bersamaan. Mekanika kuantum
menjelaskan bahwa ketika kita melakukan pengukuran dari sebuah qubit, kita akan mendapatkannya secara acak dalam state dasar dengan sebuah distribusi peluang berdasarkan pada amplitudo state yang berhubungan. Sebagai contoh, jika kita melakukan pengukuran sebuah qubit dalam state:
kita akan mendapatkan sebuah 0 dengan peluang | a0 |2 dan 1 dengan peluang | a1 |2 . •
Quantum Register
Persamaan dari sebuah kuantum bitstring adalah quantum register. Quantum register dari n qubit (Jr, Tarsem S. Purewall, 2004, p16) adalah sebuah unit vektor
dalam sebuah ruang vektor 2n dimensi . Sebagai contoh, sebuah quantum register dari 2 qubit adalah sebuah unit vektor dalam sebuah ruang vektor 4 dimensi.
23
•
Quantum Oracle
f(x) bernilai 1 jika x adalah solusi yang dicari dan f(x) bernilai 0 jika x bukan solusi, f(x) yang bernilai 1 hanya berjumlah satu untuk semua x yang ada. •
Quantum Algorithm
Algoritma kuantum adalah operator linear yang memodifikasi amplitudo dari qubit register, tetapi dengan panjang unit yang selalu sama. Transformasi linear ini
dikatakan sebagai kesatuan transformasi (unitary transformation). Transformasi ini dikatakan sebagai transformasi kesatuan jika dan hanya jika hasil kali representasi matriks dengan konjugasi transposnya sama dengan matriks identitas. Matriks representasi yang dimaksudkan adalah sebagai berikut:
24 2.2.2
Teori Dasar Algoritma Grover
Pada tahun 1996, Lov Grover (Grover, L.K, 1996, p212) menemukan sebuah algoritma menarik berdasarkan model perhitungan kuantum yang memecahkan masalah dengan hanya memerlukan jumlah query sebesar akar dari jumlah query sebelumnya. Karena model kuantum ini membuat query dalam sebuah state superposisi, dengan demikian algoritma ini dapat meningkatkan kecepatan aksesnya. Pada persoalan pencarian dengan exhaustive search, diberikan suatu fungsi f(x), x=0,1...,(N-1), di mana f(x) adalah fungsi yang akan selalu menghasilkan 0 untuk semua x, kecuali satu nilai x yang akan menghasilkan 1. Tujuan dari persoalan ini adalah mencari nilai x sehingga f(x) = 1. Ide dasar dari algoritma pencarian kuantum (algoritma Grover) adalah misalkan ada N buah status yang berkorespondensi dengan N item dalam suatu daftar tak terurut. Peluang untuk setiap status, bahwa status tersebut adalah yang dicari dalam daftar tersebut adalah 1/N. Dengan prinsip mekanika kuantum, dimungkinkan untuk meningkatkan nilai peluang status yang dicari karena pengaruh status yang lain (status yang bukan status yang dicari), sehingga pada akhirnya status yang dicari akan memiliki nilai peluang tertinggi. Prinsip mekanika kuantum juga memungkinkan untuk berada dalam lebih dari satu status, dan melakukan lebih dari satu komputasi dalam waktu yang bersamaan. Pada pencarian dengan probabilitas pada komputer klasik, peluang untuk status yang dicari akan meningkat sebesar 1/N setiap kali iterasi pada kalang for, sehingga dengan iterasi sebanyak N kali, akan ditemukan solusi dengan nilai peluang tertinggi. Kompleksitas algoritma ini adalah O(N).
25 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. Sesuai dengan penjelasan sebelumnya, amplitudo untuk status yang dicari akan meningkat sebesar 1/√N setiap kali iterasi pada kalang for, sehingga dengan iterasi sebanyak √N kali, akan ditemukan solusi dengan nilai peluang tertinggi, dengan peluang sebesar kuadrat dari amplitudo. Oleh karena itu, kompleksitas algoritma pencarian kuantum ini adalah O(√N). 2.2.3 Gambaran serta Langkah-Langkah Algoritma Grover
Berikut ini gambaran yang lebih lengkap mengenai algoritma pencarian kuantum. Misalkan dalam suatu persoalan terdapat sejumlah N status yaitu S1,S2,...SN, di mana N = 2n, status-status ini direpresentasikan dengan string n bit. Di antara statusstatus tersebut terdapat status unik Sv yang memenuhi C(Sν) =1, sedemikian hingga Sv merupakan status yang dicari, sementara status-status lain S, C(S)=0. Persoalannya adalah bagaimana mengidentifikasi status Sν, yang dijabarkan sebagai berikut: (i)
Inisialisasi sistem menjadi distribusi
(vektor baris aritmatika) Distribusi ini diturunkan dengan kompleksitas O(logN).
26 Untuk lebih jelasnya dapat dilihat pada gambar di bawah ini :
Gambar 2.2.3.1 Superposisi dari x State yang ada dapat direpresentasikan sebagai berikut:
(Σ menunjukkan deret aritmatika) (ii)
Ulangi operasi berikut sebanyak √N langkah: (a) Misalkan sistem berada dalam status S: jika C(S) = 1, rotasikan fase sebanyak π rad. jika C(S) = 0, abaikan. Misalkan dari gambar 2.2.3.1, record yang dicari adalah x = 10, oleh karena itu record tersebut akan berubah tanda seperti gambar berikut :
Gambar 2.2.3.2 Quantum Oracle
27 State dari titik ini adalah sebagai berikut:
(b) Aplikasikan transformasi difusi D yang didefinisikan oleh matriks D sbb:
Matriks D dapat direpresentasikan sebagai berikut :
D bisa diimplementasikan sebagai: D = WRW, di mana R adalah matriks rotasi dan W adalah matriks transformasi Walsh-Hadamard yang didefinisikan sbb:
di mana
adalah representasi biner dari i dan
titik dari dua string n bit,
dan
.
merupakan hasil kali
28 Walsh Hadamard Transform direpresentasikan sebagai berikut:
(termasuk matriks simetris)
Secara umum:
Walsh Hadamard Transform akan membangkitkan sebuah nilai q
antara antara 0 sampai (N-1) dengan amplitudo bernilai1/√N untuk masing-masing nomor. Tanda dari amplitudo ditentukan dengan perhitungan berikut. Bilangan q dan r direpresentasikan dengan biner. Jika jumlah dari posisi bit 1 yang berada pada q dan juga r adalah genap, maka tandanya positif. Sebaliknya, jika jumlahnya ganjil, maka tandanya negatif. Sebagai contoh misal q = 01110101 dan r = 10110111, maka posisi bit 1 yang sama pada kedua bilangan tersebut (dihitung dari least significant bit) adalah pada posisi 3, 4, 6, dan 8. Jumlahnya adalah 4
buah maka tanda dari amplitudonya adalah positif. (iii)
Ambil status yang dicari. Jika C(Sν) = 1 maka ada status unik Sν sedemikian hingga Sν merupakan status yang dicari dengan peluang ≥ ½. Langkah ini dapat dilihat pada gambar di bawah ini :
29
Gambar 2.2.3.3 Pencarian record dengan peluang ≥ ½ 2.2.4
Jumlah Iterasi Optimal
Jika diperhatikan pada efek masing-masing iterasi dengan amplitudo Sv, secara klasik seseorang akan berpikir bahwa dengan mengaplikasikan semakin banyak iterasi, maka kemungkinan sukses lebih baik. Hal ini tidak dapat dikatakan benar secara 100%, (Boyer, M., Brassard; G., Hyer, P.; dan Tapp, A,
1996, p9-10) karena adakala
probabilitas dari sukses tidak bertambah secara monoton dengan jumlah iterasi. Berikut adalah persamaan untuk amplitudo Sv dan semua state lain dalam beberapa iterasi dari algoritma, j. Persamaan ini akan mengambil nilai k0 = l0 = 1/√N:
Persamaan di atas menunjukkan bahwa kj adalah amplitudo Sv saat iterasi j, dan lj merupakan amplitudo dari semua state lainnya. Sudut θ didefinisikan dengan sin2θ= 1/ N , di mana dua persamaan di atas dapat ditunjukkan pula dengan:
30
Persamaan ini memberikan kemampuan untuk memecahkan masalah amplitudo untuk masing-masing state setealh beberapa kali iterasi, j. Grover menyatakan bahwa setelah M iterasi, probabilitas dari pengukuran Sv akan menghasilkan paling kecil ½. Dua persamaan di atas dapat digunakan untuk memecahkan masalah untuk M dan akan mendapatkan jumlah iterasi yang maksimal. Dinyatakan bahwa probabilitas dari kegagalan paling besar 1/N jika Π ⁄ 4θ iterasi yang dilakukan. Untuk N dalam jumlah besar, probabilitasnya Π⁄4 √N, dan jumlah ini merupakan jumlah iterasi yang dibutuhkan untuk algoritma Grover saat ini. 2.2.5
Solusi untuk Iterasi Tunggal
Dalam algoritma Grover, adakalanya dengan jumlah iterasi tunggal akan ditemukan solusi ketika t = N/4. Jika t = N/4 , maka θ = Π/6 . Dengan demikian (Boyer, M., Brassard, G.; Hyer, P.; dan Tapp, A, 1996, p11):
Hanya dengan satu kali iterasi, amplitudo dari state yang bukan solusi menjadi nol, oleh karena itu probabilitas untuk mendapatkan salah satu dari state ini juga nol.
31 2.2.6 Contoh Penerapan Algoritma Grover
Anggaplah bahwa Anda 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 2 sehingga iterasi hanya berlangsung dua 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 (Grover, L.K, 1996, p212) untuk bilangan q dan r dengan tanda sesuai dengan perhitungan yang telah dijelaskan sebelumnya: Tabel 2.2.4.1 Tabel amplitudo untuk setiap q dan r
Sesuai dengan algoritma pencarian kuantum yang telah dijelaskan sebelumnya, maka berikut ini adalah gambaran langkah-langkah proses pencarian dengan algoritma kuantum, dengan asumsi aran yang dicari berada pada indeks ke-2 (aran ke-3):
32
(i)
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].
(ii)
Diasumsikan nilai r yang dihasilkan pada langkah (i) 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]. (iii)
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. Untuk q = 0, maka ada 4 kemungkinan jalur yang dilalui: a) Sebelum langkah (iii), r = 0, setelah langkah(iii), r tetap 0. Hasil kali antara amplitudo v[0], dengan amplitudo saat q = 0 dan r = 0 (dilihat dari Tabel 2.2.4.1) adalah: 0.5 x 0.5 = 0.25. b) Sebelum langkah (iii), r = 1, setelah langkah(iii), r menjadi 0.Hasil kali antara amplitudo v[1], dengan amplitudo saat q = 0 dan r = 1 (dilihat dari Tabel 2.2.4.1) adalah: 0.5 x 0.5 = 0.25. c) Sebelum langkah (iii), r = 2, setelah langkah(iii), r menjadi 0. Hasil kali
33 antara amplitudo v[2], dengan amplitudo saat q = 0 dan r = 2 (dilihat dari Tabel 2.2.4.1) adalah: -0.5 x 0.5 = -0.25. d) Sebelum langkah (iii), r = 3, setelah langkah(iii), r menjadi 0. Hasil kali antara amplitudo v[2], dengan amplitudo saat q = 0 dan r = 3 (dilihat dari Tabel 2.2.4.1) adalah 0.5 x 0.5 = 0.25. 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. Pada langkah ini diperoleh v = [0.5, -0.5, 0.5, 0.5]. (iv)
Diasumsikan nilai r yang dihasilkan pada langkah (iii) 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]. (v)
Pada langkah ini dikerjakan operasi yang sama seperti pada langkah (iii), yaitu menghitung amplitudo untuk semua kemungkinan bilangan yang dibangkitkan oleh fungsi qrandom(4,r). Pada langkah ini diperoleh v = [0.0, 0.0, -1.0, 0.0].
Dari himpunan amplitudo v yang diperoleh pada langkah (v) dapat diketahui peluang untuk: r = 0 : (0.0)2 = 0 r = 1 : (0.0)2 = 0 r = 2 : (-1.0)2 = 1 r = 3 : (0.0)2 = 0 Dari peluang di atas dapat dilihat bahwa aran yang dicari terletak pada indeks ke-2.
34 2.3
Penelitian Relevan
Terdapat 3 penelitian yang akan dibahas dalam kaitannya dengan algoritma Grover, di antaranya: •
Optimalisasi Pencarian Data Dalam Basis Data Indeks Takterurut Menggunakan Algoritma Grover
Penelitian ini dilakukan oleh Ardian Nata Atmaja (mahasiswa ITB). Dalam penelitiannya, dia menggunakan simulasi algoritma Grover dengan jumlah N = 2" = 8 (n = 3, banyaknya qubit). •
Higher-order Pertubation Theory for Decoherence in Grover’s Algorithm
Penelitian ini dilakukan oleh Azuma, Hiroo (mahasiswa Universitas Tamagawa). Dalam penelitian ini, diasumsikan masing-masing qubit yang merupakan bagian dari sebuah register mengalami phase-flip error (σz error) dengan probabilitas p secara terpisah dalam setiap langkah algoritma. Misalkan sebuah n qubit operator dalam perulangan Grover diaplikasikan sebanyak M kali, diperluas dengan tenaga 2Mnp, dan diturunkan elemen dari matriks permintaan demi permintaan di bawah batas n. Kita mengambil relasi yang terjadi antar batas waktu dalam ekspansi pertubatif. Dengan relasi ini, dihitung permintaan yang lebih tinggi dari pertubatif secara efisien, kemudian diperluas jangkauan dari parameter pertubatif yang meliputi analisis yang dapat dipercaya. Kemudian dihitung elemen matriks secara numerik dengan metode ini, dan diturunkan nilai maksimum dari parameter pertubatif x yang algoritma tersebut dapatkan dengan pemberian peluang threshold Pth atau lebih. Kita mengambil sebuah kurva Xc sebagai sebuah fungsi Pth dengan mengulang perhitungan
35 numerik ini untuk titik-titik Pth dan dapatkan fakta: sebuah tangen dari kurva yang diambil di Pth =1 dihasilkan dari x= (8/5) (1- Pth ) , dan didapatkan xc
-
(8/5) loge Pth dekat dengan Pth =0 . •
Quantum Optical Implementation of Grover's Algorithm
Penelitian ini dilakukan oleh Marlan O. Scully dan M. S. Zubairy (mahasiswa Universitas A&M, Texas). Penelitian ini merepresentasikan sebuah skema untuk implementasi optik kuantum dari algoritma Grover yang didasarkan pada interaksi atom resonansi dengan medan klasik dan alat penghubung yang berhamburan dengan medan rongga penunjuk. Tujuan skema bergantung pada persiapan kedudukan yang tidak teratur dan dalam kedudukan teknologi saat ini.
