Чтобы извлечь из квантового регистра информацию, надо провести
измерение. При этом измерить можно любой набор квантовых битов.
Кроме того, поскольку квантовые состояния образуют евклидово про-
странство, измерения можно проводить в различных базисах. Однако
проведение измерения приводит к переходу системы в базисное со-
стояние, соответствующее результатам измерения.
Квантовый компьютер может осуществлять преобразования над
квантовым регистром. Квантовым преобразованием будем называть
отображение унитарного пространства, образуемого квантовой систе-
мой, в себя. С квантовыми системами можно производить только ли-
нейные унитарные преобразования, причем любое линейное унитар-
ное преобразование допустимо. В силу линейности, квантовые пре-
образования полностью определяются их действием на базисные век-
торы.
Некоторые важнейшие элементарные преобразования (квантовые
вентили) приведены в табл. 2
Криптоанализ симметричных шифров.
Один из известных кван-
товых алгоритмов — алгоритм Гровера. Обычно его описывают как
алгоритм поиска в неупорядоченном массиве. Однако небольшая мо-
дификация превращает его в алгоритм для восстановления ключа сим-
метричного алгоритма шифрования по тексту сообщения и шифротек-
сту. При использовании классического компьютера для этого требуется
полный перебор, имеющий сложность
O
(2
m
)
, где
m
— длина ключа.
Для квантового компьютера эту сложность можно сильно уменьшить.
Будем рассматривать функцию
y
=
c
(
k, x
)
. Эта функция ши-
фрует сообщение
x
на ключе
k
;
x
и
y
— целые числа в диапазоне
x, y
2
[0
,
2
n
−
1]
, где
n
— длина блока. Пусть нам известна пара
сообщение–шифротекст: x
1
, y
1
. Рассмотрим функцию
f
(
k
)
, которая
принимает значение единицы, если
c
(
k, x
1
) =
y
1
, и нуля в противном
случае. Требуется найти значение аргумента, при котором функция
равна единице.
Рассмотрим следующий квантовый алгоритм:
приводим квантовый регистр в состояние
1
√
2
m
2
m
−
1
P
t
=0
|
t
i
;
вычисляем функцию
f
от этого регистра
1
√
2
m
2
m
−
1
P
x
=0
|
t
i |
f
(
t
)
i
.
Повторяем
π
4
√
2
m
раз процедуру увеличения амплитуды всех
t
i
,
для которых
f
(
t
i
)
= 1 (эта процедура описывается далее).
Измеряем состояние регистра. Результат будет равным искомому
ключу с вероятностью около
2
−
n
. Если результат все-таки оказался
неверным (это легко проверить), весь алгоритм следует выполнить
заново.
Процедура увеличения амплитуды состоит из двух этапов: 1) из-
менение амплитуды с
a
j
на
−
a
j
для всех
t
i
, таких, что
f
(
t
i
)
= 1.
Эта операция представляет собой преобразование
Z
над последним
ISSN 1812-3368. Вестник МГТУ им. Н.Э. Баумана. Сер. “Естественные науки”. 2007. № 2
115
