«Пикассо физики»: Как играть в квантовые крестики-нолики

[Журнал ЖЖ]

«Если вы думаете, что понимаете квантовую механику, значит, вы её не понимаете». - Ричард Фейнман.
Изображение: игра в крестики-нолики на шахматной выставке, Marcin Wichary, 2008 год
rotozeev рассказывает как превратить классическую игру в квантовую, используя обобщённые схемы квантования, на примере простой игры в крестики-нолики. Не секрет, что в последнее время ведутся активные попытки построить квантовый компьютер. Вкратце, зачем это нужно. Доказано, что квантовый компьютер (когда будет построен) сможет за короткое время решать задачи, которые нынешние компьютеры (классические) могут решить лишь за тысячи лет непрерывной работы. Одной (и самой главной, из-за чего на исследования выделяются огромные деньги) из этих задач является нахождение простых множителей заданного числа (взлом шифрования с открытым ключом RSA). И, соответственно, создание новых, квантовых систем шифрования и защищенных линий связи. Возможен также и квантовый интернет, особенностью которого будут «запутанные» квантовые состояния, связывающие удаленные компьютеры между собой. А там, где новые компьютеры, там и новые игры. В этом посте я попытаюсь рассказать о двух «квантовых» вариантах простой игры в крестики-нолики. Играть в эти квантовые крестики нолики можно без всякого квантового компьютера. Квантовые крестики-нолики в данном случае важны как методическое указание, как простейший пример того, что такое квантовая суперпозиция и редукция волновой функции при измерении. Итак, для начала определимся с игровым полем - это обычные 3×3 девять клеток. Для дальнейшего удобства пронумеруем их вот так:


Изображение: rotozeev, 2015 год

Первый вариант игры, который мы рассмотрим, был предложен в работе [Allan Goff, Am. J. Phys. 74, 962 (2006)]. Суть заключается в том, что каждый игрок может имеющийся у него крестик (или нолик) не просто поставить в свободную клетку, а распределить его в двух разных клетках. Рассмотрим пример игры. Пусть крестиками играет Боб, а ноликами играет Алиса. Боб ходит первым и ставит свой первый крестик в клетки 5 и 8:


Изображение: rotozeev, 2015 год

Здесь важно к крестикам/ноликам приписывать индексы - номера ходов. Алиса делает следующий второй ход ноликом в клетки 5 и 9:


Изображение: rotozeev, 2015 год

Заметьте, в клетке 5 уже стоял крестик, но так как это был не «полноценный» крестик, а только половинка (оригинальное название таких «недокрестиков/недоноликов» - spooky marks, т.е. призрачные ходы), то в эту же клетку можно ходить еще и еще другими половинками ноликов и крестиков. Теоретически, в клетке может быть 8 таких вот полу-ноликов и полу-крестиков (при этом другие половинки покрывают все остальные клетки). Следующий третий ход Боба, он ставит крестик в клетки 5 и 6:


Изображение: rotozeev, 2015 год

В клетке 5 уже скопилось три половинки (призрака)! Но вот четвертый ход и ходит Алиса ноликом на клетки 6 и 8:


Изображение: rotozeev, 2015 год

Это был не простой ход, Алиса замкнула «петлю связности» (cyclic entanglement) ходов {1,3,4}, вот она выделена желтым цветом и зелеными линиями:


Изображение: rotozeev, 2015 год

• Клетки 5 и 8 связаны посредством хода X1
• Клетки 8 и 6 связаны посредством хода O4
• Клетки 6 и 5 связаны посредством хода X3

То есть, у нас получился некий аналог «запутанного» состояния, который можно распутать с помощью «измерения». Так как петлю закрыла Алиса, то выбирать способ (а он не один!) распутывания должен Боб. На этом этапе «распутывания» в клетках наконец то исчезают «половинки» (призраки) крестиков и ноликов и появляются «обычные», «классические» крестики или нолики. Рассмотрим два разных возможных результата распутывания, которые может выбрать Боб. Для примера, он начинает распутывать петлю с клетки № 5 (центральная). Итак, в этой клетке Боб должен выбрать какой из сделанных ходов в эту клетку превратится из «призрака» в реальный ход и займет всю клетку. А выбор у Боба состоит из двух вариантов: X1 и X3, так как эти ходы входят в петлю, а вот призрак O2, который тоже находится в клетке 5 Боб выбрать не может, т.к. этот ход не содержится в петле. Вариант 1. Боб выбирает X3 в клетке № 5.


Изображение: rotozeev, 2015 год

