Файл: Ю. И. Богданов Физико статистические основы.pdf

139
на сложности задачи разложения большого целого числа на множители. Как следует из представленных выше результатов, создание квантовых компьютеров сделает классические криптографические системы беззащитными. Таким образом, встает вопрос о разработке новых (квантовых) способов защиты информации. Этому вопросу посвящен следующий раздел.
5.7. Квантовая криптография
Одним из практически важных направлений квантовой информатики является квантовая криптография. Задача криптографии состоит в разработке таких методов передачи информации между двумя сторонами (Алисой и
Бобом), чтобы любые попытки с третьей стороны (Ева) перехватить и рассекретить сообщение были обречены на провал.
Остановимся на передаче сообщений с помощью так называемого секретного ключа. Секретный ключ – это последовательность случайных цифр, известных только Алисе и Бобу, например такая (нижеследующий пример взят из [71]):
K={12793 41169 42357 … }
Допустим, что Алиса хочет послать Бобу сообщение, представляющее собой, например, следующую последовательность цифр.
P={73997 68279 65867 …}
В сообщении P, например, каждой букве ставится в соответствие некоторое десятичное число. Если послать в эфир непосредственно сообщение P, то оно может быть легко перехвачено и расшифровано. Для

140
того, чтобы этого не произошло, сообщение P вначале шифруется, а только потом передается в эфир.
При шифровании к каждой цифре из сообщения P прибавляется цифра ключа K, если результат больше 10, то берется последняя цифра, в результате получаем криптограмму С:
C={85680 09338 07114 …}
Боб, получив криптограмму C и, зная секретный ключ K, легко расшифрует ее, преобразовав ее в сообщение P.
Ева, которая не знает ключа K, никогда не сможет расшифровать криптограмму, если только секретный ключ K абсолютно случайный и используется только один раз (факт абсолютной секретности таких сообщений доказал Шеннон в 1949 г.)
Приведенные выше последовательности цифр соответствуют реальному письму, которое направлял Че Гевара из Боливии Ф. Кастро на Кубу в 1967 г.
[71]
Трудность описанной схемы состоит в передаче ключа (длинной последовательности цифр) от Алисы к Бобу: если они не встречаются непосредственно, то при передаче через эфир ключ может перехватить Ева.
Чтобы избежать отмеченной трудности, хорошо было бы иметь канал, секретность которого гарантируется самой Природой. Именно такой канал предоставляет квантовая информатика.
Покажем. каким образом последовательность отдельных кубитов может быть использована для передачи секретных ключей по несекретным каналам.
Рассмотрим следующую ситуацию. Алиса и Боб связаны между собой посредством обычной двухсторонней открытой линии связи и односторонним

141
(от Алисы к Бобу) квантовым каналом. Оба эти канала доступны наблюдениям со стороны Евы, которая способна перехватывать сообщения.
Рассмотрим очень простой и широко используемый протокол передачи секретного ключа BB84 (название протокола отражает фамилии его авторов –
Беннет (Bennett) и Брассар (Brassard), а также год, когда он был предложен-
1984).
Опишем передачу секретного ключа от Алисы к Бобу в рамках протокола
BB84. Алиса посылает последовательность кубитов Бобу, кодируя их следующим образом. Для каждого посылаемого фотона Алиса случайным образом использует один из следующих базисов (второй базис повернут относительно первого на o
45
):
{0 -
→
; 1-
↑
} или {0-
; 1-
}
Боб не знает о том, какой из двух базисов выбирает Алиса для каждого фотона. Он измеряет состояние получаемых фотонов также посредством случайно выбранного базиса.
После того, как передача по квантовому каналу заканчивается, Боб сообщает по открытому каналу информацию о последовательности своих базисов, а Алиса сообщает ему, в каких случаях он выбирал правильный (то есть совпадающий с ее) базис. В своей последовательности цифр Боб оставляет только те, которые соответствуют согласованному с Алисой базису.
Именно эту последовательность они могут использовать как ключ.
Случайность в выборе базисов, которой придерживаются наши герои, служит цели обеспечения случайности ключа.
В среднем Алиса и Боб будут иметь согласованность базисов в 50% случаев.
Предположим теперь, что Ева измеряет состояние фотонов, переданных
Алисой, и пересылает Бобу новые фотоны, соответствующие измеренной ею

