Ожигов Ю.С. Квантовые вычисления
Подождите немного. Документ загружается.
m
m−1
2
W
W : H
N
H −→ H
N
H
W (|Ψ, 0i = λ|Ψ, Ψi |Ψi C Ψ
W
W λ|Ψ, Ψi + µ|Ψ
1
, Ψ
1
i =
W |Ψ, 0i + W |Ψ
1
, 0i = W |Ψ + Ψ
1
, 0i = ν|Ψ + Ψ
1
, Ψ + Ψ
1
i = ν(|Ψ, Ψi + |Ψ
1
, Ψ
1
i + |Ψ, Ψ
1
i + |Ψ
1
, Ψi)
CNOT (λ|0i + µ|1i)
N
0i = λ|0, 0i + µ|1, 1 i
(λ|0i + µ|1i)
N
(λ|0i + µ|1i)
λ|0, 0, 0i + µ|1, 1, 1i
|0i −→
|0i, |1i −→ −|1i
U : α
N
ξ −→ χ α
U α
∆
∆
ξ
ξ = α|0i + β|1i
|0i |1i
˜
0 =
1
2
√
2
(|000i + |100i+ |010i+ |001i+ |110i+ |1 01i + |011i + |111 i)
˜
1 =
1
2
√
2
(|000i− |100i − |010i− |00 1i+ |110i+ |101i+ |011i− |111i).
ξ
˜
ξ = α
˜
0+β
˜
1
˜
0
˜
1 0
1
˜
i
j
k
, i = 0, 1, j = ∅, 1, 2, 3, k = ∅, 0, 1
j
˜
i k
j = k = ∅
˜
i
j
k
=
˜
i
˜
0
1
0
=
1
2
(|000i + |010i+ |001i+ |011i,
˜
0
1
1
=
1
2
(|100i + |110i+ |101i+ |111i,
˜
0
2
0
=
1
2
(|000i + |100i+ |001i+ |101i,
˜
0
2
1
=
1
2
(|010i + |110i+ |011i+ |111i,
˜
0
3
0
=
1
2
(|000i + |010i+ |100i+ |110i,
˜
0
3
1
=
1
2
(|001i + |011i+ |001i+ |101i,
˜
1
1
0
=
1
2
(|000i − |010i− |001i+ |011i,
˜
1
1
1
=
1
2
(−|100i + |110i + |101i− |111i,
˜
1
2
0
=
1
2
(|000i − |100i− |001i+ |101i,
˜
1
2
1
=
1
2
(−|010i + |110i + |011i− |111i,
˜
1
3
0
=
1
2
(|000i − |010i− |100i+ |110i,
˜
1
3
1
=
1
2
(−|001i + |011i − |001i + |101i
U
rest
:
˜
i
j
k
O
¯
0 −→
˜
i
O
˜
0
j
k
.
i
j
k
˜
0
j
k
˜
1
j
k
O I
˜
0⊥
˜
1 O⊥I
π
3
h
˜
1
1
0
|
˜
1
2
0
i = h
˜
1
1
0
|
˜
1
2
1
i =
1
2
O
U
rest
C
8
N
C
8
U
rest
A
rest
α
˜
0 + β
˜
1 −→ α
˜
0
j
k
+ β
˜
1
j
k
U
rest
−→ (α
˜
0 + β
˜
1)
O
˜
0
j
k
A
rest
−→ α
˜
0 + β
˜
1,
δ
rest
∆
∆
δ
res
δ
rest
U
A
rest
a b
a
N
b b a
1
a
2
b
U a
i
N
b = a
N
b
i
b
i
a
1
a
2
b
1
b
2
U k
b
1
, b
2
, . . . b
k
U a
i
N
b
j
= a
N
b
j
i
b
j
i
b
j
1
b
j
2
b
j
i
, b
j
0
i
i = 1, 2; j, j
0
= 1, 2, . . . k, j 6= j
0
U 2k b
j
i
k
n χ =
P
j
λ
j
e
j
, kχk = 1 2
n
{e
j
} λ
j
χ
0
−→ χ
1
−→ . . . −→ χ
t
χ
i
−→ χ
i+1
e
e = |. . . , a, b, . . .i |. . . , a, φ(a) + b, . . .i a b
+
Qu
φ
a q(e)
χ q(e)
K = {0, 1, . . . , K −1} χ =
P
j∈K
λ
j
e
j
a ∈ {0, 1}
n
χ
δ
a
(χ) =
X
j: q(e
j
)=a
|λ
j
|
2
.
χ a
P
a∈{0,1}
n
δ
a
(χ) =
1
χ
f, g {0, 1}
n
−→ {0, 1}
n
δ
χ
(f, g) =
X
a: f (a)6=g(a)
δ
a
(χ)
1/2
.
Qu
f
, Qu
g
f, g χ
kQu
f
(χ) − Qu
g
(χ)k ≤ 2δ
χ
(f, g).
L = {j ∈ K | f(q(e
j
)) 6= g(q(e
j
))} kQu
f
(χ) − Qu
g
(χ)k ≤ 2 (
P
j∈L
(|λ
j
|)
2
)
1/2
≤
2δ
χ
(f, g).
χ
0
−→ χ
1
−→ . . . −→ χ
t
,
χ
i
−→ χ
i+1
U
i
i χ
i
Qu
f
−→ χ
0
i
U
i
−→ χ
i+1
U
i
(Qu
f
(χ))
V
i,f
(χ) χ
i+1
= V
i,f
(χ
i
), i = 0 , 1, . . . , t − 1 t
t
δ
a
(χ) =
p
δ
a
(χ)
χ
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)
φ S
b
p(n) −→ 0 (n −→ ∞)
n φ
0
(x) = 0 X
0
−→ X
1
−→ . . . −→ X
t
a
ij
= δ
j
(X
i
), i = 1, 2, . . . , t; j = 1, 2, . . . , N,
N = 2
n
P
ij
a
ij
≤ t ∀i
P
j
a
ij
≤ 1
T
j
τ
P
i
a
iτ
≤ (j +1)t/N T
0
= ∅
ˆ
b
j
L
j
= T
j
\ T
j−1
P
j
ˆ
b
j
(j+1)t
N
≤ t
b 1, 2, . . . , N D
b
j
L
j
b
j
Eb
j
= b
ˆ
b
j
/N
φ
0
D φ
1
X
0
0
= X
0
−→
X
0
1
−→ . . . −→ X
0
t
φ
1
ξ = kX
t
−X
0
t
k
ε > 0 P (ξ > ε) −→ 0 n −→ ∞
Eη
2
≥
E
2
η
i 1, 2, . . . , N j
Eξ = 2E
P
i
r
P
τ ∈D
a
iτ
≤ 2E
r
t
P
j
b
j
(j + 1)t/N =
t
√
b
√
N
2E
r
P
j
b
j
(j + 1)/b ≤
o(1)
r
E
P
j
b
j
(j + 1)/b ≤ o(1)
r
1
b
P
j
b
ˆ
b
j
(j+1)
N
= o(1) (n −→ ∞).
P (ξ ≥ ε) ≤ Eξ/ε ε
P (ξ ≥ ε) n
G p
err
p
err
= 0.0016, N > 1000 f ∈ G b
f X
t
=
P
j
λ
j
e
j
B = {j | f(e
j
) = 1}, ε
0
=
P
j /∈B
|λ
j
|
2
.
ε
0
≤ p
err
,
X
t
e
j
, j ∈ B p
err
f c
j
= j/N, j = 0, 1, . . . ; L
j
= {j ∈ B | c
j
≤ |λ
j
|
2
< c
j+1
} ζ
0
=
P
j
ˆ
l
j
c
j
ˆ
l
j
= card(L
j
)
|1 − ζ
0
| ≤ ε
0
+
b
N
< 2p
err
(N −→ ∞).