Тогда, в клетке № 5 уже не должно быть X1, а значит ход X1 тем самым тоже определился с клеткой и в клетке № 8 должен быть X1. А раз так, то в клетке № 8 не должно быть других призраков, не должно быть O4. Значит раз клетка № 8 для O4 запрещена, то этому нолику остается клетка № 6. А в клетке № 6 был еще призрак хода X3, но мы же с него начали распутывание и с самого начала решили, что ход X3 будет в клетке № 5. От петли есть «отросток» в виде хода O2. Он тоже затрагивается в процессе распутывания. Так как в клетке № 5 для O2 быть запрещено (мы уже сначала решили, что в этой клетке находится X3), то для O2 остается единственный вариант - клетка № 9. И вот результат распутывания - классические, обычные ходы, когда в каждой клетке полноценный крестик или нолик:


Изображение: rotozeev, 2015 год

Вариант 2. Боб выбирает X1 в клетке № 5.


Изображение: rotozeev, 2015 год

И в итоге результат распутывания выглядит так:


Изображение: rotozeev, 2015 год

В примере выше петля состояла из трех разных клеток и для ее построения нужно было сделать три хода. Но самая простая петля может быть сделана одним игроком за один ход. Например, если бы Боб сделал свой первый ход так, что поместил две половинки X1 + X1 в одну пустую клетку, то это бы просто означало петлю в одной клетке с одним единственным вариантом распутывания:


Изображение: rotozeev, 2015 год

Это обычный «классический» ход. Можно за два хода организовать петлю в двух клетках. Петля может быть и довольно большой, содержащей больше трех клеток. Однако, всегда есть только два варианта ее распутывания. Также стоит отметить, что одним ходом не получится замкнуть сразу две разных петли. Подсказка: сама процедура «распутывания» (квантовое измерение, коллапс) не должна оставлять после себя половинок «призраков». Например, в приведенном выше примере, такая ситуация недопустима и означает, что распутывание не произведено до конца:


Изображение: rotozeev, 2015 год

Тут в девятой клетке находится один призрак (половинка) от хода O2 (другую половинку в клетке № 5 стерли во время распутывания). Так быть не должно, и вместо одинокой половинки мы должны нарисовать полноценный ход. Итак, петлю закрыла Алиса, выбирает один из двух вариантов распутывания петли Боб, и если после распутывания игра не закончена, то Боб делает свой очередной ход. Игра заканчивается так же, как и в обычных крестиках-ноликах, когда на поле имеется три полноценных (не половинки!) крестика или нолика в один ряд. Правда, есть одно отличие. Если игра заканчивается в результате распутывания нетривиальной петли (две и более клеток), то возможна ситуация, когда на поле одновременно появятся три крестика в ряд и три нолика в ряд. В этом случае правила предписывают посчитать индексы (номера ходов) у трех крестиков и трех ноликов. Тот, у кого сумма индексов меньше, тот и выиграл (получает 1 очко), а другой игрок, который как бы тоже выиграл, но у которого сумма индексов больше, получает 0.5 очка. Проиллюстрируем это на примере. Итак, пусть после распутывания Бобом петли, которую закрыла Алиса, поле выглядит так:


Изображение: rotozeev, 2015 год

После распутывания, Боб делает свой ход крестиками в клетки 4 и 7 (хотя мог бы поставить оба крестика в клетку 4, сделав тем самым «классический» ход и выиграть):


Изображение: rotozeev, 2015 год

Алисе надоело играть и она делает свой ход ноликом в те же самые клетки 4 и 7, тем самым закрывая петлю из двух клеток:


Изображение: rotozeev, 2015 год

Боб тоже решил не растягивать игру и из двух вариантов распутывания выбрал тот, где крестик в клетке 4, а нолик в клетке 7 (в принципе, мог выбрать и вариант, когда нолик был бы в клетке 4, а крестик в клетке 7, что продолжило бы игру):


Изображение: rotozeev, 2015 год

Мы видим, что в результате распутывания петли в клетках 4 и 7 получилось так, что и крестики и нолики какбы выиграли. Но теперь нужно сосчитать индексы:

• у крестиков: 5 + 1 + 3 = 9
• у ноликов: 6 + 4 + 2 = 12

Следовательно, по очкам крестики выигрывают. Боб, играющий крестиками, получает 1 очко, Алиса, играющая ноликами, получает 1/2 очка. * * * В рассмотренном выше варианте игры есть ограничения и проблемы:

• ходить можно только либо классически одним настоящим крестиком/ноликом в пустую клетку, либо разделив ход на две равноценные половинки. Пойти одновременно крестиком(ноликом) сразу в 9 клеток нельзя
• даже в случае хода двумя кретиками/ноликами нельзя распределить «вес» между ними, скажем этот крестик я сюда ставлю с «весом» 0.6, а этот - с «весом» 0.8.
• проблема «ничьей» и искусственного правила подсчета индексов