Ю.И. Ожигов - Квантовые вычисления, страница 4
Описание файла
PDF-файл из архива "Ю.И. Ожигов - Квантовые вычисления", который расположен в категории "". Всё это находится в предмете "квантовые вычисления" из 7 семестр, которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .
Просмотр PDF-файла онлайн
Текст 4 страницы из PDF
, Nk i, |e1 , N2 , . . . , Nk i, . . . , |e1 , e2 , . . . , ek i Ar Ar = A0 + B A0 020...0 −202...0 N . ... ... ...... 0. . . − N202 20...0−N0 & # $ − 2 $ N (k+1)×(k+1) %% & A A B ' k > 2r % ' & ' & ' ) () ā˙ = Aā, a(0) = |N −k/2 , . . . , N −k/2 i,√ ā(i) ≈ |ai , . . . , ai i i k N 1k ' & $ ($ ' & ' # $!#)! #+() #!"$ # % ∀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 )(Cn)kC % ' √N (log N )k−1 # ) ) %& P ∀x∃y ' & $ $ # # ( & $ & O(p|y ||x ||y | . . .
|x |) ) √N k11k( & ' % $ $ $ ' # $ # & $ ($ ' & P λ e # $ e ' 'ii i i # & ' ' e i$$ $ $ ' ' & % ## # )$ χ#'()') ξ kχ − ξk < %!) ))')x ∈ {0, 1}nf : {0, 1}n −→ {0, 1}perr ξ0 −→ ξ1 −→ . . . −→ ξT ,N x ξ0 = |x, 0i, ξT = (ξ˜ |f (x)i) , < perr /2, * ξ f (x) )$ 1−p Terr$ ' P λ |x , 0i iii P λ ξ˜ N f (x )i + ¯, ¯ = P λ ¯ kēk < p√N /2 N # # $i iii xii Ti & )$ '$)$ $ O(√N ) 1$ #' x p(x) p, N = 2|x| !) #)') |0, 0,.
. ., 0i1|0, 0, . . . , 0, γi pγ=1∃x p(x) 0 √N1MnM = log(1/)pM (n + 2) + 2 # ) m $ $ χ $ {1, 2, . . . , m} W F W F χ P e /√N 0jpj * )$ & m = √N x 1 1/2 ) ' # )"" m = 1, 2, .
. . 1 X|χi,|0 . . . 0i −→ . . . −→ √m χ≤mχ $ '$ ' ' $ ' M # 2n '$ ' # |0 . . . 0i N |x x . . . x i1 2M ' xi =Xjλj ej ,Xp(ej ) |λj |2 ≈ 1/2, e p # j|0 . . . 0iOXOOOXO( (λj |ej i|p(ej )i))...( (λj |ej i|p(ej )i)),j j p(e ) ∈ {0, 1} # p j' |a, bi |a, b + p(a) i )"" |σ1 σ2 . . . σM 0M+2 i −→ |σ1 σ2 . . . σM 0M+1 σi σ=1∃i ∈ {1, . . . , M } : σi = 1 ∀i = 1, 2, . .
. , M σ, σi ∈ {0, 1} f | i f| 0 0 0 i −→ | 0 0 0 if| 0 0 1 i −→ | 1 0 1 if| 1 0 1 i −→ | 1 1 1 if| 1 0 0 i −→ | 1 0 0 i ' ) ) i i $ $ σ i = 1, 2, . . . , M, i|δ1 δ2 . . . δM δM+1 . . . δ2M σ0i |δ1 δ2 . . . δ2M σσi |σ0i −→ |σσi, & |σ σ . . . σ 0M+1 σi 1 2M $ σ , σ , . . . , σ 1(|0 . . . |0i2 MOXOOOXOO(λj |ej i|p(ej )i))...( (λj |ej i|p(ej )i))γ) .j j M # n '$ ) $ # # # $ x $$ 1 − 1 $ 2M ) M = log 1 & γ $ (|0 . . . 0γi) ' p#'()') $ p ' p % % z , z , .
. . , z 12q∀x1 ∃x2 ∀x3 . . . Qk−1 xk−1 Qk xk p(z1 , z2 , . . . , zq , x1 , . . . , xk ). Q , Q ∈ {∃, ∀} 12!) #)') | z1 . . . zq 0 . . . 0i −→ . . . −→ | z1 . . . zq 0 . . . 0γi 122kPi=1|xk |(M n)kz1 , . . . zqγ= 0, (5) ,1, (5) .*& k k = 0 " ' ' k ) ' k * k−1P1|xi |2 $ $ ' 2 i=1 $ (M n)k−1 # p (M n)k−1 $ %&z1 , . .
. zq , xk −→ T1 ∈ {0, 1} T1 = 1 ∀x1 ∃x2 . . . Qk−1 xk−1 p(z1 , . . . , zq , x1 , . . . , xk−1 , xk ) ) & $ %&k−1 z1 , . . . , zq −→ T ∈ {0, 1}T =1∀x1 ∃x2 . . . Qk−1 xk−1 Qk xk p(z1 , . . . , zq , x1 , . . . , xk ) # $( ' Qk ∃ $ k−11 2 2 |xk | ) M n '$ #k−1k−1P1|xi | ' ' 2 2 i=1) (M n)k−1 kP1|x1 | p $ $ 2 2 i=1) (M n)k p # (M n)k $(Qk ∀ k−1& 0 −→ 1, 1 −→ 0 ' $ ' ' ' % $ m $ ' N # $ 1 ' N $ π )2 f (x) = 1 m − 2 # # $ N , N , . . . , N34m m − 2 # d , d , . . .
, d 1 2m−2 ' N N = {xj ; j = 1, 2, . . . , l } s = 1, 2, . . . , m ssssm& x1 , x2 , . . . , xl2 # # P l = N s222s=1 ! H $ H N̄ ) ' # ' % ' U I tar U H xs s = 1, 2, . . . , m, j =j1, 2, . . . , ls # x2j −1 # x1j 1 #xsj s ≥ 3 ei(dk −π) , dk ∈ [0, 2π) vk = eidk q k $ d d = d γ = l2 kkN' γ −→ 0 (n −→ ∞) ' ) Pej = √1|xi e2 &$ # $ ljx∈Nj 0̃ √1 P |xi ) Nx∈N̄' e & H 0j m * ) $ 0̃ ' $ $ I H tar0 I H e20) $ )#!)" l /N1q√l2−→ 1 (N − l1 − l2 )/d N l2 −→ 0N = o(d)I0̃ U0̃ tt = q π4l2Nn −→ ∞e2 H I U # 00̃ * & G = −I U # 0̃ & I Itar ' H ' e 0̃ ' 0̃ G02 $ &$ G ' * & ' ) ' $ &$ ' e e 1 2!)''#) &()')) % q & e , e , .
. . , e H h0̃|e i = l2 = X 1 2m02Nqlj%h0̃|ej i = N = Yj−2 j = 3, 4, . . . , n xj = 2Xjm P l /N # jj=2% q√' P l /N = 0̃ = (√1 − , X, Y , . . . , Yl1T1− = 1 −j1m−2 )N =j≥22+o() 0̃ ≈ 0̃app = (1, X, Y1 , . . . , Ym−2 )T O() ' & ! H 0 $ H 0 U I m H & U 00̃ $ 100...0 0 −10...0.0 −v1 . . .0U = 0 ... ... ... ...... 00...0 −vm−2 $ & I I ≈0̃0̃I0̃app = V −1 Ie1 V & V V 0̃app = e1 # V −1 Ie1 V 0̃app =−V −1 e = −0̃ & V 1appV =V −1 = 1−X−Y1...−Ym−2X Y1 Y2100010... ...
...000−X −Y1 −Y2100010.........Ym−2000 1XY1... −1 0 01Ie1 = 00... ...* ' & I0̃app = V −1 Ie1 V = G = −I0̃app U = . . . Ym−2...0...0.........11xy1...ym−2−1−x−y1...−ym−2,. . . −Ym−2...0....0...... ...1 ... 0... 0 ... 0 ... ...−x −y11001... ...00−x −y1 v1100v1......00−y200...0−y2 v200...0. . . −ym−2...0...0.........1,. .
. −ym−2 vm−2...0...0.........vm−2. #('# %! )' ' &$ ' ) $ $ $ $ kAk = max kAx̄k.kx̄k=1 ) ' G = −I $ & −I U 0̃app U0̃ G kG − Gk=kUkkI−Ik=kI−Ik=k0̃− 0̃app k = O() exactexact0̃0̃app0̃0̃app'' G = G GGexactexactP+ ∆ljqj≥2 &$ & ν = t∆ = √ k∆k = O() t = Nl2N l2P ' l2 = O( )l2 ν = o(1) j≥3q P = o(l ) ν l2 o(1) # # ν = o(1) 2Nj≥3t−1 Gt = (G tttexact + ∆) = Gexact + O(t∆Gexact ) = Gexact + o(1) Gt ' G G )exactexact $ G #$ p I & ) m−2 (λ) = |G − λI|$ p(λ) = 0m−2 1 − λ −x x1−λpm−2 (λ) = y10 ......
ym−20 x y1(−1)m+1 ym−2 vm−2 y2 ... ym−2−y1 v1 −y2 v200v1 − λ0......001−λ00v1 − λ00......00. . . −ym−2 vm−2...0...0.........vm−2 − λ... 0... 0... 0... ...... 0= + (vm−2 − λ)pm−3 (λ) =2ym−2vm−2 (1 − λ)(v1 − λ) . . . (vm−3 − λ) + (vm−2 − λ)pm−3 (λ). )2pm−2 (λ) = (vm−2 − λ)pm−3 (λ) + ym−2vm−2 (1 − λ)(v1 − λ) . . . (vm−3 − λ).* −p1 (λ) = (λ − 1 + ix)(λ − 1 − ix)(v1 − λ) + v1 y12 (1 − λ) ' # $ % # pm−2 (λ) = (λ − 1 + ix)(λ − 1 − ix)(v1 − λ)(v2 − λ) . . . (vm−2 − λ)+v1 y12 (1 − λ)(v2 − λ) . .
. (vm−2 − λ)+v2 y22 (1 − λ)(v1 − λ)(v3 − λ) . . . (vm−2 − λ)+2. . . + vm−2 ym−2(1 − λ)(v1 − λ) . . . (vm−3 − λ). p (λ) = (λ − 1 + ix)(λ − 1 − ix)(v − λ)(v − λ) . . . (v012m−2 − λ) p0m−2 (λ) = p + δ pδ = v1 y12 (1 − λ)(v2 − λ) . . . (vm−2 − λ)+v2 y22 (1 − λ)(v1 − λ)(v3 − λ) . . .
(vm−2 − λ)+2. . . + vm−2 ym−2(1 − λ)(v1 − λ) . . . (vm−3 − λ). p (λ) δ ( p (λ) λ = 1 − ix, λ =00121 + ix, λ3 = v1 , . . . , λm = vm−2 pm−2 λ̃1 , λ̃2 , . . . , λ̃m ' & ' λ λ̃ & δ #jj$ λ 1,2 |λ − λ | = o(|v − λ |) $ |λ − λ | δ 2 ) p '12j112 q ) %%& A = λ−v = Ω(d) λ1 λ2 |λ1 − λ2 | q $ q = γ(v − λ) · · · (v− λ) & ' σ = |λ − λ̃ | + |λ − λ̃ | 1m−2n−2m−2P vj yj2 (1−λ) γ(vj −λ)j=11122* v − λ = O(d ) 1 − λ = O(γ) σ = O(δ/q ) =jjPlj o(γ) P l = o(d√N l ) σ = O( d1j2N)0j≥3j≥3λ̃1,2 = 1 + −ix + o(γ) λ̃3 = v + o(γ) $ # # $ λ̃ = 1 + −ix + o(γ) 1,2 λ = 1 − ix + o(γ) $ & ā = (a, b, w , . .
. , wT1m−2 ) $# $ ā % (G − λE)ā = 0̄ ' ixxy1...ym−2−x−y1 v1ix00 v1 − 1 + ix......00. . . −ym−2 vm−2...0...0....... . . vm−2 − 1 + ix $# $ #ixaxay1 a...ym−2 aabw1...wm−2 = −xb+ixb−y1 v1 w1−...−ym−2 vm−2 wm−2...+(v1 − 1 + ix)w1.........+(vm−2 − 1 + ix)wm−2o(γ)o(γ)o(γ)...o(γ).= o(γ)= o(γ)= o(γ)...= o(γ) ' $ q ) # w = yj a l2jvj −1+ixN = o(d) w = o(1) o(1) a = i, b = −1 j λ = 1 + ix + o(γ) a = i, b = 1 o(1) wj = o(1) # # # $ a = 0, b = 0 o(γ) ' ' e , e 1 2* & n −→ ∞ ' ' e , e1 2 o(γ) # # $ o(1) # # t &$ 1/γ &' G o(1) ) %&$ # &$ %& %& f : {0, 1}n −→ {0, 1}n #$ % & %& $ $ $ % $ & ' $ $ %%& ) $ N = 2n $$ ) # # '$ ' %& f # f (x ) ≤ f (x ) ≤ . . .