ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 11.12.2020
Просмотров: 130
Скачиваний: 1
1.
|
0
i
⊗
n
|
1
i
–
инициализация состояний.
2.
→
1
√
2
n
P
2
n
−
1
x
=0
|
x
i
h
|
0
i−|
1
i
√
2
i
–
создание суперпозиции с использованием гейта Адамара.
3.
→
P
x
(
−
1)
f
(
x
)
|
x
i
h
|
0
i−|
1
i
√
2
i
–
вычисление
f
с использованием оракула
U
.
4.
→
P
x
P
z
1
2
n
(
−
1)
x
·
z
+
f
(
x
)
|
z
i
h
|
0
i−|
1
i
√
2
i
–
преобразование Адамара.
5.
→
z
–
измерение для получения ответа задачи.
8.3
Классы квантовых алгоритмов.
Имеется 3 класса квантовых алгоритмов
–
алгоритмы основанные на квантовых версиях Фурье преобразований (Дойча, Дойча-
Джозса, алгоритм Шора факторизации целых чисел, дискретный логарифм);
–
алгоритмы квантового поиска;
–
алгоритмы моделирования квантовых систем.
8.3.1
Квантовые алгоритмы, основанные на квантовых Фурье-преобразованиях.
Дискретное Фурье-преобразование обычно определяется как преобразование набора
x
0
, x
1
, . . . , x
n
−
1
N
-комплексных чисел в набор комплексных чисел
y
0
, y
1
, . . . , y
n
−
1
,
определенных соотношением
y
k
≡
1
√
N
N
−
1
X
j
=0
e
2
πijk/N
x
j
.
(8.20)
Такое преобразование имеет многочисленные приложения в различных отраслях науки.
Рассмотренное выше преобразование Адамара, используемое в алгоритме Дойча-Джозса
является примером этого класса Фурье-преобразований. Имея в виду, что мы определяем
линейное преобразование
U
над
n
-кубитами путем действия на вычислительный базис
состояний
|
j
i
, где
0
6
j
6
2
n
−
1
можно написать
|
j
i →
1
√
2
n
2
n
−
1
X
k
=0
e
2
πijk/
2
n
|
k
i
.
(8.21)
Можно проверить, что дискретное Фурье-преобразование унитарно и фактически может
быть реализовано как квантовая цепь. Более того, если мы записываем его действие на
суперпозицию
2
n
−
1
X
j
=0
x
j
|
j
i →
1
√
2
n
2
n
−
1
X
k
=0
"
2
n
−
1
X
j
=0
e
2
πijk/
2
n
x
j
#
|
k
i
=
2
n
−
1
X
k
=0
y
k
|
k
i
(8.22)
то видно, что преобразование соответствует векторным обозначениям для Фурье-
преобразования (8.20) для случая
N
= 2
n
.
75
8.3.2
Алгоритмы квантового поиска.
Алгоритм квантового поиска решает следующую задачу:
Задано пространство поиска содержащее
N
элементов и нет предварительной
информации о структуре расположения элементов в пространстве поиска. Необходимо
в данном пространстве элементов найти такой, который удовлетворяет заданному свойству.
Классический алгоритм требует порядка
N
операций для осуществления решения такой
задачи. Алгоритмы квантового поиска используют
√
N
операций или шагов.
8.3.3
Алгоритмы квантового моделирования.
Классические
компьютеры
имеют
большие
трудности
моделирования
общих
квантовых систем в силу физической природы квантовых процессов, что выражается в
экспоненциальном росте шагов при классическом моделировании квантового объекта.
8.4
Квантовое Фурье-преобразование.
Дискретное Фурье-преобразование набора комплексных чисел
x
0
, x
1
, . . . , x
N
−
1
в набор
комплексных чисел
y
0
, y
1
, . . . , y
N
−
1
определяется равенством Квантовое Фурье-преобразование есть аналогичное преобразование, хотя общепринятые
обозначения для квантовых Фурье-преобразований несколько отличаются. Квантовое
Фурье преобразование ортонормированного базиса
|
0
i
. . .
|
N
−
1
i
определено как линейный
оператор со следующим действием на базисные состояния:
|
j
i →
1
√
N
N
−
1
X
k
=0
exp
2
πijk
·
1
N
|
k
i
.
(8.23)
Эквивалентное, действие на произвольное состояние может быть записано в виде
N
−
1
X
j
=0
x
j
|
j
i →
N
−
1
X
k
=0
y
k
|
k
i
,
(8.24)
где амплитуды
y
k
являются дискретными Фурье преобразованиями амплитуд
x
j
. Это
преобразование является унитарным и, поэтому, может определять динамику квантовых
вычислений.
В последующем
N
= 2
n
, где
n
–
произвольное целое число, а базис
|
0
i
. . .
|
2
n
−
1
i
–
вычислительный базис для
n
-кубитового квантового компьютера. Полезно записать
состояние
|
j
i
, используя бинарное представление
j
=
j
1
j
2
. . . j
n
:
j
=
j
1
2
n
−
1
+
j
2
2
n
−
2
+
· · ·
+
j
n
2
0
.
(8.25)
Введем также следующее обозначение
O
.
j
`
j
`
+1
. . . j
m
для представления бинарной
функции
j
`
/
2 +
j
`
+1
/
4 +
· · ·
+
j
m
/
2
m
−
`
+1
.
76
В результате квантовое Фурье-преобразование может быть задано в следующей полезной
форме представления в виде произведения
|
j
1
. . . j
n
i →
1
√
2
n
|
0
i
+
e
2
πiO
.
j
m
|
1
i
|
0
i
+
e
2
πiO
.
j
n
−
1
j
n
|
1
i
. . .
. . .
|
0
i
+
e
2
πiO
.
j
1
j
2
...j
n
|
1
i
.
(8.26)
Это представление в виде произведения настолько полезно, что можно его рассматривать
как определение квантового Фурье преобразования. Эквивалентность представления в
форме произведения (8.26) и определения (8.23) следует из следующих элементарных
алгебраических выражений
|
j
i →
1
√
2
n
2
n
−
1
X
k
=0
exp(2
πijk/
2
n
)
|
k
i
=
=
1
√
2
n
1
X
k
1
=0
· · ·
1
X
k
n
=0
exp(2
πij
(
n
X
`
=1
k
`
·
2
−
`
))
|
k
1
. . . k
n
i
=
=
1
√
2
n
1
X
k
1
=0
· · ·
1
X
k
n
=0
n
Y
`
=1
exp(2
πijk
`
·
2
−
`
)
|
k
`
i
=
=
1
√
2
n
n
Y
`
=1
"
1
X
k
`
=0
exp(2
πijk
`
·
2
−
`
)
|
k
`
i
#
=
=
1
√
2
n
n
Y
`
=1
|
0
i
+ exp(2
πij
2
−
`
)
|
1
i
=
=
1
√
2
n
(
|
0
i
+ exp(2
πiO
.
j
m
)
|
1
i
) (
|
0
i
+ exp(2
πiO
.
j
n
−
1
j
n
)
|
1
i
)
. . .
. . .
(
|
0
i
+ exp(2
πiO
.
j
1
j
2
. . . j
n
)
|
1
i
)
.
(8.27)
Представление Фурье-преобразования в форме произведения (8.26) позволяет легко вывести
эффективные квантовые цепи для квантовых Фурье-преобразований. Такие квантовые цепи
изображены на рис. (8.5), на которой гейт
R
k
обозначает унитарное преобразование вида
R
k
≡
1
0
0
e
2
πi/
2
k
.
(8.28)
рис. 8.3.
77
Чтобы показать, что нарисованные цепи действительно вычисляют квантовые Фурье-
преобразования, рассмотрим изменения состояний, если начальное состояние имеет вид
|
j
1
, . . . , j
n
i
. Применяя гейт Адамара к первому биту получим
1
√
2
|
0
i
+
e
2
πiO
.
j
1
|
1
i
|
j
2
. . . j
n
i
(8.29)
так как
exp(2
πiO
.
j
1
) =
−
1
когда
j
1
= 1
и равна
+1
в противном случае.
Используя контролируемый
R
2
-гейт производим состояние:
1
√
2
|
0
i
+
e
2
πiO
.
j
1
j
2
|
1
i
|
j
2
. . . j
n
i
.
(8.30)
Продолжая вычисление действий контролируемых
R
3
, R
4
до
R
n
-гейтов, каждый из которых
добавляет экстра-бит к фазе коэффициента при
|
1
i
первого кубита. В конце этой процедуры
получим состояние:
1
√
2
|
0
i
+
e
2
πiO
.
j
1
j
2
...j
n
|
1
i
|
j
2
j
3
. . . j
n
i
.
(8.31)
Преобразуем аналогичной процедурой следующий кубит. В результате получим:
1
√
2
|
0
i
+
e
2
πiO
.
j
1
j
2
...j
n
|
1
i
|
0
i
+
e
2
πiO
.
j
2
...j
n
|
1
i
|
j
3
j
4
. . . j
n
i
.
(8.32)
Продолжая последовательно для каждого кубита, находим конечное состояние
1
√
2
n
|
0
i
+
e
2
πiO
.
j
1
j
2
...j
n
|
1
i
|
0
i
+
e
2
πiO
.
j
2
...j
n
|
1
i
. . .
|
0
i
+
e
2
πiO
.
j
n
|
1
i
(8.33)
Используя далее
SW AP
–
операторы, состояние кубитов приводится к формуле (8.26), т. е.
выполненное Фурье преобразование.
78