Теперь проведем квантовое преобразование Фурье (алгоритм кото-
рого приведен ниже), в результате чего мы получим состояние
X
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
даст дробь, знаменатель которой и есть период. В общем слу-
чае либо придется прогнать весь алгоритм несколько раз, пока мы
не получим правильное значение периода (ему соответствует макси-
мальная амплитуда, а следовательно, максимальная вероятность), либо
воспользоваться известным из теории чисел разложением в бесконеч-
ную дробь [6].
Квантовое преобразование Фурье определяется так:
U
QFT
(
|
x
i
) =
1
√
2
m
2
m
−
1
X
c
=0
e
2
πicx
2
m
|
c
i
.
Как показал П. Шор в работе [6], такое преобразование можно по-
строить с использованием только
m
(
m
+1)
/
2
квантовых вентилей двух
типов. Один из них представляет собой преобразование Адамара, при-
мененное к
j
-му квантовому биту (обозначим его
H
j
)
. Другой вентиль
реализует двухбитное преобразование вида
S
j,k
=
1 0 0 0
0 1 0 0
0 0 1 0
0 0 0
e
i
π
2
k
−
j
.
Согласно работе [6], квантовое преобразование Фурье можно за-
дать следующим образом:
H
0
S
0
,
1
. . . S
0
,m
−
1
H
1
. . . H
m
−
3
S
m
−
3
,m
−
2
S
m
−
3
,m
−
1
H
m
−
2
S
m
−
2
,m
−
1
H
m
−
1
=
=
m
−
1
Y
k
=0
H
k
m
−
1
Y
t
=
k
+1
S
k,t
.
(1)
После этого преобразования следует изменить порядок битов на
противоположный. Это можно сделать либо соответствующей кванто-
вой схемой, либо, если сразу после квантового преобразования Фурье
происходит измерение, классическим способом.
118
ISSN 1812-3368. Вестник МГТУ им. Н.Э. Баумана. Сер. “Естественные науки”. 2007. № 2
