## Perhitungan Analitik Algoritma Grover
Suhadi ∗
∗ Dosen Pendidikan Fisika, Fakultas Ilmu Tarbiyah dan Keguruan, Universitas Islam Negeri Raden Fatah Palembang, 30126, Indonesia suhadi@radenfatah.ac.id

## Abstrak
Telah dilakukan perhitungan secara analitik ulang algoritma Grover pada komputasi kuantum untuk pencarian data dalam suatu basis data. Selain itu, dengan hasil juga diberikan hasil dari perhitungan numerik bahwa pencarian/query pada basis data data tak terurut dengan kompleksitas waktu O √ N .

## Latar Belakang
Perkembangan hardware komputer pada saat ini telah ditunjukkan oleh meningkat- nya jumlah microprocessor yang ada pada sebuah komputer. Demikian yang ditunjukk- an oleh Intel Corporation dalam https://www.intel.com/ pressroom/ kits/ events /moores_law_40th /. Perkembangan software juga ditunjukkan dengan kemam- puan komputasi sebuah komputer yang se- makin cepat, meskipun komputer yang ada sekarang masih beroperasi bersadarkan pa- radigma klasik atau serial, sehingga sangat- lah beralasan untuk mengembangkan sebu- ah komputer dengan paradigma kuantum, hal ini dikarenakan ruang Hilbert yang di- gunakan oleh mekanika kuantum sangatlah besar, sehingga beberapa permasalahan yang sulit pada komputer klasik dapat dise- lesaikan. Selain itu salah satu fitur yang ditawarkan oleh mekanika kuantum ada- lah prinsip superposisi yang memungkink- an evaluasi dari semua keadaan dilakukan pada waktu yang bersamaan. Fitur ini ju- ga yang membuat komputer kuantum lebih powerfull .
Salah satu implementasi Quantum Com- puting sebagai sebuah model dalam paradi- gma komputasi yang baru adalah algoritma pencarian database dengan menggunakan algoritma Grover. Secara teori telah ditun- jukkan bahwa pencarian dengan algoritma ini menunjukkan hasil yang signifikan dalam pencarian data pada sebuah database, un- tuk itulah pada penelitian ini bagaimanak- an hasil dari simulasi dari algoritma tersebut terhadap pencarian sebuah data pada data-
base ?

## Qubit
Data - data pada komputer direpresentasik- an dalam bentuk bilangan biner yang dise- but bit , yang bernilai 0 atau 1. Pada kom- puter klasik, kita dapat menuliskan sejum- lah 2 n kemungkinan dari data - data terse- but. Sebagai ilustrasi, misalkan data 5 bit dapat ditulis ke dalam 32 kemungkinan. Ka- rena kinerja pada komputer klasik berjalan secara serial, maka pada setiap waktu ki- ta hanya akan mendapatkan satu dari se- jumlah kemungkinan yang ada. Sehingga, untuk semua kemungkinan, kita melakukan sejumlah 2 n kali perhitungan. Berbeda de- ngan komputer klasik, pada komputer kuan- tum representasi data dituliskan dalam ben- tuk state vektor yang disebut qubit (quantum bit) . Sebuah qubit dapat berada pada kea- daan ( state ). ebuah qubit dapat berada pa- da keadaan ( state ) | 0 i atau | 1 i , akan tetapi dapat juga berada pada keadaan superposi- si
| Ψ i = α | 0 i + β | 1 i (1)
dengan α dan β merupakan bilangan kom- pleks. Superposisi ini yang memungkinkan kita untuk menuliskan semua keadaan da- lam satu kombinasi linier. Superposisi ini ju- ga yang memungkinkan kita untuk menge- valuasi semua kemungkian dalam satu kali perhitugan. Pada ruang vektor (1) dapat di-
Jurnal Ilmu Fisika dan Pembelajarannya (JIFP), Vol. 2, No.1 Juni 2018, 1-5
tulis
| Ψ i = α β = α 0 + 0 β = α 1 0 + β 0 1 (2)
sehingga vektor basis | 0 i dan | 1 i masing- masing
| 0 i = 1 0 (3) | 1 i = 0 1 (4)
Sebuah qubit dapat direalisasikan dari po- larisasi photon , mengarahkan spin inti yang berada pada medan magnet uniform , atau dari dua keadaan ( ground state dan eksita- si) dari sebuah elektron yang mengorbit inti.

