PENGANTAR QUANTUM KOMPUTASI
1.
Pendahulan (Stely Novenus Tarigan)
Quantum
Komputasi terdiri dari 2 kata yaitu “Quantum” dan “Komputasi”. Quantum artinya
jumlah/quantity tanpa batas, dan Komputasi artinya ilmu komputer dimana
algoritma digunakan untuk menemukan suatu cara dalam memecahkan masalah dari
sebuah data input. Sehingga Quantum Komputasi adalah suatu bidang studi yang
berperan pada perkembangan teknologi komputer yang didasari prinsip-prinsip
teori kuantum, yang menjelaskan sifat dan perilaku energi dan materi pada tingkat
kuantum (atom dan subatom).
Komputer
Kuantum disini merupakan komputer/alat hitung yang menggunakan sebuah fenomena
mekanika kuantum, seperti superposisi dan keterkaitan, untuk melakukan operasi
data. Dalam komputer pada umumnya untuk menghitung jumlah data dengan
menggunakan bit, sedangkan dalam komputer kuantum sudah menggunakan qubit.
Pengembangan
komputer dengan sistem kuantum memerlukan algoritma baru yang sesuai dengan
prinsip kuantum. Beberapa fisikawan seperti Charles H. Bennett dari IBM, Paul
A. Benioff dari Argonne National Laboratory, Richard P. Feynman dari California
Institute of Technology (Caltech).
Sistem
kuantum yang dapat melakukan proses penghitungan merupakan suatu ide yang
dikemukakan oleh Richard P. Feynman dan sistem ini bisa menjadi simulator
percobaan fisika kuantum. Sehingga para ilmuwan mulai melakukan riset mengenai
sistem kuantum tersebut. Saat ini telah ditemukan dua algoritma baru yang bisa
digunakan dalam sistem kuantum yaitu algoritma shor dan algoritma grover.
Contohnya adalah pemfaktoran (factoring) sebuah bilangan besar masih terlalu
sulit bagi komputer meskipun mudah untuk diverifikasi. Itulah sebabnya
pemfaktoran bilangan besar ini banyak digunakan dalam metode kriprografi untuk
melindungi data.
2.
Entanglement (Cynthia Diana Sinaulan)
Entanglement
merupakan efek dari mekanik kuantum yang mengaburkan jarak antara partikel
individual sehingga sulit untuk menggambarkan partikel tersebut terpisah
walaupun anda berusaha untuk memindahkan mereka. Entanglement juga merupakan
gambaran partikel yang dapat berkorelasi dan diprediksi berinteraksi satu sama
lain tanpa terpaut jarak. Entanglement secara teoritis dapat mempercepat
komputasi dan diyakini dapat memecahkan batasan pada komputer dan kuantum.
Kuantum
entanglement adalah bagian dari fenomena kuantum mechanical yang menyatakan
bahwa dua atau lebih objek dapat digambarkan mempunyai hubungan dengan objek
lainnya walaupun objek tersebut berdiri sendiri dan terpisah dengan objek
lainnya. Fenomena ini dimanfaatkan oleh ilmuan dalam pembuatan Quantum Computing.
Einstein
mengkritisi teori kuantum mechanical, ia menunjukkan kelemahan dari teori
tersebut yang menggunakan entanglement merupakan sesuatu yang “spooky action
at a distance” karena Einstein tidak
mempercayai bahwa partikel kuantum dapat mempengaruhi partikel lainnya melebihi
cahaya. Kuantum entanglement dapat diimplementasi dalam berbagai bidang seperti
pengiriman pesan rahasia yang sulit untuk di-enkripsi dan pembuatan komputer
yang mempunyai performa cepat.
3.
Pengoprasian Data Qubit (Kemal Nurfajri)
Jika pada komputer
klasik terdapat bit sebagai memorinya, komputer kuantum menggunakan qubit atau
quantum bit sebagai memori dasar informasi. Perbedaan antara bit dan qubit
adalah jika bit pada suatu waktu hanya dapat merepresentasikan satu state saja
yaitu 0 atau 1, qubit dapat merepresentasikan 0, 1 atau gabungan keduanya yang
disebut dengan quantum superposition. Jadi, jika n bit hanya dapat merepresentasikan salah satu dari 2n states, n qubit dapat merepresentasikan 2n states tersebut secara
bersamaan atau lebih mudahnya 1 qubit dapat menampung lebih dari 1 bit.
Suatu komputer quantum
mengoperasikan qubit menggunakan quantum
gates dan measurments. Dimana
perhitungan dimulai menggunakan quantum
gates dan berakhir pada measurments yang
menghasilkan classical states.
4.
Quantum Gates (Fitri Ayu Anggraini & Novita Rakhmawati)
Gerbang
kuantum atau gerbang logika kuantum adalah rangkaian kuantum dasar yang
beroperasi pada sejumlah kecil qubit . Mereka adalah analog untuk komputer
kuantum ke gerbang logika klasik untuk komputer digital konvensional. Logika
logika kuantum bisa dibalik , tidak seperti banyak gerbang logika klasik.
Beberapa gerbang logika klasik universal, seperti gerbang Toffoli , memberikan
reversibilitas dan dapat dipetakan secara langsung ke gerbang logika kuantum.
Gerbang logika kuantum diwakili oleh matriks-matriks kesatuan .
Gerbang
kuantum yang paling umum beroperasi pada ruang satu atau dua qubit. Ini berarti
bahwa sebagai matriks, gerbang kuantum dapat digambarkan dengan matriks 2 x 2
atau 4 x 4 dengan baris ortonormal .
Ingat
Penyelidikan gerbang logika kuantum tidak terkait dengan logika kuantum , yang
merupakan formalisme dasar untuk mekanika kuantum berdasarkan modifikasi
beberapa aturan logika proposisional .
Berikut
ini merupakan contoh dari gerbang kuantum :
a. Gerbang hadamard
Gerbang ini beroperasi dengan qubit tunggal. Hal ini
ditunjukkan oleh matriks Hadamard:
Karena baris matriks bersifat ortogonal, H memang
merupakan matriks kesatuan.
b.
Fase shifter
gates
Gates di kelas ini beroperasi dengan qubit tunggal.
Mereka diwakili oleh 2 x 2 matriks dari bentuknya dimana θ adalah pergeseran
fasa .
c.
Gerbang
Terkendali
Misalkan U adalah gerbang yang beroperasi pada qubit
tunggal dengan representasi matriks
Gerbang terkontrol U adalah gerbang yang beroperasi
pada dua qubit sedemikian rupa sehingga qubit pertama berfungsi sebagai
kontrol.
|00⟩ ↦
|00⟩
|01⟩ ↦
|01⟩
|10⟩ ↦ |1⟩ U
| 0⟩ =
|1⟩ (
x 00|0⟩ +
x 01|1⟩)
|11⟩ ↦ |1⟩ U
| 1⟩ =
|1⟩ (
x 10| 0⟩ +
x 11| 1⟩)
Dengan demikian matriks gerbang U yang dikontrol
adalah sebagai berikut:
d.
Gerbang
Takterkendali
Karena gerbang ini bisa direduksi menjadi gerbang yang
lebih elementer, biasanya tidak termasuk dalam repertoar dasar gerbang kuantum.
Disebutkan disini hanya untuk kontras dengan gerbang yang dikontrol sebelumnya.
Universal Quantum Gates
Satu
set gerbang kuantum universal adalah seperangkat gerbang yang memungkinkan
operasi pada komputer kuantum dapat dikurangi. Satu set sederhana dari gerbang
kuantum universal dua qubit adalah gerbang Hadamard ( H ), gerbang rotasi fase 
, dan gerbang yang
dikendalikan-TIDAK , sebuah kasus khusus yang dikendalikan-U sedemikian itu
, dan gerbang yang
dikendalikan-TIDAK , sebuah kasus khusus yang dikendalikan-U sedemikian itu
Sebuah
gerbang tunggal yang terdiri dari gerbang kuantum universal juga dapat
diformulasikan dengan menggunakan gerbang Deutsch tiga-qubit, D ( θ )
Gerbang
logika klasik universal, gerbang Toffoli , dapat direduksi menjadi gerbang
Deutsch, 
, sehingga menunjukkan bahwa
semua operasi logika klasik dapat dilakukan pada komputer kuantum universal.
, sehingga menunjukkan bahwa
semua operasi logika klasik dapat dilakukan pada komputer kuantum universal.
5.
Algoritma Shor (Alfan Fadhila A)
Algoritma Shor merupakan
algoritma yang ditemukan oleh Peter Shor pada tahun 1995. Sebuah komputer
kuantum dapat memecahkan sebuah kode rahasia yang saat ini secara umum
digunakan untuk mengamankan pengiriman data. Jika data disandikan melalui kode
RSA, data yang dikirimkan akan aman karena kode RSA tidak dapat dipecahkan
dalam waktu yang singkat. Selain itu, pemecahan kode RSA membutuhkan kerja
ribuan komputer secara paralel sehingga kerja pemecahan ini tidaklah efektif.
Algoritma yang
berdasarkan dari sebuah teori bilangan: fungsi F(a) = xamod n adalah
fungsi periodik jika x adalah bilangan bulat yang relatif prima dengan n. Dalam
Algoritma Shor, n akan menjadi bilangan bulat yang hendak difaktorkan.
Bila menghitung
fungsi tersebut pada komputer konvensional untuk jumlah yang eksponensial, akan
membutuhkan waktu eksponensial pula. Pada masalah ini algoritma quantum shor
memanfaatkan pararellisme quantum untuk melakukannya hanya dengan satu langkah.
Dikarenakan F(A)
adalah fungsi periodik, jadi fungsi ini memiliki sebuah periode r. Diketahui x0mod
n = 1, maka xr mod n = 1, begitu juga x2r mod n dan
seterusnya.
Dengan informasi
ini dan manipulasi persamaan sederhana berikut:
xr
≡ 1 mod n
(xr/2)2
≡ 1 mod n
(xr/2)2
– 1 ≡ 0 mod n
Dengan anggapan r
adalah angka genap:
(xr/2
– 1)(xr/2 + 1) ≡ 0 mod n
Dapat dilihat bahwa
hasil dari (xr/2 – 1)(xr/2 + 1) adalah kelipatan n. Maka
selama |xr/2| ≠ 1, setidaknya salah satu dari (xr/2 – 1)
atau (xr/2 + 1) memiliki faktor yang sama dengan n. Maka, dengan
menghitung gcd(xr/2 – 1,n) dan gcd(xr/2 + 1,n) faktor dari n akan
didapat.
Lain halnya untuk
menghitung r dari persamaan xr ≡ 1 mod n akan membutuhkan waktu
eksponensial di komputer konvensional. Oleh karena itu proses ini perlu
dijalankan dengan komputer quantum agar seluruh nilai superposisi akan
terhitung dalam sekali jalan.
Langkah-langkah
Algoritma Shor
Masalah yang
hendak dipecahkan adalah: Diketahui sebuah bilangan komposit N, dicari sebuah
bilangan bulat x dengan x bernilai 1 < x < N.
1.
Algoritma
Shor untuk mencari faktor dari bilangan bulat n, dapat dipecah menjadi
langkah-langkah berikut:
Menentukan
apakan N adalah prima, genap, atau perpangkatan dari bilangan prima. Jika ya,
maka Algoritma Shor tidak akan dipakai. Terdapat algoritma konvensional yang
efisien untuk menentukan jenis n dan memfaktorkannya. Langkah ini akan
dilakukan di komputer konvensional.
2.
Ambil
bilangan bulat q, dimana q adalah nilai dari perpangkatan 2 yang memenuhi: n2
≤ q < 2n2. Langkah ini akan dilakukan di komputer konvensional.
3.
Mencari
bilangan bulat random x yang relatif prima dengan n. Terdapat algoritma
konvensional yang efisien untuk proses ini. Langkah ini akan dilakukan di
komputer konvensional.
4.
Membuat
quantum register yang dipartisi menjadi dua bagian, katakan register 1 dan
register 2. Register satu harus cukup besar untuk merepresentasikan bilangan
bulat sebesar q-1, sedangkan register 2 sebesar n-1. Langkah ini perlu
dilakukan di komputer quantum.
5.
Masukkan
kedalam register 1 superposisi yang setara dari semua bilangan bulat 0 sampai
q-1, dan register 2 bilangan bulat 0. Langkah ini dapat dilaksanakan dengan menggunakan
hadamard gates. Langkah ini perlu dilakukan di komputer quantum. Pada langkah
ini, state dari quantum memory register adalah :
6.
Aplikasikan
fungsi xa mod n ke dalam
semua bilangan bulat di dalam register 1, dan menyimpan hailnya di register 2.
Karena prinsip pararellisme quantum, proses ini hanya perlu dilakukan sekali
saja. Langkah ini perlu dilakukan di komputer quantum. Pada langkah ini, state
dari quantum memory register adalah:
7.
Mengukur
dan memeriksa nilai yang disimpan pada register 2, mendapatkan nilai k. Langkah
ini perlu dilakukan di komputer quantum. Langkah ini akan membuat register 1
semua superposisi state a dimana xa mod n ≠ k “kolaps”. Setelah
langkah ini, state dari quantum memory register adalah:
Dengan
A adalah himpunan dari a’ dimana x n k a mod = , dan ||A|| adalah jumlah elemen
dalam himpunan tersebut.
8.
Menghitung
transformasi quantum Fourier pada register 1. Langkah ini perlu dilakukan di
komputer quantum. Sifat transformasi Fourier quantum akan mengubah |a>
menjadi
Karena
pararellisme quantum, langkah ini cukup dilakukan satu kali. State dari
register setelah transformasi:
9.
Ukur
nilai state register satu, katakan nilai ini sebagai m. Bilangan bulat m
memiliki probabilitas tinggi adalah kelipatan q/r, dimana r adalah periode yang
kita cari. Langkah ini perlu dilakukan di komputer quantum.
10. Gunakan nilai m untuk mencari nilai r,
dengan nilai m dan q diketahui. Jika r tidak dapat ditentukan, maka kembali ke
langkah 4. Langkah ini akan dilakukan di komputer konvensional.
11. Setelah r diketahui, faktor n dapat
ditentukan dengan menghitung gcd(xr/2 + 1, n) dan gcd(xr/2-1,n). Disaat ini
faktor n telah ditemukan, dan Algoritma telah selesai. Langkah ini akan
dilakukan di komputer konvensional.
Kelemahan
dan Kelebihan Algoritma Shor
Berbeda dengan
komputer konvensional yang deterministik, komputer quantum bersifat
nondeterministik dan probabilistik, yang berarti suatu algoritma kadang kala
dapat berhasil dan kadang kala akan gagal biarpun untuk kondisi yang sama. Hal
ini dikarena sifat pengukuran dalam mekanika quantum yang probabilistik.
Akibatnya, Algoritma Shor dapat gagal menemukan faktor karena beberapa sebab,
diantaranya:
·
Hasil
pengukuran dari transformasi quantum fourier dapat berupa 0, membuat langka ke
10 tak mungkin dilakukan.
·
Kadang
hasil faktorisasi algoritma akan menghasilkan 1 dan n, yang secara definisi
benar tetapi tidak berguna.
·
Bila
hasil r ganjil, maka langkah ke 10 tidak dapat dilakukan.
Walaupun begitu,
probabilitas sukses akan bertambah setiap kali algoritma diulang. Dalam
Algoritma Shor yang dimodifikasi dengan penentuan order, probabilitas sukses
setelah 2 kali jalan lebih dari 60%, dan probabilitas sukses setelah 4 kali
jalan lebih dari 90%.
Referensi :
