Введение 3
Глава 1. Обзорный раздел по предметной области 4
1.1. Квантовые подходы 4
1.1.1 Hop-based подход 4
1.1.2 Edge-based 6
1.2. TTopt 8
1.3. Постановка задачи 9
Глава 2. Проведенные эксперименты 10
2.1. Малый граф 11
2.2. Граф 3 х 3 12
2.3. Граф 5 х 5 14
2.4. Граф 7 х 7 16
Глава 3. Выводы 18
Список литературы 19
Проблема нахождения кратчайшего пути является хорошо изученной областью в теории графов. Самый простой для описания вариант этой задачи включает наличие одного источника и одного пункта назначения: необходимо найти путь с минимальной стоимостью между заданными начальной и конечной вершинами в графе с учетом стоимости переходов по ребрам. Эта задача является центральной для широкого круга практических приложений, таких как навигация, планирование маршрутов для автономных транспортных средств и анализ социальных сетей.
Квантовый отжиг — это метод оптимизации системы из N кубитов с использованием зависящего от времени гамильтониана путем постепенного уменьшения квантовых флуктуаций [1]. Гамильтониан представляет собой функцию энергии, которая начинается в полностью запутанном, случайном состоянии и постепенно превращается в гамильтониан, связанный с задачей оптимизации. Медленное развитие квантового энергетического состояния позволяет системе кубитов преодолевать энергетические барьеры и находить глобальный минимум многомерной энергетической функции. Процесс отжига начинается, когда все кубиты находятся в состоянии суперпозиции. Когда процесс завершен, кубиты находятся в основном состоянии искомого гамильтониана задачи и, следовательно, представляют собой глобальный оптимум [2]-[4]. Затем считывается и возвращается вектор решения значений кубитов. Функция энергии обычно выражается в виде модели Изинга или связанной с ней квадратичной неограниченной бинарной оптимизации (QUBO).
В данной работе исследуется QUBO постановка задачи и сравниваются методы квантового отжига и алгоритма Tensor train optimization (TTopt) [5] на данных постановках. TTopt представляет собой метод, используемый для эффективного представления многомерных тензоров (многомерных массивов) со значительно уменьшенным количеством параметров. Этот метод особенно полезен в областях машинного обучения, сжатия данных и численного моделирования, где тензоры с большим количеством измерений и элементов трудно хранить, обрабатывать и вычислять.
По результатам работы, реализованы 2 QUBO подхода для решения задачи поиска кратчайшего пути на графе, проведены сравнения работы данных подходов с помощью квантового отжига и алгоритма Ttopt.
Если говорить об алгоритмах, TTopt алгоритм хорошо работает на малых графах (для edge-based и hop-based подходов), в том числе, TTopt для hop-based на графе 3 х 3 отработал лучше, чем квантовый отжиг на hop-based подходе. На больших графах, TTopt-у необходимо большое число обращений к функции для качественного поиска экстремума, из-за чего метод квантового отжига для больших графов является более предпочтительным.
Если сравнивать подходы, edge-based тоже хорошо подходит только для решения задачи на малых графах. На графе 5 х 5 все методы решения для edge-based подхода ни разу не нашли кратчайшего пути. На больших графах наилучший результат показывает hop-based подход. Единственный недостаток подхода - он использует сильно больше переменных (кубическая зависимость от размера графа), чем edge-based подход (квадратическая зависимость). Более того, hop-based подход с симуляцией квантового отжига не только не работает хуже с увеличением размера графа, он почти с одной и той же вероятностью возвращает кратчайший путь.
Идея инициализировать квантовый отжиг результатом TTopt к особым результатам не привела, квантовый отжиг с инициализацией работает не лучше, чем квантовый отжиг с рандомной инициализацией переменных. Вероятнее всего, это связано с имплеминтацией симуляции квантового отжига на обычном компьютере.
Отдельное внимание стоит обратить на метрику Equal vertices в сводных табличках. Во всех случаях, hop based подход на квантовом отжиге всегда выбирает те вершины, которые лежат на кратчайшем пути. Условие правильности пути в постановке hop-based сильно упирается в допустимость, однако, в исследуемых графах восстановить кратчайший путь можно однозначно по выданным вершинам. Таким образом, для графов, с которыми мы работаем, можно всегда восстановить кратчайший путь, используя hop-based подход.