142
поляризации. В этом процессе она будет использовать неверный базис в 50% случаев и пересылать фотоны в этом же базисе Бобу. Это приведет к тому, что
Боб, измеряя в правильном базисе, будет иметь ошибку с вероятностью 25%.
Таким образом, подслушивание приводит к большому количеству ошибок
(25%), что легко смогут обнаружить Алиса и Боб, обмениваясь достаточно длинной последовательностью.
Заметим, что вмешательство Евы может сделать связь между Алисой и
Бобом невозможной. Однако, если Алиса и Боб будут действовать правильно, то никакое вмешательство Евы не сможет разрушить секретность их связи.
Задача 5.15
Придумайте схему, основанную, например, на БЧХ- кодах, которая могла бы обеспечивать (сколь угодно) высокую секретность протоколу BB84.
Современная оптико – волоконная связь позволяет, в принципе, передавать квантовые сообщения на расстояние до 100 км и далее.
Принципиальное ограничение связано с невозможностью усиления сигнала
(из теоремы о невозможности клонирования следует, что попытки усиления сигнала неизбежно приведут к его разрушению).
С целью преодоления указанного ограничения предложены возможные различные технологические решения, в том числе связанные с разработкой квантовых криптографических протоколов на когерентных оптических состояниях. Когерентные оптические состояния могут нести в себе большое число фотонов. Это, с одной стороны, способствует увеличению дальности передачи секретных сообщений, а с другой стороны, создает дополнительные проблемы с защитой информации. Рассмотрение этих вопросов выходит за рамки нашего изложения.

143
5.8. Алгоритм Гровера
Алгоритм Гровера направлен на поиск записи в неструктурированной базе данных. Он обеспечивает поиск решения за
( )
N
O
шагов в базе из
N
элементов. Заметим, что классический алгоритм способен решит задачу только за
( )
N
O
шагов.
Рассмотрим квантовую постановку задачи. Пусть имеется
N
состояний.
1
,...,
1
,
0
−
N
Допустим, что задача имеет
M
решений (
N
M
≤
≤
1
).
1
=
M
- частный случай в рассматриваемой постановке.
Рассмотрим функцию такую, что
( )
1
=
x
f
, если
x
- решение и
( )
0
=
x
f
, если
x
не есть решение. Унитарный оператор
f
U
, обеспечивающий рассматриваемую функцию, называется оракулом и обозначается буквой
O
Действие оракула поясняется схемой
Рис. 5.9 Схема действия оракула
Таким образом, оракул выполняет следующее преобразование
( )
x
f
q
x
q
x
⊕
→
Оракул способен распознать решение и пометить его:
1 0
x
x
→
, если
x
- решение
0 0
x
x
→
, если
x
не есть решение

144
Пусть состояния
x
, где
1
,...,
1
,
0
−
=
N
x
мы поочередно подаем на вход оракула и ждем, когда кубит оракула перевернётся и тем самым будет получено решение. Очевидно, что таким образом будет реализован небыстрый алгоритм поиска и он будет обеспечивать решение за
( )
N
O
шагов.
Наша задача состоит в том, чтобы за счёт квантового параллелизма (т.е. за счет подачи на вход некоторой суперпозиции состояний) предложить быстрый алгоритм, обеспечивающий поиск за
( )
N
O
шагов.
Последовательность осуществления алгоритма следующая.
Пусть
(
)
1 0
2 1
−
=
q
. Такое состояние уже использовалось нами в реализации алгоритма Дойча. Это состояние играет роль «катализатора», который сам не меняется, но обеспечивает изменение состояния других кубитов. Действительно, действие оракула в рассматриваемом случае сводится к преобразованию:
( )
( )
q
x
q
x
x
f
1
−
→
Договоримся о сокращенной записи (опуская неизменный кубит-
«катализатор»)
( )
( )
x
x
x
f
1
−
→
Таким образом, мы видим, что оракул помечает решение посредством фазы
π
Введем теперь некоторый унитарный оператор (так называемый оператор условного сдвига фазы)
I
U
−
=
0 0
2
, где
I
- единичный (тождественный) оператор.

145
Покажем, что введенный выше оператор действительно является унитарным. Используем условие полноты системы базисных функций
I
x
x
N
x
=
∑
−
=
1 0
Тогда для оператора условного сдвига фазы получаем
∑
≠
−
=
−
=
0 0
0 0
0 2
x
x
x
I
U
Отсюда видим, что
0 0
=
U
и
x
x
U
−
=
, если
0
≠
x
Рассмотрим теперь состояние, играющее центральную роль в квантовых алгоритмах и неоднократно использовавшееся нами ранее. Это состояние представляет собой равномерную суперпозицию всех базисных состояний:
∑
−
=
=
ψ
1 0
1
N
x
x
Т
Далее значком
ψ
будем обозначать это конкретное состояние.
Задача 5.16
Докажите справедливость тождества
(
)
I
H
I
H
n
n
−
ψ
ψ
=
−
⊗
⊗
2 0
0 2
Теперь мы готовы ввести оператор Гровера. Он определяется последовательностью двух операторов: действием сперва оракулом
O
, а затем оператором
I
−
ψ
ψ
2
, в результате получаем оператор Гровера:
(
)
O
I
G
−
ψ
ψ
= 2

