ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 11.12.2020
Просмотров: 97
Скачиваний: 1
Семинар 9.
9.1
Оценка фазы.
Фурье- преобразование является основой для общей процедуры, известной как оценка
фазы (phase estimation), которая является ключевой для многих квантовых алгоритмов.
Пусть есть унитарный оператор
U
, имеющий собственный вектор
|
U
i
и собственное число
exp(2
πiϕ
)
, где
ϕ
- неизвестно. Задача алгоритма оценки фазы состоит в вычислении
ϕ
.
Квантовая процедура оценки фазы использует два регистра. Первый регистр содержит
t
кубит первоначально находящихся в состоянии
|
0
i
. Второй регистр начинается с состояния
|
U
i
и содержит столько кубит, сколько необходимо чтобы собрать
|
U
i
.
Первый шаг процедуры вычисления фазы определяется квантовой цепью вида
Данная цепь состоит в использовании гейта Адамара с последующим применением
controlled-
U
- операций на второй регистр, с
U
увеличенным до степени
2
. Конечное состояние
первого регистра будет иметь вид:
1
2
t/
2
|
0
i
+ exp(2
πi
2
t
−
1
ϕ
)
|
1
i
|
0
i
+ exp(2
πi
2
t
−
2
ϕ
)
|
1
i
. . .
. . .
|
0
i
+ exp(2
πi
2
0
ϕ
)
=
1
2
t/
2
2
t
−
1
X
k
=0
exp(2
πiϕk
)
|
k
i
(9.1)
Состояние второго регистра не меняется. Второй шаг вычисления фазы состоит
в применении обратного квантового Фурье-преобразования для первого регистра.
Оно образуется путем обращения цепи квантового Фурье-преобразования. Третий и
окончательный шаг есть чтение состояния первого регистра. Схематично весь алгоритм
определяется квантовой цепью
79
Пусть
ϕ
- выражается точно
t
-битами
ϕ
= 0
.ϕ
1
. . . ϕ
t
, тогда состояние (
??
), после первого
шага оценки может быть записано в виде:
1
2
t/
2
(
|
0
i
+ exp(2
πi
0
.ϕ
t
)
|
1
i
)(
|
0
i
+ exp(2
πi
0
.ϕ
t
−
1
ϕ
t
)
|
1
i
)
. . .
. . .
(
|
0
i
+ exp(2
πi
0
.ϕ
1
ϕ
2
. . . ϕ
t
)
|
1
i
)
(9.2)
Используя выражение для Фурье-преобразования в виде произведения, ясно, что
выходное состояние первого регистра после второго шага есть состояние вида
|
ϕ
1
. . . ϕ
t
i
.
Измерение таким образом дает точно
ϕ
.
Алгоритм квантовой оценки фазы.
Входные данные:
1. Черный ящик,который производит controlled -
U
j
операцию, для целого
j
.
2. Собственное состояние
|
U
i
унитарного преобразования и с собственным числом
e
2
πiϕ
.
3.
t
=
n
+ [log(2 +
1
2
ε
)]
кубит находящихся в состоянии
|
0
i
.
Выходные данные:
n
- битовое приближение
f
ϕ
n
и
ϕ
n
.
Процедура
1.
|
0
i |
U
i
- начальное состояние.
2.
1
√
2
t
P
2
t
−
1
j
=0
|
j
i |
U
i
- создание суперпозиции.
3.
1
√
2
t
P
2
t
−
1
j
=0
|
j
i
U
j
|
U
i
- применение "черного ящика".
=
1
√
2
t
P
2
t
−
1
j
=0
e
2
πijϕ
n
|
j
i |
U
i
- результат работы "черного ящика".
4.
|
f
ϕn
i |
U
i
- применение обратного Фурье-преобразования.
5.
f
ϕ
n
-измерение первого регистра.
Процедура оценки фазы может быть использована для решения ряда интересных задач,
таких как проблема нахождения периода и проблема факторизации.
9.2
Алгоритм Шора.
Алгоритм факторизации Шора состоит в определении простых множителей
p
и
q
для
заданного целого числа
M
=
p
·
q
с использованием квантовой схемы определения периода
r
некоторой периодической функции вида:
y
M
(
x
) =
a
x
modM
где
x
= 0
,
1
,
2
. . . N
−
1
, N
= 2
L
,
a
–
любое число, не имеющее общих делителей с
M
.
Пусть, например,
M
= 15
Выберем
a
= 2
. В этом случае последовательность чисел
a
x
по
модулю
15
представляются в следующем виде:
x
0
1
2
3
4
5
6
7
8
. . .
a
x
2
0
2
1
2
2
2
3
2
4
2
5
2
6
2
7
2
8
. . .
Число
1
2
4
8
16
32
64
128
256
. . .
a
x
mod
15
1
2
4
8
1
2
4
8
1
∗
К.А. Валиев, А.А. Копин Квантовые компьютеры: надежды и реальность. R&C Москва. Ижевск 2001.
80
Таким образом последовательность чисел
a
x
≡
2
x
по модулю
15
представляется в следующем
виде:
1
,
2
,
4
,
8
,
1
,
2
,
4
,
8
. . .
, то есть имеет период по
x
равный
r
= 4
и удовлетворяет состояние
2
r
≡
1
mod
15
. В общем случае
a
r
≡
1
mod M
, а параметр
r
называется порядком функции
a
x
mod M
, когда
a < M
и не имеет общих множителей с
M
.
Если известен период
r
, множители числа
M
определяются с помощью классического
Алгоритма Евклида как наибольшие общие делители чисел
2
r/
2
±
1
и
M
. В рассматриваемом
примере
2
4
/
2
±
1 = (5
,
3)
. Другими словами
15 = 5
·
3
.
Алгоритм поиска наибольшего общего делителя для пары чисел
n
0
>
n
1
состоит в
вычислении последовательных делений.
n
0
=
d
1
×
n
1
+
n
2
n
1
=
d
2
×
n
2
+
n
3
. . . . . . . . . . . . . . . . . . . . . . . .
n
m
−
2
=
d
m
−
1
×
n
m
−
1
+
n
m
n
m
−
1
=
d
m
×
n
m
+ 0
.
где
d
m
–
целая часть от деления
n
m
−
1
>
n
m
на каждом шаге. Последний не нулевой
сомножитель
n
m
является ответом алгоритма. Например последовательность:
91 =3
×
28 + 7
28 =4
×
7 + 0
показывает, что наибольший общий делитель пары чисел (91, 28) равен 7. Как видно для
определения наибольшего общего делителя потребовалось два шага. В общем случае число
шагов порядка
∼
log log
n
1
.
Квантовый алгоритм Шора
использует два квантовых регистра
X
и
Y
, первоначально
находящихся в нулевом булевском состоянии
|
0
i
. В регистре
X
размещаются аргументы
функции
y
m
(
x
)
, то есть
N
состояний
|
x
i
=
|
x
L
−
1
, x
L
−
2
. . . x
0
i ≡ |
x
L
−
1
i ⊗ |
x
L
−
2
i ⊗ · · · ⊗ |
x
0
i
.
Вспомогательный регистр
Y
используется для размещения значений самой функции
y
m
(
x
)
с
подлежащим определению периодом
r
. Число состояний регистра
N
= 2
L
>
M
2
r
2
.
1-й этап рассматриваемого алгоритма состоит в переводе начального состояния
|
0
i
регистра
X
в равновероятную суперпозицию всех булевских состояний
N
= 2
L
|
x
i
=
|
x
L
−
1
, x
L
−
2
. . . x
0
i
, путем применения операции Уолша-Адамара. Регистр
Y
не меняется. В
результате, для системы двух регистров
X
и
Y
получается состояние
|
Φ(
x,
0)
i
=
r
1
N
N
−
1
X
x
=0
|
x
i ⊗ |
0
i
=
r
1
N
N
−
1
X
x
=0
|
x,
0
i
.
†
Shor P. Polinomial-Time Algorithms for Prime Factorization and Descreete Logarithms on a Quantum Com-
puter. SIAM Your Comp., 1997, V.26, N5, p. 1484-1509.
81
Если, например
M
= 15
данное состояние есть
|
ϕ
[
x, y
m
(
x
)]
i
=
1
√
N
N
−
1
X
x
=0
|
x
i ⊗ |
y
m
(
x
)
i
=
1
√
N
N
−
1
X
x
=0
|
x
i ⊗ |
2
x
mod
15
i
=
=
1
√
N
(
|
0
i ⊗ |
1
i
+
|
1
i ⊗ |
2
i
+
|
2
i ⊗ |
4
i
+
|
3
i ⊗ |
8
i
+
|
4
i ⊗ |
1
i
+
|
5
i ⊗ |
2
i
+
+
|
6
i ⊗ |
4
i
+
|
7
i ⊗ |
8
i
+
. . .
|
N
−
1
i ⊗
2
N
−
1
mod
15
)
(9.3)
т.е. последовательность функций
y
15
(
x
)
имеет период
r
= 4
.
Каждому
фиксированному
состоянию
второго
регистра
(
Y
)
соответствует
последовательность амплитуд, оставшихся в первом
(
X
)
-регистре. Например, если
зафиксировано состояние второго регистра
|
y
i
, то в первом регистре соответствующие
числа отличаются на период
r
= 4
.
|
ϕ
[
x, y
]
i
=
1
√
N
(
|
2
i
+
|
6
i
+
|
10
i
+
· · ·
+
|
4
A
+
`
i
)
⊗ |
4
i
=
1
√
A
+
`
A
X
j
=0
|
rj
+
`
i ⊗ |
4
i
(9.4)
где
0
6
`
6
r < M
;
A
=
целая часть
[
N
2
−
1]
. В рассматриваемом случае
`
= 2
–
начальное
значение (определяемое выбором фиксированного значения состояния второго регистра).
Таким образом второй регистр служит для приготовления периодического состояния в первом
регистре.
На втором этапе выделения периода
r
. Над состоянием первого регистра производится
операция Фурье-преобразования. Для простоты пусть
N
точно делится на
r
, так что
A
=
N/
2
−
1
. В этом случае Фурье-преобразование есть:
QF T
N
:
r
r
N
A
X
j
=0
|
rj
+
`
i ⇒
N
−
1
X
k
=0
f
`
(
k
)
|
k
i
(9.5)
где
f
`
(
k
) = (
√
r/N
)
A
X
j
=0
exp
2
πi
(
jr
+
`
)
N
k
.
(9.6)
Вероятность получить состояние
|
k
i
определяется выражением:
p
(
k
) =
|
f
`
(
k
)
|
2
=
r
N
2
A
X
j
=0
exp(2
πijrk/N
)
2
(9.7)
которое как видно не зависит от
l
. Так как основной вклад в (9.7) дают слагаемые, у которых
rk/N
→
близко к целому числу, точнее
−
r
2
6
rk
mod
N
6
r/
2
,
(9.8)
82
в случае малых значений
r/N
для каждого
r
, которое удовлетворяет (9.8), можно получить
оценку для вероятности в виде:
p
(
k
)
>
4
/
(
π
2
r
)
(9.9)
Из(9.9) следует, что по крайней мере с вероятностью
4
/π
2
'
0
,
405
измеренное значение
принимает дискретные значения
k
=
N
2
ν,
где
ν
= 0
,
1
, . . . r
−
1
.
То есть в результате квантового Фурье-преобразования суперпозиция (9.3) преобразуется в
равновероятную суперпозицию (9.6) с периодом
N/r
.
Измерение вероятности (9.7) позволяет определить значения
k
≡
ν
N
r
, имея которые
при известном
k/N
, можно найти отношение
ν/r
. Если
ν
и
r
не имеют общих множителей,
можно определить период
r
путем преобразования отношения
ν/r
к виду, когда числитель
и знаменатель не имеют общих наибольших делителей. После этого с помощью алгоритма
Евклида легко найти и множители числа
M
.
9.3
Алгоритм Гровера (поиск в базе данных).
Пусть несортированная база данных состоит из
N
записей
S
(0)
, S
(1)
. . . S
(
x
)
. . . S
(
N
−
1)
,
представленных
N
= 2
L
состояниями квантового регистра из
L
-кубитов. Одна из записей,
соответствующих состоянию
x
=
v S
(
v
)
≡
a
–
маркирована. Ее и требуется найти. В
квантовом алгоритме Гровера выполняются такие шаги:
1. Первый шаг: создание равновероятной (c равными амплитудами) суперпозиции
|
S
i
всех
N
= 2
L
булевских состояний.
|
y
i
=
|
y
L
−
1
, y
L
−
2
. . . y
0
i
Все амплитуды равны
1
/
√
N
. Такая суперпозиция достигается применением гейта Уолша-
Адамара, действующего на каждый из
L
кубитов в состоянии
|
0
i
.
|
S
i
= ˆ
W
|
0
i
=
1
√
N
N
−
1
X
y
=0
|
y
i
(9.10)
83