ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 23.11.2023
Просмотров: 126
Скачиваний: 5
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
СОДЕРЖАНИЕ
120
заключается сбалансированность). Пусть, например, имеется функция
( )
x
f
с
10-ти битовой областью определения. Тогда для некоторых 512 значений
x
получим
( )
0
=
x
f
, а для остальных 512 значений
x
получим
( )
1
=
x
f
Задача Дойча- Джозса состоит в том, чтобы отличить постоянную функцию от сбалансированной.
Алгоритм Дойча- Джозса является непосредственным обобщением алгоритма Дойча на случай многокубитовых систем. Он описывается следующей квантовой схемой, приведенной на рисунке.
Рис. 5.5 Квантовая схема алгоритма Дойча- Джозса
Задача 5.8
Покажите, что на вход вычислителя
f
U
в схеме Дойча-
Джозса поступает состояние
(
)
2 1
0 2
1 2
0
−
∑
−
=
n
x
n
x
Задача 5.9
Покажите, что на выходе вычислителя
f
U
в схеме Дойча-
Джозса возникает состояние
( )
( )
(
)
2 1
0 2
1 1
2 0
−
−
∑
−
=
n
x
n
x
f
x
121
Задача 5.10
Убедитесь, что действие оператора Адамара
H
на базисные состояния
1
,
0
=
x
отдельного кубита описывается формулой:
( )
∑
=
−
=
1 0
2 1
z
xz
z
x
H
. Покажите, что непосредственно из указанной формулы следует ее
n
- кубитовое обобщение: действие оператора Уолша- Адамара
n
H
⊗
на базисные состояния
n
- кубитового регистра
1 2
,...,
1
,
0
−
=
n
x
описывается формулой:
( )
∑
−
=
⊗
−
=
1 2
0 2
1
n
z
n
xz
n
z
x
H
Здесь
(
)
n
x
x
x
x
,...,
,
2 1
=
и
(
)
n
z
z
z
z
,...,
,
2 1
=
- запись номеров состояний в двоичном представлении,
x
и
z
представляют собой
n
- компонентные строки из нолей и единиц,
n
n
z
x
z
x
z
x
xz
+
+
+
=
2 2
1 1
- скалярное произведение соответствующих строк.
Непосредственно из результатов представленных выше задач следует, что на выходе схемы Уолша- Адамара возникает следующее
1
+
n
- кубитовое состояние:
( )
( )
(
)
2 1
0 2
1 1
2 0
1 2
0
−
−
=
ψ
∑∑
−
=
−
=
+
n
n
z
x
n
x
f
xz
out
z
122
Проведем теперь измерение первых
n
кубитов (регистра запроса).
Амплитуда вероятности найти регистр запроса в состоянии
n
n
z
⊗
=
=
=
0 0
,...,
0
,
0 0
3 2
1
, очевидно, есть:
( )
( )
∑
−
=
−
=
1 2
0 0
,...,
0
,
0 2
1
n
n
x
n
x
f
M
4 3
42 1
Пусть функция
( )
x
f
постоянна, т.е.
( )
( )
1 2
)
1
(
0
−
=
=
=
n
f
f
f
. В этом случае все
n
2
слагаемых в рассматриваемой сумме одинаковы (происходит их конструктивная интерференция), в итоге суммарная амплитуда вероятности оказывается равной
1
+
или
1
−
, а соответствующая вероятность равной единице. Таким образом, если неизвестная функция
( )
x
f
постоянна, то все
n
кубитов регистра запроса с достоверностью оказываются в состоянии
0
Пусть теперь неизвестная функция
( )
x
f
переменна и сбалансирована.
Сбалансированность означает, что для половины из
n
2
возможных значений аргумента
x
функция равна нулю (
( )
0
=
x
f
), а для другой половины возможных значений аргумента
x
- единице (
( )
1
=
x
f
). В этом случае в сумме
( )
( )
∑
−
=
−
=
1 2
0 0
,...,
0
,
0 2
1
n
n
x
n
x
f
M
4 3
42 1
положительные и отрицательные слагаемые полностью скомпенсируют друг друга (деструктивная интерференция).
Теперь суммарная амплитуда и соответствующая вероятность окажутся равными нулю. Таким образом, если неизвестная функция
( )
x
f
123
сбалансирована, то регистр запроса никогда не будет обнаружен в состоянии
3 2
1
n
0
,...,
0
,
0
. Другими словами, хотя бы один из
n
кубитов регистра запроса окажется при измерении в состоянии
1
Мы видим, что алгоритм Дойча- Джозса позволяет с достоверностью отличить постоянную функцию от сбалансированной посредством одного- единственного обращения к вычислителю
f
U
1 2 3 4 5 6 7 8
Задача 5.11
Покажите, что при классическом рассмотрении задачи Дойча-
Джозса для того, чтобы с достоверностью отличить постоянную функцию от сбалансированной может потребоваться до
1 2
1
+
−
n
обращений к устройству, производящему вычисление функции
( )
x
f
Результат представленной задачи показывает, что алгоритм Дойча-
Джозса обеспечивает квантовому компьютеру экспоненциальное преимущество в скорости по сравнению с классическим компьютером.
Это преимущество, однако, имеет место только для идеальной задачи абсолютно безошибочной классификации. В реальных задачах нам, как правило, достаточно ограничиться правдоподобным ответом, который является правильным лишь с вероятностью, очень близкой к единице. Кроме того, получать абсолютно достоверные ответы на вопросы при помощи вычислений невозможно и по чисто техническим причинам, поскольку преобразование данных в компьютере (классическом или квантовом) неизбежно сталкивается с возможными технологическими ошибками, шумами и сбоями. Если же мы ограничиваемся правдоподобными (с вероятностью, близкой к единице) ответами, то в задаче Дойча- Джозса пропадает
124
экспоненциальное преимущество квантового алгоритма по сравнению с классическим вероятностным алгоритмом. Последний заключается в том, что на вход классического вычислителя функции
( )
x
f
подается последовательность случайных чисел
m
x
x
x
,...,
,
2 1
объема
m
и по результатам
( ) ( )
( )
m
x
f
x
f
x
f
,...,
,
2 1
вырабатывается правдоподобный ответ на вопрос о виде функции (постоянная она или сбалансированная).
Задача 5.12
Пусть задача Дойча- Джозса решается на классическом вероятностном компьютере, причем допускается некоторая малая вероятность
ε
ошибки (когда сбалансированная функция принимается за постоянную).
Какой объем
m
последовательности случайных чисел следует взять?
Алгоритм Дойча- Джозса относится к так называемым квантовым вычислениям с оракулом (прорицателем). Роль оракула здесь играет вычислительное устройство
f
U
. Фактически это устройство представляет собой черный ящик, содержание которого неизвестно и несущественно в данной задаче. Все что мы знаем- это то, что оракул обеспечивает выполнение унитарного преобразования
f
U
, где
f
- постоянная или сбалансированная функция. Любое устройство
f
U
- это, конечно, некоторый квантовый код
(алгоритм), который обеспечивает выполнение заданного преобразования. Мы можем считать, что синтаксически рассматриваемый код настолько сложен, что мы не в состоянии понять какую функцию он вычисляет (постоянную или сбалансированную). Не имея возможности понять код, мы используем его как черный ящик в квантовой схеме, при этом вопрос о постоянстве или сбалансированности неизвестной функции
f
решается экспериментально посредством алгоритма Дойча – Джозса. Заметим, однако, что такая постановка задачи несколько искусственна.
125
Главное значение алгоритмов Дойча и Дойча- Джозса методическое: они раскрывают сущность квантового параллелизма и демонстрируют возможности квантовых вычислений.
5.4. Квантовое преобразование Фурье.
Пусть имеется система из
n
кубитов. Ее состояние представляет собой вектор в гильбертовом пространстве размерности
n
N 2
=
. Базисные состояния квантовой системы есть
j
, где
1
,...,
1
,
0
−
=
N
j
Квантовое преобразование Фурье задается следующим унитарным преобразованием базисных состояний:
k
N
jk
i
N
j
N
k
QFT
2
exp
1 1
0
∑
→
−
=
⎟
⎠
⎞
⎜
⎝
⎛ π
Преобразование Фурье базисных функций определяет соответствующее преобразование вектора состояния
∑
∑∑
→
∑
−
=
−
=
−
=
−
=
=
⎟
⎠
⎞
⎜
⎝
⎛ π
=
ψ
1 0
1 0
1 0
1 0
2
exp
1
N
k
k
N
k
N
j
j
QFT
N
j
j
k
c
k
c
N
jk
i
N
j
c
Здесь
j
N
j
k
c
N
jk
i
N
c
2
exp
1
1 0
∑
−
=
⎟
⎠
⎞
⎜
⎝
⎛ π
=
Последняя формула представляет собой преобразование Фурье комплексных амплитуд вероятности. Результат в точности соответствует так называемому классическому дискретному преобразованию
Фурье,
126
примененному к столбцу комплексных чисел
j
c
, где
1
,...,
1
,
0
−
=
N
j
(см. например [70]).
Обратное преобразование Фурье для амплитуд вероятности есть
k
N
k
j
c
N
jk
i
N
c
2
exp
1 1
0
∑
−
=
⎟
⎠
⎞
⎜
⎝
⎛
π
−
=
Квантовое преобразование Фурье принципиально отличается от аналогичного дискретного преобразования Фурье классического сигнала
(несмотря на тождество соответствующих формул). Дело в том, что в квантовой информатике мы имеем дело со специфическим «сигналом», который образован амплитудами вероятности (а не электрическими или механическими напряжениями как в классическом случае). В отличии от классического сигнала, квантовый «сигнал» нельзя измерить никаким
«осциллографом» (при измерении квантовое состояние редуцируется в одно из базисных состояний). В то же время, в квантовой информатике мы можем оперировать векторами данных экспоненциально большой размерности
(например при
1000 2
=
N
).
Для простоты изложения остановимся более подробно на трехкубитовом преобразовании Фурье (
3
=
n
,
8 2
3
=
=
N
).
Например, базисное состояние
5
=
j
будет претерпевать следующее изменение
( )
⎟⎟
⎠
⎞
⎟
⎠
⎞
⎜
⎝
⎛ π
+
⎟
⎠
⎞
⎜
⎝
⎛ π
+
⎟
⎠
⎞
⎜
⎝
⎛ π
+
π
+
⎜⎜
⎝
⎛
+
⎟
⎠
⎞
⎜
⎝
⎛ π
+
⎟
⎠
⎞
⎜
⎝
⎛ π
+
⎟
⎠
⎞
⎜
⎝
⎛ π
+
=
=
⎟⎟
⎠
⎞
⎜⎜
⎝
⎛
⎟
⎠
⎞
⎜
⎝
⎛
π
+
+
⎟
⎠
⎞
⎜
⎝
⎛ π
+
→
7 4
3
exp
6 2
3
exp
5 4
exp
4
exp
3 4
7
exp
2 2
exp
1 4
5
exp
0 8
1 7
8 70
exp
1 8
10
exp
0 8
1 5
i
i
i
i
i
i
i
i
i
QFT
127
Квантовое преобразование Фурье может быть построено на основе элементов Адамара и контролируемого преобразования фазы.
Пусть
k
R
- следующее однокубитовое преобразование фазы:
⎟⎟
⎟
⎠
⎞
⎜⎜
⎜
⎝
⎛
⎟
⎠
⎞
⎜
⎝
⎛ π
=
k
k
i
R
2 2
exp
0 0
1
На рисунке 5.6 изображен двухкубитовый элемент, осуществляющий контролируемое фазовое преобразование. Управляемый кубит (нижний) подвергается преобразованию
k
R
, если управляющий кубит (верхний) находится в состоянии
1
Рис. 5.6 Двухкубитовый элемент, осуществляющий управляемое фазовое преобразование.
На рисунке 5.7 представлена квантовая цепь, обеспечивающая трехкубитовое преобразование Фурье
Рис. 5.7 Квантовая цепь для трехкубитового преобразования Фурье
128
Задача 5.13
Пусть на вход трехкубитовой квантовой схемы, изображенной на представленном выше рисунке, подается состояние
5
=
ψ
in
. Покажите, что на выходе квантовой схемы будет состояние:
( )
⎟⎟
⎠
⎞
⎟
⎠
⎞
⎜
⎝
⎛ π
+
⎟
⎠
⎞
⎜
⎝
⎛ π
+
⎟
⎠
⎞
⎜
⎝
⎛ π
+
π
+
⎜⎜
⎝
⎛
+
⎟
⎠
⎞
⎜
⎝
⎛ π
+
⎟
⎠
⎞
⎜
⎝
⎛ π
+
⎟
⎠
⎞
⎜
⎝
⎛ π
+
=
ψ
111 4
3
exp
011 2
3
exp
101 4
exp
001
exp
110 4
7
exp
010 2
exp
100 4
5
exp
000 8
1
i
i
i
i
i
i
i
out
Решите ту же задачу для других входных состояний
j
7
,...,
1
,
0
=
j
Решение задачи свидетельствует о том, что квантовая схема на рисунке действительно дает трехкубитовое преобразование Фурье с одной существенной оговоркой. Легко видеть, что для того, чтобы результат был правильный, на выходе схемы порядок следования кубитов должен быть обращен. Другими словами, двоичное представление состояний на выходе следует читать не слева направо, а справа налево: например
100
означает состояние
1
и т.д.
Конечно, на выходе схемы можно ввести дополнительные операции обмена состояниями кубитов, но с практической точки зрения это нецелесообразно (лучше договориться об инверсии порядка нумерации кубитов).
Представленная выше трехкубитовая схема допускает простое обобщение на произвольное число кубитов.
Общий алгоритм квантового преобразования Фурье может быть реализован с помощью схемы, изображенной на рисунке.
129
Рис. 5.8 Квантовая цепь для
n
- кубитового преобразования Фурье
Подсчитаем число операций, необходимых для осуществления квантового преобразования Фурье. Из схемы видно, что с первым (верхним) кубитом можно связать
n
преобразований (преобразование Адамара и
1
−
n
фазовое преобразование), аналогично со вторым (сверху) кубитом можно связать
1
−
n
преобразование и т.д. Полное число преобразований, равное сумме арифметической прогрессии, есть
( )
2 1 n
n
+
. Таким образом, число операций, необходимых для осуществления квантового преобразования Фурье, есть величина порядка
( )
(
)
(
)
2 2
log
N
O
n
O
. Отметим, что самые быстрые классические алгоритмы выполняют преобразование Фурье за порядка
(
)
(
)
N
N
O
log операций (так называемое быстрое преобразование Фурье).
Таким образом, квантовый алгоритм имеет экспоненциальное преимущество по сравнению со своим классическим аналогом.
Пример.
Пусть имеется 1000- кубитовое состояние (
1000
=
n
). Ему отвечает вектор состояния, описывающийся
301 10 07
,
1 2
⋅
=
=
n
N
комплексными числами. Для осуществления классического быстрого преобразования потребуется проделать порядка
304 2
10 07
,
1
log
⋅
=
N
N
130
операций. В то же время, квантовое преобразование над рассматриваемым вектором осуществляется примерно за
(
)
6 2
2 10 1
log
⋅
=
N
операций.
Таким образом, экспоненциальное преимущество квантового алгоритма по сравнению с классическим позволит на квантовом компьютере ставить и решать задачи, которые никогда не будут решены на классическом компьютере.
5.5. Нахождение периода функции
Задача определения периода функции является важным примером применения квантового преобразования Фурье.
Предположим, что имеется периодическая функция
( )
x
f
с периодом
T
Это означает, что для всех
x
выполняется тождество:
(
) ( )
x
f
T
x
f
=
+
В последней формуле под операцией сложения подразумевается сложение по модулю
N
. Предположим дополнительно, что все значения функции
( )
x
f
на одном периоде различны. Очевидно, что функция может быть в точности периодической только в том случае, когда
N
делится на
T
без остатка, т.е. если
T
N
M
/
=
- целое число.
В качестве начального состояния возьмем следующую однородную суперпозицию (квантовая схема для получения такого состояния представлена в задаче 5.3.3):
( )
∑
−
=
=
ψ
1 0
,
1
N
x
in
x
f
x
N
131
Проведем измерение второго регистра (регистра функции). Предположим, что при этом мы получим некоторое значение функции
0
f
. Пусть
0
x
- одно из значений аргумента, при котором
( )
0 0
f
x
f
=
. В результате редукции вектора состояния в суперпозиции «выживут» только слагаемые, отвечающие
mT
x
x
+
=
0
, где
1
,..,
1
,
0
−
=
M
m
, поскольку только для них
(
)
0 0
f
mT
x
f
=
+
В результате первый регистр (отвечающий аргументу
x
) перейдет в следующее квантовое состояние:
∑
−
=
+
=
ψ
1 0
0 1
M
m
mT
x
M
Выполним теперь квантовое преобразование Фурье над полученным состоянием. Согласно определению, каждое отдельно взятое базисное состояние будет подвергнуто следующему преобразованию:
(
)
k
N
mT
x
k
i
N
mT
x
N
k
QFT
2
exp
1 1
0 0
0
∑
→
−
=
⎟
⎠
⎞
⎜
⎝
⎛
+
π
+
Суперпозиция, представляющая состояние
ψ
, в результате квантового преобразования Фурье примет вид:
(
)
k
N
mT
x
k
i
M
N
N
k
M
m
out
2
exp
1 1
0 1
0 0
∑∑
−
=
−
=
⎟
⎠
⎞
⎜
⎝
⎛
+
π
=
ψ
Задача 5.14
Пусть
( )
∑
−
=
⎟
⎠
⎞
⎜
⎝
⎛ π
=
1 0
2
exp
M
m
M
km
i
k
F
, где
1
,...,
1
,
0
−
=
N
k
и
MT
N
=
. Покажите, что
( )
M
k
F
=
, если
jM
T
N
j
k
=
=
, где
1
,...,
1
,
0
−
=
T
j
и
( )
0
=
k
F
при всех остальных значениях
k
132
Результаты представленной выше задачи показывают, что выходное состояние регистра может быть записано в виде:
T
N
j
T
j
x
i
T
T
j
out
2
exp
1 1
0 0
∑
−
=
⎟
⎠
⎞
⎜
⎝
⎛ π
=
ψ
Последний шаг процедуры – это измерение полученного состояния. Мы видим, что с равной вероятностью возможно любое из
T
состояний
T
N
j
, где
1
,...,
1
,
0
−
=
T
j
Пусть Природа «выбрала» некоторое
0
j
и в результате измерения возникло состояние
T
N
j
l
0 0
=
. Тогда, имеем следующее тождество для четырех целых чисел:
N
l
T
j
0 0
=
Здесь
0
l
и
N
доступные исследователю числа, в то время как
0
j
и
T
- числа, неизвестные ему. Наша цель- определить
T
. Полученное тождество показывает, что исследователь не может гарантированно определить
T
при однократном выполнении процедуры. Чтобы его поиски оказались продуктивны, ему следует уповать на то, что «выбранное» Природой число
0
j
и период
T
окажутся взаимно простыми (т.е. не будут иметь общих делителей, кроме единицы). Тогда, приведя дробь
N
l /
0
к несократимой, он сможет восстановить
0
j
и
T
. В этом случае нам удастся с помощью одного уравнения (7) найти два неизвестных целых числа. Если же исследователю не
133
повезет и Природа «выберет» такое
0
j
, что дробь
T
j /
0
окажется сократимой, то вместо истинного периода
T
он получит меньшее значение.
Приведем пример. Пусть
1024 2
10
=
=
N
- заранее известное число.
64
=
T
- период, неизвестный исследователю. Природа может «выбрать» любое
0
j
от 0 до 63. Пусть, например, она «выбрала»
21 0
=
j
. Тогда исследователь получит
336 0
0
=
=
T
N
j
l
. Сократив дробь
1024 336
до
64 21
, исследователь правильно определит, что
21 0
=
j
и
64
=
T
. Пусть теперь, Природа «выбрала»
12 0
=
j
Этот выбор неудачен для исследователя, поскольку числа 12 и 64 имеют общий делитель, равный 4. Теперь
192 0
0
=
=
T
N
j
l
. Сократив дробь
1024 192
до
16 3
, исследователь может сделать неправильный вывод, будто бы
3 0
=
j
и
16
=
T
. Для того, чтобы с высокой вероятностью получить правильный ответ, исследователь будет вынужден повторять описанную процедуру многократно.
Тогда, очевидно, в качестве ответа ему следует взять период, отвечающий наибольшему из возможных значений (максимальный знаменатель в дроби
N
l /
0
после ее сокращения).
Оценим, сколько раз исследователь должен проделать описанную выше процедуру, чтобы определить неизвестный период
T
с высокой гарантией.
Для этого нужно оценить вероятность того, что «выбранное» Природой число
0
j
окажется взаимно простым с
T
. Известно, что при больших
T
количество простых чисел, не превышающих
T
можно оценить как
T
T log
/
. Отсюда следует, что вероятность удачи при отдельном испытании больше или порядка
N
T
log
/
1
log
/
1
≥
. Таким образом, если исследователь
134
повторит процедуру
(
)
N
O log раз, то с высокой гарантией, он сможет найти неизвестный период. Например, если
2 1000
=
N
, то потребуется всего порядка 1000 испытаний (в оценках такого рода мы не делаем различия между натуральным и двоичным логарифмами).
Резюмируем полученный результат. Квантовый алгоритм нахождения периода функций требует всего
(
)
(
)
3
log
N
O
операций (для квантового преобразования Фурье требуется
(
)
(
)
2
log
N
O
операций и
(
)
N
O
log операций требуется для описанной выше процедуры угадывания).
Рассматриваемый алгоритм является полиномиальным по числу кубитов и, соответственно, по количеству знаков в числе
N
(поскольку число шагов алгоритма определяется полиномом третьей степени).
Для экспоненциально больших
N
полиномиальный квантовый алгоритм обладает радикальным преимуществом по сравнению с любыми известными классическими алгоритмами. Важный пример использования отмеченного преимущества рассмотрен в следующем разделе.
1 2 3 4 5 6 7 8
Задача 5.11
Покажите, что при классическом рассмотрении задачи Дойча-
Джозса для того, чтобы с достоверностью отличить постоянную функцию от сбалансированной может потребоваться до
1 2
1
+
−
n
обращений к устройству, производящему вычисление функции
( )
x
f
Результат представленной задачи показывает, что алгоритм Дойча-
Джозса обеспечивает квантовому компьютеру экспоненциальное преимущество в скорости по сравнению с классическим компьютером.
Это преимущество, однако, имеет место только для идеальной задачи абсолютно безошибочной классификации. В реальных задачах нам, как правило, достаточно ограничиться правдоподобным ответом, который является правильным лишь с вероятностью, очень близкой к единице. Кроме того, получать абсолютно достоверные ответы на вопросы при помощи вычислений невозможно и по чисто техническим причинам, поскольку преобразование данных в компьютере (классическом или квантовом) неизбежно сталкивается с возможными технологическими ошибками, шумами и сбоями. Если же мы ограничиваемся правдоподобными (с вероятностью, близкой к единице) ответами, то в задаче Дойча- Джозса пропадает
124
экспоненциальное преимущество квантового алгоритма по сравнению с классическим вероятностным алгоритмом. Последний заключается в том, что на вход классического вычислителя функции
( )
x
f
подается последовательность случайных чисел
m
x
x
x
,...,
,
2 1
объема
m
и по результатам
( ) ( )
( )
m
x
f
x
f
x
f
,...,
,
2 1
вырабатывается правдоподобный ответ на вопрос о виде функции (постоянная она или сбалансированная).
Задача 5.12
Пусть задача Дойча- Джозса решается на классическом вероятностном компьютере, причем допускается некоторая малая вероятность
ε
ошибки (когда сбалансированная функция принимается за постоянную).
Какой объем
m
последовательности случайных чисел следует взять?
Алгоритм Дойча- Джозса относится к так называемым квантовым вычислениям с оракулом (прорицателем). Роль оракула здесь играет вычислительное устройство
f
U
. Фактически это устройство представляет собой черный ящик, содержание которого неизвестно и несущественно в данной задаче. Все что мы знаем- это то, что оракул обеспечивает выполнение унитарного преобразования
f
U
, где
f
- постоянная или сбалансированная функция. Любое устройство
f
U
- это, конечно, некоторый квантовый код
(алгоритм), который обеспечивает выполнение заданного преобразования. Мы можем считать, что синтаксически рассматриваемый код настолько сложен, что мы не в состоянии понять какую функцию он вычисляет (постоянную или сбалансированную). Не имея возможности понять код, мы используем его как черный ящик в квантовой схеме, при этом вопрос о постоянстве или сбалансированности неизвестной функции
f
решается экспериментально посредством алгоритма Дойча – Джозса. Заметим, однако, что такая постановка задачи несколько искусственна.
125
Главное значение алгоритмов Дойча и Дойча- Джозса методическое: они раскрывают сущность квантового параллелизма и демонстрируют возможности квантовых вычислений.
5.4. Квантовое преобразование Фурье.
Пусть имеется система из
n
кубитов. Ее состояние представляет собой вектор в гильбертовом пространстве размерности
n
N 2
=
. Базисные состояния квантовой системы есть
j
, где
1
,...,
1
,
0
−
=
N
j
Квантовое преобразование Фурье задается следующим унитарным преобразованием базисных состояний:
k
N
jk
i
N
j
N
k
QFT
2
exp
1 1
0
∑
→
−
=
⎟
⎠
⎞
⎜
⎝
⎛ π
Преобразование Фурье базисных функций определяет соответствующее преобразование вектора состояния
∑
∑∑
→
∑
−
=
−
=
−
=
−
=
=
⎟
⎠
⎞
⎜
⎝
⎛ π
=
ψ
1 0
1 0
1 0
1 0
2
exp
1
N
k
k
N
k
N
j
j
QFT
N
j
j
k
c
k
c
N
jk
i
N
j
c
Здесь
j
N
j
k
c
N
jk
i
N
c
2
exp
1
1 0
∑
−
=
⎟
⎠
⎞
⎜
⎝
⎛ π
=
Последняя формула представляет собой преобразование Фурье комплексных амплитуд вероятности. Результат в точности соответствует так называемому классическому дискретному преобразованию
Фурье,
126
примененному к столбцу комплексных чисел
j
c
, где
1
,...,
1
,
0
−
=
N
j
(см. например [70]).
Обратное преобразование Фурье для амплитуд вероятности есть
k
N
k
j
c
N
jk
i
N
c
2
exp
1 1
0
∑
−
=
⎟
⎠
⎞
⎜
⎝
⎛
π
−
=
Квантовое преобразование Фурье принципиально отличается от аналогичного дискретного преобразования Фурье классического сигнала
(несмотря на тождество соответствующих формул). Дело в том, что в квантовой информатике мы имеем дело со специфическим «сигналом», который образован амплитудами вероятности (а не электрическими или механическими напряжениями как в классическом случае). В отличии от классического сигнала, квантовый «сигнал» нельзя измерить никаким
«осциллографом» (при измерении квантовое состояние редуцируется в одно из базисных состояний). В то же время, в квантовой информатике мы можем оперировать векторами данных экспоненциально большой размерности
(например при
1000 2
=
N
).
Для простоты изложения остановимся более подробно на трехкубитовом преобразовании Фурье (
3
=
n
,
8 2
3
=
=
N
).
Например, базисное состояние
5
=
j
будет претерпевать следующее изменение
( )
⎟⎟
⎠
⎞
⎟
⎠
⎞
⎜
⎝
⎛ π
+
⎟
⎠
⎞
⎜
⎝
⎛ π
+
⎟
⎠
⎞
⎜
⎝
⎛ π
+
π
+
⎜⎜
⎝
⎛
+
⎟
⎠
⎞
⎜
⎝
⎛ π
+
⎟
⎠
⎞
⎜
⎝
⎛ π
+
⎟
⎠
⎞
⎜
⎝
⎛ π
+
=
=
⎟⎟
⎠
⎞
⎜⎜
⎝
⎛
⎟
⎠
⎞
⎜
⎝
⎛
π
+
+
⎟
⎠
⎞
⎜
⎝
⎛ π
+
→
7 4
3
exp
6 2
3
exp
5 4
exp
4
exp
3 4
7
exp
2 2
exp
1 4
5
exp
0 8
1 7
8 70
exp
1 8
10
exp
0 8
1 5
i
i
i
i
i
i
i
i
i
QFT
127
Квантовое преобразование Фурье может быть построено на основе элементов Адамара и контролируемого преобразования фазы.
Пусть
k
R
- следующее однокубитовое преобразование фазы:
⎟⎟
⎟
⎠
⎞
⎜⎜
⎜
⎝
⎛
⎟
⎠
⎞
⎜
⎝
⎛ π
=
k
k
i
R
2 2
exp
0 0
1
На рисунке 5.6 изображен двухкубитовый элемент, осуществляющий контролируемое фазовое преобразование. Управляемый кубит (нижний) подвергается преобразованию
k
R
, если управляющий кубит (верхний) находится в состоянии
1
Рис. 5.6 Двухкубитовый элемент, осуществляющий управляемое фазовое преобразование.
На рисунке 5.7 представлена квантовая цепь, обеспечивающая трехкубитовое преобразование Фурье
Рис. 5.7 Квантовая цепь для трехкубитового преобразования Фурье
128
Задача 5.13
Пусть на вход трехкубитовой квантовой схемы, изображенной на представленном выше рисунке, подается состояние
5
=
ψ
in
. Покажите, что на выходе квантовой схемы будет состояние:
( )
⎟⎟
⎠
⎞
⎟
⎠
⎞
⎜
⎝
⎛ π
+
⎟
⎠
⎞
⎜
⎝
⎛ π
+
⎟
⎠
⎞
⎜
⎝
⎛ π
+
π
+
⎜⎜
⎝
⎛
+
⎟
⎠
⎞
⎜
⎝
⎛ π
+
⎟
⎠
⎞
⎜
⎝
⎛ π
+
⎟
⎠
⎞
⎜
⎝
⎛ π
+
=
ψ
111 4
3
exp
011 2
3
exp
101 4
exp
001
exp
110 4
7
exp
010 2
exp
100 4
5
exp
000 8
1
i
i
i
i
i
i
i
out
Решите ту же задачу для других входных состояний
j
7
,...,
1
,
0
=
j
Решение задачи свидетельствует о том, что квантовая схема на рисунке действительно дает трехкубитовое преобразование Фурье с одной существенной оговоркой. Легко видеть, что для того, чтобы результат был правильный, на выходе схемы порядок следования кубитов должен быть обращен. Другими словами, двоичное представление состояний на выходе следует читать не слева направо, а справа налево: например
100
означает состояние
1
и т.д.
Конечно, на выходе схемы можно ввести дополнительные операции обмена состояниями кубитов, но с практической точки зрения это нецелесообразно (лучше договориться об инверсии порядка нумерации кубитов).
Представленная выше трехкубитовая схема допускает простое обобщение на произвольное число кубитов.
Общий алгоритм квантового преобразования Фурье может быть реализован с помощью схемы, изображенной на рисунке.
129
Рис. 5.8 Квантовая цепь для
n
- кубитового преобразования Фурье
Подсчитаем число операций, необходимых для осуществления квантового преобразования Фурье. Из схемы видно, что с первым (верхним) кубитом можно связать
n
преобразований (преобразование Адамара и
1
−
n
фазовое преобразование), аналогично со вторым (сверху) кубитом можно связать
1
−
n
преобразование и т.д. Полное число преобразований, равное сумме арифметической прогрессии, есть
( )
2 1 n
n
+
. Таким образом, число операций, необходимых для осуществления квантового преобразования Фурье, есть величина порядка
( )
(
)
(
)
2 2
log
N
O
n
O
. Отметим, что самые быстрые классические алгоритмы выполняют преобразование Фурье за порядка
(
)
(
)
N
N
O
log операций (так называемое быстрое преобразование Фурье).
Таким образом, квантовый алгоритм имеет экспоненциальное преимущество по сравнению со своим классическим аналогом.
Пример.
Пусть имеется 1000- кубитовое состояние (
1000
=
n
). Ему отвечает вектор состояния, описывающийся
301 10 07
,
1 2
⋅
=
=
n
N
комплексными числами. Для осуществления классического быстрого преобразования потребуется проделать порядка
304 2
10 07
,
1
log
⋅
=
N
N
130
операций. В то же время, квантовое преобразование над рассматриваемым вектором осуществляется примерно за
(
)
6 2
2 10 1
log
⋅
=
N
операций.
Таким образом, экспоненциальное преимущество квантового алгоритма по сравнению с классическим позволит на квантовом компьютере ставить и решать задачи, которые никогда не будут решены на классическом компьютере.
5.5. Нахождение периода функции
Задача определения периода функции является важным примером применения квантового преобразования Фурье.
Предположим, что имеется периодическая функция
( )
x
f
с периодом
T
Это означает, что для всех
x
выполняется тождество:
(
) ( )
x
f
T
x
f
=
+
В последней формуле под операцией сложения подразумевается сложение по модулю
N
. Предположим дополнительно, что все значения функции
( )
x
f
на одном периоде различны. Очевидно, что функция может быть в точности периодической только в том случае, когда
N
делится на
T
без остатка, т.е. если
T
N
M
/
=
- целое число.
В качестве начального состояния возьмем следующую однородную суперпозицию (квантовая схема для получения такого состояния представлена в задаче 5.3.3):
( )
∑
−
=
=
ψ
1 0
,
1
N
x
in
x
f
x
N
131
Проведем измерение второго регистра (регистра функции). Предположим, что при этом мы получим некоторое значение функции
0
f
. Пусть
0
x
- одно из значений аргумента, при котором
( )
0 0
f
x
f
=
. В результате редукции вектора состояния в суперпозиции «выживут» только слагаемые, отвечающие
mT
x
x
+
=
0
, где
1
,..,
1
,
0
−
=
M
m
, поскольку только для них
(
)
0 0
f
mT
x
f
=
+
В результате первый регистр (отвечающий аргументу
x
) перейдет в следующее квантовое состояние:
∑
−
=
+
=
ψ
1 0
0 1
M
m
mT
x
M
Выполним теперь квантовое преобразование Фурье над полученным состоянием. Согласно определению, каждое отдельно взятое базисное состояние будет подвергнуто следующему преобразованию:
(
)
k
N
mT
x
k
i
N
mT
x
N
k
QFT
2
exp
1 1
0 0
0
∑
→
−
=
⎟
⎠
⎞
⎜
⎝
⎛
+
π
+
Суперпозиция, представляющая состояние
ψ
, в результате квантового преобразования Фурье примет вид:
(
)
k
N
mT
x
k
i
M
N
N
k
M
m
out
2
exp
1 1
0 1
0 0
∑∑
−
=
−
=
⎟
⎠
⎞
⎜
⎝
⎛
+
π
=
ψ
Задача 5.14
Пусть
( )
∑
−
=
⎟
⎠
⎞
⎜
⎝
⎛ π
=
1 0
2
exp
M
m
M
km
i
k
F
, где
1
,...,
1
,
0
−
=
N
k
и
MT
N
=
. Покажите, что
( )
M
k
F
=
, если
jM
T
N
j
k
=
=
, где
1
,...,
1
,
0
−
=
T
j
и
( )
0
=
k
F
при всех остальных значениях
k
132
Результаты представленной выше задачи показывают, что выходное состояние регистра может быть записано в виде:
T
N
j
T
j
x
i
T
T
j
out
2
exp
1 1
0 0
∑
−
=
⎟
⎠
⎞
⎜
⎝
⎛ π
=
ψ
Последний шаг процедуры – это измерение полученного состояния. Мы видим, что с равной вероятностью возможно любое из
T
состояний
T
N
j
, где
1
,...,
1
,
0
−
=
T
j
Пусть Природа «выбрала» некоторое
0
j
и в результате измерения возникло состояние
T
N
j
l
0 0
=
. Тогда, имеем следующее тождество для четырех целых чисел:
N
l
T
j
0 0
=
Здесь
0
l
и
N
доступные исследователю числа, в то время как
0
j
и
T
- числа, неизвестные ему. Наша цель- определить
T
. Полученное тождество показывает, что исследователь не может гарантированно определить
T
при однократном выполнении процедуры. Чтобы его поиски оказались продуктивны, ему следует уповать на то, что «выбранное» Природой число
0
j
и период
T
окажутся взаимно простыми (т.е. не будут иметь общих делителей, кроме единицы). Тогда, приведя дробь
N
l /
0
к несократимой, он сможет восстановить
0
j
и
T
. В этом случае нам удастся с помощью одного уравнения (7) найти два неизвестных целых числа. Если же исследователю не
133
повезет и Природа «выберет» такое
0
j
, что дробь
T
j /
0
окажется сократимой, то вместо истинного периода
T
он получит меньшее значение.
Приведем пример. Пусть
1024 2
10
=
=
N
- заранее известное число.
64
=
T
- период, неизвестный исследователю. Природа может «выбрать» любое
0
j
от 0 до 63. Пусть, например, она «выбрала»
21 0
=
j
. Тогда исследователь получит
336 0
0
=
=
T
N
j
l
. Сократив дробь
1024 336
до
64 21
, исследователь правильно определит, что
21 0
=
j
и
64
=
T
. Пусть теперь, Природа «выбрала»
12 0
=
j
Этот выбор неудачен для исследователя, поскольку числа 12 и 64 имеют общий делитель, равный 4. Теперь
192 0
0
=
=
T
N
j
l
. Сократив дробь
1024 192
до
16 3
, исследователь может сделать неправильный вывод, будто бы
3 0
=
j
и
16
=
T
. Для того, чтобы с высокой вероятностью получить правильный ответ, исследователь будет вынужден повторять описанную процедуру многократно.
Тогда, очевидно, в качестве ответа ему следует взять период, отвечающий наибольшему из возможных значений (максимальный знаменатель в дроби
N
l /
0
после ее сокращения).
Оценим, сколько раз исследователь должен проделать описанную выше процедуру, чтобы определить неизвестный период
T
с высокой гарантией.
Для этого нужно оценить вероятность того, что «выбранное» Природой число
0
j
окажется взаимно простым с
T
. Известно, что при больших
T
количество простых чисел, не превышающих
T
можно оценить как
T
T log
/
. Отсюда следует, что вероятность удачи при отдельном испытании больше или порядка
N
T
log
/
1
log
/
1
≥
. Таким образом, если исследователь
134
повторит процедуру
(
)
N
O log раз, то с высокой гарантией, он сможет найти неизвестный период. Например, если
2 1000
=
N
, то потребуется всего порядка 1000 испытаний (в оценках такого рода мы не делаем различия между натуральным и двоичным логарифмами).
Резюмируем полученный результат. Квантовый алгоритм нахождения периода функций требует всего
(
)
(
)
3
log
N
O
операций (для квантового преобразования Фурье требуется
(
)
(
)
2
log
N
O
операций и
(
)
N
O
log операций требуется для описанной выше процедуры угадывания).
Рассматриваемый алгоритм является полиномиальным по числу кубитов и, соответственно, по количеству знаков в числе
N
(поскольку число шагов алгоритма определяется полиномом третьей степени).
Для экспоненциально больших
N
полиномиальный квантовый алгоритм обладает радикальным преимуществом по сравнению с любыми известными классическими алгоритмами. Важный пример использования отмеченного преимущества рассмотрен в следующем разделе.
1 2 3 4 5 6 7 8
Покажите, что при классическом рассмотрении задачи Дойча-
Джозса для того, чтобы с достоверностью отличить постоянную функцию от сбалансированной может потребоваться до
1 2
1
+
−
n
обращений к устройству, производящему вычисление функции
( )
x
f
Результат представленной задачи показывает, что алгоритм Дойча-
Джозса обеспечивает квантовому компьютеру экспоненциальное преимущество в скорости по сравнению с классическим компьютером.
Это преимущество, однако, имеет место только для идеальной задачи абсолютно безошибочной классификации. В реальных задачах нам, как правило, достаточно ограничиться правдоподобным ответом, который является правильным лишь с вероятностью, очень близкой к единице. Кроме того, получать абсолютно достоверные ответы на вопросы при помощи вычислений невозможно и по чисто техническим причинам, поскольку преобразование данных в компьютере (классическом или квантовом) неизбежно сталкивается с возможными технологическими ошибками, шумами и сбоями. Если же мы ограничиваемся правдоподобными (с вероятностью, близкой к единице) ответами, то в задаче Дойча- Джозса пропадает
124
экспоненциальное преимущество квантового алгоритма по сравнению с классическим вероятностным алгоритмом. Последний заключается в том, что на вход классического вычислителя функции
( )
x
f
подается последовательность случайных чисел
m
x
x
x
,...,
,
2 1
объема
m
и по результатам
( ) ( )
( )
m
x
f
x
f
x
f
,...,
,
2 1
вырабатывается правдоподобный ответ на вопрос о виде функции (постоянная она или сбалансированная).
Задача 5.12
Пусть задача Дойча- Джозса решается на классическом вероятностном компьютере, причем допускается некоторая малая вероятность
ε
ошибки (когда сбалансированная функция принимается за постоянную).
Какой объем
m
последовательности случайных чисел следует взять?
Алгоритм Дойча- Джозса относится к так называемым квантовым вычислениям с оракулом (прорицателем). Роль оракула здесь играет вычислительное устройство
f
U
. Фактически это устройство представляет собой черный ящик, содержание которого неизвестно и несущественно в данной задаче. Все что мы знаем- это то, что оракул обеспечивает выполнение унитарного преобразования
f
U
, где
f
- постоянная или сбалансированная функция. Любое устройство
f
U
- это, конечно, некоторый квантовый код
(алгоритм), который обеспечивает выполнение заданного преобразования. Мы можем считать, что синтаксически рассматриваемый код настолько сложен, что мы не в состоянии понять какую функцию он вычисляет (постоянную или сбалансированную). Не имея возможности понять код, мы используем его как черный ящик в квантовой схеме, при этом вопрос о постоянстве или сбалансированности неизвестной функции
f
решается экспериментально посредством алгоритма Дойча – Джозса. Заметим, однако, что такая постановка задачи несколько искусственна.
125
Главное значение алгоритмов Дойча и Дойча- Джозса методическое: они раскрывают сущность квантового параллелизма и демонстрируют возможности квантовых вычислений.
5.4. Квантовое преобразование Фурье.
Пусть имеется система из
n
кубитов. Ее состояние представляет собой вектор в гильбертовом пространстве размерности
n
N 2
=
. Базисные состояния квантовой системы есть
j
, где
1
,...,
1
,
0
−
=
N
j
Квантовое преобразование Фурье задается следующим унитарным преобразованием базисных состояний:
k
N
jk
i
N
j
N
k
QFT
2
exp
1 1
0
∑
→
−
=
⎟
⎠
⎞
⎜
⎝
⎛ π
Преобразование Фурье базисных функций определяет соответствующее преобразование вектора состояния
∑
∑∑
→
∑
−
=
−
=
−
=
−
=
=
⎟
⎠
⎞
⎜
⎝
⎛ π
=
ψ
1 0
1 0
1 0
1 0
2
exp
1
N
k
k
N
k
N
j
j
QFT
N
j
j
k
c
k
c
N
jk
i
N
j
c
Здесь
j
N
j
k
c
N
jk
i
N
c
2
exp
1
1 0
∑
−
=
⎟
⎠
⎞
⎜
⎝
⎛ π
=
Последняя формула представляет собой преобразование Фурье комплексных амплитуд вероятности. Результат в точности соответствует так называемому классическому дискретному преобразованию
Фурье,
126
примененному к столбцу комплексных чисел
j
c
, где
1
,...,
1
,
0
−
=
N
j
(см. например [70]).
Обратное преобразование Фурье для амплитуд вероятности есть
k
N
k
j
c
N
jk
i
N
c
2
exp
1 1
0
∑
−
=
⎟
⎠
⎞
⎜
⎝
⎛
π
−
=
Квантовое преобразование Фурье принципиально отличается от аналогичного дискретного преобразования Фурье классического сигнала
(несмотря на тождество соответствующих формул). Дело в том, что в квантовой информатике мы имеем дело со специфическим «сигналом», который образован амплитудами вероятности (а не электрическими или механическими напряжениями как в классическом случае). В отличии от классического сигнала, квантовый «сигнал» нельзя измерить никаким
«осциллографом» (при измерении квантовое состояние редуцируется в одно из базисных состояний). В то же время, в квантовой информатике мы можем оперировать векторами данных экспоненциально большой размерности
(например при
1000 2
=
N
).
Для простоты изложения остановимся более подробно на трехкубитовом преобразовании Фурье (
3
=
n
,
8 2
3
=
=
N
).
Например, базисное состояние
5
=
j
будет претерпевать следующее изменение
( )
⎟⎟
⎠
⎞
⎟
⎠
⎞
⎜
⎝
⎛ π
+
⎟
⎠
⎞
⎜
⎝
⎛ π
+
⎟
⎠
⎞
⎜
⎝
⎛ π
+
π
+
⎜⎜
⎝
⎛
+
⎟
⎠
⎞
⎜
⎝
⎛ π
+
⎟
⎠
⎞
⎜
⎝
⎛ π
+
⎟
⎠
⎞
⎜
⎝
⎛ π
+
=
=
⎟⎟
⎠
⎞
⎜⎜
⎝
⎛
⎟
⎠
⎞
⎜
⎝
⎛
π
+
+
⎟
⎠
⎞
⎜
⎝
⎛ π
+
→
7 4
3
exp
6 2
3
exp
5 4
exp
4
exp
3 4
7
exp
2 2
exp
1 4
5
exp
0 8
1 7
8 70
exp
1 8
10
exp
0 8
1 5
i
i
i
i
i
i
i
i
i
QFT
127
Квантовое преобразование Фурье может быть построено на основе элементов Адамара и контролируемого преобразования фазы.
Пусть
k
R
- следующее однокубитовое преобразование фазы:
⎟⎟
⎟
⎠
⎞
⎜⎜
⎜
⎝
⎛
⎟
⎠
⎞
⎜
⎝
⎛ π
=
k
k
i
R
2 2
exp
0 0
1
На рисунке 5.6 изображен двухкубитовый элемент, осуществляющий контролируемое фазовое преобразование. Управляемый кубит (нижний) подвергается преобразованию
k
R
, если управляющий кубит (верхний) находится в состоянии
1
Рис. 5.6 Двухкубитовый элемент, осуществляющий управляемое фазовое преобразование.
На рисунке 5.7 представлена квантовая цепь, обеспечивающая трехкубитовое преобразование Фурье
Рис. 5.7 Квантовая цепь для трехкубитового преобразования Фурье
128
Задача 5.13
Пусть на вход трехкубитовой квантовой схемы, изображенной на представленном выше рисунке, подается состояние
5
=
ψ
in
. Покажите, что на выходе квантовой схемы будет состояние:
( )
⎟⎟
⎠
⎞
⎟
⎠
⎞
⎜
⎝
⎛ π
+
⎟
⎠
⎞
⎜
⎝
⎛ π
+
⎟
⎠
⎞
⎜
⎝
⎛ π
+
π
+
⎜⎜
⎝
⎛
+
⎟
⎠
⎞
⎜
⎝
⎛ π
+
⎟
⎠
⎞
⎜
⎝
⎛ π
+
⎟
⎠
⎞
⎜
⎝
⎛ π
+
=
ψ
111 4
3
exp
011 2
3
exp
101 4
exp
001
exp
110 4
7
exp
010 2
exp
100 4
5
exp
000 8
1
i
i
i
i
i
i
i
out
Решите ту же задачу для других входных состояний
j
7
,...,
1
,
0
=
j
Решение задачи свидетельствует о том, что квантовая схема на рисунке действительно дает трехкубитовое преобразование Фурье с одной существенной оговоркой. Легко видеть, что для того, чтобы результат был правильный, на выходе схемы порядок следования кубитов должен быть обращен. Другими словами, двоичное представление состояний на выходе следует читать не слева направо, а справа налево: например
100
означает состояние
1
и т.д.
Конечно, на выходе схемы можно ввести дополнительные операции обмена состояниями кубитов, но с практической точки зрения это нецелесообразно (лучше договориться об инверсии порядка нумерации кубитов).
Представленная выше трехкубитовая схема допускает простое обобщение на произвольное число кубитов.
Общий алгоритм квантового преобразования Фурье может быть реализован с помощью схемы, изображенной на рисунке.
129
Рис. 5.8 Квантовая цепь для
n
- кубитового преобразования Фурье
Подсчитаем число операций, необходимых для осуществления квантового преобразования Фурье. Из схемы видно, что с первым (верхним) кубитом можно связать
n
преобразований (преобразование Адамара и
1
−
n
фазовое преобразование), аналогично со вторым (сверху) кубитом можно связать
1
−
n
преобразование и т.д. Полное число преобразований, равное сумме арифметической прогрессии, есть
( )
2 1 n
n
+
. Таким образом, число операций, необходимых для осуществления квантового преобразования Фурье, есть величина порядка
( )
(
)
(
)
2 2
log
N
O
n
O
. Отметим, что самые быстрые классические алгоритмы выполняют преобразование Фурье за порядка
(
)
(
)
N
N
O
log операций (так называемое быстрое преобразование Фурье).
Таким образом, квантовый алгоритм имеет экспоненциальное преимущество по сравнению со своим классическим аналогом.
Пример.
Пусть имеется 1000- кубитовое состояние (
1000
=
n
). Ему отвечает вектор состояния, описывающийся
301 10 07
,
1 2
⋅
=
=
n
N
комплексными числами. Для осуществления классического быстрого преобразования потребуется проделать порядка
304 2
10 07
,
1
log
⋅
=
N
N
130
операций. В то же время, квантовое преобразование над рассматриваемым вектором осуществляется примерно за
(
)
6 2
2 10 1
log
⋅
=
N
операций.
Таким образом, экспоненциальное преимущество квантового алгоритма по сравнению с классическим позволит на квантовом компьютере ставить и решать задачи, которые никогда не будут решены на классическом компьютере.
5.5. Нахождение периода функции
Задача определения периода функции является важным примером применения квантового преобразования Фурье.
Предположим, что имеется периодическая функция
( )
x
f
с периодом
T
Это означает, что для всех
x
выполняется тождество:
(
) ( )
x
f
T
x
f
=
+
В последней формуле под операцией сложения подразумевается сложение по модулю
N
. Предположим дополнительно, что все значения функции
( )
x
f
на одном периоде различны. Очевидно, что функция может быть в точности периодической только в том случае, когда
N
делится на
T
без остатка, т.е. если
T
N
M
/
=
- целое число.
В качестве начального состояния возьмем следующую однородную суперпозицию (квантовая схема для получения такого состояния представлена в задаче 5.3.3):
( )
∑
−
=
=
ψ
1 0
,
1
N
x
in
x
f
x
N
131
Проведем измерение второго регистра (регистра функции). Предположим, что при этом мы получим некоторое значение функции
0
f
. Пусть
0
x
- одно из значений аргумента, при котором
( )
0 0
f
x
f
=
. В результате редукции вектора состояния в суперпозиции «выживут» только слагаемые, отвечающие
mT
x
x
+
=
0
, где
1
,..,
1
,
0
−
=
M
m
, поскольку только для них
(
)
0 0
f
mT
x
f
=
+
В результате первый регистр (отвечающий аргументу
x
) перейдет в следующее квантовое состояние:
∑
−
=
+
=
ψ
1 0
0 1
M
m
mT
x
M
Выполним теперь квантовое преобразование Фурье над полученным состоянием. Согласно определению, каждое отдельно взятое базисное состояние будет подвергнуто следующему преобразованию:
(
)
k
N
mT
x
k
i
N
mT
x
N
k
QFT
2
exp
1 1
0 0
0
∑
→
−
=
⎟
⎠
⎞
⎜
⎝
⎛
+
π
+
Суперпозиция, представляющая состояние
ψ
, в результате квантового преобразования Фурье примет вид:
(
)
k
N
mT
x
k
i
M
N
N
k
M
m
out
2
exp
1 1
0 1
0 0
∑∑
−
=
−
=
⎟
⎠
⎞
⎜
⎝
⎛
+
π
=
ψ
Задача 5.14
Пусть
( )
∑
−
=
⎟
⎠
⎞
⎜
⎝
⎛ π
=
1 0
2
exp
M
m
M
km
i
k
F
, где
1
,...,
1
,
0
−
=
N
k
и
MT
N
=
. Покажите, что
( )
M
k
F
=
, если
jM
T
N
j
k
=
=
, где
1
,...,
1
,
0
−
=
T
j
и
( )
0
=
k
F
при всех остальных значениях
k
132
Результаты представленной выше задачи показывают, что выходное состояние регистра может быть записано в виде:
T
N
j
T
j
x
i
T
T
j
out
2
exp
1 1
0 0
∑
−
=
⎟
⎠
⎞
⎜
⎝
⎛ π
=
ψ
Последний шаг процедуры – это измерение полученного состояния. Мы видим, что с равной вероятностью возможно любое из
T
состояний
T
N
j
, где
1
,...,
1
,
0
−
=
T
j
Пусть Природа «выбрала» некоторое
0
j
и в результате измерения возникло состояние
T
N
j
l
0 0
=
. Тогда, имеем следующее тождество для четырех целых чисел:
N
l
T
j
0 0
=
Здесь
0
l
и
N
доступные исследователю числа, в то время как
0
j
и
T
- числа, неизвестные ему. Наша цель- определить
T
. Полученное тождество показывает, что исследователь не может гарантированно определить
T
при однократном выполнении процедуры. Чтобы его поиски оказались продуктивны, ему следует уповать на то, что «выбранное» Природой число
0
j
и период
T
окажутся взаимно простыми (т.е. не будут иметь общих делителей, кроме единицы). Тогда, приведя дробь
N
l /
0
к несократимой, он сможет восстановить
0
j
и
T
. В этом случае нам удастся с помощью одного уравнения (7) найти два неизвестных целых числа. Если же исследователю не
133
повезет и Природа «выберет» такое
0
j
, что дробь
T
j /
0
окажется сократимой, то вместо истинного периода
T
он получит меньшее значение.
Приведем пример. Пусть
1024 2
10
=
=
N
- заранее известное число.
64
=
T
- период, неизвестный исследователю. Природа может «выбрать» любое
0
j
от 0 до 63. Пусть, например, она «выбрала»
21 0
=
j
. Тогда исследователь получит
336 0
0
=
=
T
N
j
l
. Сократив дробь
1024 336
до
64 21
, исследователь правильно определит, что
21 0
=
j
и
64
=
T
. Пусть теперь, Природа «выбрала»
12 0
=
j
Этот выбор неудачен для исследователя, поскольку числа 12 и 64 имеют общий делитель, равный 4. Теперь
192 0
0
=
=
T
N
j
l
. Сократив дробь
1024 192
до
16 3
, исследователь может сделать неправильный вывод, будто бы
3 0
=
j
и
16
=
T
. Для того, чтобы с высокой вероятностью получить правильный ответ, исследователь будет вынужден повторять описанную процедуру многократно.
Тогда, очевидно, в качестве ответа ему следует взять период, отвечающий наибольшему из возможных значений (максимальный знаменатель в дроби
N
l /
0
после ее сокращения).
Оценим, сколько раз исследователь должен проделать описанную выше процедуру, чтобы определить неизвестный период
T
с высокой гарантией.
Для этого нужно оценить вероятность того, что «выбранное» Природой число
0
j
окажется взаимно простым с
T
. Известно, что при больших
T
количество простых чисел, не превышающих
T
можно оценить как
T
T log
/
. Отсюда следует, что вероятность удачи при отдельном испытании больше или порядка
N
T
log
/
1
log
/
1
≥
. Таким образом, если исследователь
134
повторит процедуру
(
)
N
O log раз, то с высокой гарантией, он сможет найти неизвестный период. Например, если
2 1000
=
N
, то потребуется всего порядка 1000 испытаний (в оценках такого рода мы не делаем различия между натуральным и двоичным логарифмами).
Резюмируем полученный результат. Квантовый алгоритм нахождения периода функций требует всего
(
)
(
)
3
log
N
O
операций (для квантового преобразования Фурье требуется
(
)
(
)
2
log
N
O
операций и
(
)
N
O
log операций требуется для описанной выше процедуры угадывания).
Рассматриваемый алгоритм является полиномиальным по числу кубитов и, соответственно, по количеству знаков в числе
N
(поскольку число шагов алгоритма определяется полиномом третьей степени).
Для экспоненциально больших
N
полиномиальный квантовый алгоритм обладает радикальным преимуществом по сравнению с любыми известными классическими алгоритмами. Важный пример использования отмеченного преимущества рассмотрен в следующем разделе.
1 2 3 4 5 6 7 8
5.6 Факторизация чисел
Алгоритм нахождения периода функции, рассмотренный выше, может быть с успехом применен для разложения заданного целого числа на множители. Эта задача решается с помощью алгоритма, придуманного П.
Шором в 1994 г.
В настоящее время алгоритм Шора- самый знаменитый из известных квантовых алгоритмов. Он позволяет за
(
)
(
)
3
log
N
O
шагов осуществить разложение целого числа
N
на множители и, таким образом, является
135
алгоритмом полиномиальной сложности. Заметим, что аналогичный классический полиномиальный алгоритм неизвестен.
Пусть
N
- целое нечетное число (при четном
N
имеем тривиальное решение задачи). Нам требуется разложить данное число на простые множители или показать, что оно простое.
Выберем случайно число
N
a
<
. Вычислим наибольший общий делитель
(НОД) чисел
a
и
N
(это можно сделать с помощью алгоритма Евклида, который изложен в конце настоящего раздела).
Если НОД чисел
a
и
N
оказался большим, чем единица, то задача решена.
Предположим, что НОД чисел
a
и
N
равен единице. Тогда, согласно известной в теории чисел теореме Эйлера, существует такое
r
, что:
N
a
r
mod
1
=
Выберем минимальное
r
, удовлетворяющее указанному тождеству. Оно называется порядком числа
a
по модулю
N
Рассмотрим теперь функцию
( )
N
a
x
f
x
mod
=
Заметим, что утверждение о том, что
r
есть порядок числа
a
по модулю
N
и утверждение о том, что функция
( )
x
f
периодична с периодом
r
, эквивалентны.
Таким образом, задача о вычислении порядка сводится к задаче о нахождения периода функции (для чего можно применить алгоритм раздела
5.5).
136
Сделаем одно замечание. Чтобы применить алгоритм из разд. 5.5., следует ограничить область определения функции
( )
x
f
некоторым конечным интервалом
0 0
x
x
<
≤
. Алгоритм из раздела 5.5 предполагает, что
0
x
делится на
r
без остатка. Заметим, что это предположение несущественно, если только
0
x
выбрать достаточно большим так, чтобы на нем укладывалось большое число периодов функции
( )
x
f
Предположим, что найденное
r
- четное, тогда (1) можно переписать в виде:
(
)(
)
N
a
a
r
r
mod
0 1
1 2
/
2
/
=
+
−
Это означает, что число
(
)(
)
1 1
2
/
2
/
+
−
r
r
a
a
должно делиться на
N
без остатка.
Предположим дополнительно, что каждое из чисел
(
)
1 2
/
±
r
a
не делится на
N
без остатка. Тогда у каждого из этих чисел есть общие делители с числом
N
Находя соответствующие наибольшие общие делители числа
N
с числами
(
)
1 2
/
−
r
a
и
(
)
1 2
/
+
r
a
, мы решаем поставленную задачу.
Мы видим, что изложенный метод срабатывает не всегда. Чтобы метод сработал, нам нужно, чтобы
r
было четным и, одновременно, числа
(
)
1 2
/
±
r
a
не делились на
N
без остатка. Можно показать, что это происходит с вероятностью
5 0
≥
, если только
a
выбирается случайно.
137
Такой вероятности достаточно, чтобы путем повторения добиться гарантированно успеха.
Приведем пример. Пусть
85
=
N
,
7
=
a
Прямым вычислением получаем (по модулю 85):
7 7
1
=
,
49 7
2
=
,
3 7
3
=
,
21 7
4
=
,
62 7
5
=
,
9 7
6
=
,
63 7
7
=
,
16 7
8
=
,
27 7
9
=
,
19 7
10
=
,
48 7
11
=
,
81 7
12
=
,
57 7
13
=
,
59 7
14
=
,
73 7
15
=
,
1 7
16
=
,
7 7
17
=
и т.д.
Таким образом
16
=
r
Далее:
(
) ( )
5764800 1
7 1
8 2
/
=
−
=
−
r
a
(
) ( )
5764802 1
7 1
8 2
/
=
+
=
+
r
a
Вычислим теперь необходимые наибольшие общие делители.
НОД(5764800, 85)=5, НОД(5764802, 85)=17.
Окончательно имеем разложение 17*5=85.
В рассмотренном демонстративном примере мы нашли
r
посредством прямого расчета. В реальных задачах с большим
N
для этого может потребоваться квантовый компьютер.
Для справок приводим алгоритм Евклида нахождения наибольшего общего делителя.
Пусть
a
и
b
- натуральные числа. Без ограничения общности будем считать, что
b
a
>
Пусть
1
ρ
- остаток от деления
a
на
b
. Вместо пары
[ ]
b
a
;
рассмотрим пару
[ ]
1
;
ρ
b
и, проделав с ней тоже самое, получим
2
ρ
. Далее рассмотрим пару
[
]
2 1
;
ρ
ρ
и т.д. до тех пор, пока остаток от деления первого числа на
138
второе не станет равным нулю. Тогда возникнет пара
[ ]
0
;
n
ρ
, в которой число
n
ρ
и будет искомым наибольшим общим делителем чисел
a
и
b
. Всего требуется
(
)
a
O
n
log
итераций для достижения результата.
Пример: Найдем наибольший общий делитель чисел 315 и 168. Алгоритм
Евклида приведет нас к последовательности пар чисел: [315;168] [168;147]
[147; 21] [21;0]. Число 21 и есть наибольший общий делитель чисел 315 и 168
: НОД(315, 168)=21
Резюмируем полученный результат. Мы описали полиномиальный квантовый алгоритм разложения целого числа на множители. Примечательно, что подобный классический алгоритм неизвестен. Рассматриваемый результат имеет важное теоретическое и практическое значение.
В теоретическом плане можно констатировать, что классическая арифметика (без алгоритма Шора) конструктивно (алгоритмически) неполна.
Действительно, в арифметике хорошо известны простые конструктивные способы сложения, вычитания и умножения целых чисел. В то же время, операция разложения целого числа на множители, которая является обратной по отношению к умножению, оказывается сложной в вычислительном отношении. Получается, что в классической арифметике мы легко можем вычислить произведение двух больших простых чисел, но сталкиваемся с практически неразрешимой проблемой при попытках решения обратной задачи. Алгоритм Шора делает арифметику алгоритмически полной, поскольку теперь мы можем говорить и о факторизации чисел как о конструктивно решаемой задаче.
Отмеченная алгоритмическая неполнота классической арифметики лежит в основе современных криптографических методов защиты информации, которые нашли широкое применение в банковской сфере, Интернете и др.
Речь, в частности, идет о так называемом коде RSA, который, как раз основан