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