Процедурная генерация с помощью квантовых вычислений

Сегодня разберем выступление Джеймса Вуттона из IBM Quantum на конференции FDG 2020. Речь пойдет о квантовых вычислениях — потенциально многообещающей технологии, для которой, однако, на современном этапе развития находится мало применения. И все же одно из них нашлось в процедурной генерации.

Поговорим подробнее, как реализовать ее на кубитах, а также приведем коды программы.




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



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

Создание компьютеров, способных выполнять квантовые вычисления, — задача сама по себе непростая и находящаяся в процессе решения уже долгие годы. Одним из важных параметров описания квантового устройства является количество кубитов. По факту, это те же биты, но реализованные квантовым способом — а потому имеющие больше состояний, нежели привычные 0 и 1. В разрезе квантовой физики мы можем записать значения битов при помощи пары ортогональных векторов: |0⟩ и |1⟩. В случае кубитов к описанию состояний добавятся еще комплексные амплитуды c₀ и c₁, удовлетворяющие условию: |c₀|² + |c₁|² = 1, благодаря чему и достигается большее число состояний кубита c₀|0⟩ + c₁|1⟩.



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

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

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



Есть и более скромные по мощностях устройства, состоящие из порядка 20 кубитов. А квантовые программы, задействующие до 15 кубитов, IBM даже выложили в бесплатный общий доступ. Кроме того, они создали программное обеспечение для эмуляции, которое поможет при проектировании и тестировании квантовых программ. И хотя эмуляция более 50 кубитов представляет собой сложную вычислительную задачу, даже ваш ноутбук без проблем справится с эмуляцией примерно 20 кубитов.

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



Итак, что же все это значит для процедурной генерации? Зависит от того, на какую из трех эпох вы ориентируетесь: сегодняшнюю, готовую предоставить лишь десятки кубитов; на ближайшее будущее, когда устройства будут иметь сотни кубитов; или на далекое будущее, когда нам будут доступны более тысячи кубитов.

Если говорить о сегодняшнем дне, квантовое программное обеспечение, ориентированное на мощность лишь 20 кубитов, еще не может делать ничего уникального. Сам факт, что мы можем запустить его на эмуляторе, означает, что вам даже не понадобится квантовое оборудование. Но могут ли квантовые программы все-таки сделать что-нибудь полезное? Можем ли мы написать квантовую программу на 20 кубитов, которая будет давать результаты, полезные для реального конечного пользователя?

Если мы сможем достичь действительно полезных результатов с помощью 20 кубитов, со временем и увеличением вычислительной мощности этот эффект будет только умножаться. Средняя эра станет эпохой исследования все более сложных способов квантовых вычислений, действенных в том числе для процедурной генерации. Мы перейдем к созданию инструментов, о которых, вероятно, и не подумали бы, если бы не мыслили категориями квантов.

Но не будем забегать вперед. Первый шаг к эре расширения полезности — доказать, что даже квантовое программное обеспечение, рассчитанное на 20 кубитов, может оказаться полезным. Этим мы и займемся.



А теперь пришло время уточнить некоторые детали.

Процедурная генерация означает, что нам нужно что-то сгенерировать. Но что?

Генерация ландшафта — самое очевидное, так что давайте начнем с нее.

Шум Перлина — повсеместный инструмент для процедурной генерации ландшафта. Но существует и еще один, гораздо менее сложный метод его создания — с помощью набора случайных точек с последующим их размытием. Реализация чего-то подобного показалась нам более достижимой целью для первого шага, поэтому ее мы и возьмем за основу.

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



Будем работать с черно-белыми изображениями, где яркость пикселя может иметь значение от 0 до 1. Точно так же их можно принять за карты высот. Как только мы научимся кодировать эти карты высот в виде схем, мы сможем ими управлять. Используемая кодировка направлена ​​на то, чтобы сжать как можно больше точек в как можно меньшее количество кубитов. Этот способ не оставляет большой гибкости для обеспечения удобного и гибкого управления. При этом практически любое изменение схемы вызовет интерференционные эффекты.

В основном мы используем операции, которые можно рассматривать как частичные формы логического элемента НЕ. Применительно к обычным битам НЕ меняет значение с 0 на 1 и наоборот. С помощью квантовых вентилей мы можем параметризовать этот элемент для выполнения операции, которая может выполнять половину НЕ, или четверть, или любую другую дробную часть, которую можно представить набором из 2ⁿ амплитуд n кубитов.

