Документ взят из кэша поисковой машины. Адрес оригинального документа : http://qilab.phys.msu.ru/papers/kurs4-sych-ru.pdf
Дата изменения: Mon Feb 4 18:39:24 2008
Дата индексирования: Mon Oct 1 19:45:39 2012
Кодировка:

. .. , ,

426

. .-. .,

, 15 2000 .

1 2 3 3.1 . . . . . . . . . . . . . . . . . . . . . . . . 3.2 . . . . . . . . . . . . . . . . . 3.3 . . . . . . . . . . . . . 3.4 . . . . . . . . . 3.5 . . . . . . . . 3.6 -- . 2 3 4 4 5 5 7 8 9 10 10 11 11 12 12 13 15 16 17

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

4 4.1 . . . . . . . . . . . . . . . . . . . . . 4.2 . . . . . . . . . . . . . . . . . . . . . 4.3 . . . . . . . . . . . . . . . . . . . . . . 5 5.1 . . . . . . . . . . . . . . . . . . . . . . . . . 5.2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

1

1

1982 [1]. . -, - ( ) , ( )? , . , . , . , . , . , -- , , .. , . , ( ). , . 1980 . [2] , , .e. , . , , . . [3] 1985 . , . , . 1992 [4] [5]. , , ( , ). , . , : , f (0) = f (1) . : f (0) f (1), -- . , 0 1 . . [6] 1993 [7] 1994 , ( ). . f : {0, 1} n {0, 1}n . () ( ), ( ). ,

2

, , . , , ""a, .. f (x a) = f (x) ( XOR). "". , ( n) , , , . [8] 1994 . , . [9] 1995 . N N . [10] 1995 . , , . -- . -, . -, () . . . "" "". ( ) ( , ). . , ( 10 -6 ), , -- . , "" . , , , [11].

2

. ( 3) . ( 4) "" ( ), ( 5) . ( ). [14] , IBM PC. : , . , -- 3

. " "( ) . Bernstein and Vazirani [6] , , . , . , (, ). . "" ( ) ( ) . , [12], . 5 "" "". 10. , , . , . , ( N 2 , N -- ""). - , .

3

3.1
-- , ( quantum bit of information, qubit). , . , 0 1, : |0 |1 . , |q = a |0 +b |1 . |0 |a|2 |1 |b|2 . , , : |a| 2 + |b|2 = 1. , , ( ) .

4

3.2
N , . , , , , Q = 2N . :
Q

. , , |6 , |6 = 110 2 , : q1 = |1 , q2 = |1 , q3 = |0 . ri , : |ri |2 -- |i . :
Q 1 1 i : |R = 2 |010 + 2 |001 + 2 |110 . - , 2 N . , , , 1 1 |R = |q1 |q2 ... |qN . , |R = 2 |00 + 2 |11 |q = a |0 +b |1 , .. . , (entangled) . , , , . , . () , . : , . , , . , , . i=1

|R =

i=1

ri |i . |i : i

|ri |2 = 1.

3.3
( gate ). , "" , . - . . . : G |R = |R . -- : 5

1 i 1 1 1 i G( |010 + |001 + |110 ) = |010 + |101 + |111 . 2 2 2 2 2 2 . , . , , , .e. . . . : , -- . . , , . NOT XOR (XOR CNOT NOT). : . ( (CCNOT) (CSWAP) -- ) ( NOT CNOT). -- NOT CNOT . NOT |q = a |0 +b |1 |q = b |0 +a |1 , .e. . NOT, .. . CNOT (Controlled NOT), : C N OT (R00 |00 +R01 |01 +R10 |10 +R11 |11 ) = R00 |00 +R01 |01 +R11 |10 +R10 |11 XOR. 1000 0 1 0 0 C N OT = 0 0 0 1 0010 | | C N OT : | | 0 0 1 1 0 1 0 1 | | | | 0 0 1 1 0 1 1 0 : ; | | ; | | 6

G(|p + |q ) = G |p +G |q ). :

N OT =

01 10

.

:

N OT :

|0|1| . |1|0|

. ( ). . "" ( , ). . , -- . . . , -- , 1 () . : "" , , , "" . Gate, Gate -- . NOT -- .

3.4
NOT CNOT . , , . : H (Hadamard), R (rotate), S (swap), CCNOT ( ), CSWAP ( ). () , , . 1 H |x = (-1)xy |y 2 Rk,l (|k , |l ) = (|k , (k 1 + k e
i 2
k-l

) |l );

S(|x , |y ) = (|y , |x );

