В серии статей я собираюсь обсудить QUBO, как сформулировать задачу QUBO и запустить ее на D’Wave QPU. Эта статья состоит из 5 небольших сегментов, мы начнем с того, что такое Целевая функция, Модель Изинга, это сходство между QUBO,сопоставление QUBO с ГРАФИКА и, наконец, АРХИТЕКТУРА QPU D'Wave.
ЦЕЛЬНАЯ ФУНКЦИЯ
Рассмотрим систему, это могут быть взаимодействующие частицы, магнитные ионы, городской трафик или курсы акций, и для этой конкретной системы вы можете написать гамильтониан или функцию энергии, обозначающую некоторую величину, которую вы хотите оптимизировать, предпочтительно минимизировать, в случае частиц/ магниты - это Энергия, и в остальной части статьи мы будем использовать функцию Энергии и Целевую функцию взаимозаменяемо.
Здесь мы видим, что существует два типа МИНИМУМА, Локальный и Глобальный, в некоторых случаях локальный минимум также приемлем, но если нам требуется оптимальное решение, нам нужно найти глобальный Минимум.
МОДЕЛЬ ИЗИНГА
Модель Изинга является базовой математической моделью ферромагнетизма в статистической физике. Модель имеет дискретную переменную (+1 и -1), представляющую магнитные дипольные моменты спинов атомов, и эти спины могут быть расположены в графе (предпочтительно в виде решетки), допуская локальные взаимодействия (только соседние).
Функция Гамильтона/Энергии таких систем может быть записана как
где Jпредставляет собой взаимодействие между i-м и j-м спинами, также известное как квадратичный член, соответствующий силе связи, и линейный член, h соответствует смещениям кубитов.
QUBO - Квадратичная неограниченная двоичная оптимизация
Теперь, когда мы знаем о модели Изинга, мы можем продолжить обсуждение задач QUBO, которые представляют собой не что иное, как оптимизацию квадратичного полинома с двоичными переменными.
Функция оптимизации задач QUBO определяется следующим образом, где Q — это верхняя треугольная матрица NXN с действительными весами, а x — вектор двоичных переменных, диагональный член Q представляет собой линейный член, тогда как недиагональный член представляет Квадратичный член.
Как мы видим из уравнения 1 и уравнения 2, модель Изинга и QUBO представляют собой похожие уравнения разных полей.
ГРАФИК
Двигаясь вперед, давайте посмотрим, как мы можем представить целевую функцию в виде графика, что поможет нам в будущем сопоставить цель с QPU.
Рассмотрим , f(x) = Ax+By +Cxy , как целевую функцию, она может быть представлено на графике, как показано на рисунке 3, узлы с линейным коэффициентом и соединением с квадратичным коэффициентом, показывая смещение кубита и силу связи соответственно.
Дальнейшие примеры будут включать более сложные графы.
АРХИТЕКТУРА D’WAVE
В этом разделе мы рассмотрим, как отобразить график проблем, как показано на рис. 3, с топологией QPU.
D'Wave QPU представляет собой решетку взаимосвязанных кубитов, которые не полностью связаны, хотя некоторые из них связаны друг с другом через Coupler и известны как CHIMERA (показаны на рис. 4). ).
Как показано, граф Chimera состоит из элементарной ячейки,каждая элементарная ячейка состоит из четырех горизонтальных кубитов, которые соединены с четырьмя вертикальными кубитами через ответвители. Элементарные ячейки мозаичны, как показано на рис.4., по вертикали и горизонтали с соседними элементарными ячейками, создавая решетку кубитов.
В D’Wave QPU набор кубитов и ответвителей, доступных для вычислений, называется рабочим графом.
Кубиты единичной ячейки могут быть связаны друг с другом двумя способами, как показано ниже.
В каждом соединении есть два набора из четырех кубитов, каждый из которых связан с четырьмя другими в другом наборе, но не связан в своем собственном наборе из четырех.
Теперь, что касается проблемы, узлы и ребра на графе отображаются на кубиты и соединители в Chimera. Процесс сопоставления логических кубитов с физическими кубитами известен как второстепенное встраивание.
ССЫЛКИ
https://docs.dwavesys.com/docs/latest/c_gs_1.html (также для Рис.4 и Рис.5)
https://frnsys.com/ai_notes/foundations/optimization.html (для рисунка 1)
