Ю.И. Ожигов - Квантовые вычисления, страница 7
Описание файла
PDF-файл из архива "Ю.И. Ожигов - Квантовые вычисления", который расположен в категории "". Всё это находится в предмете "квантовые вычисления" из 7 семестр, которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .
Просмотр PDF-файла онлайн
Текст 7 страницы из PDF
$ $ # ' ijk ' 0̃jk 1̃jk O I 0̃⊥1̃ O⊥I π h1̃1 |1̃2 i = h1̃1 |1̃2 i = 1 0 00 132' O # U' ' ) restN 8 $ $ ' $ $ 8CC ) $ & ' ' U & rest# $ ' & # & A $ & & %restα0̃ + β 1̃ O j ArestUrest−→α0̃jk + β 1̃jk −→(α0̃ + β 1̃)0̃k −→ α0̃ + β 1̃, & ) ) ) ) & # & ' δ $ rest ∆ ) & & ' ) $ ) )# # ∆ ' & ' ' δ ( ) δ' resrest' & & )$ ' ) # # $ & & ' ) & & # ) # & # $ $ & ( ' & $ # ' ) # # $ ' & ' ' U ' %& &$ & Arest & ' ' ' & a b a N b b a a $ b ' 12NNU ai b = a bi # $ bi # & & a1 a b b ' 212 U & k $ $ NNb1 , b2 , .
. . bk & U ai bj = a bji # $ bji & ' bj bj ' $ 12 bj , bj0 ' i = 1, 2; j, j 0 = 1, 2, . . . k, j 6= j 0 iiU 2k # # bji k * & # ) ' # $ & ' & ' ' # ' &# & # & # ) ( & # ) $ $ && $ %%$ ) # $ & ) # # '$ ) '' & &$ ' & ) # $ $ # ( % $ " " " "%$ " % '"$$ #$ " ! ! $ # "% % " % %$ $%" ( # %&" ' ) ) ' ) )$ # & ' & # ) ' &$ ) ( ) ' & $ $ ' &$ ) % $ * # # # ' $$ ) '# # ' ) ' $ ' ' ' ) $ '# $ ) # $ ' ' ) ' & # $ # # $' ' %% # # ) ) '# $ # '$ $ ) # # # $ ' & $ ' ) # & '# & # # # # ' (' n $ χ = P λ e , kχk = 1 2n j jj {e } λ jj χ −→ χ −→ . .
. −→ χ $ # χ −→ χ01tii+1 '# & ' ##$ $ # # $ % $ e $ e = | . . . , a, b, . . .i | . . . , a, φ(a) + b, . . .i a b + ' Qu a q(e) φ χ ) # # q(e) ' K = {0, 1, . . . , K − 1} χ = P λ e j j a ∈ {0, 1}n χ Xδa (χ) =|λj |2 .j∈Kj: q(ej )=a χaPδa (χ) =a∈{0,1}n1(' χ & ' # %&$ f, g {0, 1}n −→ {0, 1}n ' δχ (f, g) = X1/2δa (χ). a: f (a)6=g(a))""Quf , Qug #)#f, g χkQuf (χ) − Qug (χ)k ≤ 2δχ (f, g).' L = {j ∈ K | f (q(e )) 6= g(q(e ))} * kQu (χ) − Qu (χ)k ≤ 2( P (|λ |)2 )1/2 ≤jjjfgj∈L 2δχ (f, g).( χ0 −→ χ1 −→ .
. . −→ χt , '$ ) χ −→ χ & # #ii+1QufUi$ U # i χ −→χ0i −→χi+1 Ui (Quf (χ))ii V (χ) χt # i,fi+1 = Vi,f (χi ), i = 0, 1, . . . , t − 1$ ' t ' δ (χ) = pδ (χ) aa )""χ0 −→ χ1 −→ . . . −→ χta ∈ {0, 1}ngf fgχ0 −→ χ01 −→ . . . −→ χ0tkχt − χ0t k ≤ 2 t−1Xδa (χi ).i=0 $*& t " Vt−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−2t−1PP2δa (χt−1 ) + kχt−1 − χ0t−1 k = 2δa (χt−1 ) + 2δa (χi ) = 2δa (χi ).i=0i=0 $) %$ ) p B ' $ err P |λ |2 # χ = P λ ejtj∈B ) 1 − perrj jj $ $ $ %& %&φ : {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 1$ $ ' t(n) ' φ $ ) %&$ φ t(n) = o(pN/b(n)), n −→ ∞ )#!)" φφ(x) = 1 0 < < 1 p(n) t(n) φ p(n) −→ 0 (n −→ ∞) Sb %& 'nφ0 (x) = 0 X0 −→ X1 −→ . . . −→ Xt & a = δ (X ), i = 1, 2, . . .
, t; j = 1, 2, . . . , N, ijjiPPa ≤ t ∀iN = 2n a ≤ 1ijijijj T ' # τ # P ajiiτ≤ (j + 1)t/N T0 = ∅ P b̂j (j+1)t≤ tb̂j ' Lj = Tj \ Tj−1 Nj b # 1, 2, . . . , N ' D b # # ' ' L bjjj $$ $ ' Eb = bb̂ /N jjφ0 D %& φ1 X00 = X0 −→X10 −→ .
. . −→ Xt0 φ1 ' ξ = kXt − Xt0 k $ $$ $ & ')"" ε > 0 P (ξ > ε) −→ 0 n −→ ∞ $ $$ Eη 2 ≥E η i 1, 2, . . . , N j r PrP√Pr Pt bEξ = 2Eaiτ ≤ 2E t bj (j + 1)t/N = √2Ebj (j + 1)/b ≤Nijjτ ∈Dr Pr Pbb̂j (j+1)o(1) E bj (j + 1)/b ≤ o(1) 1b= o(1) (n −→ ∞).N2jj ) P (ξ ≥ ε) ≤ Eξ/ε ε % P (ξ ≥ ε) ' n ' ) $ # % G ) p ' err#perr = 0.0016, N > 1000 %& f ∈ G b P ) f X = λ e t B = {j | f (e ) = 1}, ε =j0Pj ∈B/|λj |2 . j jj ε0 ≤ perr , X ' e , j ∈ B ) p tjP err 'fcj = j/N, j = 0, 1, . .
. ; Lj = {j ∈ B | cj ≤ |λj |2 < cj+1 } ζ0 = l̂j cjj ˆl = card(L ) jj|1 − ζ0 | ≤ ε0 +b< 2perr (N −→ ∞).N %& f 0 ∈ S $ B 0 = {j | f 0 (e ) = 1} bj$ l f 0jlj = card {j | j ∈ Lj ∩ B 0 }. El = bl̂ /N f 0 jjPSb & ζ =lj cj ' $$ $ $ f 0 j ' Eζ =Xcj Elj =jX cj bl̂jjN= O(1)b/N = o(1) (N −→ ∞) ) P (ζ ≥ 0.9) ≤109 Eζ P (ζ ≥ 0.9) −→ 0 (N −→ ∞). ' card(G)/card(S ) = = const b0 X 0 = P λ0 e $ %& f 0 jtjj f 0 ∈ G 0X0≤|λ0j |2 ≤ perr .
Pj ∈B/ 0 ξ 2 −→ 0 (N −→ ∞). ' j∈B 0 \B0|λ0j |2 = r .|λ0j |2 = q 0 , j∈B∩B 00j ∈B∪B/PPPξ 2 = kXt − Xt0 k2 =|λj − λ0j |2 +|λj − λ0j |2 +00j∈B\Bj∈B \BPP|λj − λ0j |2 +|λj − λ0j |2 .P0j ∈B∪B/|λ0j |2 = z 0 Pj∈B 0 \B|λj |2 = q,P0j ∈B∪B/|λj |2 = z,Pj∈B∩B 0|λj |2 = r, q ≤ ε ≤ pz ≤ perr ka − bk ≥0err# * |kak − kbk|a, b $ ) δ = |√q 0 − √q|2 $ ) √√| z 0 − z|2 N )$ j∈B∩B 0 ξ 2 < perr .$ N q 0 < 4p $ q 0 ≥err√√ 4perr perr > δ ≥ ( q 0 − perr )2 ≥ perr P 0 20z < 4pN −→ ∞|λ | = q 0 + z 0 <err j ∈B/j P 0 28perr $ |λj | > 1 − 8perr j∈B 0 r0 > 1 − 9perr .* L j1 .N $ |r−r0 | = |√r − √r0 |(√r + √r0 ) < 2√s ≤ 2√p s err |ζ − r0 | < 1 + 2√p ζ > 1 − 9p − 2√p − 1 > 0.903errerrerrNN |ζ − r| <0 # $ ' $ ω ∗ # ' # % ω #$ %& f : {0, 1}∗ −→ {0, 1}∗ x ∈ {0, 1}n k # $ f $ &$ f {0} (x) = x, f {k+1} (x) = f (f {k} (x)) x −→ f (x) −→ f (f (x)) −→ .
. . −→ f (. . . f (x) . . .) = f {T } (x)| {z }T ' $ T = O(2n/7 ) ' $ % & $ !' % !) * & $ # x n x # ' $ ' ) ' # %& f ' T $ # # T # # # L %& Par (g) =g(x) & g : {0, 1}n −→ {0, 1} x 2n−1 $ g ) %&$ F : {g} −→ {0, 1} {g} ' %&$ g : {0, 1}n −→ {0, 1} T = %$ " & % %# ($ % " ! &$ %&%($) & ' % % %$ % ! % " o(2n ), n −→ ∞ # %&$ ' T g $ '$ '$ & '$ & %&$ Par (g) ' &% g ' # &%# # # '# # ' )$ $ $ # & ' T ) ' # T )#!)" nT = O(2 7+ε ), ε > 0fTTf & n ' $ $ %& f # & $ $ x & f {T } (x) f $ $ # T ' )$ $ & & ' $ $ & $ ' ) # T &$ ' & $ $ )#!)" fTf√Ω( T )f # ' $ ' N ' ' § ⊆ 2N ' σ N ∅, N ∈ § § &$ A \ B #∞∞# $ $ S A , T A § iii=0i=0 § %& # P : § −→ [0, 1] P (∅) =#$ 0, P (N ) = 1,{Ai } !∞∞[XPAi =P (Ai ).i=0i=0 σ ' S ⊆ 2N §(S) S ' ) $ §(S) $ ' $ P M ' # '$ g : {0, 1}n −→ {0, 1}n card(M ) = v .nnn v = 2n2n F ' # F #$ n %&$ f : {0, 1}∗ −→ {0, 1}∗ ' g , g , .
. . %&$1 2gi ∈ Mi '# % g ∈ M i = 1, 2, . . . , n ' A(g , g , . . . , g ) =ii1 2n{f | f = (g1 , g2 , . . . , gn , . . .)} P (A(g1 , . . . , gn )) = (v1 v2 . . . vn )−1 ) P S ' A(g , . . . , g )1n # n g , g , . . . , g $ §(S).1 2n # P σ § = §(S) !")! n x, y ∈ {0, 1} . f (x) = y nP (Bxy ) Bxy = {f | f (x) = y}. 2−n $ A, B ∈ §, P (B) 6= 0 P (A | B) = P (A ∩B)/P (B) $ A ' F1 , F2 , . .