|
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:
| 1234567891011 | 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_0input01_output1 = Ufunction_gate * qubits_01_0input10_output0 = Ufunction_gate * qubits_10_0input11_output0 = Ufunction_gate * qubits_11_0 |
Deutsch-Jozsa: kasus fungsi seimbang dengan 2 input.
Jumlah input teratas = 2 qubit.
Kode Program Matlab/Octave:
| 12345678910111213141516 | qubit_0 = [1; 0]qubit_1 = [0; 1]Nx = 2input_x = [1]for k=1:Nx input_x = kron(input_x, qubit_0);endinput_xy = kron(input_x, qubit_1);checkpoint_0 = input_xyHadamard_gate = [ 1/sqrt(2) 1/sqrt(2); 1/sqrt(2) -1/sqrt(2) ]Hx = [1]for k=1:Nx Hx = kron(Hx, Hadamard_gate);endHxy = kron(Hx, Hadamard_gate);checkpoint_1 = Hxy * checkpoint_0 |
Kode Program Matlab/Octave:
| 12345678910111213141516171819202122 | qubit_0 = [1; 0]qubit_1 = [0; 1]Nx = 2 input_x = [1]for k=1:Nx input_x = kron(input_x, qubit_0);endinput_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);endHxy = 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:
| 123456789101112131415161718192021222324 | qubit_0 = [1; 0]qubit_1 = [0; 1]Nx = 2 input_x = [1]for k=1:Nx input_x = kron(input_x, qubit_0);endinput_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);endHxy = 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_1Identity_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:
| 1234567891011121314151617181920212223242526272829 | 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 = 2SecretFunction_gate = balance_A_function input_x = [1]for k=1:Nx input_x = kron(input_x, qubit_0);endinput_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 https://keamanansiber.id/blog/2020/07/09/praktek-algoritma-deutsch-jozsa-dengan-matlab-octave/
|
