Exponential Speedup of Shor’s Factoring Algorithm

Spread the love

Shor’s Algorithm : Shor, P. W. (1994, November). Algorithms for quantum computation: discrete logarithms and factoring. In Proceedings 35th annual symposium on foundations of computer science (pp. 124-134). Ieee.
https://ieeexplore.ieee.org/document/365700

Algoritma Shor 1994 yang terkenal menang sebagai algoritma besar pertama yang diusulkan untuk komputasi kuantum.
Algoritma Shor terkenal dengan anjak bilangan bulat dalam waktu polinomial.
Karena algoritma klasik paling terkenal membutuhkan waktu superpolinomial untuk mencari faktor produk dari dua bilangan prima, kriptosistem yang banyak digunakan, RSA, mengandalkan integer factoring yang susah dikomputasi untuk bilangan bulat yang cukup besar.

How Quantum Computers Break Encryption | Shor’s Algorithm Explained =
https://www.youtube.com/watch?v=lvTqbM5Dq4Q

Demonstrasi percepatan komputasi pada komputasi quantum =
https://www.slideshare.net/japh44/demonstrating-quantum-speedup-with-a-twotransmon-quantum-processor-phd-defense-upmc-cea-15112011

Masalah faktorisasi bilangan bulat sangat penting.
(contoh: faktor 15 adalah 3 dan 5)
Mencari faktor dari bilangan bulat kecil itu mudah, tetapi sulit untuk angka yang besar.
Sebagian besar keamanan internet didasarkan pada kenyataan bahwa sulit untuk mencari faktor bilangan bulat besar pada komputer klasik.
Cryptosystem yang banyak digunakan, RSA, mengandalkan faktorisasi yang “tidak mungkin” untuk bilangan bulat yang cukup besar.

Algoritma Peter Shor menakjubkan dapat melakukan faktorisasi bilangan bulat dalam waktu polinomial dan benar-benar membawa komputasi kuantum menjadi pusat perhatian.
Algoritma Shor didasarkan pada fakta berikut: masalah kerumitan mencari faktor bilangan bulat dapat dikurangi, dengan menemukan periode dari fungsi tertentu.

% Try it in Matlab/Octave:
N = 371
a = 2
fr = []
for r = 0 : N-1
	if r == 0
		ArModN = mod(a^r , N)
	else
		ArModN = mod( fr(r) * a , N)
	end
	fr = [fr ArModN]
end

The Quantum Part of the Algorithm

Melanjutkan algoritma, kami mengukur qubit bawah |ϕ2>, yang merupakan superposisi dari banyak state.

Langkah terakhir dari bagian kuantum dari algoritma Shor adalah mengambil superposisi dan mengembalikan periodenya, dengan jenis transformasi Fourier, yang disebut quantum Fourier transform dan dilambangkan sebagai QFT.

Selanjutnya, Dari Periode ke Faktor.
(bagaimana periode r akan membantu kita menemukan faktor N)

Exponential Speedup!
Algoritma kuantum Shor memang lebih cepat.

Download pdf dari artikel ini = Shor’s Algorithm

Tinggalkan Balasan

This site uses Akismet to reduce spam. Learn how your comment data is processed.