PERHITUNGAN ANALITIK ALGORITMA GROVER

TUGAS

QUANTUM COMPUTATION

“PERHITUNGAN ANALITIK ALGORITMA GROVER“

 

DISUSUN OLEH :

RAHMA INDAH SAFITRI (55415553)

KELAS 4IA05

FAKULTAS TEKNOLOGI INDUSTRI

TEKNIK INFORMATIKA

1.1           Latar Belakang

            Perkembangan hardware komputer pada saat ini telah ditunjukkan oleh meningkatnya jumlah microprocessor yang ada pada sebuah komputer. Demikian yang ditunjukkan oleh Intel Corporation dalam https://www.intel.com/ pressroom/ kits/ events /moores_law_40th /. Perkembangan software juga ditunjukkan dengan kemampuan komputasi sebuah komputer yang semakin cepat, meskipun komputer yang ada sekarang masih beroperasi bersadarkan paradigma klasik atau serial, sehingga sangatlah beralasan untuk mengembangkan sebuah komputer dengan paradigma kuantum, hal ini dikarenakan ruang Hilbert yang digunakan oleh mekanika kuantum sangatlah besar, sehingga beberapa permasalahan yang sulit pada komputer klasik dapat diselesaikan. Selain itu salah satu fitur yang ditawarkan oleh mekanika kuantum adalah prinsip superposisi yang memungkinkan evaluasi dari semua keadaan dilakukan pada waktu yang bersamaan. Fitur ini juga yang membuat komputer kuantum lebih powerfull.

            Salah satu implementasi Quantum Computing sebagai sebuah model dalam paradigma komputasi yang baru adalah algoritma pencarian database dengan menggunakan algoritma Grover. Secara teori telah ditunjukkan bahwa pencarian dengan algoritma ini menunjukkan hasil yang signifikan dalam pencarian data pada sebuah database, untuk itulah pada penelitian ini bagaimanakan hasil dari simulasi dari algoritma tersebut terhadap pencarian sebuah data pada database

1.2           Metode yang digunakan

Dalam artikel ini digunakan 2 metode yaitu dengan menggunakan Qubit dan Gerbang Kuantum. Berikut ini penjelasan dari masing-masing metode

1.     Qubit

      Data - data pada komputer direpresentasikan dalam bentuk bilangan biner yang disebut bit, yang bernilai 0 atau 1. Pada komputer klasik, kita dapat menuliskan sejumlah 2n kemungkinan dari data - data tersebut. Sebagai ilustrasi, misalkan data 5 bit dapat ditulis ke dalam 32 kemungkinan. Karena kinerja pada komputer klasik berjalan secara serial, maka pada setiap waktu kita hanya akan mendapatkan satu dari sejumlah kemungkinan yang ada. Sehingga, untuk semua kemungkinan, kita melakukan sejumlah 2n kali perhitungan. Berbeda dengan komputer klasik, pada komputer kuantum representasi data dituliskan dalam bentuk state vektor yang disebut qubit ( quantum bit). Sebuah qubit dapat berada pada keadaan (state). ebuah qubit dapat berada pada keadaan (state) |0i atau |1i, akan tetapi dapat juga berada pada keadaan superposi-si

|Ψi =α|0i+β|1i

dengan α dan β merupakan bilangan kompleks. Superposisi ini yang memungkinkan kita untuk menuliskan semua keadaan dalam satu kombinasi linier. Superposisi ini juga yang memungkinkan kita untuk mengevaluasi semua kemungkian dalam satu kali perhitugan. Pada ruang vektor (1) dapat ditulis

sehingga vektor basis |0i dan |1i masing-masing

               

Sebuah qubit dapat direalisasikan dari polarisasi photon, mengarahkan spin inti yang berada pada medan magnet uniform, atau dari dua keadaan (ground state dan eksitasi) dari sebuah elektron yang mengorbit inti.

2.     Gerbang Kuantum

Sebuah gerbang kuantum adalah analog dengan gerbang logika pada komputer klasik. Gerbang kuantum adalah komponen dasar dari algoritma kuantum. Perbedaan dalam konteks klasik dan kuantum adalah gerbang kuantum diimplementasikan secara uniter seperti

UU^† =I         

Salah satu gerbang kuantum yang sering digunakan adalah gerbang Hadamard

  

yang biasa digunakan untuk membentuk superposisi dari dua keadaan seperti berikut

