ISSN 1991-3087
Рейтинг@Mail.ru Rambler's Top100
Яндекс.Метрика

НА ГЛАВНУЮ

Теория игр в квантовой криптографии


Мазикова Анастасия Андреевна,

соискатель Санкт-Петербургского государственного инженерно-экономического университета.

 

Со времён появления квантовой криптографии учёными было проведено большое количество исследований направленных на изучение способов передачи сообщения между двумя участниками и разработку способов предотвращения перехвата и чтения сообщения, передаваемого по квантовому каналу. Одним из направлений в исследованиях является изучение различных стратегий передачи сообщения получателю. Для этого используются основы теории игр с элементами квантовой физики [1]. Действия отправителя и злоумышленника рассматриваются как ассиметричная квантовая игра двух игроков. Для того чтобы понять влияние квантовой механики на выбор стратегий в подобной игре, а так же изучить результаты игр, была проанализирована простейшая ассиметричная игра для двух игроков – крестики-нолики [2]. Чтобы превратить классическую игру в квантовую, используются обобщённые схемы квантования [3, 6, 7].  - квантовый ход игрока. Квантовые ходы могут быть любой нормированной комбинацией классических ходов, то есть за один ход возможно занять любое количество клеток. Чтобы определить условия выигрыша вводится переменная , обозначающая вес, который имеет игрок на прямой линии, проходящей через клетки  где  обозначает амплитуду, соответствующую клетке  на квантовом шаге . Игрок  выигрывает после хода , если для некоторого направления  [8, 9].

Вначале было проведено большое количество случайных квантовых и классических игр, чтобы понять, как играть в квантовые крестики-нолики и чем классическая и квантовая игры в действительности отличаются друг от друга. Результаты представлены в таблице 1.

 

Таблица 1.

Результаты 10000 классических и 10000 квантовых случайных игр. Показано количество выигрышей в процентах Игрока 1 и Игрока 2 после k ходов для каждой из игр. Игрок 2 имеет только 4 хода, поэтому k=5 – процент игр, заканчивающихся вничью [8].

Ход k

Классическая игра (%)

Квантовая игра (%)

Игрок 1

Игрок 2

Игрок 1

Игрок 2

1

0

0

0

0

2

0

0

0

0

3

9.4

9.0

0

0

4

26.5

19.5

21.8

14.2

5/ ничья

22.4

13.2

38.5

25.5

 

Из таблицы 1 видно, что в обоих случаях Игрок 1 выигрывает 60% всех игр. Игрок 2 имеет невыгодные условия в случайных квантовых играх, так как выигрывает всего 14.2% проведённых игр, в отличие от случайных классических игр – 28.5%. Кроме того, очевидно, что и Игрок 1, и Игрок 2 выигрывают около 9% игр после третьего хода в классическом варианте игры. В случайных квантовых играх один из игроков не выигрывает после третьего хода [5]. Также было исследовано влияние открывающего и заключительного ходов на результаты квантовых игр (см. таблицу 2). Открывающий ход – первый ход, сделанный в игре. Он важен, так как влияет на построение дальнейшей стратегии. Для сравнения использовались три вида открывающих ходов: классический, квантовый и случайный. При классическом открывающем ходе Игрок 1 всегда делает классический ход  в качестве своего первого хода, в то время как при квантовом открывающем ходе его ход описывается формулой .

 

Таблица 2.

Результаты десяти тысяч случайных квантовых игр для каждого из трёх открывающих ходов. В таблице представлены проценты выигрышей игроков после k ходов. Так как Игрок 2 имеет всего четыре хода, то ход k=5 обозначает, что игра закончилась вничью.

Ход k

Открывающие ходы

Классические (%)

Квантовые (%)

Случайные (%)

Игрок 1

Игрок 2

Игрок 1

Игрок 2

Игрок 1

Игрок 2

1

0

0

0

0

0

0

2

0

0

0

0

0

0

3

0

0

0

0

0

0

4

7.6

28.9

23.4

16.4

21.8

14.2

5

27.0

36.5

35.0

25.2

38.5

25.5

 

Судя по результатам, приведенным в табл. 2, если Игрок 1 и Игрок 2 не выбирают конкретной стратегии, то квантовый открывающий ход даёт Игроку 1 значительное преимущество.

Для исследования заключительных ходов были выбраны игры, в которых Игрок 1 находится на грани победы. Чтобы дойти до заключительного хода, были сыграны случайные квантовые игры. Очевидно, что ходы, приводящие к победе, должны быть тесно связаны с ходами, которые увеличивают вес Игрока 1 вдоль одной или нескольких из восьми прямых. Чтобы найти максимизирующий ход , который увеличивает вес Игрока 1 вдоль направления pqr, при условии, что он ортонормален для всех предыдущих шагов, используется метод множителей Лагранжа. Таким образом, учитывая явные ограничения  необходимо решить следующую систему уравнений:

 

 