## Gerbang Kuantum
Sebuah gerbang kuantum adalah analog dengan gerbang logika pada komputer kla- sik. Gerbang kuantum adalah komponen dasar dari algoritma kuantum. Perbedaan dalam konteks klasik dan kuantum adalah gerbang kuantum diimplementasikan seca- ra uniter seperti
UU † = I (5)
Salah satu gerbang kuantum yang sering di- gunakan adalah gerbang Hadamard
H ≡ 1 √ 2 1 1 1 − 1 (6)
yang biasa digunakan untuk membentuk su- perposisi dari dua keadaan seperti berikut
H | 0 i = 1 √ 2 1 1 1 − 1 1 0 = 1 √ 2 1 1 = 1 √ 2 1 0 + 0 1 = 1 √ 2 {| 0 i + | 1 i} (7)
H | 1 i = 1 √ 2 1 1 1 − 1 0 1 = 1 √ 2 1 − 1 = 1 √ 2 1 0 − 0 1 = 1 √ 2 {| 0 i − | 1 i} (8)
Komputasi Kuantum dapat diimplemen- tasikan berdasarkan serangkaian gerbang kuantum yang beroperasi secara uniter. Da- lam mekanika kuantum operasi uniter ini diperlukan agar probabilitas sistem setelah operasi tidak beruba dan sifat ini digunak- an sebagai dasar operasi berkebalikan pa- da Komputasi Kuantum selain prinsip super- posisi yang menjadikan Komputasi Kuantum lebih powefull terhadap komputer klasik. Sa- lah satu contoh sukses besar Komputasi Ku- antum adalah algoritma Grover pada masa- lah pencarian data dari sejumlah entri tak terurut dari suatu basis data dengan kom- pleksitas waktu . Pada makalah ini kami tinjau ulang tentang algoritma Grover terse- but, dan dibuat aplikasi untuk mensimulasik- an algoritma ini dalam bahasa pemrogram- an Java. Bagian teori makalah ini adalah tinjauan ulang mengenai algoritma Grover, bagian simulasi berisi tentang simulasi da- lam bahasa pemrograman Java, dan bagian hasil dan diskusi menjelaskan hasil dari si- mulasi yang diperoleh.

## Algoritma Grover
Pada pencarian sejumlah M data suatu ba- sis data sepanjang N = 2 n entri data tak ter- urut, algoritma Grover terdiri dari dua regis- ter. Register pertama merupakan superpo- sisi semua kemungkinan state vektor, se- mentara register kedua merupakan register yang mengkodekan solusi. Secara sederha- na, algoritma Grover dapat ditunjukkan se- bagai berikut :
1. Siapkan sistem dalam keadaan super- posisi
2. Lakukan Operasi Perulangan untuk operasi :
Jurnal Ilmu Fisika dan Pembelajarannya (JIFP), Vol. 2, No.1 Juni 2018, 1-5
(a)
Ψ 0 = O | Ψ i (9)
(b)
Ψ 00 = D Ψ 0 (10)
3. Lakukan pengukuran terhadap | Ψ 00 i
Perulangan akan behenti jika | Ψ 00 i = | ξ i , jika tidak maka ulangi langkah 2.
Oracle O pada persamaan (9) didefinisik- an sebagai
O ≡ I − 2 | ξ i h ξ | (11)
yang berfungsi mem-flip-kan state vektor ke- pada solusi. Sementara operator D pada persamaan (10) didefinisikan seperti
D ≡ 2 | Ψ i h Ψ | − I (12)
atau dapat ditulis dalam bentuk matrik
D =       2 N − 1 2 N · · · 2 N
2 N 2 N − 1 · · · .. .
.. . .. . . .. .. . 2 N 2 N · · · 2 N − 1       (13)
Misalkan kita akan mencari sebuah data dengan index | ξ i = | 2 i = 0 1 0 T pa- da ruang vektor N = 2 3 = 8 . Keadaan sistem dimulai dari
| 0 i = 1 | 000 i = 1   0 0 0   (14)
Penerapan gerbang Hadamard pada sistem memberikan hasil
| Ψ i = H | 000 i = 1 2 √ 2 7 ∑ j = 0 | j i (15)
untuk j merupakan nilai pada bilangan biner sehingga
| Ψ i = 1 2 √ 2 111 ∑ j = 000 | j i = 1 2 √ 2 ( | 000 i + | 001 i
+ | 010 i + | 011 i + | 100 i + | 101 i + | 110 i + | 111 i ) (16)
Sesuai langkah pada Algoritma Grover ma- ka Oracle yang kita gunakaan adalah
O =   1 0 0 0 1 0 0 0 1   − 2   0 0 0 0 1 0 0 0 0   =   1 0 0 0 − 1 0 0 0 1   . (17)
Sehingga penerapan Oracle pada sistem memberikan
Ψ 0 = 1 2 √ 2 ( | 000 i + | 001 i .
− | 010 i + | 011 i + | 100 i
+ | 101 i + | 110 i + | 111 i ) (18)
Setelah itu, kita kerjakan operator Difusi pa- da keadaan sistem terakhir
[ 2 | Ψ i h Ψ | − I ] Ψ 0 =
[ 2 | Ψ i h Ψ | − I ] | Ψ i − 2 2 √ 2 | 010 i = 1 2 | Ψ i + 1 √ 2 | 010 i (19)
Substitusi (16) pada (19) maka memberikan hasil
Ψ 00 = 1 4 √ 2 7 ∑ j = 0 j 6 = 2 | j i + 5 4 √ 2 | 010 i . (20)
Sampai di sini selesailah iterasi pertama dengan amplitudo solusi adalah
5 4 √ 2 2 = 78 . 125 . Ulangi prosedur yang sama sehing- ga memberikan hasil
Ψ 00 = − 1 8 √ 2 7 ∑ j = 0 j 6 = 2 | j i + 11 8 √ 2 | 010 i . (21)
dengan amplitudo solusi adalah 11 8 √ 2 2 = 94 . 53125 .

