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

UptoLike

ВУЗ: 

МГУ | Москва

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

Рубрика: 

χ
0
−→ χ
1
−→ . . . −→ χ
t
f g
f a ∈ {0, 1}
n
χ
0
−→ χ
0
1
−→ . . . −→ χ
0
t
g
kχ
t
− χ
0
t
k ≤ 2
t−1
X
i=0
δ
a
(χ
i
).
t V
t−1,g
kχ
t
− χ
0
t
k = kV
t−1,f
(χ
t−1
) −V
t−1,g
(χ
0
t−1
)k ≤
kV
t−1,f
(χ
t−1
) − V
t−1,g
(χ
t−1
)k + kV
t−1,g
(χ
t−1
) − V
t−1,g
(χ
0
t−1
)k ≤
2δ
a
(χ
t−1
) + kχ
t−1
− χ
0
t−1
k = 2δ
a
(χ
t−1
) + 2
t−2
P
i=0
δ
a
(χ
i
) = 2
t−1
P
i=0
δ
a
(χ
i
).
p
err
B
P
j∈B
|λ
j
|
2
χ
t
=
P
j
λ
j
e
j
1 − p
err
φ : {0, 1}
n
−→ {0, 1} S
φ
G ⊆ S
> 0 φ ∈ G
card(G)/card(S)
p p : 0 < p ≤ 1
S
O(1)
φ(0), φ(1), . . . , φ(k)
p = 1 − 2
−k
S = S
b
b x φ(x) =
1 n, t(n), b(n) t = o(
p
N/b), n −→ ∞, N = 2
n
t(n)
φ
φ
t(n) = o(
p
N/b(n)), n −→ ∞
φ t(n) φ(x) = 1
0 < < 1 p(n)
                                                                                                

 
    )""               χ0 −→ χ1 −→ . . . −→ χt
                                                        
                                                                      
                                                                                               
                                                                                                 f            g
       
     f
                            g
                                  a ∈ {0, 1}n            χ0 −→ χ01 −→ . . . −→ χ0t

                                                                      t−1
                                                                                                                             

                                                                      X
                                                    kχt − χ0t k ≤ 2         δa (χi ).

        
                                                                      i=0



   *&  t                          "          V                                $
                                                                                  t−1,g
     

                           kχt − χ0t k = kVt−1,f (χt−1 ) − Vt−1,g (χ0t−1 )k ≤
                           kVt−1,f (χt−1 ) − Vt−1,g (χt−1 )k + kVt−1,g (χt−1 ) − Vt−1,g (χ0t−1 )k ≤
                                                                            t−2
                                                                            P                t−1
                                                                                             P
                           2δa (χt−1 ) + kχt−1 − χ0t−1 k = 2δa (χt−1 ) + 2      δa (χi ) = 2     δa (χi ).
                                                                                 i=0            i=0
     
     $)                   %  $  
 )  p       B  '     &  #   $   
              err
 P |λ |2      #           χ = P λ e
                  j                                                                                                   t       j j
           j∈B                                                                                                            j
  )    1 − p 
                   err


                                                                         
                                                                                                            

 $   $      $ %&      %&
φ : {0, 1}n −→ {0, 1}   )   S      ' $ & $    $
'                     )  
   $         # %& $ φ    $& $   
'   G ⊆ S       %    
              )   > 0     $    φ ∈ G 

              card(G)/card(S)     '  
) p    p : 0 < p ≤ 1 
     S  '    #   # %& $  ) '  ' &   
                 O(1)      ) $    $
     $ φ(0), φ(1), . . . , φ(k)   $    %&  $  
  p = 1 − 2−k 
     S = S  '    #   # %& $    b  x     φ(x) =
               b
     n, t(n), b(n)      t = o(pN/b), n −→ ∞, N = 2n    
  $      $ ' t(n)             
1
                                                                                                                 
'                  φ      
  $    )   %& $ φ 
                                                                              
                       t(n) = o(pN/b(n)), n −→ ∞              
          
 )#!)"
       φ                          t(n)               φ(x) = 1 
                         0 <  < 1    p(n)            
                                                                             
                                                                                             

Страницы