Квантовые вычисления. Ожигов Ю.С. - 45 стр.

UptoLike

ВУЗ: 

МГУ | Москва

Составители: 

Рубрика: 

k
k χ
i
= a
i
0
|N
1
, N
2
, . . . , N
k
i+ a
i
1
|e
1
, N
2
, . . . , N
k
i +
. . . + a
i
k
|e
1
, e
2
, . . . , e
k
i + R
i
R
i
|. . . , N
p
, . . . , e
q
, . . .i
Z
k
= (−1)
k
W
(k)
R
(k)
0
W
(k)
F
(k)
,
W
(k)
= W
1
N
W
2
N
. . .
N
W
k
N
I W
i
x
i
i = 1, 2, . . . , k
R
(k)
0
= R
01
N
. . .
N
R
0k
N
I R
0i
x
i
i = 1, 2, . . . , k F
(k)
=
F
1
N
. . .
N
F
k
N
I F
i
x
i
e
i
I
A
χ
i
= Aχ
i−1
A 2
kn
A
A
r
k + 1
|N
1
, N
2
, . . . , N
k
i, |e
1
, N
2
, . . . , N
k
i, . . . , |e
1
, e
2
, . . . , e
k
i A
r
A
r
= A
0
+ B A
0
0 2 0 . . . 0
−
2
N
0 2 . . . 0
. . . . . . . . . . . .
0 . . . −
2
N
0 2
0 . . . 0 −
2
N
0
.
−
2
N
(k+1)×(k+1) A A
r
B k > 2
˙
¯a = A¯a, a(0) = |N
−k/2
, . . . , N
−k/2
i,
¯a(i) ≈ |a
i
1
, . . . , a
i
k
i i k
√
N
∀x
1
∃y
1
∀x
2
∃y
2
. . . ∃y
k
p(x
1
, y
2
, . . . , x
k
, y
k
)
N = 2
n
x
1
y
1
. . . x
k
y
k
{0, 1}
n
O(
√
N)
(Cn)
k
C
                                                                                 
                                                    
       $           $         
                                                                  k               &      
   k      χ = ai |N , N , . . . , N i + ai |e , N , . . . , N i +
                                                                     i   0  1  2      k    1 1   2   k
. . . + aik |e1 , e2 , . . . , ek i + Ri        Ri  '         
| . . . , N , . . . , e , . . .i            
        p         q
                                                                      (k)
                                                       Zk = (−1)k W (k) R0 W (k) F (k) ,
 W (k) = W N W N . . . N W N I  '$    W  $    x  i = 1, 2, . . . , k 
  (k)            N 1 N 2 N  '                k                                                  i               i
                                                           & %  $  R  $    x  i = 1, 2, . . . , k  F (k) =
R0N= RN      01     . . .
                    N  '$R 0k       I                                                     0i               i
F1     . . . Fk           I                  Fi  $    xi                          e     I  $  
                                                                                                         i
&  
      & A      &                                                         
χi = Aχi−1 A                                     2 kn        &  
                                                                                                                       A   
Ar    $                k + 1                            '          
|N1 , N2 , . . . , Nk i, |e1 , N2 , . . . , Nk i, . . . , |e1 , e2 , . . . , ek i       Ar  Ar = A0 + B   A0
    
                                                                                                 
                                                            0         2         0      ...    0
                                                      −2             0         2      ...    0 
                                                      N                                        
                                                                                                                                  
                                                     
                                                      ... ... ...                               
                                                                                                    .
                                                                                            ... 
                                                      0             . . . − N2          0    2 
                                                                                          2
                                                            0        ...        0      −N     0
       &       #                                                 $   − 2    $ 
  (k+1)×(k+1)      %%   &                                          A  Ar      B     'N   k > 2
 % '    &    ' 
 &   '           
                                                                                                             
                                                                                                                

                                                                                                                                   
                                                                                                           )   ()

                                         ā˙ = Aā, a(0) = |N −k/2 , . . . , N −k/2 i,        
 ā(i) ≈ |ai , . . . , ai i  i        k  N       √
                                       '     &
             1            k
                                                                            $
           (   $        
     '  &    '          
     # $ 

!#)! #+() #!"$
                                         # %    
    
                            ∀x1 ∃y1 ∀x2 ∃y2 . . . ∃yk p(x1 , y2 , . . . , xk , yk )                                             
    %                                 % 


          
                                                          
     N = 2n   ' x y . . . x y   '  {0, 1}n 
                                                                              
                             1 1      k k
                                                               

  )#!)"
   
    
            
                     
                          
                                     O(√N )                      
                                                                          
                                                                           C
                                                                                     
                                                               
  (Cn)k                                        

Страницы