Ожигов Ю.С. Квантовые вычисления
Подождите немного. Документ загружается.
f(x) = 1
O(
√
N) f
P
P f
f(x) = 1 P
f
f
W =
1
√
2
1
√
2
1
√
2
−
1
√
2
!
.
n W W
N
n
w
i,j
= (−1)
(i·j)
i j
i j
n−1
P
s=0
i
s
2
s
n−1
P
s=0
j
s
2
s
i · j =
n−1
P
s=0
i
s
j
s
(W
n
)
−1
= W
n
W
n
n
φ
0
=
1
√
N
N−1
X
i=0
|e
i
i.
e
iφ
a
I
a
|bi =
b, a b,
−a, a = b.
a
a a = 0
a
a = 0
a
res
a
0 a
V
V
V
0 0 0 −→ 0 0 0
1 0 0 −→ 1 0 1
0 0 1 −→ 0 0 1
1 0 1 −→ 1 1 1
V
n
V
n−1
. . . V
1
Sign V
−1
1
V
−1
2
. . . V
−1
n
,
V
j
V j Sign |0i, |1i
−1 0
0 1
.
ψ
N
¯
0 ψ
0
N
¯
0
|e
0
i
φ
0
I
φ
0
= W
n
I
¯
0
W
n
|¯ai |
¯
bi |¯ai = U |
¯
bi
I
¯a
= U I
¯
b
U
−1
U
f(x) = 1 f
f(x) = 1
tar
I
tar
f
b
b
b ψ
0
=
1
√
2
(|0i + |1i)
Qu
f
1
a
G = −I
φ
0
I
tar
φ
0
t
0
=
h
π
√
N
4
i
tar G
G |tari φ
0
G
G G
α φ
˜
0 |tari
α ≈ sin α = |htar|φi| = 1/
√
N 1/N
3/2
G t
0
1/N tar
f(x) = 1
x
x
O(
√
N)
I
tar
L
f
G
f(x) = 1 I
tar
L
f
φ
0
˜
φ
0
˜
φ
0
L
f
tar
tar
˜
φ
0
φ
0
˜
φ
0
t
0
h
π
4|htar|
˜
φ
0
i|
i
φ
0
|htar|
˜
φ
0
i| 1/
√
N
tar
˜
φ
0
tar
˜
φ
0
1/N
1/
√
N
1/
√
N
N
|htar|
˜
φ
0
i|
l
p
l/N
tar
C
√
N C
tar −tar
π/4
O(
√
N)
l = O(
√
N) O(N
1/4
)
C
√
N
O(
p
N/L)
tar φ
0
f(x) = 1
g
g(x) = 1 f(x) = 1
GSA = (W I
0
W I
tar
)
t
t =
h
π
√
N
4
i
N
1
|sqrtN
P
¯x
¯x
GSA W
¯
0
M I
tar
M
GSA GSA)M W
g
f(x, y) (x
0
, y
0
)
g(x) x
0
g(x) = 1
S = {0, 1, . . . , L − 1} × { 0, 1, . . . , L − 1} x y
{0, 1, . . . , L − 1} |x, yi F (x, y) G(x)
F (x, y) = 1 x
0
, y
0
G(x) = 1
M x
1
, x
2
, . . . , x
M
x
0
M L M 1 M
2
L x
0
, y
0
O(LM ) x x
G(x) = 1 y
W
x
¯
0
1
√
M
M
P
j=1
x
j
W
x
= GSA
M
O(
q
M
L
) O(
q
L
M
)
W
x
V
V |xi =
|xi, if x 6= x
0
,
−x
0
i, if x = x
0
.
y A
y = 0 x
S
I
tar
|x, yi
V
1
= (W I
0
W I
tar
)
τ
W A,
τ
h
π
√
L
4
i
V
1
|xi =
|x
0
, y
0
i, if x = x
0
,
|x,
¯
0i
V
−1
= A
−1
W (W I
0
W I
tar
)
τ
¯
0 6= y
0
x
0
, y
0
V
V = V
−1
1
I
tar
V.
W
x
V
|x
0
i
(W
x
V W
x
I
0
)
τ
0
W
x
τ
0
=
h
π
√
M
4
i
GSA
x
0
|x
0
i
O((
√
L +
q
L
M
)
√
M) O(
√
LM)
W
x
W
x
(1/
√
M)
GSA
x
0
√
MO(
q
M
L
) = o(1)
M
2
L
S
1
, S
2
, . . . , S
k
S
i
x
0
i
f
i
(x
i
) = 1
f
i
x
0
j
, j < i.
|x
i
| = n, N = 2
n
, k N |x| x x
0
k
k ≥ 2
x
0
1
, x
0
2
, . . . , x
0
k
kπ
√
N
4
k/N
f
i
, i = 1, 2, . . . , k f
i
x
j
, j < i
f
i
f
i
f
i
(x
1
, x
2
, . . . , x
i
)
f
i
(x
1
, . . . , x
i
) = 1 x
0
1
, x
0
2
, . . . , x
0
i
, i = 1, 2, . . . , k.
f
i
x
0
i
i
l
2l+1
√
N
x
i
6= x
0
i
x
0
i
i + 1
O(
kπ
√
N
4
√
2
)
√
2 k
k = 2
f
i
f
1
(x) = 1 f
2
(x, y) = 1
√
2
x
0
, y
0
f(x, y) = 1
g {x | g(x) = 1} M x
0
M = 1 1 M N
O(
√
MN )
M = 1
√
2
u, x, y H
0
= C
N
a = a
1
N
a
2
∈
C
4
a
1
= a
2
=
1
√
2
(|0i − |1i) f
1
(x), f
2
(x, y)
e
1
, e
2
x, y
f
1
= 1, f
2
= 1
H = H
0
N
H
0
N
H
0
N
C
4
F
1
|u, x, y, ai = |u, x, y, a
1
L
f
1
(u), a
2
i,
F
2
|u, x, y, ai = |u, x, y, a
1
, a
2
L
f
2
(x, y)i,
P |u, x, y, ai = |u
L
x, x, y, ai.
F
1
|u, x, y, ai =
|u, x, y, ai, u 6= e
1
,
−|u, x, y, ai, u = e
1
;
F
2
|u, x, y, ai =
|u, x, y, ai, |x, yi 6= |e
1
, e
2
i,
−|u, x, y, ai, |x, yi = |e
1
, e
2
i;
H R
0
= I
N
R
0x
N
R
0y
N
I; W =
I
N
W
x
N
W
y
N
I; F = P (F
1
|
u,a
1
N
F
2
|
x,y,a
2
)P, x, y
0 I
Z = WR
0
WF.
Z
χ
0
= |
¯
0i
O
1
√
N
N−1
X
i=0
|e
i
i
O
1
√
N
N−1
X
i=0
|e
i
i
O
a
h
π
√
N
2
√
2
i
t =
h
π
√
N
2
√
2
i
Z
{t}
(χ
0
) x = e
1
, y = e
2
O(
1
√
N
)
Z F
1
F
2
f
1
, f
2
h
π
√
N
2
√
2
i
f
1
f
2
h
π
√
N
2
i
π
√
N
4
f
1
f
2
√
2
{0, 1}
n
N/2
f
1
e
1
f
2
f
1
f
2
√
2
f
i
, f
i+1
, i = 1, 2, . . . , k − 1.
O(k/
√
N)
W
y
, R
0y
W
x
, R
0x
, P, F
1
P F
2
Z
Z = −[(I
O
W
x
R
0x
W
x
O
I)P F
1
P ][−(I
O
(W
y
R
0y
W
y
)
O
I)F
2
],
Z = {−W
x
R
0x
W
x
F
1
}{−W
y
R
0y
W
y
F
2
},
F
1
|u, x, y, ai =
|u, x, y, ai x 6= e
1
,
−|u, x, y, ai x = e
1
.
F
2
, F
1
Z χ
0
−→ χ
1
−→ . . . −→ χ
t
χ
i+1
= Z(χ
i
), i = 0, 1, . . . , t − 1