где множитель Лагранжа для обеспечения нормализации,  матрица  множителей Лагранжа для обеспечения ортогонализации,  матрица , составленная из пяти предыдущих ходов. Узнав восемь максимизирующих ходов Игрока 1и максимальный вес для каждого из них, Игрок 2 может сделать ход с самым большим весом из всех в качестве блокирующего хода. И если в классической версии игры он заблокирует только одно направление, то в квантовых крестиках-ноликах он может перекрыть все выигрышные направления Игрока 1. Блокирующий ход Игрока 2 может быть случайным или взвешенным. Случайный блокирующий ход – любой ход с весом большим, чем вес Игрока 1. Взвешенный ход – ход состоящий из трёх лучших ходов  Игрока 1, которые дают максимальный вес . В ходе исследования было замечено, что взвешенный ход статистически более эффективен, чем случайный (см. рис. 1).

 

Рис. 1. Эффективность случайных блокирующих ходов (слева) и взвешенных блокирующих ходов (справа).

 

После исследования открывающих и заключительных ходов, стало понятно, что основным элементом для игры в квантовые крестики-нолики является максимизирующий ход. Так же стали очевидны различия между стратегиями Игрока 1 и Игрока 2. Таким образом, чтобы выяснить, как результаты игр зависят от стратегий, выбираемых Игроком 1 и Игроком 2, были исследованы квантовые игры с определённой стратегией. Всего выделили четыре типа возможных стратегий, условно называемых Победа/Блокировка (ПБ), Победа-блокировка/Блокировка (ПбБ), Победа/Победа-блокировка (ППб), Победа-блокировка/Победа-блокировка (ПбПб). При выборе стратегии ПБ Игрок 1 стремится выиграть, используя только наступательные ходы, в то время как Игрок 2 использует только блокирующие ходы. При стратегии ПбБ Игрок 1 использует наступательные ходы, но если он не выиграл на этом ходу и заметит, что Игрок 2 выиграет после следующего хода, то будут использованы блокирующие ходы. Игрок 2 использует только блокирующие ходы. При выборе стратегии ППб Игрок 1 использует только наступательные движения, а Игрок 2 – наступательные ходы или блокирующие, если он не выиграл на этом ходу и Игрок 1 выиграет после следующего хода. Стратегия ПбПб предполагает, что оба игрока начинают с наступательных ходов, но переключаются на блокирующие в любой момент, когда на грани победы оказывается соперник. Под наступающим ходом подразумевается максимизирующий ход с максимальным весом из всех, которые уже определены.
Блокирующий ход в данном случае – взвешенный ход.

В результате были сделаны следующие выводы: если оба Игрока при любой стратегии используют классические открывающие ходы, то выше шанс, что выиграет Игрок 2 или игра закончится вничью. При квантовых и случайных открывающих ходах процент выигрыша Игрока 1 значительно выше. Однако если Игрок 2 использует стратегии ПБ и ПбБ, шанс, что игра закончится вничью выше и процент выигрышей Игрока 1 снижается. Если Игрок 2 использует стратегии ППб и ПбПб, процент выигрышей Игрока 1 становится ещё выше.

Квантовые крестики-нолики рассматривались в данной статье в связи с тем, что необходимо было выработать стратегию для отправителя сообщения по квантовому каналу так, чтобы процент срыва передачи сообщения злоумышленником был низок. Полученные результаты для Игроков 1 и 2 можно применить к отправителю сообщения и злоумышленнику соответственно, получив, таким образом, искомую стратегию.

 

Литература

 

1.                  J. Eisert, M. Wilkens, and M. Lewenstein, Quantum games and quantum strategies, Physical Review Letters.

2.                  F. Guinea andM. A.Mart´ın-Delgado, Quantum Chinos game: winning strategies through quantum fluctuations, Journal of Physics A: Mathematical and General 36(13), L197–L204 (2003).

3.                  C. F. Lee and N. F. Johnson, Efficiency and formalism of quantum games, Physical Review A 67(2), 022311 (2003).

4.                  A. Nawaz and A. H. Toor, Generalized quantization scheme for two-person non-zero sum games, Journal of Physics A: Mathematical and General 37(47), 11457–11464 (2004).

5.                  S. K. ¨Ozdemir, J. Shimamura, and N. Imoto, A necessary and sufficient condition to play games in quantum mechanical settings, New Journal of Physics 9, 43 (2007).

6.                  A. Goff, D. Lehmann, and J. Siegel, Quantum tic-tac-toe, spooky-coins & magic-envelopes, as metaphors for relativistic quantum physics, Proceedings of the 38th AIAA/ASME/SAE/ASEE Joint Propulsion Conference and Exhibit (Indianapolis, USA, 7-10 July 2002), 2002.

7.                  A. Goff, Quantum tic-tac-toe: A teaching metaphor for superposition in quantum mechanics, American Journal of Physics 74(16), 962–973 (2006).

8.                  J. N. Leaw, Quantum Tic Tac Toe, final year project thesis, School of Physical and Mathematical Sciences, Nanyang Technological University. Available at URL: http://hdl.handle.net/10356/40799.

9.                  Quantum tic-tac-toe. URL: http://en.wikipedia.org/wiki/Quantum_tic_tac_toe (дата обращения 24.04.2012).

 

Поступила в редакцию 29.05.2012 г.

2006-2019 © Журнал научных публикаций аспирантов и докторантов.
Все материалы, размещенные на данном сайте, охраняются авторским правом. При использовании материалов сайта активная ссылка на первоисточник обязательна.