Теперь вычислим от него функцию
f
так, чтобы у нас получилось
состояние
1
√
2
n
2
n
−
1
x
=0
|
x, f
(
x
)
.
Измерим последние
m
квантовых битов (т.е. квантовые биты, от-
носящиеся к
f
(
x
))
. Квантовый регистр перейдет в состояние
x
:
f
(
x
)=
u
|
x, u .
Проведем квантовое преобразование Фурье, в результате чего мы
получим состояние
j
c
j
j
2
n
r
,
где
c
j
равны нулю при всех
j
, не кратных
2
n
/
r
. Если период
r
не делит
2
n
, преобразование выполняется не точно, причем большая амплитуда
сосредоточена вблизи целых значений, кратных [
2
n
/r
].
Наконец, измерив полученное состояние, в результате получим чи-
сло
v
.
Если период равняется степени двойки, то
v
=
j
2
n
r
. А посколь-
ку в большинстве случаев
j
и
r
— взаимно просты, то сокращение
дроби
v
2
n
даст дробь, знаменатель которой и есть период. В общем
случае либо придется прогнать весь алгоритм несколько раз, пока мы
не получим правильное значение периода (ему соответствует макси-
мальная амплитуда, а следовательно, максимальная вероятность), либо
воспользоваться известным из теории чисел разложением в бесконеч-
ную дробь (подробности см. работу [10]).
Алгоритм разложениячисла на простые множители (алгоритм
Шора).
Поставим задачу следующим образом: у нас есть натуральное
число
N
, имеющее ровно два простых делителя. Требуется найти эти
делители.
Наилучший известный классический алгоритм решения этой зада-
чи (так называемый алгоритм решета числового поля) имеет сверх-
полиномиальную сложность. На этом факте, в частности, основана
стойкость криптосистемы RSA.
Однако существует квантовый алгоритм, решающий эту задачу за
полиномиальное время. Действительно, предположим, что для неко-
торого числа
a
его порядок по модулю
N
(т.е. минимальное число
r
,
такое, что
a
r
= 1(mod
N
))
четен. Тогда выражение
a
r
= 1(mod
N
)
можно записать в виде
a
r
2
−
1
a
r
2
+ 1 = 0(mod
N
)
.
ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2006. № 2 43
