Quantum Computing Algorithms: Simon’s Periodicity Algorithm

Simon’s Periodicity Algorithm : Simon, D. R. (1994). On the power of quantum computation, in Proceedings of the 35th Symposium on Foundations of Computer Science, S. Goldwasser, ed.
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.51.5477

adalah algoritma kuantum pertama yang menunjukkan percepatan eksponensial versus algoritma klasik terbaik dalam memecahkan masalah tertentu.
Simon’s Periodicity Algorithm mengilhami algoritma kuantum untuk transformasi Fourier diskrit, juga dikenal sebagai transformasi quantum Fourier, yang digunakan dalam algoritma kuantum paling terkenal: Shor’s factoring algorithm.

Simon’s Problem: Determine the c (the period of f) !

Untuk fungsi periodik f yang diberikan, kita dapat menemukan periode c, dalam n evaluasi fungsi.
Berbeda dengan 2pangkat(n−1) + 1 yang dibutuhkan oleh algoritma klasik.

Masalah factoring integers (mencari faktor bilangan bulat) sangat penting.
Sebagian besar keamanan internet (RSA cryptography) didasarkan pada kenyataan bahwa “sulit” untuk mencari faktor bilangan bulat pada komputer klasik.
RSA menggunakan fakta bahwa perkalian secara komputasi “mudah” dan mencari faktor bilangan bulat adalah komputasi “sulit.”

Kerumitan masalah mencari faktor bilangan bulat dapat dikurangi dengan menemukan periode fungsi tertentu.

Tentukan c (periode f)!
dalam kasus terburuk, menggunakan pendekatan komputer klasik, evaluasi fungsi 2pangkat(n−1) + 1 akan diperlukan.
Bisakah kita melakukan yang lebih baik menggunakan Algoritma Quantum?

Algoritma Simon adalah kombinasi dari prosedur kuantum serta prosedur klasik.

qubit_0 = [1; 0]
qubit_1 = [0; 1]
n = 3
input_x = [1]
input_y = [1]
for i=1:n
input_x = kron(input_x, qubit_0);
input_y = kron(input_y, qubit_0);
end
input_xy = kron(input_x, input_y)
checkpoint_0 = input_xy

qubit_0 = [1; 0]
qubit_1 = [0; 1]
n = 3
input_x = [1]
input_y = [1]
for i=1:n
input_x = kron(input_x, qubit_0);
input_y = kron(input_y, qubit_0);
end
input_xy = kron(input_x, input_y)
checkpoint_0 = input_xy

Hadamard_gate = [ 1/sqrt(2) 1/sqrt(2); 1/sqrt(2) -1/sqrt(2) ]
Identity_gate = eye(2)
Hn = [1]
In = [1]
for i=1:n
Hn = kron(Hn, Hadamard_gate);
In = kron(In, Identity_gate);
end
Hn_In = kron(Hn, In);
checkpoint_1 = Hn_In * input_xy

qubit_0 = [1; 0]
qubit_1 = [0; 1]
n = 3
input_x = [1]
input_y = [1]
for i=1:n
input_x = kron(input_x, qubit_0);
input_y = kron(input_y, qubit_0);
end
input_xy = kron(input_x, input_y)
checkpoint_0 = input_xy

Hadamard_gate = [ 1/sqrt(2) 1/sqrt(2); 1/sqrt(2) -1/sqrt(2) ]
Identity_gate = eye(2)
Hn = [1]
In = [1]
for i=1:n
Hn = kron(Hn, Hadamard_gate);
In = kron(In, Identity_gate);
end
Hn_In = kron(Hn, In);
checkpoint_1 = Hn_In * input_xy

% U_function_gate = ?see next slide?
checkpoint_2 = U_function_gate * checkpoint_1

qubit_0 = [1; 0]
qubit_1 = [0; 1]
n = 3
input_x = [1]
input_y = [1]
for i=1:n
input_x = kron(input_x, qubit_0);
input_y = kron(input_y, qubit_0);
end
input_xy = kron(input_x, input_y)
checkpoint_0 = input_xy

Hadamard_gate = [ 1/sqrt(2) 1/sqrt(2); 1/sqrt(2) -1/sqrt(2) ]
Identity_gate = eye(2)
Hn = [1]
In = [1]
for i=1:n
Hn = kron(Hn, Hadamard_gate);
In = kron(In, Identity_gate);
end
Hn_In = kron(Hn, In);
checkpoint_1 = Hn_In * input_xy

% U_function_gate = ?see next slide?
checkpoint_2 = U_function_gate * checkpoint_1

checkpoint_3 = Hn_In * checkpoint_2

Kesimpulannya, untuk fungsi periodik f yang diberikan, kita dapat menemukan periode c dalam n evaluasi fungsi.
Ini berbeda dengan 2n−1 + 1 yang dibutuhkan dengan algoritma klasik.

Bagaimana cara menerjemahkan fungsi menjadi matriks kesatuan (menggunakan Matlab)?
Pertama buat pemetaan kombinasi input dan output, kemudian lakukan :

% U * matrix_input = matrix_output 
% U * matrix_input * inv(matrix_input) = matrix_output * inv(matrix_input) 
% U * I = matrix_output * inv(matrix_input) 
% U = matrix_output * inv(matrix_input)

Download m file =
https://github.com/keamanansiber/qiskit/blob/master/Matlab_Octave/SimonsPeriodicityAlgorithm.m

Download pdf dari artikel ini = Simon’s Periodicity Algorithm