CCNOT(|x , |y , |z ) = (|x , |y , |x y z ); CSWAP(|x , |y , |z ) = (|x , |x z + x y , |x y + x z ). , -- 2 ( CNOT): a b = a + b mod 2. : 1 0 0 0 0 0 1 0 0 1 0 0 0 0 0 1 1 0 0 0 0 1 0 0 0 0 0 0 1 0 k 0 ei2
-l

1 H: 2

11 1 -1

;

S:

;

R

k,l

:

;

7

( -- , NOT, CNOT, SWAP, CCNOT, CSWAP):
f a q a q q a q

CCNOT :

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 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

;

CSWAP :

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 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 1

.

SWAP CNOT :
qaq aqa

: |0 |1 |0 |1 |1 |1 |1 |0 ; |1 |0 |1 |1 |0 |1 |0 |1 ; |1 |1 |1 |0 |1 |0 |1 |1 ; |0 |0 |0 |0 |0 |0 |0 |0 , .

3.5
, , . , (, "" 1 0 ). N (N -- ). ( ) N . , , ( -- ). N . 3 e N . , , . (.. , ) ( ). : , , , 8

1 1 , |R1 = 2 |10 - 2 |11 . |11 . |11 1 . 1. 2 1 1 . |R2 = 2 |10 + 2 |11 . |10 , .. . , . . , . . , . . .

. , , , . . CH (Controlled Hadamard), : 10 0 0 0 1 0 0 . CH = 1 1 0 0 2 2 1 1 00 -2 2

3.6 --
. , , . , f (0) = f (1) . , . . . : U f : |x |y |x |y f (x) , , f (x) = 1. |x |y 0 1, , , 1 . 0 1: 2 (|0 ± |1 ), H . 1 1 : |0 2 (|0 + |1 ) |1 2 (|0 - |1 ). , :

9

i Hq i HU

i H
f

: 1 1 |0 |1 (|0 + |1 )(|0 - |1 ) (-1) 2 2
f (0)

|0 +(-1)

f (1)

|1

(|0 - |1 )

1 1 (-1)f (0) + (-1)f (1) |0 + (-1)f (0) - (-1)f (1) |1 (|0 - |1 ) 2 2 , |0 |1 . . U f , , , . 1 2 (|0 ± |1 ) f (x). 1 2 (|0 ± |1 ) . H , , |0 |1 . . 0, : f (0) = f (1) (.. (-1)f (0) - (-1)f (1) = 0), 1, f (0) = f (1). .

4

4.1
. , . . : P NP ( , , ). - (Polynomial), , .. . NP- (Nondeterministic Polynomial) ( , ) . NP- , ( ). NP- NP- NP-. - -, NP. -- . , , , . -, , NP. NP- -- , - 10

TSP (Traveling Salesman Problem). : . - "" , . ( ), -- P- , NP -- NP. [14], , , .. . . , P = N P , P/NP .

4.2
, , . ( ). , , , , .e. . [13], , .

4.3
|q = a |0 +b |1 . a b , |a|2 + |b|2 = 1. -- : |q = (q1 , q2 , q3 , q4 ). . : |q = (q1 + iq2 ) |0 +(q3 + iq4 ) |1 .
4

, -- . , , . , , - . , . . . ( 11

i=1

2 qi = 1 : |qi | 1. ,

). , . , , , , . , , (. ). (q 1 , q2 , q3 , q4 ). . , , , , . NOT CNOT, . NOT FuncNOT CNOT -- FuncCNOT. N OT (a |0 +b |1 ) = b |0 +a |1 F uncN OT (q1 , q2 , q3 , q4 ) = (q3 , q4 , q1 , q2 ) C N OT (R00 |00 +R01 |01 +R10 |10 +R11 |11 ) = R00 |00 +R01 |01 +R11 |10 +R10 |11 F uncN OT (R00 , R01 , R10 , R11 ) = (R00 , R01 , R11 , R10 )

5

5.1
, , . "", , . (, ), . 1994 129- , RSA129 [18]. 1600 , , 8 . 150 . 400 . (400 ) , .. ( ). . "" (< 10 ). : , 12

, ?

5.2
, . ( , ). , ( ) , , . , , "". "" , . : , "" SWAP , "". "" .

. 1: 1-2. 1-2, -- "". S SWAP (. ). N 2 , N -- ( ). , , . -- (QFFT Quantum Fast Fourier Transform). ( ). Q = 2n . , -

13

|a | |
Q,a

Q,a

, : e
i2
a Q

1 Q

Q-1 b=0

b

|b

, , . : 1 |Q,a (|0 +ei20.a1 |1 )(|0 +ei20.an-1 an |1 )...(|0 +ei20.a1 ...an-1 an |1 ) Q a1 ...an -- : |a = |a1 ...an . , 1 |b | Q,a ( 1, .. e
n j =1 i2 (x+N )

e

i2 x

, N ): 2
n-1 an

