Review Jurnal

Algoritma Quantum Shor untuk Faktorisasi Bilangan Bulat

Andika Pratama

Jurusan Teknik Informatika Institut Teknologi Bandung Jl. Ganesha 10, Bandung

 Email : if17005@students.if.itb.ac.id

A. QUANTUM COMPUTING

            Sebuah alat hitung yang menggunakan mekanika kuantum seperti superposisi dan keterkaitan, yang digunakan untuk peng-operasi-an data. Perhitungan jumlah data pada komputasi klasik dihitung dengan bit, sedangkan perhitungan jumlah data pada komputer kuantum dilakukan dengan qubit. Prinsip dasar komputer kuantum adalah bahwa sifat kuantum dari partikel dapat digunakan untuk mewakili data dan struktur data, dan bahwa mekanika kuantum dapat digunakan untuk melakukan operasi dengan data ini. Dalam hal ini untuk mengembangkan komputer dengan sistem kuantum diperlukan suatu logika baru yang sesuai dengan prinsip kuantum.

Sejarah singkat

·         Pada tahun 1970-an pencetusan atau ide tentang komputer kuantum pertama kali muncul oleh para fisikawan dan ilmuwan komputer, seperti Charles H. Bennett dari IBM, Paul A. Benioff dari Argonne National Laboratory, Illinois, David Deutsch dari University of Oxford, dan Richard P. Feynman dari California Institute of Technology (Caltech).

·         Feynman dari California Institute of Technology yang pertama kali mengajukan dan menunjukkan model bahwa sebuah sistem kuantum dapat digunakan untuk melakukan komputasi. Feynman juga menunjukkan bagaimana sistem tersebut dapat menjadi simulator bagi fisika kuantum.

·         Pada tahun 1985, Deutsch menyadari esensi dari komputasi oleh sebuah komputer kuantum dan menunjukkan bahwa semua proses fisika, secara prinsipil, dapat dimodelkan melalui komputer kuantum. Dengan demikian, komputer kuantum memiliki kemampuan yang melebihi komputer klasik.

·         Pada tahun 1995, Peter Shor merumuskan sebuah algoritma yang memungkinkan penggunaan komputer kuantum untuk memecahkan masalah faktorisasi dalam teori bilangan.

