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

Размещено на http://www.allbest.ru

Размещено на http://www.allbest.ru

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

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

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

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

.

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

9. Quantum tic-tac-toe.

Размещено на Allbest.ru