Kode Program Matlab/Octave untuk Deutsch’s Algorithm
Download pdf dari materi tutorial Deutsch’s Algorithm dengan Matlab / Octave = DeutschAlgorithm
Deutsch’s Algorithm:
Deutsch, D. (1985). Quantum theory, the Church–Turing principle and the universal quantum computer. Proceedings of the Royal Society of London. A. Mathematical and Physical Sciences, 400(1818), 97-117.
https://royalsocietypublishing.org/doi/10.1098/rspa.1985.0070
Deutsch’s Algorithm: n inputs –> fungsi balanced atau constant?
Semua algoritma kuantum bekerja dengan kerangka dasar berikut:
– Sistem akan mulai dengan qubit dalam kondisi klasik tertentu.
– Dari sana sistem dimasukkan ke state superposisi.
– Diikuti dengan beberapa operasi unitary.
– Dan akhirnya, pengukuran qubit.
Problem dari Algoritma Deutsch:
Diberi fungsi f: {0, 1} → {0, 1} sebagai KOTAK HITAM
(di mana orang dapat mengevaluasi input, tetapi tidak bisa “melihat ke dalam” dan “melihat” bagaimana fungsi didefinisikan).
Tentukan apakah fungsinya seimbang atau konstan.
Illustration:
Secret_function = ??unknown??
Answer = OurAlgorithm( Secret_function ) * Input
Mari kita siapkan suatu algoritma, sehingga kita dapat menemukan jawabannya (Apakah itu Fungsi Seimbang atau Konstan?)
Namun, untuk sistem kuantum: setiap gerbang harus UNITARY (dan karenanya dapat dibalik / REVERSIBLE)
Dengan output, kita harus dapat menemukan input.
Kode program Matlab / Octave:
U_function = [ 0 1; 1 0 ] input_0 = [1; 0] result_1 = U_function * input_0 input_1 = [0; 1] result_0 = U_function * input_1
Kode program Matlab / Octave:
qubit_0 = [1; 0] qubit_1 = [0; 1] input_00 = kron(qubit_0, qubit_0) input_01 = kron(qubit_0, qubit_1) input_10 = kron(qubit_1, qubit_0) input_11 = kron(qubit_1, qubit_1) U_function = [ 0 1 0 0; 1 0 0 0; 0 0 1 0; 0 0 0 1 ] output_01 = U_function * input_00 output_00 = U_function * input_01 output_10 = U_function * input_10 output_11 = U_function * input_11
Kode program Matlab / Octave:
qubit_0 = [1; 0] qubit_1 = [0; 1] checkpoint1 = kron(qubit_0, qubit_1) Hadamard_gate = [ 1/sqrt(2) 1/sqrt(2); 1/sqrt(2) -1/sqrt(2) ] checkpoint2 = kron(Hadamard_gate, Hadamard_gate) * checkpoint1
Kode program Matlab / Octave:
qubit_0 = [1; 0] qubit_1 = [0; 1] checkpoint1 = kron(qubit_0, qubit_1) Hadamard_gate = [ 1/sqrt(2) 1/sqrt(2); 1/sqrt(2) -1/sqrt(2) ] checkpoint2 = kron(Hadamard_gate, Hadamard_gate) * checkpoint1 U_function = [ 0 1 0 0; 1 0 0 0; 0 0 1 0; 0 0 0 1 ] checkpoint3 = U_function * checkpoint2
Kode program Matlab / Octave:
qubit_0 = [1; 0] qubit_1 = [0; 1] checkpoint1 = kron(qubit_0, qubit_1) Hadamard_gate = [ 1/sqrt(2) 1/sqrt(2); 1/sqrt(2) -1/sqrt(2) ] checkpoint2 = kron(Hadamard_gate, Hadamard_gate) * checkpoint1 U_function = [ 0 1 0 0; 1 0 0 0; 0 0 1 0; 0 0 0 1 ] checkpoint3 = U_function * checkpoint2 Identity_gate = eye(2) checkpoint4 = ( kron(Hadamard_gate, Identity_gate) ) * checkpoint3
Cukup ukur qubit teratas.
Jika qubit itu dalam keadaan |0>, maka kita tahu bahwa f adalah fungsi konstan, jika tidak maka itu adalah fungsi seimbang.
Speedup (separuh): O(2) –> O(1)
Kode program Matlab / Octave:
balance_A_function = [1 0 0 0; 0 1 0 0; 0 0 0 1; 0 0 1 0] balance_B_function = [ 0 1 0 0; 1 0 0 0; 0 0 1 0; 0 0 0 1 ] constant_C_function = [1 0 0 0; 0 1 0 0; 0 0 1 0; 0 0 0 1] constant_D_function = [0 1 0 0; 1 0 0 0; 0 0 0 1; 0 0 1 0] U_secret_function = balance_B_function 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) ] DeutschAlgorithm = ( kron(Hadamard_gate, Identity_gate) ) * (U_secret_function * (kron(Hadamard_gate, Hadamard_gate) * (kron(qubit_0, qubit_1)) ) )
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 Deutsch’s Algorithm Matlab/Octave di Github =
https://github.com/keamanansiber/qiskit/blob/master/Matlab_Octave/Deutsch_Algorithm_Matlab.m