Это преобразование можно представить в виде матрицы
D
=
⎛
⎜⎜⎜⎜⎜⎜⎜⎝
2
N
−
1
2
N
. . .
2
N
2
N
2
N
−
1
· · ·
2
N
· · ·
· · ·
· · ·
· · ·
2
N
2
N
· · ·
2
N
−
1
⎞
⎟⎟⎟⎟⎟⎟⎟⎠
.
Как показал Гровер в работе [2], это преобразование может быть
эффективно реализовано на квантовом компьютере, а сложность всего
алгоритма оценивается как
O
√
2
n
.
Квантовое преобразование Фурье
определяется так:
U
QFT
(
|
x
) =
1
√
2
m
2
m
−
1
c
=0
e
2
πicx
2
m
|
c .
Как показано в работе [10], такое преобразование можно постро-
ить, используя только
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
⎞
⎟⎟⎟⎟⎟⎟⎠
.
Согласно данным работы Шора [10], квантовое преобразование
Фурье можно задать следующим образом:
U
QFT
=
=
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
.
Квантовый алгоритм нахожденияпериода функции.
Пусть есть
периодическая функция
f
(
x
)
. Область определения и область зна-
чений этой функции — целые числа, причем
0
x
2
n
−
1
и
0
f
(
x
) 2
m
−
1
. Для того чтобы найти период этой функции, нужен
квантовый регистр, состоящий из
n
+
m
квантовых битов. Приведем
его в состояние
1
√
2
n
2
n
−
1
x
=0
|
x,
0
.
42 ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2006. № 2
