Praktek Algoritma Deutsch-Jozsa dengan Matlab / Octave
Download pdf dari materi tutorial praktek Algoritma Deutsch-Jozsa dengan Matlab / Octave = Deutsch-JozsaAlgorithm
Deutsch-Jozsa Algorithm:
Deutsch, D., & Jozsa, R. (1992). Rapid solution of problems by quantum computation. Proceedings of the Royal Society of London. Series A: Mathematical and Physical Sciences, 439(1907), 553-558.
https://royalsocietypublishing.org/doi/10.1098/rspa.1992.0167
Deutsch-Jozsa Algorithm: n inputs –> balanced or constant function?
Dalam komputer tradisional, skenario terburuk membutuhkan evaluasi fungsi 2<sup>n − 1</sup> + 1.
Bisakah kita melakukan yang lebih baik menggunakan Algoritma Quantum?
Kode Program Matlab/Octave:
qubit_0 = [1; 0] qubit_1 = [0; 1] qubits_00_0 = kron( kron(qubit_0, qubit_0) , qubit_0) qubits_01_0 = kron( kron(qubit_0, qubit_1) , qubit_0) qubits_10_0 = kron( kron(qubit_1, qubit_0) , qubit_0) qubits_11_0 = kron( kron(qubit_1, qubit_1) , qubit_0) Ufunction_gate = [0 1 0 0 0 0 0 0; 1 0 0 0 0 0 0 0; 0 0 0 1 0 0 0 0; 0 0 1 0 0 0 0 0; 0 0 0 0 1 0 0 0; 0 0 0 0 0 1 0 0; 0 0 0 0 0 0 1 0; 0 0 0 0 0 0 0 1] input00_output1 = Ufunction_gate * qubits_00_0 input01_output1 = Ufunction_gate * qubits_01_0 input10_output0 = Ufunction_gate * qubits_10_0 input11_output0 = Ufunction_gate * qubits_11_0
Deutsch-Jozsa: kasus fungsi seimbang dengan 2 input.
Jumlah input teratas = 2 qubit.
Kode Program Matlab/Octave:
qubit_0 = [1; 0] qubit_1 = [0; 1] Nx = 2 input_x = [1] for k=1:Nx input_x = kron(input_x, qubit_0); end input_xy = kron(input_x, qubit_1); checkpoint_0 = input_xy Hadamard_gate = [ 1/sqrt(2) 1/sqrt(2); 1/sqrt(2) -1/sqrt(2) ] Hx = [1] for k=1:Nx Hx = kron(Hx, Hadamard_gate); end Hxy = kron(Hx, Hadamard_gate); checkpoint_1 = Hxy * checkpoint_0
Kode Program Matlab/Octave:
qubit_0 = [1; 0] qubit_1 = [0; 1] Nx = 2 input_x = [1] for k=1:Nx input_x = kron(input_x, qubit_0); end input_xy = kron(input_x, qubit_1); checkpoint_0 = input_xy Hadamard_gate = [ 1/sqrt(2) 1/sqrt(2); 1/sqrt(2) -1/sqrt(2) ] Hx = [1] for k=1:Nx Hx = kron(Hx, Hadamard_gate); end Hxy = kron(Hx, Hadamard_gate); checkpoint_1 = Hxy * checkpoint_0 Ufunction_gate = [0 1 0 0 0 0 0 0; 1 0 0 0 0 0 0 0; 0 0 0 1 0 0 0 0; 0 0 1 0 0 0 0 0; 0 0 0 0 1 0 0 0; 0 0 0 0 0 1 0 0; 0 0 0 0 0 0 1 0; 0 0 0 0 0 0 0 1] checkpoint_2 = Ufunction_gate * checkpoint_1
Kode Program Matlab/Octave:
qubit_0 = [1; 0] qubit_1 = [0; 1] Nx = 2 input_x = [1] for k=1:Nx input_x = kron(input_x, qubit_0); end input_xy = kron(input_x, qubit_1); checkpoint_0 = input_xy Hadamard_gate = [ 1/sqrt(2) 1/sqrt(2); 1/sqrt(2) -1/sqrt(2) ] Hx = [1] for k=1:Nx Hx = kron(Hx, Hadamard_gate); end Hxy = kron(Hx, Hadamard_gate); checkpoint_1 = Hxy * checkpoint_0 Ufunction_gate = [0 1 0 0 0 0 0 0; 1 0 0 0 0 0 0 0; 0 0 0 1 0 0 0 0; 0 0 1 0 0 0 0 0; 0 0 0 0 1 0 0 0; 0 0 0 0 0 1 0 0; 0 0 0 0 0 0 1 0; 0 0 0 0 0 0 0 1] checkpoint_2 = Ufunction_gate * checkpoint_1 Identity_gate = eye(2) HxIy = kron(Hx, Identity_gate); checkpoint_3 = HxIy * checkpoint_2
Deutsch-Jozsa Algorithm: –> Percepatan eksponensial!
Kita telah memecahkan masalah dengan cukup SATU KALI evaluasi fungsi, yang bertentangan dengan evaluasi fungsi yang diperlukan dalam perhitungan klasik.
Kita telah mendemonstrasikan algoritma, menggunakan case Balanced Function A.
Sekarang, kita cukup mengukur qubit teratas.
Jika itu dalam keadaan | 0>, maka kita tahu bahwa f adalah fungsi konstan, jika tidak maka itu adalah fungsi seimbang.
Exponential Speedup:
Kode Program Matlab / Octave:
qubit_0 = [1; 0] qubit_1 = [0; 1] Identity_gate = eye(2) Hadamard_gate = [ 1/sqrt(2) 1/sqrt(2); 1/sqrt(2) -1/sqrt(2) ] balance_A_function = [0 1 0 0 0 0 0 0; 1 0 0 0 0 0 0 0; 0 0 0 1 0 0 0 0; 0 0 1 0 0 0 0 0; 0 0 0 0 1 0 0 0; 0 0 0 0 0 1 0 0; 0 0 0 0 0 0 1 0; 0 0 0 0 0 0 0 1] balance_B_function = [1 0 0 0 0 0 0 0; 0 1 0 0 0 0 0 0; 0 0 1 0 0 0 0 0; 0 0 0 1 0 0 0 0; 0 0 0 0 0 1 0 0; 0 0 0 0 1 0 0 0; 0 0 0 0 0 0 0 1; 0 0 0 0 0 0 1 0] constant_D_function = [0 1 0 0 0 0 0 0; 1 0 0 0 0 0 0 0; 0 0 0 1 0 0 0 0; 0 0 1 0 0 0 0 0; 0 0 0 0 0 1 0 0; 0 0 0 0 1 0 0 0; 0 0 0 0 0 0 0 1; 0 0 0 0 0 0 1 0] % Change this as you like! Nx = 2 SecretFunction_gate = balance_A_function input_x = [1] for k=1:Nx input_x = kron(input_x, qubit_0); end input_xy = kron(input_x, qubit_1); Hx = [1] for k=1:Nx Hx = kron(Hx, Hadamard_gate); end Hxy = kron(Hx, Hadamard_gate); DeutschJozsaAlgorithm = kron(Hx,Identity_gate) * SecretFunction_gate * Hxy result = DeutschJozsaAlgorithm * input_xy
Untuk proof pembuktian matematikanya, langsung lihat di buku sumber = Yanofsky, N. S., & Mannucci, M. A. (2008). Quantum computing for computer scientists. Cambridge University Press.
http://www.sci.brooklyn.cuny.edu/~noson/qctext.html
Kode program Algoritma Deutsch-Jozsa Matlab/Octave di Github =
https://github.com/keamanansiber/qiskit/blob/master/Matlab_Octave/Deutsch_Jozsa_Algorithm_Matlab.m