Ожигов Ю.С. Квантовые вычисления
Подождите немного. Документ загружается.
f
0
∈ S
b
B
0
= {j | f
0
(e
j
) = 1}
l
j
f
0
l
j
= card {j | j ∈ L
j
∩B
0
}.
El
j
= b
ˆ
l
j
/N f
0
S
b
ζ =
P
j
l
j
c
j
f
0
Eζ =
X
j
c
j
El
j
=
X
j
c
j
b
ˆ
l
j
N
= O(1)b/N = o(1) (N −→ ∞)
P (ζ ≥ 0.9) ≤
10
9
Eζ
P (ζ ≥ 0.9) −→ 0 (N −→ ∞).
card(G)/card(S
b
) =
0
= const
X
0
t
=
P
j
λ
0
j
e
j
f
0
f
0
∈ G
0
0 ≤
X
j /∈B
0
|λ
0
j
|
2
≤ p
err
.
ξ
2
−→ 0 (N −→ ∞).
ξ
2
= kX
t
− X
0
t
k
2
=
P
j∈B\B
0
|λ
j
− λ
0
j
|
2
+
P
j∈B
0
\B
|λ
j
− λ
0
j
|
2
+
P
j /∈B∪B
0
|λ
j
− λ
0
j
|
2
+
P
j∈B∩B
0
|λ
j
− λ
0
j
|
2
.
P
j∈B
0
\B
|λ
0
j
|
2
= q
0
,
P
j /∈B∪B
0
|λ
0
j
|
2
= z
0
P
j∈B
0
\B
|λ
j
|
2
= q,
P
j /∈B∪B
0
|λ
j
|
2
= z,
P
j∈B∩B
0
|λ
j
|
2
= r,
P
j∈B∩B
0
|λ
0
j
|
2
= r
0
.
q ≤ ε
0
≤ p
err
z ≤ p
err
ka − bk ≥
|kak − kbk| a, b
δ = |
√
q
0
−
√
q|
2
|
√
z
0
−
√
z|
2
N
ξ
2
< p
err
.
N q
0
< 4p
err
q
0
≥
4p
err
p
err
> δ ≥ (
√
q
0
−
√
p
err
)
2
≥ p
err
z
0
< 4p
err
N −→ ∞
P
j /∈B
|λ
0
j
|
2
= q
0
+ z
0
<
8p
err
P
j∈B
|λ
0
j
|
2
> 1 − 8p
err
0
r
0
> 1 − 9p
err
.
L
j
|ζ − r| <
1
N
.
|r−r
0
| = |
√
r−
√
r
0
|(
√
r+
√
r
0
) < 2
√
s ≤ 2
√
p
err
s
|ζ − r
0
| <
1
N
+ 2
√
p
err
ζ > 1 − 9p
err
− 2
√
p
err
−
1
N
> 0.903
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
| {z }
T
(x) . . .) = f
{T }
(x)
T = O(2
n/7
)
x n
x
f
T
T
Par (g) =
L
x
g(x) g : {0, 1}
n
−→ {0, 1}
2
n−1
g
F : {g} −→ {0, 1} {g}
g : {0, 1}
n
−→ {0, 1} T =
o(2
n
), n −→ ∞
T g
Par (g)
g
T
T
T = O(2
n
7+ε
), ε > 0 f
T T f
n
f
x
f
{T }
(x) f
T
T
f
T f Ω(
√
T ) f
N § ⊆ 2
N
σ
N ∅, N ∈ § § A \ B
∞
S
i=0
A
i
,
∞
T
i=0
A
i
§
§ P : § −→ [0, 1] P (∅) =
0, P (N) = 1, {A
i
}
P
∞
[
i=0
A
i
!
=
∞
X
i=0
P (A
i
).
σ S ⊆ 2
N
§(S)
S §(S)
P
M
n
g : {0, 1}
n
−→ {0, 1}
n
card(M
n
) = v
n
.
v
n
= 2
n2
n
F F
f : {0, 1}
∗
−→ {0, 1}
∗
g
1
, g
2
, . . .
g
i
∈ M
i
g
i
∈ M
i
i = 1, 2, . . . , n A(g
1
, g
2
, . . . , g
n
) =
{f | f = (g
1
, g
2
, . . . , g
n
, . . .)} P (A(g
1
, . . . , g
n
)) = (v
1
v
2
. . . v
n
)
−1
P S A(g
1
, . . . , g
n
)
n g
1
, g
2
, . . . , g
n
§(S).
P σ § = § (S)
n x, y ∈ {0, 1}
n
. f (x) = y
P (B
xy
) B
xy
= {f | f(x) = y}. 2
−n
A, B ∈ §, P (B) 6= 0 P (A | B) = P (A ∩
B)/P (B) A F
1
, F
2
, . . . , F
m
F
i
∩ F
j
= ∅ i 6= j A ∈
m
S
i=1
F
i
P (A) =
m
P
i=1
P (A | F
i
)P (F
i
)
t(n), T (n) T = O(2
n
7+ε
), ε > 0 C
S(C, n, t, T ) f ∈ M
n
C f
{T }
(
¯
0)
t f
¯
0
C > 0 n P (S(C, n, T −
1, T )) <
α = 5+
ε
2
n
ζ
i
= hξ
i
, f
i
, T
i
, x
i
i ξ
i
H
1
|ξ
i
| = 1 f
i
∈ M
n
x
i
∈ T
i
⊆ {0, 1}
n
i
i = 0 ξ
0
= χ
0
f
0
∈ M
n
x
0
=
¯
0 T
0
= {0, 1}
n
ξ
i+1
= V
i,f
i
(ξ
i
),
T
i+1
= T
i
∩ R
i
, R
i
= {a | δ
a
(ξ
i+1
) <
1
T
α
},
x
i+1
T
i+1
f
i+1
=
f
i
(x), x 6= x
i
,
x
i+1
, x = x
i
.
ζ
i
ζ
i
D
i
, i = 1, 2, . . . N
i
f
i
∈ M
n
ξ
i
, T
i
, x
i
hξ
i
, f
i
, T
i
, x
i
i ∈ D
i
i ≤ T n −→ ∞
P (N
i
) = 1 − O
T
α+1
i
2
n
.
i ζ
0
ζ
i
=
hξ
i
, f
i
, T
i
, x
i
i ζ
i+1
x
i+1
2
n
−T
α+1
2
n
card(T
i
) > 2
n
−T
α
i ≥ 2
n
−T
α+1
1 − O
T
α+1
i
2
n
1 −
T
α+1
2
n
=
1 − O
T
α+1
(i+1)
2
n
t = T − 1 ζ
i
V
i
= V
i,f
t
, V
∗
i
= V
i,f
i
V
i
V
0
(x) = V
0
(x), V
i
(x) = V
i
(V
i−1
(x))
˜
V
i
˜
V
0
= V
∗
0
,
˜
V
i
(x) = V
∗
i
(
˜
V
i−1
(x)) ξ
i+1
=
˜
V
i
(ξ
0
)
ξ
0
0
= ξ
0
, ξ
0
i+1
= V
i
(ξ
0
), ∂
i
= |ξ
i
− ξ
0
i
|, ∆
i
= |V
∗
i
(ξ
i
) − V
i
(ξ
i
)|
f
i
f
t
X
i
= {x
i
, x
i+1
, . . . , x
t−1
} ∀a ∈ X
i
δ
a
(ξ
i
) <
1
T
α
∆
i
≤
2t
1/2
T
α/2
.
∂
i
≤
P
k<i
∆
k
.
i
∂
i+1
= |
˜
V
i
(ξ
0
) − V
i
(ξ
0
)| = |V
∗
i
(
˜
V
i−1
(ξ
0
)) − V
i
(V
i−1
(ξ
0
))| ≤
≤ |V
∗
i
(ξ
i
) − V
i
(ξ
i
)| + |V
i
(ξ
i
) − V
i
(ξ
0
i
)| = ∆
i
+ ∂
i
.
∀i = 1, . . . , t ∂
i
≤
2it
1/2
T
α/2
.
f
i
∀i ≤ t δ
x
t
(ξ
i
) <
1
T
α
.
x = x
t
δ
x
(ξ
i
− ξ
0
i
) ≤
2it
1/2
T
α/2
, δ
x
(ξ
i
) <
1
T
α/2
, δ
x
(ξ
0
i
) ≤ δ
x
(ξ
i
− ξ
0
i
) + δ
x
(ξ
i
).
δ
x
(ξ
0
i
) ≤
3t
3/2
T
α/2
.
f
t+1
= f
T
ξ
0
−→ ξ
00
1
−→ . . . −→ ξ
00
t
f
{T }
t+1
(
¯
0) f
t+1
|ξ
0
t
− ξ
00
t
| < 2
X
i≤t
δ
x
(ξ
0
i
) ≤
6t
5/2
T
α/2
< γ(n)
α = 5 +
ε
2
γ(n) n
ξ
0
t
ξ
00
t
f
{T }
t+1
(
¯
0) = a ξ
0
t
a
P ( | f
t
) f
T
f
{T }
T
(
¯
0) 6= f
{T }
T −1
(
¯
0)
f
t
f
t
f
{T }
T
(
¯
0) P ( | f
t
) =
2
n
−T
α+1
2
n
−→ 1 (n −→ ∞)
f
t
2
n
− T
α+1
x
t+1
˜p
f
T
f
{T }
T
(
¯
0)
˜p =
X
f
t
P ( | f
t
)p(f
t
) =
2
n
− T
α+1
2
n
1 − O
T
α+2
2
n
−→ 1 (n −→ ∞).
p
not
f f
{T }
(
¯
0)
p
not
≥ ˜p p
not
−→ 1 (n −→ ∞)
C
1
, C
2
, . . .
R(C, n, t, T )
g
n
∈ M
n
C g
{T }
n
(
¯
0) t
g
n
> 0 i = 1 , 2, . . .
n
i
P (R(C
i
, n
i
, T − 1, T )) > 1 − 2
−i
N T
∞
T
i=1
R(C
i
, n
i
, T −1, T ) ⊆ N
¯
N ⊆
∞
S
i=1
S(C
i
, n
i
, T − 1, T ) P (
¯
N) ≤
∞
P
i=1
P (S(C
i
, n
i
, T − 1 , T )) =
∞
P
i=1
2
−i
=
C > 0 t(n), T (n) : t
2
= o(T ) (n −→ ∞)
n P (S(C, n, t, T )) <
f n f
k
= f
{k}
(
¯
0)
k = 0, 1, . . . , T (a
ij
) a
ij
= δ
f
j
(χ
i
), i = 0, 1, . . . , t; j =
0, 1, . . . , T.
i = 0, . . . , t
T
P
j=0
a
ij
≤ 1 t ≥
t
P
i=0
T
P
j=0
a
ij
=
T
P
j=0
t
P
i=0
a
ij
q > 0 T (1 − 1/q) τ ∈ {0, 1, . . . , T }
t
P
i=0
a
iτ
≤
qt
T
τ
f f
τ
g
g
{T }
(
¯
0) 6= f
{T }
(
¯
0) p
n
−→ 1 (n −→ ∞) χ
0
−→ χ
0
1
−→ . . . −→ χ
0
t
g g p
n
|χ
t
− χ
0
t
| ≥ 1/4 f ∈ S(C, n, t, T )
|χ
t
− χ
0
t
| ≤ 2
t
P
i=0
√
a
iτ
≤ 2
p
t
P
a
iτ
≤ 2t
√
q/T
1/2
< γ(n) −→
0 (n −→ ∞) q
˜p
n
−→ 1 (n −→ ∞) g
{T }
(
¯
0)
