Физики придумали квантовое го

Китайские физики придумали и экспериментально реализовали квантовый вариант игры в го. Они показали, что множество возможных позиций в такой игре значительно больше, чем у классического аналога. Благодаря своей сложности квантовое го может стать одним из перспективных кандидатов для демонстрации квантового превосходства. Препринт статьи доступен на arXiv.org.

В 2016 году программа AlphaGo, которая использует алгоритмы машинного обучения, обыграла Ли Седоля, а затем и Кэ Цзе — сильнейших игроков в го. На тот момент казалось, что обработать такое огромное количество информации и обыграть профессионала просто невозможно. Подробнее об этом читайте в материале «Го: речь поражения».

Ученые под руководством Сань Минь Цзинь (Xian-Min Jin) из Научно-технического университета Китая решили увеличить и без того большое число возможных позиций игры с помощью квантовой механики. Такая задача становится интересной не только с точки зрения возможностей машинного обучения, но и с точки зрения квантовых технологий. Она может быть слишком сложной для классического компьютера, что дает возможность квантовым вычислениям продемонстрировать свое превосходство.

В классическое го играют камнями двух цветов — черного и белого. Два игрока по очереди выставляют камни на пересечения клеток игрового поля размеров 19 на 19 (возможны варианты 9 на 9, 13 на 13). Цель игры — отгородить своими камнями территорию больше, чем у соперника. Дополнительные очки можно получить, если на захваченной территории есть камни противника.

Авторы предложили новую версию игры с использованием квантовой суперпозиции и измерений. В квантовом го появляется возможность ставить камень сразу в два разных места доски. Игрок выбирает две позиции, в которых может находиться камень и указывает их. С этого момента и до того, как этот камень будет измерен, он находится в состоянии суперпозиции. То есть с определенными вероятностями он может быть обнаружен в одном или другом положении. Даже игрок, который поставил этот квантовый камень не знает, где именно окажется камень после измерения. Измерение в квантовой механике заставляет квантовый объект выбрать одно из двух состояний (сколлапсировать). В данном случае после измерения квантовый камень превращается в классический и занимает только одно место на доске. Измерение камня происходит тогда, когда на соседнем пересечении появляется другой камень.

Такая вариация игры добавляет в нее элемент случайности и значительно увеличивает множество возможных расстановок. Помимо этого усложнить игру можно и другим способом: скрывать часть информации об игре от участников. В квантовом го можно предоставить игроку самому выбирать вероятности положения камня и не говорить о них сопернику. В таком случае игра может быть сведена к классическому го, если каждый раз одному из положений присваивать единичную вероятность.

В исследовании своей задумки авторы пошли дальше и создали экспериментальный прототип игры. Для этого они использовали источник пар запутанных фотонов, которые измерялись с помощью однофотонных детекторов. Каждое измерение в игре производилось над реальной квантовой системой, коллапс которой говорил о том, куда необходимо поставить измеряемый камень. Такая оптическая схема позволяет реализовывать и вариант игры со скрытой информацией.

Простейшая модель игры на доске 3 на 3 показала, что множество позиций для квантового го значительно больше, чем для классического. Кроме того, квантовое го оказалось сложнее не только своего классического аналога, но и других недетерминированных игр и игр со скрытой информацией. Благодаря своей сложности новая игра может стать полем для экспериментов в области классических и квантовых алгоритмов.

Пока программы на основе алгоритмов машинного обучения показывают успехи в соревновании с людьми. Так, ученые из DeepMind разработали алгоритм AlphaStar для игры StarCraft 2, который обыграл 99,8 процента игроков в одном турнире. Покер тоже не остался без внимания: искусственный интеллект Libratus выиграл у профессиональных игроков в 20-дневном покерном турнире. А новая версия AlphaGo Zero самостоятельно научилась играть в шахматы и сёги.

Оксана Борзенкова