Indonesian Journal of Physics Kontribusi Fisika Indonesia
Vol. 14 No.4, Oktober 2003
Pencarian Data Dengan Indeks Takterurut Menggunakan Algoritma Kuantum Freddy P. Zen, Ardian Nata Atmaja, dan Susanto Sigit Laboratorium Fisika Teoretik, Departemen Fisika, Institut Teknologi Bandung, Jl. Ganesa No.10, Bandung 40132 email:
[email protected];
[email protected];
[email protected]
Abstrak Dalam tulisan ini dibahas algoritma Grover untuk mencari data dalam suatu basis data. Untuk basis data dengan N indeks takterurut satu-satunya cara dalam mencari data adalah dengan memeriksa setiap indeks, kemudian dicocokan dengan data yang dicari dengan jumlah oracle yang digunakan O(N ) . Dengan menggunakan algoritma pencarian Grover dan sifat paralelisme quantum maka pencarian dalam indeks takterurut akan menggunakan oracle sebanyak O ( N ). Miy klasik. Kata kunci: algoritma Grover, basis data, oracle, paralelisme quantum Abstract This paper will discuss about Grover algorithm for searching a record in a database. There is only one way to search a record in a database with N unordered indices, which is by checking each index and comparing with the record that will be searched. This classical algorithm uses an oracle as much O(N ) . By using Grover algorithm and quantum parallelism, which will solve the searching problem with uses an oracle as much O ( N ). Grover algorithm is more efficient compared to the classical algorithm if the N number is bigger. Keywords: Grover algorithm, database, oracle, quantum parallelism
⎧⎪1 bila x = x0 f ( x) = ⎨ ⎪⎩0 bila x ≠ x0
1. Pendahuluan Sistem pencarian data dalam sebuah basis data merupakan kebutuhan yang sangat penting bagi kemajuan sebuah perusahaan. Kebutuhan akan informasi yang cepat mengakibatkan dinamika basis data yang semakin cepat pula. Untuk itu jarang sekali indeks-indeks dalam basis data tersebut diurutkan terlebih dahulu, karena mengingat waktu yang dibutuhkan untuk pengurutan indeks-indeks itu sendiri cukup lama meskipun pencarian data akan membutuhkan waktu relatif lebih singkat dibandingkan dengan indeks-indeks yang tak terurut.
(1)
dengan x adalah indeks-indeks yang berada dalam database dan x0 merupakan indeks dari data yang akan dicari2). Untuk jumlah N yang sangat besar, algoritma pencarian klasik seperti yang disebut sebelumnya, maka akan membutuhkan pemakaian oracle berulangkali dengan rata-rata 0.5N dan probabilitas rata-rata 0.5 untuk mendapatkan data yang dicari3).
2. Komponen-komponen Algoritma Quantum
2.2 Efisiensi Algoritma
2.1 Oracle
Pada umumnya algoritma yang menghasilkan proses iterasi yang tidak lebih besar dari pangkat polinomial masukan datanya, dalam hal ini N, bisa dikatakan sudah efisien4). Seperti yang telah diketahui bahwa proses pencarian data secara klasik berada dalam O ( N ) , jadi bisa dikatakan sudah efisien. Pencarian data dalam indeks takterurut dapat dibuat lebih efisien menggunakan komputer quantum dengan algoritma Grover yang secara umum berada dalam O ( N ). Algoritma Grover memanfaatkan informasi atau data dalam bentuk qubit atau quantum bit yang merupakan state dari ruang Hilbert dimensi dua5). Qubit sendiri memiliki sifat-sifat khas yang tidak dimiliki bit pada umumnya, yaitu superposisi dan paralelisme
Dalam pencarian data dengan N buah indeks takterurut maka satu-satunya cara yang paling efisien adalah dengan memeriksa setiap indeks data dalam basis data dan mencocokan dengan data yang akan dicari1). Proses pemeriksaan dalam basis data ini memerlukan sebuah Oracle yang merupakan fungsi pemetaan yang memberikan hasil keluaran ‘YES’ bila data yang dicari ada dalam indeks tersebut dan ‘NO’ bila sebaliknya. Fungsi oracle secara detail tidak dapat diketahui, ia hanya merupakan sebuah pemetaan yang secara sederhana digambarkan dalam persamaan di bawah ini.
169
170
IJP Vol. 14 No. 4, 2003
quantum6). 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 bulat7). Informasi dalam qubit dapat dimanipulasi dengan menggunakan sebuah operator uniter8). Hal ini untuk menjaga probabilitas total dari qubit tersebut agar nilainya tetap baik sebelum maupun sesudah proses manipulasi. Karena untuk menjaga nilai probabilitas dari qubit yang tetap, maka dapat dikatakan operator uniter adalah sebuah operator rotasi dalam ruang Hilbert6).
diketahui. Informasi yang dapat diketahui dari Oracle ini hanyalah masukan dan keluarannya saja. Apabila komputer kuantum diketahui mempunyai suatu Oracle sebagai fungsi f , yang memetakan F2n ke
F2n dan ada suatu bilangan c dengan: f ( x) = f ( y ) ↔ x = y + c⎛⎜ mod F2n ⎞⎟ ⎝ ⎠
maka bilangan c dapat ditemukan dengan algoritma Simon. Penjumlahan ini bersifat biner dan pada dasarnya fungsi yang diberikan adalah suatu fungsi yang periodik dalam F2n dengan periode c. Apabila dipilih fungsi f apa pun yang memenuhi criteria (3.1) maka komputer klasik akan mengerjakan persoalan di atas dengan melakukan komputasi sebanyak fungsi O(2n/2) evaluasi untuk mendapatkan c. Sebelum masuk ke dalam pembahasan algoritma Simon, perlu diperkenalkan gerbang Hadamard yang merupakan bagian penting dalam algoritma tersebut. Representasi matriks dari gerbang Hadamard adalah
2.3 Operator Inversi
Salah satu operator uniter yang digunakan dalam algoritma Grover adalah operator Inversi yang didefinisikan sebagai berikut. I
x0
= I − 2 x0 x0
(2)
dengan I menyatakan operator identitas. Operator inversi bila tersebut akan menghasilkan keluaran − x
H=
0
dioperasikan terhadap ket x0 dan tetap untuk ket
x
ψ
= I −2ψ ψ
2k / 2
∑ (− 1)
a.b
Vb
(6)
b =0
dengan
maka ada sebuah
a.b =
operator inversi
I
(5)
2 k −1
1
H ⊗k (Va ) =
secara umum dapat dinyatakan sebagai percerminan pada sebuah hyperplane yang tegak lurus terhadap ket x 0 2). ψ
1 ⎛1 1 ⎞ ⎜⎜ ⎟⎟ 2 ⎝ 1 − 1⎠
transformasi Hadamard untuk setiap qubit k untuk suatu vector Va dalam F2n adalah:
lainnya ( x ≠ x0 ) . Dapat dilihat bahwa fungsi oracle berada dalam operator I x0 > ini. Operator inversi I x0 >
Secara umum untuk sembarang ket
(4)
∑a
i
(mod 2)
bi
(7)
i
(3)
adalah inner product biner antara a dan b. Sebagai awal algoritma Simon, digunakan dua register n-qubit V0, yaitu V0⊗V0. Langkah pertama adalah mengubah register pertama V0 menjadi bentuk superposisi orthogonal dari semua string biner terurut sepanjang n sehingga komputer berada dalam keadaan:
yang merupakan pencerminan pada hyperplane yang tegak lurus terhadap ket ψ . 3. Algoritma Quantum 3.1 Algoritma Simon
2 −n / 2
Algoritma Simon digunakan untuk mendapatkan periode dari sebuah Oracle yang diberikan. Algoritma ini menentukan proses yang harus dilakukan komputer kuantum sehingga hasil yang diharapkan dapat ditemukan secara efisien dan dengan biaya komputasi seminimal mungkin. Kelebihan algoritma ini dibandingkan dengan komputer digital adalah kemampuannya mengolah datadata dalam ruang vektor secara simultan dan parallel (Quantum Paralellism). Semua angka yang ada dimungkinkan untuk keluar sebagai hasil komputasi kuantum, akan tetapi hasil yang diharapkan keluar dengan kebolehjadian yang besar. Oracle adalah pemetaan data sebagai subrutin komputer kuantum. Pemetaan ini bersifat faithfull yaitu pemetaan satu-satu f , dan dianggap sebagai kotak hitam karena isi dan kerja Oracle secara detil tidak dapat
2 n −1
∑V
x
⊗ V0
.
(8)
x =0
Langkah kedua adalah meletakkan keluaran Oracle f dalam register kedua sehingga komputer berada dalam keadaan : 2
−n / 2
2 n −1
∑V
x
⊗ V f ( x) .
(9)
x =0
Langkah di atas adalah trasformasi klasik terbalikkan selama nilai x masih disimpan di memori dan dengan demikian merupakan transformasi uniter. Langkah ketiga adalah mentransformasi Fourier register pertama sehingga keadaan komputer menjadi 2 −n / 2
2 n −1 2 n −1
∑ ∑ (− 1) x =0
170
y =0
x. y
V y ⊗ V f ( x)
(10)
IJP Vol. 14 No. 3, 2003
171
akhirnya pengukuran keadaan komputer berada dalam basis Vi⊗Vj . Dalam kerja Oracle sebagai fungsi periodik, ada dua nilai masukan x yang akan menghasilkan nilai f(x) yang sama, yaitu nilai x dan x+c. Keadaan Vy⊗Vf(x) dalam penjumlahan di atas didapatkan dengan kebolehjadian sama dengan kuadrat amplitudonya, yaitu:
2
− 2n
((− 1)
)
( x + c ). y 2
+ (− 1)
x. y
(11) -2n+2
atau 0 Kebolehjadian ini dapat bernilai 2 bergantung kepada nilai y.c, apakah 0 atau 1. Pengukuran di atas, dengan y.c=0, menghasilkan nilai y yang random. Proses ini memerlukan waktu komputasi O(n). Apabila prosedur di atas dilakukan sebanyak O(n) kali maka semakin dapat dipastikan bahwa nilai yang diperoleh adalah periodanya. Secara keseluruhan, waktu komputasi yang diperlukan adalah O(n2+nF), dengan F adalah biaya komputasi yang diperlukan dalam mengevaluasi Oracle, dengan demikian untuk kasus ini, komputasi kuantum lebih efisien dari pada komputasi klasik yang memerlukan waktu komputasi O(2n/2). 3.2 Langkah-langkah Algoritma Grover
Langkah pertama dalam algortima Grover untuk N = 2 n buah indeks adalah mempersiapkan sebuah ket awal ψ 0 yang merupakan sebuah superposisi dari basis yang dibentuk oleh n-qubit yang dapat dinyatakan seperti di bawah ini. ψ0 = H 0 =
1
Q=I
denga ket ψ 0⊥ ψ0
dengan nilai
probabilitas 1/N. Prinsip kerja dari algoritma Grover adalah mentransformasikan atau merotasikan ket ψ 0 agar mendekati
x0 .
ket
Hal
ini
dilakukan
dengan
terhadap ket
0
H −1 I
x0
(13)
. Operator Q dapat ditulis sebagai
ψ0
berikut: Q = −I
ψ0
I
x0
(14)
Dengan memandang kerja operator inversi dalam bidang Euclidean yang dibentuk oleh ket ψ 0 dan x0 (saling bebas linier dengan
x 0 ψ 0 ), maka operator
inversi akan bersifat I
ψ 0⊥
= −I
ψ0
sehingga dapat ditulis
(15)
yang
x0⊥
ke ket x0
yang dapat
dinyatakan sebagai 2β. Proses pengerjaan operator uniter Q disebut juga penguatan amplitudo probabilitas, karena setiap kali digunakan akan menaikan amplitudo probabilitas ket x0 yang dicari dan sebagai timbal baliknya akan menurunkan amplitudo probabilitas ket-ket lainnya. Akan tetapi berapa kali operator uniter Q dikerjakan pada ket ψ 0 agar nilai probabilitas ket x0 dalam ket
ψ0
lebih besar dari 0.5. Untuk pemecahannya
pertama-tama kita pandang ket
ψ0
dalam bidang
Euclidean dengan bentuk berikut ini. ψ 0 = sin β x 0 + cos β x 0⊥
(17)
Setelah kita kerjakan operator uniter Q sebanyak k kali maka ket akhirnya adalah. ψk = Qk ψ0 = sin[(2k + 1)β] x 0
(18)
+ cos[(2k + 1)β] x 0⊥
Karena kondisi berhenti bila probabilitas ket x0 mendekati 1, maka dapat diambil suatu kondisi sin[(2k + 1)β] ≈ 1
(19)
jadi,
[(2k + 1)β] ≈
mengerjakan operator
Q = − HI
dalam bidang Euclidean.
yang dibentuk oleh ket
1)
ψ0
adalah ket yang tegak lurus terhadap ket
dilanjutkan pencerminan terhadap ket x0 dalam bidang Euclidean. Besarnya sudut rotasi sebuah ket akibat dikerjakan sebuah operator uniter Q adalah dua kali sudut
k =0
yang terkandung juga dalam ket awal
(16)
x0
dipandang sebagai percerminan terhadap ket x0⊥
(12)
dengan H adalah operator uniter Hadamard dari n-qubit. Nilai indeks yang akan dicari dinyatakan sebagai ket x0
I
Jadi secara keseluruhan operator uniter Q dapat
N −1
∑k N
ψ 0⊥
π
(20)
2
Sehingga didapat, ⎛ π 1⎞ ⎢ π ⎥ k = round ⎜⎜ − ⎟⎟ = ⎢ ⎥ ⎝ 4β 2 ⎠ ⎣ 4β ⎦
(21)
dengan round adalah fungsi yang membulatkan ke bilangan bulat terdekat, sedangkan ‘ ⎣ ⎦ ’ menyatakan fungsi floor. Selanjutnya yang menjadi pertanyaan adalah berapa besarnya sudut β, yang dapat dicari sebagai berikut. x0 ψ 0 = sin β =
1 N
sehingga sudut β diberikan oleh,
(22)
172
IJP Vol. 14 No. 4, 2003
⎛ 1 ⎞ 1 ⎟⎟ ≈ β = sin −1 ⎜⎜ (untuk N besar) N ⎝ N⎠
(23)
⎢ ⎥ π ⎥ k=⎢ ⎢ 4 sin −1 ( 1 ) ⎥ N ⎦ ⎣ ⎥ ⎢π N ⎥ (untuk N besar) ≈⎢ 4 ⎦ ⎣
(24)
Jadi,
ket
Setelah dilakukan iterasi sebanyak k kali kemudian ψk diukur terhadap basis standar akhir
{0 , 1 ,K, N − 1 }
probabilitas
yang
untuk
akan ket
menghasilkan
x0
nilai Gambar 2. Probabilitas dan posisi ket awal
sebesar
sin 2 [( 2 K + 1)β] ≥ 1 - N1 . Jadi semakin besar N maka akan
semakin besar nilai probabilitas keluaran untuk ket x 0 . Dari pembahasan sebelumnya kita dapatkan operator linier Q yang digunakan sebanyak k kali. Jadi algoritma Grover akan menggunakan oracle sebanyak yang lebih sedikit dibandingkan algoritma klasik biasa dengan O (N ) . O( N )
dengan
3.3 Simulasi Algortima Grover
Di bawah ini akan ditampilkan hasil simulasi dari algoritma Grover dengan jumlah N = 2n = 8 (n = 3 qubit)9) dan indeks dari data yang akan dicari adalah x0 = 4 . Gambar 3. Iterasi pertama dan ket keluarannya
Gambar 1. Inisialisasi jumlah qubit dan indeks yang dicari
Gambar 4. Probabilitas dan posisi ket keluaran
172
IJP Vol. 14 No. 3, 2003
173
dibutuhkan. Meskipun algoritma Grover bersifat probabilistik akan tetapi banyaknya iterasi yang dilakukan bisa bersifat deterministik. Untuk dapat diimplementasikan secara sederhana nampaknya algoritma Grover membutuhkan kelengkapan dari hampir seluruh perangkat keras dari komputer quantum. Hal ini dikarenakan sulitnya mengimplementasikan oracle yang bekerja secara paralel dalam sebuah operator inversi. Daftar Pustaka
1. 2. Gambar 5. Iterasi kedua dan ket keluarannya
3. 4. 5.
6. 7.
Gambar 6. Probabilitas dan posisi ket keluaran
8.
4. Kesimpulan
9.
Pencarian data dengan indeks takterurut dengan menggunakan algoritma Grover akan bekerja dengan baik bila informasinya disimpan dalam bentuk qubit dan dapat menggunakan gerbang-gerbang logika quantum yang merepresentasikan operator-operator uniter yang
Jozsa, Richard, Searching in Grover’s Algorithm. arXiv:quant-ph/9901021, University of Plymouth, Januari, 1999. Lomonaco, S.J.Jr., Grover’s Quantum Search Algorithm, Proceeding of Symposia in Applied Mathematics. Washington DC, 2000 Grover, L. K., Quantum Mechanics Helps in Searching for Needle in A Haystack, arXiv:quantph/9706033. Bell Labs. 1997 Ekert, A., Hayden, P., & Inamori, H., Basic Concepts in Quantum Computation, University of Oxford, Center for Quantum Computation, 2000. Lomonaco, S.J. Jr., A Rosetta Stone for Quantum Mechanics with an Introduction to Quantum Computation, Proceeding of Symposia in Applied Mathematics. Washington DC, Januari 2000 John, P., Lectures Notes for Physics 229: Quantum Information and Computation, California Institute of Technology, 1998. Hutasoit, D.P., & Zen, F.P., Algoritma Waktu Polinomial pada Komputer Kuantum, Prosiding Seminar MIPA, 368-373, November 2000. Sakurai, J.J., Modern Quantum Mechanics, AddisonWesley Publishing Company, Inc. New York, 1994. Atmaja, A. N., Optimalisasi Pencarian Data Dalam Basis Data Indeks Takterurut Menggunakan Algoritma Grover, Tugas Akhir S1. Departemen Fisika Institut Teknologi Bandung, 2003.