Приведенная ниже функция преобразует исходное изображение в квантовую схему:

def height2circuit(height):
# определяем размер сетки
L = max(max(height))+1
# создаем сетку
grid = make_grid(L)
# определяем необходимое количество кубитов
n = 2*int(np.ceil(np.log(L)/np.log(2)))
# создаем нулевое состояние
state = [0]*(2**n)
# заполняем его необходимыми амплитудами
H = 0
for bit string in grid:
(x,y) = grid[bit string]
if (x,y) in height:
h = height[x,y]
state[ int(bit string,2) ] = np.sqrt( h )
H += h
# нормировка состояния
for j,amp in enumerate(state):
state[ j ] = amp/np.sqrt(H)
# инициализация квантовой схемы
qc = QuantumCircuit(n,n)
qc.initialize(state,range(n))
# в случае Qiskit используем
# qc.initialize( state, qc.qregs[0])
return qc

Затем нам необходимо произвести обратный процесс — преобразовать квантовую схему в изображение:

def circuit2height(qc):
# извлекаем количество кубитов из схемы
n = qc.num_qubits
grid = make_grid(int(2**(n/2)))
# извлекаем из нее начальное состояние
ket = qi.Statevector(qc.data[0][0].params)
qc.data.pop(0)
# преобразуем это состояние при помощи остальной части схемы
ket = ket.evolve(qc)
# получаем конечные вероятности
p = ket.probabilities_dict()
# определяем максимальное значение вероятности для изменения масштаба
max_h = max( p.values() )
# сопоставляем высоту с этими значениями вероятности
height = {}
for bit string in p:
if bit string in grid:
height[grid[bit string]] = p[bit string]/max_h
return height

Если мы применим эту операцию ко всем кубитам, сможем увидеть, как изменяется карта высот по мере увеличения дроби. Получится что-то вроде эффекта размытия. Затем возникнут интерференционные эффекты, создающие паттерн, который невозможно получить путем простого размытия.

В примере выше в (a) мы начинаем с пары, казалось бы, произвольных точек. Постепенно они претерпевают размытие, после чего на них накладываются интерференционные эффекты. Это приводит к появлению паттерна — в нашем случае по типу шахматной доски на (f). Этот конкретный результат имеет явную связь с двумя пикселями, с которых мы начинали. Если взять за отправную точку другие данные, результат тоже окажется совсем другой.

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



После генерации этих карт задействуем их для квантового аналога высокочастотного шума Перлина.

Итак, теперь мы создаем основной профиль — например, острова — каким-то другим способом — как в © в нашем примере. Затем нам понадобится начальный набор пикселей, как в (a). Квантово его размываем, чтобы сгенерировать паттерн, подобный (b). После этого наносим его на основной профиль для создания окончательного ландшафта.

Здесь вы можете увидеть 2D-пример, а также 3D-рендеринг, который использовался в обучающей игре IBM QiskitBlocks. Такие детали, как информация о типе травы и размещении деревьев в 3D-рендеринге, также были разработаны с использованием квантовых операций.




Поскольку RGB-изображения, как правило, представляют собой три совмещенные вместе карты высот, мы также можем управлять этими изображениями. Таким образом просто создавать какие-то странные картинки с использованием наложения. Сложнее, но эффективнее — кодирование пары изображений и создание между ними эффекта телепортации.

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



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


и уровне Марио:


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

Также художница Либби Хини использовала некоторые из этих идей в качестве отправной точки для своих работ.


Квантовая природа вычислений подчеркивается в обоих этих случаях: для пользователя важно, чтобы результаты исходили из квантовой области пространства алгоритмов, а не были просто блестящей линейной алгеброй.



Описанный здесь метод больше подходит для эмуляции, нежели реального квантового оборудования, но скоро это изменится. На самом деле, одно из самых больших квантовых устройств в IBM тоже уже использовали для процедурной генерации, правда, совершенно другим способом.

А пока вы можете сами опробовать эффект квантового размытия. Он написан на Python, но есть плагин и для Unity. Быть может, они окажутся для вас полезными.

Ссылка на полный текст статьи: здесь.