·         Sampai saat ini, riset dan eksperimen pada bidang komputer kuantum masih terus dilakukan di seluruh dunia. Berbagai metode dikembangkan untuk memungkinkan terwujudnya sebuah komputer yang memilki kemampuan yang luar biasa ini. Sejauh ini, sebuah komputer kuantum yang telah dibangun hanya dapat mencapai kemampuan untuk memfaktorkan dua digit bilangan. Komputer kuantum ini dibangun pada tahun 1998 di Los Alamos, Amerika Serikat, menggunakan NMR (Nuclear Magnetic R`Esonance).

B. PEMBAHASAN SINGKAT JURNAL

1.         I.   Komputer Quantum

Komputer quantum dapat jauh lebih cepat dari komputer konvensional pada banyak masalah, salah satunya yaitu masalah yang memiliki sifat berikut:

1.      Satu-satunya cara adalah menebak dan mengecek jawabannya berkali-kali

2.      Terdapat n jumlah jawaban yang mungkin

3.      Setiap kemungkinan jawaban membutuhkan waktu yang sama untuk mengeceknya.

4.      Tidak ada petunjuk jawaban mana yang kemungkinan benarnya lebih besar: memberi jawaban dengan asal tidak berbeda dengan mengeceknya dengan urutan tertentu.

Contoh dari masalah itu misalnya password cracker yang mencoba menebak password dari file terenkripsi(dengan asumsi passwordnya memiliki panjang maksimal).

     II.            Qubit

Pemanfaatan sifat superposisi qubit ini adalah Paralellisme Quantum. Paralelisme Quantum muncul dari kemampuan quantum register untuk menyimpan superposisi dari base state. Maka setiap operasi pada register berjalan pada semua kemungkinan dari superposisi secara simultan. Karena jumlah state yang mungkin adalah 2n, dengn n adalah jumlah qubit pada quantum register, kita dapat melakukan pada komputer quantum satu kali operasi yang membutuh kan waktu eksponensial pada komputer konvensional.

Kelemahan dari metode ini adalah, semakin besar base state yang bersuperposisi, semakin kecil kemungkinan hasil pengukuran dari nilai hasil pengukuran tersebut benar. Kelemahan ini membuat pararellisme quantum tidak berguna bila operasi dilakukan pada nilai yang spesifik.

Namun kelemahan ini tidak begitu berpengaruh pada fungsi yang memperhitungkan nilai dari semua input, bukan hanya satu. Sebagaimana ditunjukkan pada Algoritma Shor.[6]

  III.          III.        Algoritma Shor

Algoritma Shor didasarkan 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..

C. HASIL EKSPERIMEN

            Simulasi Algoritma Quantum telah banyak dibuat untuk komputer konvensional, tetapi patut diingat bahwa simulasi-simulasi tersebut tidak akan bisa benar-benarmeniru komputer quantum dengan sempurna, karena efek-efek eksklusif quantum seperti superposisi quantum dan quantum entanglement.

Program yang saya gunakan untuk simulasi dibawah adalah program shor yang dibuat olah Bernhard Oemer, ditulis dalam bahasa c++ dengan library QULIB untuk mensimulasikan komputer quantum abstrak.[7]

Disimulasikan proses Algoritma Shor dalam memfaktorkan bilangan bulat 15, karena 15 adalah bilangan bulat terkecil yang masih dapat difaktorkan oleh Algoritma Shor.

           Hasil output program:

factoring 15: random seed = 7, tries = 1. allocating 12 quBits with 256 terms.

RESET: reseting state to |0,0>

FFT: performing 1st Fourier transformation. EXPN: trying x = 2. |a,0> --> |a,2^a mod 15> MEASURE: 2nd register: |*,1>

FFT: performing 2nd Fourier transformation. MEASURE: 1st register: |0,1>

measured zero in 1st register. trying again ...

RESET: reseting state to |0,0>

FFT: performing 1st Fourier transformation. EXPN: trying x = 8. |a,0> --> |a,8^a mod 15> MEASURE: 2nd register: |*,4>

FFT: performing 2nd Fourier transformation. MEASURE: 1st register: |64,4>

rational approximation for 64/2^8 is 1/4, possible period: 4

8^2 mod 15 = 4. possible common factors of 15 with 5 and 3.

15 = 5 * 3.

program succeeded after 1 s and 2 iterations.

Pembahasan Simulasi:

Pada percobaan pertama, Algoritma Shor gagal karena hasil pengukuran 0 pada register pertama berarti q/r = 0 tidak memberikan informasi mengenai periode r. Pada percobaan kedua, hasil pengukuran menghasilkan nilai dari puncak spektrum |64>. Dengan 64/256 = ¼ = q/r, periode r =4 diketahui dan kemungkinan faktor dari 15 telah ditemukan. Setelah faktor teronfirmasi, simulasi ini selesai.

Dari hasil simulasi tersebut terlihat sifat algoritma quantum yang non-deterministik, yaitu jumlah operasi yang harus dilakukan untuk berhasil tidaklah tetap. Namun secara probabilistas statistik, jumlah opersi yang dibutuhkan maksimal akan selesai dalam waktu polinomial.

D. ANALISIS KELEBIHAN & KEKURANGAN

     KELEBIHAN :

• Abstrak lebih jelas, sehingga dengan membaca abstraknya saja pembaca dapat mengetahui hasil dari penelitian tersebut
• Prosedur penelitian disusun dengan teratur, sehingga mudah untuk dipahami.
• kesimpulan yang dibuat sudah terperinci dan dipaparkan secara jelas

      KEKURANGAN :

•   Penulis kurang lengkap dalam menyimpulkan keseluruhan isi dari jurnal ini.

E.  KESIMPULAN 
       Pada bagian kesimpulan ini penulis cukup baik dalam menjelaskan tentang quantum computing ini apa saja yang terdapat didalamnya. Namun penulis kurang lengkap dalam menyimpulkan keseluruhan isi dari jurnal ini dan menurut saya penulis kurang detail dalam memberikan hasil yang didapat dalam melakukan penelitiannya.