Розв’язування задачі пошуку найбільшої незалежної множини вершин графу на квантово-класичних хмарних сервісах
Мат. XXVI Міжн. наук. конф. "Сучасні проблеми прикладної математики та комп'ютерних наук APAMCS-2021" (Львів, 27–28 вересня 2021 р.). Львів, Львівський національний університет ім.І.Франка, 120-124.
Анотація:
Квантові комп'ютери дозволяють отримати в кілька разів швидше рішення ряду NP-складних проблем комбінаторної оптимізації в порівнянні з обчислювальними кластерами. Створення алгоритмів для розв’язування задач комбінаторної оптимізації для гібридних квантово-напівпровідникових обчислювальних комплексів дозволяє прискорити отримання результатів та отримати наближені розв’язки. Наведено приклад розв’язування задачі пошуку найбільшої незалежної множини на квантових комп’ютерах IBM і D-wave, які доступні через хмарні сервіси.
Ключові слова: квантовий комп'ютер, квантова комп'ютерна математика, кубіт, максимальна незалежна множина для графа.