ALGORITMA SHOR

Nama       : Safira
Kelas        : 4IA20
Dosen      :  Lely Prananingrum
Mata Kuliah : Pengantar Komputasi Modern

Algoritma Shor

Pada tahun 1994 Peter Shor (Bell Laboratories) menemukan algoritma kuantum pertama yang secara prinsip dapat melakukan faktorisasi yang efisien. Hal ini menjadi sebuah aplikasi kompleks yang hanya dapat dilakukan oleh sebuah komputer kuantum. Pemfakotiran adalah salah satu masalah yang paling penting dalam kriptografi. Misalnya, keamanan RSA (sistem keamanan perbankan elektronik) - kriptografi kunci publik - tergantung pada pemfaktoran dan hal itu akan menjadi masalah yang besar. Karena banyak fitur yang bermanfaat dari komputer kuantum, para ilmuwan berupaya lebih untuk membangunnya. Apabila, pemecahan segala jenis enkripsi saat ini memerlukan waktu hampir seabad pada komputer yang ada, mungkin hanya memakan waktu beberapa tahun pada komputer kuantum

Algoritma Shor adalah contoh lanjutan paradigma dasar (berapa banyak waktu komputasi diperlukan untuk menemukan faktor bilangan bulat n-bit?), tapi algoritma ini tampak terisolir dari kebanyakan temuan lain ilmu informasi quantum. Sekilas, itu cuma seperti trik pemrograman cerdik dengan signifikansi fundamental yang kecil. Penampilan tersebut menipu; para periset telah menunjukkan bahwa algoritma Shor bisa ditafsirkan sebagai contoh prosedur untuk menetapkan level energi sistem quantum, sebuah proses yang fundamental. Seiring waktu berjalan dan kita mengisi lebih banyak pada peta, semestinya kian mudah memahami prinsip-prinsip yang mendasari algortima Shor dan algoritma quantum lainnya dan, kita harap, mengembangkan algoritma baru.

Sebagai contoh  Algoritma Shor yang paling sederhana adalah menemukan faktor-faktor untuk  bilangan  15,  di mana membutuhkan sebuah komputer kuantum dengan tujuh qubit.  Para  ahli  kimia mendesain dan menciptakan sebuah molekul yang memiliki tujuh putaran nukleus. Nukleus dari lima atom fluorin dan dua atom karbon yang dapat berinteraksi satu dengan yang lain sebagai qubit, dapat diprogram dengan menggunakan denyut-denyut  frekuensi radio dan dapat dideteksi melalui peralatan resonansi  magnetis nuklir (nuclear magnetic resonance, atau NMR) yang mirip dengan yang banyak digunakan di rumah-rumah sakit dan laboratorium-laboratorium kimia.

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: ∑ − = 1 0 | ,0 1 q a a q

6. Aplikasikan fungsi x n a mod 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: ∑ − = 1 0 | , mod 1 q a a a x n q

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 x n k a mod ≠ “kolaps”. Setelah langkah ini, state dari quantum memory register adalah: ∑= ∈ 〉 a a A a k A ' ' | ', || || 1 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.

 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.[6]

Kelemahan dan kelebihan

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%.[2]

Maka walaupun perlu berjalan untuk waktu yang tak ditentukan, waktu tersebut adalah polinomial. Lebih tepatnya, Algoritma Shor berjalan dengan kecepatan O((log n)2 *log log n) pada komputer quantum, dan harus melakukan paska prosesing selama O(log n) pada komputer konvensional. Secara utuh algoritma ini polinomial.