Вирішення транспортної задачі за допомогою квантового комп’ютера

В роботі був написаний та проаналізований алгоритм для квантового комп’ютера, що виконує задачу комівояжера, тобто шукає найбільш оптимальний маршрут обходу графу із поверненням в початкову точку. Були проведені тести програми із різними варіантами вирішення задачі і порівняний час виконання алгоритму квантовим комп’ютером і класичним. Із результатів тестів видно, що навіть із усіма недоліками теперішніх квантових комп’ютерів, вони вже можуть значно краще виконувати такого роду задачі. Так, для пошуку шляху в графі з 50 вершин, квантовому комп’ютеру знадобилося всього 7.5 секунд, в той час як класичному – 829 секунд. Крім того, навіть із стандартними параметрами методу оптимізації, складність алгоритму для квантового комп’ютера складає 𝑂(𝑛 log (𝑛)), а в класичного з використанням генетичного алгоритму - 𝑂(𝑛^2).
Завдяки тому, що алгоритм реалізовано з використанням мови програмування Python, його можна легко змінювати для виключення маршрутів, зміни початкової і кінцевої точки маршруту. Крім того, можливо передавати результат виконання алгоритму зовнішнім програмам, для їх подальшого використання, наприклад, для візуалізації маршруту на карті.

Турченко Є. О. Вирішення транспортної задачі за допомогою квантового комп’ютера : дипломна робота бакалавра : 123 Комп’ютерна інженерія / Турченко Євгеній Олександрович. - Київ, 2022. – 25 с.