21 Quantum calculator simulator based on reversible operation 1100366 2010 3 1
i
Abstract Quantum calculator simulator based on reversible operation Ryota Yoshimura Quantum computation is the novel computational scheme that has attracted recent attention because of its potential for massive parallelism. Another hallmark of quantum computation is its reversibility which helps expand the computational toolbox. As opposed to such popular subject of investigation as Shor s and Grover s algorithms, which are powerful but specialized, there has been very few research on the subject of elementary algebra of addition, which is the most basic and universal algorithm. In this work, we theoretically design the reversible quantum circuit that is capable of adding and subtracting two N qubits. Based on this design, we construct a quantum calculation simulator on conventional computer, and examine the power and possibility of quantum computation. key words Quantum bits Quantum logic gate Reversible operation ii
1 1 1.1................................... 1 1.2................................... 1 2 2 2.1.................................. 2 2.2.................................. 3 2.3................................ 3 2.3.1............................. 3 2.3.2................................ 3 2.3.3............................ 4 Cx................................ 5 Tf................................ 6 2.4.................................... 6 3 7 3.1................................... 7 3.1.1 2 1..................... 7 3.1.2 3 1........................ 8 3.1.3 2 n....................... 8 3.2................................. 9 3.2.1............................ 10 4 11 4.1 0 0..................... 12 iii
4.2 255 255................... 13 4.3 12 88.................... 14 4.4 55 199................... 15 4.5 123 210................... 16 5 17 18 19 iv
2.1 Cx.................................... 5 2.2 Tf..................................... 6 3.1 2 1......................... 7 3.2 3 1............................ 8 3.3 2 n............................ 9 3.4 E....................... 9 3.5................................. 10 4.1 0 0...................... 12 4.2 255 255................... 13 4.3 12 88..................... 14 4.4 55 199.................... 15 4.5 123 210................... 16 v
2.1 Cx.................................... 5 2.2 Tf..................................... 6 vi
1 1.1 1.2 1
2 2.1 (qubit Qbit) 0 1 0 1 0 1. Q = 0 + 1 (2.1) 2 + 2 = 1 (2.2) 1 ( ) 1 0 = 0 (2.3) 2 0 = 1 0 0 0 (2.4) 2
2.2 2.2 2 2.3 2.3.1 A AA = A A = I (2.5) A A 2 n 2 n 2.3.2 AND OR NOT AND OR 2 1 Controlled not gate (Cx) Toffoli gate (Tf) 3
2.3 2.3.3 2 I X ( 1 0 I = 0 1 ) (2.6) X = ( 0 1 1 0 ) (2.7) Controlled not gate Toffoli gate ( ) I 0 Cx = 0 X (2.8) T f = I 0 0 0 0 I 0 0 0 0 I 0 0 0 0 X (2.9) Cx Tf 4
2.3 Cx Cx 2.1 Cx 2.1 Cx Ain Bin Aout Bout 0 0 0 0 0 1 0 1 1 0 1 1 1 1 1 0 5
2.4 Tf Tf 2.2 Tf 2.2 Tf Ain Bin Cin Aout Bout Cout 0 0 0 0 0 0 0 0 1 0 0 1 0 1 0 0 1 0 0 1 1 0 1 1 1 0 0 1 0 0 1 0 1 1 0 1 1 1 0 1 1 1 1 1 1 1 1 0 2.4 6
3 3.1 3.1.1 2 1 a b 1 = C (0,1) x T (0,1,2) f 0, b, a = s 1, s 0, a Cx C x (0,1) c, b, a = c, b + a, a Tf T (0,1,2) f c, b, a = c + a.b, b, a, s 1 s 0 2 1 3.1 3.1 2 1 7
3.1 3.1.2 3 1 r a b 1 r + a + b = r s (1 2) = C x C x (0 2) T (1 2 3) f T (0 1 3) f T (0 2 3) f 0 b a r = r s a r. 3 1 3.2 3.2 3.2 3 1 3.1.3 2 n A + B = S 2 A = a n a 1 a 0 B = b n b 1 b 0 S = s n+1 s 1 s 0 2 n 3.3 a r s 8
3.2 3.3 2 n 3.2 3.4 n r E 3.4 E 9
3.2 3.2.1 3.5 E E 3.5 10
4 3 C 8 (1 ) 2 11
4.1 0 0 4.1 0 0 4.1 0 0 12
4.2 255 255 4.2 255 255 4.2 255 255 13
4.3 12 88 4.3 12 88 4.3 12 88 14
4.4 55 199 4.4 55 199 4.4 55 199 15
4.5 123 210 4.5 123 210 4.5 123 210 16
5 17
18
[1] D.Bouwmeester A.Ekert A.Zeilinger, 2007 [2] 1997 [3] 2002 [4] 1999 [5] 2002 19