Ожигов Ю.С. Квантовые вычисления
Подождите немного. Документ загружается.
a
1
a
1
F
F
P
B
P x y B(x, y) 0
1 p A
x y p x
B(x, y) = 1 A NP
A NP
x A y
x B(x, y)
B
x B y
P NP
0101 . . . 01 N
01 log N
2
10
7
p
H ψ
0
t
ψ(t) = e
−iHt
ψ
0
e
0
, e
1
, . . . , e
N−1
ψ(t) =
N−1
P
j=0
λ
j
(t)|e
j
i λ
j
(t)
p
|e
p
i
|λ
p
|
2
t
quant
t
quant
< t
class
t
class
p
p
t
quant
p
F
F (F (. . . F (x
0
) . . .))
p
n
ψ =
N−1
X
j=0
λ
j
|e
j
i,
|e
0
i = |00 . . . 00i
|e
1
i = |00 . . . 01i
|e
2
i = |00 . . . 10i
|e
3
i = |00 . . . 11i
. . . . . .
|e
N−1
i = |11 . . . 11i,
N = 2
n
n
N
¯
U = {U
1
, U
2
, . . . , U
s
, . . .}
U
i
1
, U
i
2
, . . . , U
i
k
U
i
1
N
U
i
2
N
. . .
N
U
i
k
N ×N
n
f(x) = 1 f : {0, 1}
n
−→ {0, 1}
x = 0
x 1
x 0 x
f(x)
f(x) = 1
f
f n > 1
f
Qu
f
|¯a, bi = |¯a, b
M
f(¯a)i,
¯a ∈ {0, 1}
n
b ∈ {0, 1}
f
b
f(¯a)
f
f
Qu
f
Qu =
Qu
f
N
I ¯a, b
ψ
0
−→ . . . −→ ψ
h
1
−→ ψ
h
1
+1
−→ . . . −→ ψ
h
2
−→ ψ
h
2
+1
−→ . . . . . . −→ ψ
h
r
−→ ψ
h
r
+1
−→ . . . −→ ψ
R
r
U
F =
∞
S
n=1
F
n
f : {0, 1}
∗
−→{0, 1}
∗
F
n
2
2n
{0, 1}
2n
F
n
|¯a,
¯
bi = |¯a, f ( ¯a)
M
¯
bi, ¯a,
¯
b ∈ {0, 1}
n
,
L
{z
0
+ z
1
| z
1
, z
2
∈ , |z
0
|
2
+ |z
1
|
2
= 1}
2
v
1
, v
2
, ···, v
τ
v
τ +1
, v
τ +2
, ···, v
τ +2n
τ = τ(n)
n Q = {v
1
, v
2
, ···, v
τ +2n
}
e : Q−→{0, 1} |e(v
1
), e(v
2
), ···, e(v
τ +2n
)i
{0, 1} K = 2
τ +2n
e
0
, e
1
, ···, e
K−1
H K
e
0
, e
1
, ···, e
K−1
H
H
1
N
H
2
N
···
N
H
τ +2n
H
i
v
i
, i = 1, 2, ···, τ + 2n x ∈ H kxk = 1
G, U
G ⊂ {1 , 2, ···, τ + 2n} U ∈ U 2
card(G)
W
G,U
H E
N
U
0
U
0
U
N
i∈G
H
i
E
N
i/∈G
H
i
Qu
f
H E
N
F
0
n
F
0
n
F
n
τ +2n
N
i=τ+1
H
i
E
τ
N
i=1
H
i
χ =
K−1
P
i=0
λ
i
e
i
,
e
i
|λ
i
|
2
ω M
{q
b
, q
w
, q
q
, q
o
, ···} h(C) C
D
R : D−→2
{1,2,···,τ +2n}
×
U ∀C ∈ D R(C) = hG, Ui U 2
card(G)
U h(C) G
a
0
∈ ω
S = hQ(S), C(S)i Q(S) C(S)
S
0
−→S
1
−→···−→S
τ
,
i = 0, 1, ···, τ − 1 C(S
i
)−→C(S
i+1
)
h(C(S
i
)) = q
w
Q(S
i+1
) = W
R(C(S
i
))
(Q(S
i
))
h(C(S
i
)) = q
q
Q(S
i+1
) = Qu
f
(Q(S
i
))
h(C(S
i
)) = q
b
i = 0 Q(S
0
) = e
0
, C(S
0
)
a ∈ {0, 1}
n
h(C(S
i
)) = q
o
i = τ
Q(S
i+1
) = Q(S
i
)
F (a)
p ≥ 2/3 a S
τ
F (a) p
p < 1 p
0
> p
p
p = 1
τ