Ожигов Ю.С. Квантовые вычисления
Подождите немного. Документ загружается.
P
j≥2
l
j
/N =
˜
0 = (
√
1 − , X, Y
1
, . . . , Y
m−2
)
T
q
l
1
N
=
√
1 − = 1 −
2
+
o()
˜
0 ≈
˜
0
app
= (1, X, Y
1
, . . . , Y
m−2
)
T
O()
H
0
H
0
U I
˜
0
m H
0
U
U =
1 0 0 . . . 0
0 −1 0 . . . 0
0 0 −v
1
. . . 0
. . . . . . . . . . . . . . .
0 0 . . . 0 −v
m−2
.
I
˜
0
I
˜
0
≈
I
˜
0
app
= V
−1
I
e
1
V V V
˜
0
app
= e
1
V
−1
I
e
1
V
˜
0
app
=
−V
−1
e
1
= −
˜
0
app
V
V =
1 X Y
1
Y
2
. . . Y
m−2
−X 1 0 0 . . . 0
−Y
1
0 1 0 . . . 0
. . . . . . . . . . . . . . . . . .
−Y
m−2
0 0 0 . . . 1
,
V
−1
=
1 −X −Y
1
−Y
2
. . . −Y
m−2
X 1 0 0 . . . 0
Y
1
0 1 0 . . . 0
. . . . . . . . . . . . . . . . . .
Y
m−2
0 0 0 . . . 1
.
I
e
1
=
−1 0 . . . 0
0 1 . . . 0
0 0 . . . 0
. . . . . . . . . . . .
I
˜
0
app
= V
−1
I
e
1
V =
−1 −x −y
1
−y
2
. . . −y
m−2
−x 1 0 0 . . . 0
−y
1
0 1 0 . . . 0
. . . . . . . . . . . . . . . . . .
−y
m−2
0 0 0 . . . 1
,
G = −I
˜
0
app
U =
1 −x −y
1
v
1
−y
2
v
2
. . . −y
m−2
v
m−2
x 1 0 0 . . . 0
y
1
0 v
1
0 . . . 0
. . . . . . . . . . . . . . . . . .
y
m−2
0 0 0 . . . v
m−2
.
kAk = max
k¯xk=1
kA¯xk.
G = −I
˜
0
app
U −I
˜
0
U
G
exact
kG − G
exact
k = kU kkI
˜
0
−I
˜
0
app
k = kI
˜
0
−I
˜
0
app
k = k
˜
0 −
˜
0
app
k = O()
G G
exact
G = G
exact
+ ∆
k∆k = O() t =
q
N
l
2
ν = t∆ =
P
j≥2
l
j
√
Nl
2
l
2
= O(
P
j≥3
) l
2
ν = o(1)
P
j≥3
= o(l
2
) ν
q
l
2
N
o(1) ν = o(1)
G
t
= (G
exact
+ ∆)
t
= G
t
exact
+ O(t∆G
t−1
exact
) = G
t
exact
+ o(1)
G
t
exact
G G
exact
G
p
m−2
(λ) = |G − λI| I
p
m−2
(λ) = 0
p
m−2
(λ) =
1 − λ −x −y
1
v
1
−y
2
v
2
. . . −y
m−2
v
m−2
x 1 − λ 0 0 . . . 0
y
1
0 v
1
− λ 0 . . . 0
. . . . . . . . . . . . . . . . . .
y
m−2
0 0 0 . . . v
m−2
− λ
=
(−1)
m+1
y
m−2
v
m−2
x 1 − λ 0 . . . 0
y
1
0 v
1
− λ . . . 0
y
2
0 0 . . . 0
. . . . . . . . . . . . . . .
y
m−2
0 0 . . . 0
+ (v
m−2
− λ)p
m−3
(λ) =
y
2
m−2
v
m−2
(1 − λ)(v
1
− λ) . . . (v
m−3
− λ) + (v
m−2
− λ)p
m−3
(λ).
p
m−2
(λ) = (v
m−2
− λ)p
m−3
(λ) + y
2
m−2
v
m−2
(1 − λ)(v
1
− λ) . . . (v
m−3
− λ).
−p
1
(λ) = (λ−1 + ix)(λ−1 −ix)(v
1
−λ)+ v
1
y
2
1
(1−λ)
p
m−2
(λ) = (λ − 1 + ix)(λ − 1 − ix)(v
1
− λ)(v
2
− λ) . . . (v
m−2
− λ)+
v
1
y
2
1
(1 − λ)(v
2
− λ) . . . (v
m−2
− λ)+
v
2
y
2
2
(1 − λ)(v
1
− λ)(v
3
− λ) . . . (v
m−2
− λ)+
. . . + v
m−2
y
2
m−2
(1 − λ)(v
1
− λ) . . . (v
m−3
− λ).
p
0
(λ) = (λ −1 + ix)(λ −1 −ix)(v
1
−λ)(v
2
−λ) . . . (v
m−2
−λ)
p
m−2
(λ) = p
0
+ δ
δ = v
1
y
2
1
(1 − λ)(v
2
− λ) . . . (v
m−2
− λ)+
v
2
y
2
2
(1 − λ)(v
1
− λ)(v
3
− λ) . . . (v
m−2
− λ)+
. . . + v
m−2
y
2
m−2
(1 − λ)(v
1
− λ) . . . (v
m−3
− λ).
p
m−2
p
0
(λ) δ p
0
(λ) λ
1
= 1 −ix, λ
2
=
1 + ix, λ
3
= v
1
, . . . , λ
m
= v
m−2
p
m−2
˜
λ
1
,
˜
λ
2
, . . . ,
˜
λ
m
λ
j
˜
λ
j
δ
λ
1,2
|λ
1
− λ
2
| = o(|v
j
− λ
1
|) |λ
1
− λ
2
| δ
2
p
q A = λ−v = Ω(d)
λ
1
λ
2
|λ
1
−λ
2
| q
q = γ(v
1
−λ) ···(v
n−2
−λ) σ = |λ
1
−
˜
λ
1
|+ |λ
2
−
˜
λ
2
|
σ = O(δ/q
0
) =
m−2
P
j=1
v
j
y
2
j
(1−λ)
γ(v
j
−λ)
v
j
− λ = O(d
j
) 1 − λ = O(γ)
σ = O(
1
d
P
j≥3
l
j
N
) o(γ)
P
j≥3
l
j
= o(d
√
Nl
2
)
˜
λ
1,2
= 1 + −ix + o(γ)
˜
λ
3
= v + o(γ)
˜
λ
1,2
= 1 + −ix + o(γ)
λ = 1 − ix + o(γ) ¯a = (a, b, w
1
, . . . , w
m−2
)
T
¯a (G − λE)¯a =
¯
0
ix −x −y
1
v
1
. . . −y
m−2
v
m−2
x ix 0 . . . 0
y
1
0 v
1
− 1 + ix . . . 0
. . . . . . . . . . . . . . .
y
m−2
0 0 . . . v
m−2
− 1 + ix
a
b
w
1
. . .
w
m−2
=
o(γ)
o(γ)
o(γ)
. . .
o(γ)
.
ixa −xb −y
1
v
1
w
1
−. . . −y
m−2
v
m−2
w
m−2
= o(γ)
xa +ixb = o(γ)
y
1
a +(v
1
− 1 + ix)w
1
= o(γ)
. . . . . . . . . . . . . . . . . .
y
m−2
a +(v
m−2
− 1 + ix)w
m−2
= o(γ)
w
j
=
y
j
a
v
j
−1+ix
q
l
2
N
= o(d)
w
j
= o(1) o(1) a = i, b = −1
λ = 1 + ix + o(γ) a = i, b = 1 o(1)
w
j
= o(1)
a = 0, b = 0 o(γ)
e
1
, e
2
n −→ ∞ e
1
, e
2
o(γ)
o(1)
t 1/γ
G o(1)
f : {0, 1}
n
−→ {0, 1}
n
N = 2
n
f f(x
0
) ≤ f(x
1
) ≤ . . . ≤ f (x
N−1
j x
j
k
x
j
f(x
j
k
) < f (x
j
) x
j
0
, j
0
> j
k
x
j
k+1
x
N−1
√
N
e
2iπ wx
ω
ω ∈ [0, 1)
F f = φ(λ) =
1
√
2π
R
D
e
−iλx
f(x) dx,
F
−1
φ = f(x) =
1
√
2π
R
D
e
iλx
φ(λ) dλ.
e
2iπ wx
D = R
D −B, B B
F f = φ(λ) =
1
√
2π
Z
D
e
i(2πω−λ)x
f(x) dx.
λ 2πω
λ = 2πω
2πω
ω
f φ
QFT : |ai −→
1
√
N
N−1
X
b=0
e
−
2πi ab
N
|bi, QFT
−1
: |ai −→
1
√
N
N−1
X
b=0
e
2πi ab
N
|bi.
U
U
U
cond
|x, αi −→
|U x, αi, α = 1,
|x, αi α = 0.
U
U
cond
U
n
α
U
|ξ,
¯
0i
ξ =
P
k
x
k
ψ
k
ψ
k
U
w
k
QFT
2
U
cond
QF T
2
.
=
1
√
N
P
k
N−1
P
α=0
x
k
|ψ
k
, αi
U ψ
k
U U
cond
|ψ
k
, αi =
|U
α
ψ
k
, αi = e
2iπw
k
α
|ψ
k
, αi
1
√
N
P
k
P
α
e
2iπw
k
α
|ψ
k
, αi
1
N
X
k
X
c
N−1
X
α=0
e
2iπα(w
k
−
c
N
)
|ψ
k
, ci.
c w
k
α N
c x
k
x
k
c
N−1
P
α=0
e
2iπαβ
= 0 β 6= 0
X
k
|ψ
k
, w
k
i,
w
k
U
ξ
a = a
0
+ a
0
2 + . . . + a
l−1
2
l−1
|a
0
a
1
. . . a
l−1
i a
j
b
j
b = b
0
+b
0
2+. . .+b
l−1
2
l−1
i
i
i
i
i
r r r r
r r r
r r
r
r
r r
r r r
r r r r
a
4
a
3
a
2
a
1
a
0
b
0
b
1
b
2
b
3
b
4
QFT
−1
W
1
U
k,j
=
1 0 0 0
0 1 0 0
0 0 1 0
0 0 0 e
iπ/2
k−j
, k > j.
a
b
1/2
l/2
φ e
iφ
b
0
j
= b
l−1−j
, j = 0, 1, . . . , l −1
a b
a b
πa
j
b
0
j
j
j < k πa
j
b
0
k
/2
k−j
a b
j a
j
k
b
0
k
π
π
P
l>k>j≥0
a
j
b
0
k
2
k−j
+ π
P
l>j≥0
a
j
b
0
j
=
2π
P
l>j+k≥0
a
j
b
k
2
j+k
2
l
=
2π
P
l>j,k≥0
a
j
b
k
2
j+k
2
l
=
2π
2
l
P
l>j≥0
a
j
2
j
P
l>k≥0
b
k
2
j
=
2π
2
l
.
l
2
π/2
k−j
C l C
N × N
e
a n
1/3
q = q
1
q
2
q
r y
q y
r
≡ 1 (mod q) r
y r
r y
r
−1 = (y
r/2
−1)(y
r/2
+1) ≡ 1 (mod q)
q
q r q y
U
y
n 2
n−1
≤ q < 2
n
n
U U|xi −→ |yx (mod q)i yx
q q, q +1, . . . , 2
n
−1
y q
(y, q) = 1 y