Algoritma Shor
Algoritma
Shor, dinamai matematikawan Peter Shor , adalah algoritma kuantum yaitu
merupakan suatu algoritma yang berjalan pada komputer kuantum yang
berguna untuk faktorisasi bilangan bulat. Algoritma Shor dirumuskan pada
tahun 1994. Inti dari algoritma ini merupakan bagaimana cara
menyelesaikan faktorisasi terhaadap bilanga interger atau bulat yang
besar.
Efisiensi
algoritma Shor adalah karena efisiensi kuantum Transformasi Fourier ,
dan modular eksponensial. Jika sebuah komputer kuantum dengan jumlah
yang memadai qubit dapat beroperasi tanpa mengalah kebisingan dan
fenomena interferensi kuantum lainnya, algoritma Shor dapat digunakan
untuk memecahkan kriptografi kunci publik skema seperti banyak digunakan
skema RSA. Algoritma Shor terdiri dari dua bagian:
- Penurunan yang bisa dilakukan pada komputer klasik, dari masalah anjak untuk masalah ketertiban -temuan.
- Sebuah algoritma kuantum untuk memecahkan masalah order-temuan.
Hambatan
runtime dari algoritma Shor adalah kuantum eksponensial modular yang
jauh lebih lambat dibandingkan dengan kuantum Transformasi Fourier dan
pre-/post-processing klasik. Ada beberapa pendekatan untuk membangun dan
mengoptimalkan sirkuit untuk eksponensial modular. Yang paling
sederhana dan saat ini yaitu pendekatan paling praktis adalah dengan
menggunakan meniru sirkuit aritmatika konvensional dengan gerbang
reversibel , dimulai dengan penambah ripple-carry. Sirkuit Reversible
biasanya menggunakan nilai pada urutan n ^ 3, gerbang untuk n qubit.
Teknik alternatif asimtotik meningkatkan jumlah gerbang dengan
menggunakan kuantum transformasi Fourier , tetapi tidak kompetitif
dengan kurang dari 600 qubit karena konstanta tinggi.sumber : http://djuneardy.blogspot.co.id/2015/04/quantum-computing-entanglement.html
Tidak ada komentar:
Posting Komentar