-n

ab = 2 ·b
n

-n

n

ai 2

n-i

bj 2

n-j

=

i,j =1

0.a1 a2 ...an · bj 2

n-j

= 0.an · b1 + 0.a

· b2 + ... + 0.a1 ...a

n-1 an

|b . , : "" Rl,k Hi , . , . n - , , : F =H
l-1

R

l-2,l-1

H

l-2

Rl-3,l-1 Rl-3,l-2 Hl-3 Rl-4,l-1 R ...H1 R0,l-1 R0,l-2 ...R0,1 H0

l-4,l-2

R

l-4,l-3

H

l-4

...

, [16],[8]. , , . 2. . , . 3. : F =H
l-1

R

l-2,l-1

Hl-2 Sl-1,l-2 Rl-3,l-2 Sl-1,l-2 R ...S1,2 R0,1 S1,2 R0,1 H0

l-3,l-2

H

l-3

...

4. , , - . "" (R l,k , Hi ) "", "" . , "", -- " " , . 14

. 2: , (. ).

. 3: -- .

5.3
-- , --. -- , --. , "". . . H Hadamard. i=l-k+1 Rotate Rl,k , | 1 > ( 1 i- ) , "" . S SWAP ( ).

15

. 4: , ( )

6

, . -- . ( "-- ) , , -- . . , - . ( ). 1

: Preskill [15], Aharonov [16], " "[17], Williams and Clearwater [18], ""[19], . [20].

1

16

[1] R. Feynman, Simulating physics with computers, Internat. J. Theoret. Phys., 21 (1982), pp. 467-468. [2] P. Benioff, The computer as a physical system: A microscopic quantum mechanical Hamiltonian model of computers as represented by Turing machines, J. Statist. Phys., 22 (1980), pp. 563-591. [3] D. Deutsch, Quantum theory, the Church-Turing principle and the universal quantum computer, Proc. Roy. Soc. London Ser. A, 400, (1985) pp.96-117. [4] D. Deutsch and R. Jossa, Rapid solution of problems by quantum computation, Proc. Roy Soc. London Ser. A, 439, (1992) pp.553-558. [5] A. Berthiaume and G. Brassard, The quantum chalenge to structural complexity theory, in Proceedings of the Seventh Annual Structure in Complexity Theory Conference, IEEE Computer Society Press, Los Alamos, CA, (1992) pp. 132-137. [6] E. Bernstein and U. Vazirani, Quantum complexity theory, in Proceedings of the 25th Annual ACM Symposium on Theory of Computing, ACM, New York, (1993) pp. 11-20. [7] D. Simon, On the power of quantum computation, in Proceeding of the 35th Annual Symposium on Foundations of Computer Science, IEEE Computer Society Press, Los Alamitos, CA, (1994) pp. 116-123. [8] P. W. Shor, Algorithms for quantum computation: Discrete logarithms and factoring,in Proceeding of the 35th Annual Symposium on Foundations of Computer Science, IEEE Computer Society Press, Los Alamitos, CA, (1994) pp. 124-134. [9] L. K. Grover, Quantum mechanics helps in searching for a needle in a haystack, Phys. Rev. Lett. 79, 325-328 1997 [10] A. Yu. Kitaev, Quantum measurements and the Abelian stabilizer problem (1995), in LANL e-print quant-ph/9511026, http://xxx.lanl.gov [11] J. Preskill, Reliable Quantum Computers (1997), in LANL e-print archive quantph/9705031, http://ru.arxiv.org/abs/quant-ph/9705031 [12] .. , " ", , 30, N 5 (2000) [13] E. Bernstein and U. Vazirani (1993), Quantum Complexity Theory, SIAM Journal of Computation 26 5 pp. 1411-1473 October, 1997

17

[14] A. Turing, "On Computable Numbers with an Application to the Entscheidungsproblem", Proceedings of the London Mathematical Society, Vol. 42(1937), pp. 230-265, erratum in 43(1937), pp. 544-546. [15] : http://www.theory.caltech.edu/ preskill/ph229 [16] D. Aharonov, "Quantum Computation"(1998), in LANL e-print archive quant-ph/9812037, http://ru.arxiv.org/abs/quant-ph/9812037 [17] " ", http://web.uni.udm.ru/ rcd/qc/index.html :

[18] C.P. Williams S.H. Clearwater, "Explorations in Quantum Computing", ISBN 0-38794768-X Springer-Verlag New York Berlin Heidelberg (1998). [19] ., http://www.computerra.ru/1997/47/3.html?inside "", N47(1997),

[20] . ( .), : http://www.mccme.ru/ium/s98/quantcomp.html.

18