Komputasi Kuantum dapat diimplementasikan berdasarkan serangkaian gerbang kuantum yang beroperasi secara uniter. Dalam mekanika kuantum operasi uniter ini diperlukan agar probabilitas sistem setelah operasi tidak beruba dan sifat ini digunakan sebagai dasar operasi berkebalikan pada Komputasi Kuantum selain prinsip superposisi yang menjadikan Komputasi Kuantum lebih powefull terhadap komputer klasik. Salah satu contoh sukses besar Komputasi Kuantum adalah algoritma Grover pada masalah pencarian data dari sejumlah entri tak terurut dari suatu basis data dengan kompleksitas waktu . Pada makalah ini kami tinjau ulang tentang algoritma Grover tersebut, dan dibuat aplikasi untuk mensimulasikan algoritma ini dalam bahasa pemrograman Java. Bagian teori makalah ini adalah tinjauan ulang mengenai algoritma Grover, bagian simulasi berisi tentang simulasi dalam bahasa pemrograman Java, dan bagian hasil dan diskusi menjelaskan hasil dari simulasi yang diperoleh.

1.3           Analisa

       Pada pencarian sejumlah M data suatu basis data sepanjang N = 2ⁿ entri data tak terurut, algoritma Grover terdiri dari dua register. Register pertama merupakan superposisi semua kemungkinan state vektor, sementara register kedua merupakan register yang mengkodekan solusi. Secara sederhana, algoritma Grover dapat ditunjukkan sebagai berikut :

1.     Siapkan sistem dalam keadaan superposisi

2.     Lakukan Operasi Perulangan untuk operasi:

a.    

b.    

3.     Lakukan pengukuran terhadap |Ψ⁰⁰i

Perulangan akan behenti jika |Ψ⁰⁰i=|ξi, jika tidak maka ulangi langkah 2.

Oracle O pada persamaan (9) didefinisikan sebagai

O ≡I−2|ξihξ|     

yang berfungsi mem-flip-kan state vektor kepada solusi. Sementara operator D pada persamaan didefinisikan seperti

D ≡2|ΨihΨ|−I  

atau dapat ditulis dalam bentuk matrik

                                         D

Misalkan kita akan mencari sebuah data dengan index          ^Tpada ruang vektor N = 2³ = 8. Keadaan sistem dimulai dari

|0i =1|000i

0

0

0

Penerapan gerbang Hadamard pada sistem memberikan hasil

|Ψi =H|000i

untuk j merupakan nilai pada bilangan biner sehingga

                                                                                                                         (16)

Sesuai langkah pada Algoritma Grover maka Oracle yang kita gunakan adalah

O =  1 0 0                          0 0 0

             0 1 0              − 2      0 1 0

                                              0 0 1                          0 0 0

      1  0  0

=    0 −1 0

      0  0  1

Sehingga penerapan Oracle pada sistem memberikan

      

Setelah itu, kita kerjakan operator Difusi pada keadaan sistem terakhir

 (19)

Substitusi (16) pada (19) maka memberikan hasil

     4√ 2       j = 0            4 √ 2

Sampai di sini selesailah iterasi pertama dengan amplitudo solusi adalah   

   78.125

            Ulangi prosedur yang sama sehingga memberikan hasil

       8 √2          j = 0           8 √2

dengan amplitudo solusi adalah 94.53125.

1.4           Tanggapan

       Algoritma kuantum merupakan algoritma yang dikembangkan berdasarkan paradigma mekanika kuantum. Algoritma Grover yang merupakan salah satu algoritma tersebut, memberikan hasil yang signifikan dalam suatu pencarian data. Selain perhitungan secara analitik sebagaimana diilustrasikan di atas, perhitungan numerik juga memberikan hasil yang signifikan sebagaimana pada uraian berikut:

Pada pencarian data dengan indek |3i = 0 0 0 1 )  ^T pada basis data dengan jumlah data N = 4, dengan hasil bahwa state vektor yang dicari ditemukan paad iterasi ke 1. Hasil simulasi untuk jumlah data N = 4 sampai N = 4096 diberikan oleh Tabel.1. Tabel 1. Hasil simulasi algoritma Grover.

DAFTAR PUSTAKA

http://jurnal.radenfatah.ac.id/index.php/jifp/article/view/2798/1901 diunduh pada tanggal 7 Juli 2019 pukul 19:00