DOOM на квантовом компьютере
Калькуляторы были, банкоматы были, даже были тесты на беременность — на чем только ни запускали DOOM. Если учесть, что пробовали сделать компьютер из крабов (логические вентили), то, по некоторым подсчетам, для запуска DOOM хватило бы чуть больше 16 млрд крабов. Так вот аспирант, которому, видимо, не надо дописывать диплом, решил проверить, а можно ли было бы запустить хотя бы первый уровень легендарной игры в виде квантовой схемы. Свой проект он назвал Quandoom.
В чем суть?
Это, конечно, не реальная игра на квантовом компьютере, а теоретическая разработка. Автор переписал первый уровень DOOM, используя только два типа квантовых вентилей (это базовые операции в квантовых алгоритмах) — Адамара и Тоффоли. Полученная схема слишком велика для современных квантовых компьютеров (72,376 кубитов и более 80 миллионов вентилей), но ее можно эффективно симулировать на обычном ноутбуке со скоростью 10-20 кадров в секунду. Лучше, чем на тесте на беременность.
Автор выложил исходный код целиком на Гитхаб и позаботился, чтобы любой мог попробовать запустить симуляцию у себя.
Как это работает?
- Создается начальное квантовое состояние
- В него записываются входные данные от нажатий клавиш
- Применяется квантовая схема через специальный симулятор
- Измеряются 64000 кубитов, отвечающих за изображение
- Результаты преобразуются в картинку 320x200 пикселей
- Цикл повторяется, сохраняя состояние и обновляя только входы и экран
Одно из главных проблем квантовых схем по сравнению с алгоритмами на классических компьютерах — все операции должны быть обратимыми. В классическом программировании мы можем написать: "Добавь 1 к числу. Если оно становится больше 5, тогди верни его к 5”.
В квантовых схемах такая операция невозможна, потому что она необратима – если мы видим на выходе число 5, мы не можем определить, какое было исходное значение. Оно могло быть как 4 (тогда к нему добавили 1 и получили 5), так и 5 (тогда к нему добавили 1, получили 6, и из-за ограничения вернули обратно к 5). Когда разные входные значения могут давать одинаковый результат, это делает операцию необратимой.
Поэтому в Quandoom используется другой подход: "добавь 1 к числу, при достижении максимума вернись к минимальному значению". Это заметно усложняет код, но сохраняет обратимость.
Еще одна особенность – в схеме можно только переключать пиксели, но не устанавливать их значение напрямую. Из-за этого графика получается "каркасной", как рентгеновский снимок. А еще перекрывающиеся линии создают “негатив”, и объекты видны как бы “сквозь” друг друга.
Почему схему можно эффективно симулировать?
Хотя набор вентилей Адамара и Тоффоли универсальны (теоретически на нем можно реализовать любые квантовые вычисления), аспирант придумал, как сделать схему классически симулируемой.
Ключевой здесь момент – работа со случайностью. Для таких вещей как попадание выстрелов или поведение врагов нужны случайные числа. В схеме они генерируются применением вентилей Адамара к специальному регистру в начале работы. Когда такой вентиль применяется к кубиту в состоянии |0⟩, он создает суперпозицию – состояние, которое при измерении дает |0⟩ или |1⟩ с равной вероятностью 50%. Эти операции применяются к специально выделенному регистру кубитов в начале работы схемы, и при последующих измерениях этого регистра получаются случайные двоичные числа.
Важно, что этот регистр сбрасывается после каждого кадра. Поэтому гейты Адамара всегда действуют на состояние |0⟩, а не на произвольную суперпозицию. Благодаря этому в системе никогда не возникает отрицательных фаз и квантовой интерференции.
Не лень, а оптимизация
Автор честно признает, что некоторые решения в его коде и подходе продиктованы соображениями простоты реализации (читай: ленью или экономией сил и времени). Например, для рендеринга спрайтов вместо алгоритмов масштабирования он просто "запек" все возможные размеры каждого спрайта:
"К моменту необходимости реализации [алгоритма масштабирования] я уже достаточно устал от проекта (около 6 месяцев выходных, потраченных на него), поэтому было решено просто запечь все возможные масштабы каждого спрайта"
Так что вместо настоящего ray casting для определения видимости врагов используется предварительно рассчитанная таблица видимости для сетки 10x10 в каждой комнате.
Ну и зачем?!
Во-первых, это красиво. Хоть и незатейливо (снобски говоря).
Во-вторых, тут становятся понятные интересные особенности квантовых алгоритмов — в чем их отличия от классических (требование обратимости, работа с суперпозициями). А попутно — и текущие ограничения квантовых компьютеров (почему схему можно только симулировать, но не раскатать на реальном квантовом компьютере: 70 тыс кубитов на дороге не валяются, да и вообще нигде не валются пока что). Ну и заодно автор попробовал сам посмотреть и другим показать, как можно эффективно симулировать некоторые типа квантовых алгоритмов на классических компьютерах.