146
Решение задачи поиска сводится к последовательному действию оператором Гровера на исходное состояние
ψ
. Опишем подробности алгоритма.
Заметим вначале, что состояние
ψ
можно представить в виде суперпозиции двух состояний, одно из которых есть сумма всех решений, а другое- сумма всех «не- решений»:
β
+
α
−
=
ψ
N
M
N
M
N
Здесь
β
- нормированная сумма всех решений
∑
=
β
'
'
1
x
x
M
Аналогично,
α
- нормированная сумма всех «не- решений»
∑
−
=
α
''
''
1
x
x
M
N
В представленных формулах мы помечаем решения одним штрихом, а
«не- решения»- двумя штрихами.
Действие оператора Гровера лучше всего изображать графически на двумерном графике, оси которого образованы состояниями
α
и
β
Действие оператора оракула
O
сводится к отражению относительно оси
α
Аналогично, действие оператора
I
−
ψ
ψ
2
сводится к отражению относительно состояния
ψ
. Первая итерация Гровера изображена на рисунке

147
Рис.5.10 Графическая иллюстрация алгоритма Гровера
Задача 5.17
Пусть
N
M
N
−
=
⎟
⎠
⎞
⎜
⎝
⎛ θ
2
cos
,
N
M
=
⎟
⎠
⎞
⎜
⎝
⎛ θ
2
sin
. Покажите, что результат действия
k
итераций Гровера может быть представлен в виде:
( )
(
)
(
)
β
⎟
⎠
⎞
⎜
⎝
⎛
θ
+
+
α
⎟
⎠
⎞
⎜
⎝
⎛
θ
+
=
ψ
2 1
2
sin
2 1
2
cos
k
k
G
k
Из полученного результата мы видим, итерации Гровера приводят к постепенному вращению вектора состояния в сторону вертикальной оси
β
(т.е. в сторону решений задачи). Итерационный процесс следует закончить, когда будет приближенно выполняться равенство:
(
)
2 2
1 2
π
=
θ
+
k
Отсюда следует, что необходимое число итераций задается приближенно условием:
M
N
k
4
π
≈

148
В результате измерения, проведенного после
k
итераций Гровера с высокой (хотя и не равной единице) вероятностью будет найдено одно из решений задачи поиска.
Алгоритм Гровера имеет важное значение в области квантового моделирования
5.9 Введение в квантовое исправление ошибок
Повышение надежности передачи и хранения информации достигается посредством избыточности. Например, в трехбитовом коде каждый логический бит информации задаётся тремя физическими битами
111 1
000 0
→
→
В рассматриваемом случае реализуется мажоритарная система исправления ошибок (принятие решения на основе большинства голосов). В случае трехбитового кодирования сообщение (логический бит) передаётся правильно, если число ошибок в физических битах равно нулю или единице.
Соответственно, сообщение может быть передано неверно, если ошибок две или три.
Рассмотрим в качестве простого введения двоичный симметричный канал. Пусть
p
- вероятность ошибки в одном физическом бите: вероятность превращения нуля в единицу (
1 0
→
), либо наоборот, единицы в нуль (
0 1
→
).
Будем считать обе эти вероятности одинаковыми (отсюда название- симметричный канал). Вероятность безошибочной передачи информации
(
0 0
→
, либо
1 1
→
), соответственно, равна
p
−
1
Задача 5.18
Покажите, что классический трёхбитовый код характеризуется следующей вероятностью ошибки передачи одного логического бита информации

149 3
2 2
3
p
p
P
e
−
=
Покажите далее, что избыточность увеличивает надежность передачи информации (т.е.
p
P
e
<
, если
5 0
<
p
).
Перейдем теперь к рассмотрению квантового бита (кубита). Рассмотрим вначале так называемый канал с классической ошибкой (название
«классическая ошибка» довольно условно).
Такая ошибка описывается действием оператора
X
(NOT), когда состояние 0 меняется на 1, а состояние 1 меняется на 0:
ψ
X
, т.е.
0 1
1 0
→
→
Таким образом, действие ошибки описывается следующим преобразованием состояния кубита
0 1
1 0
b
a
b
a
+
→
+
Трёхбитовый код в квантовом исполнении (резервирование одного логического кукубита тремя физическими кубитами) выглядит следующим образом:
111 000 1
0
b
a
b
a
+
→
+
, т.е.
000 0
0
≡
→
L
111 1
1
≡
→
L
Реализация рассматриваемого способа кодирования посредством квантовой схемы представлена на рисунке.