Численное решение оптимизационных задач методом квантового отжига

1.

МИНИСТЕРСТВО НАУКИ И ВЫСШЕГО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ
федеральное государственное бюджетное образовательное учреждение высшего образования
«Уфимский государственный авиационный технический университет» (ФГБОУ ВО «УГАТУ»)
У ГАТ У
Курсовая работа
Численное решение оптимизационных задач
методом квантового отжига
Автор: Асфандияров Айдар Зилюрович, гр. ПМ-355
Научный руководитель: Касаткин Алексей Александрович, доцент
21 декабря 2022 г.
кафедра ВВТиС

2.

У ГАТ У
Уфимский государственный
авиационный технический
университет
Цель и задачи
Численное решение
оптимизационных задач
методом квантового отжига
Цель исследования – численно решить задачу коммивояжера методом
квантового отжига.
Задачи исследования
Сформулировать задачу численного решения проблемы оптимизации (задачи
коммивояжера) методом квантового отжига.
Построить решение методом квантового отжига с использованием квантового
приближенного алгоритма оптимизации (QAOA)..
Решить задачу на языке программирования Q# средствами Microsoft Quantum
Development Kit (QDK).
2

3.

У ГАТ У
Уфимский государственный
авиационный технический
университет
Постановка задачи
Численное решение
оптимизационных задач
методом квантового отжига
Задача коммивояжера - одна из самых известных задач комбинаторной
оптимизации, заключающаяся в поиске самого выгодного маршрута,
проходящего через указанные города хотя бы по одному разу с последующим
возвратом в исходный город.
Схема всех возможных путей:
3

4.

У ГАТ У
Уфимский государственный
авиационный технический
университет
Постановка задачи
Численное решение
оптимизационных задач
методом квантового отжига
Однако у этой задачи также есть ограничения. Путешествие коммивояжёра
должно начинаться и заканчиваться в точке A, и он должен посетить каждое
место ровно один раз.
Подходящие маршруты:
4

5.

У ГАТ У
Уфимский государственный
авиационный технический
университет
Результаты
Численное решение
оптимизационных задач
методом квантового отжига
Общая стоимость поездки составляет:
Далее, с учетом ограничений по маршруту и добавления штрафы к функции
затрат за нарушение ограничений мы получаем функцию общей стоимости:
5

6.

Результаты
У ГАТ У
Уфимский государственный
авиационный технический
университет
1
Численное решение
оптимизационных задач
методом квантового отжига
• Затем, выбирая