## Kesimpulan
Algoritma kuantum merupakan algoritma yang dikembangkan berdasarkan paradi- gma mekanika kuantum. Algoritma Grover yang merupakan salah satu algoritma ter- sebut, memberikan hasil yang signifikan da- lam suatu pencarian data. Selain perhitung- an secara analitik sebagaimana diilustrasik- an di atas, perhitungan numerik juga mem- berikan hasil yang signifikan sebagaimana pada uraian berikut :
Pada pencarian data dengan indek | 3 i = 0 0 0 1 T pada basis data dengan jumlah data N = 4 , dengan hasil bahwa sta- te vektor yang dicari ditemukan paad iterasi ke 1. Hasil simulasi untuk jumlah data N = 4 sampai N = 4096 diberikan oleh Tabel.1. Ta- bel 1. Hasil simulasi algoritma Grover.
Adapun data pada tabel tersebut dapat dilihat pada Gambar 1.
Gambar 1 merupakan plot dari itera- si yang diperlukan pada simulasi algortima Grover untuk berbagai pembulatan amplitu- di state vektor yang dicari. Dari gambar ter- lihat untuk pembulatan A > 0 , 65 , A > 0 , 85 dan A > 0 , 95 jumlah iterasi yang diperlukan lebih kecil dari O √ N , akan tetapi untuk probabilitas sukses menemukan data 100% ,
untuk jumlah data 4 ≤ N < 128 jumlah iterasi
yang dibbutuhkan lebih besar dari O √ N , sedangkan untuk jumlah data N ≥ 256 jum- lah iterasi yang diperlukan ≈ O √ N . Dari hasil simulasi yang telah dilakukan dapatlah disimpulkan bahwa untuk kesuksesan pen- carian 100% , algoritma Grover berhasil dite- rapkan untuk pencarian data dengan jumlah data yang besar khusunya untuk N ≥ 256 .

## Pustaka
[1] http://www.intel.com/ pressroom/ kits/ events/ moores_law_40th/
[2] Yung Man-Hong, Whitfield J D., Boi- xo S, Tempel D G. and Aspuru-Guzik A, Introduction to Quantum Algori- thms for Physics and Chemistry, arX- iv:1203.1331v1 [quant-ph], 2012.
[3] Das S and Kunstatter Q, Adiabatic quantum computation and Deutsch’s algo- rithm, Phy. Rev. A 65, 062310, 2002.
[4] Bang J, Yoo S, Lim J, Ryu J, Lee C and Lee J, Quantum heuristic algo- rithm for traveling salesman problem, arXiv:1004.4124v2 [quant-ph], 2010.
[5] McMahon D, Quantum Computing Explained, John Wiley & Sons Inc. 2008.
[6] Nielsen M A. and Chuang I L., Quantum Computation and Quantum Informa- tion 10th Anniversary Edition, Cambridge University Press, 2010.
[7] Pinski S, Samson J, Adiabatic Qu- antum Computing, arXiv:1108.0560v1 [physics.pop-ph], 2011.
[8] Dasgupta S., Papadimitriou C.H., and Vazirani U.V., Algorithms, 2006, ht- tp://www.cs.berkeley.edu / ∼ vazirani/ al- gorithms.html.
[9] Barahona F, On the computational complexity of Ising spin glass models, J. Phys. A 15, 3241, 1982.
[10] Shor P.W., Polynomial-Time Algorithms for Prime Factorization and Discrete
Logarithms on a Quantum Computer, arXiv:quant-ph/9508027v2, 1996.
[11] Harrow A W., Hassidim A and Lloyd S, Quantum Algorithm for Linear Sys- tems of Equations, Phys. Rev. Lett, 103, 150502, 2009.
[12] Pittenger A O., An Introduction to Quantum Computing Algorithms, Birkhäus- er Boston, 2000.
[13] Perry R T., The Temple of Quantum Computing Version 1.2, 2010.
[14] Farhi E, Goldstone J, Gutmann S and Sipser M, Quantum Computation by Adiabatic Evolution, arXiv:quant- ph/0001106v1, 2000.
[15] Cullimore M., Everitt M.J., Ormerod M. A., Samson J.H., Wilson R.D. and Zagoskin A.M., Relationship between minimum gap and success probabi- lity in adiabatic quantum computing, arXiv:1107.4034v2 [quant-ph], 2012.