копирующее преобразование, то должно выполняться (учитывая (1))
P
(
|
z
|
0 ) =
|
z
|
z
=
1
2
(
|
x
|
x
+
|
x
|
y
+
|
y
|
x
+
|
y
|
y
)
.
С другой стороны, в силу линейности,
P
(
|
z
|
0 ) =
1
√
2
(
P
(
|
x
|
0 ) +
P
(
|
y
|
0 )) =
1
√
2
(
|
x
|
x
+
|
y
|
y
)
.
Мы пришли к противоречию.
Таким образом, копирование неизвестных квантовых состояний в
общем случае невозможно.
Алгоритм поиска Гровера.
Поставим задачу следующим обра-
зом. Пусть имеется некоторая функция
f
(
x
)
, где
x
— целое число в
диапазоне
0
x
2
n
−
1
. При некоторых значениях аргумента эта
функция принимает значение 1, а при всех остальных — 0. Требуется
найти хотя бы одно значение аргумента, при котором функция равна 1.
На классическом компьютере эта задача в общем случае может
быть решена только методом полного перебора. Для этого требуется
в среднем
2
n
−
1
раз вычислить функцию
f
(
x
)
и произвести столько же
сравнений.
На квантовом компьютере возможен следующий алгоритм:
1. Приводим квантовый регистр в состояние
1
√
2
n
2
n
−
1
x
=0
|
x
;
2. Вычисляем функцию
f
от этого регистра
1
√
2
n
2
n
−
1
x
=0
|
x
|
f
(
x
)
;
3. Повторяем
π
4
√
2
n
раз процедуру увеличения амплитуды всех
x
i
,
для которых
f
(
x
i
)
= 1. (Эта процедура описывается ниже);
4. Измеряем состояние регистра. Результат будет верным с вероят-
ностью около
2
−
n
. Если результат все-таки оказался неверным, весь
алгоритм следует повторить.
Процедура увеличения амплитуды состоит из двух этапов.
1. Изменение амплитуды с
a
j
на
−
a
j
для всех
x
i
, таких, что
f
(
x
i
) = 1
. Эта операция представляет собой преобразование
Z
над
последним квантовым битом регистра.
2. Инверсия относительно среднего. Это преобразование можно
записать следующим образом:
i
|
x
i
→
i
(2
a
ср
−
a
i
)
|
x
i
,
где
a
ср
— средняя амплитуда.
ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2006. № 2 41
