2020, випуск 2, c. 5-13
Одержано 03.04.2020; Виправлено 17.04.2020; Прийнято 30.06.2020
Надруковано 24.07.2020; Вперше Online 27.07.2020
https://doi.org/10.34229/2707-451X.20.2.1
Попередня | Повний текст | Наступна
Розв’язування задач комбінаторної оптимізації на квантових комп’ютерах
В.Ю.
Корольов 1 
,
О.М. Ходзінський 1 *
1 Інститут кібернетики імені В.М. Глушкова НАН України, Київ
* Листування: Ця електронна адреса захищена від спам-ботів. Вам потрібно увімкнути JavaScript, щоб побачити її.
Вступ. Квантові комп'ютери дозволяють отримати в кілька разів швидше рішення ряду NP-складних проблем комбінаторної оптимізації у порівнянні з обчислювальними кластерами. Тенденція подвоєння кількості кубітів квантових комп'ютерів щороку дає підстави припускати існування аналога закономірності Мура для квантових комп'ютерів, а це означає, що в найближчому майбутньому на них також можна буде отримати істотне прискорення вирішення багатьох прикладних задач великої розмірності.
Мета роботи. Полягає в огляді алгоритмів квантової комп'ютерної математики для задач комбінаторної оптимізації та в аналізі впливу особливостей зв'язків між кубітами на виконання квантової обробки даних.
Результат. У роботі запропоновано принципи класифікації алгоритмів розв'язання задач з точки зору квантової комп'ютерної математики. Показано, що кількість і сила зв'язків між кубітами впливає на розмірність задач, розв'язуваних алгоритмами квантової комп'ютерної математики. Запропоновано розглядати два підходи до обчислення задач комбінаторної оптимізації на квантових комп'ютерах: універсальний, за допомогою квантових вентилів, і спеціалізований, на базі параметризації фізичних процесів. Наведено приклад побудови напівсуматора для двох кубітів квантового процесора фірми IBM і приклад вирішення задачі пошуку максимальної незалежної множини для квантових комп'ютерів фірм IBM і D-wave.
Висновок. Сьогодні квантові комп'ютери доступні онлайн через хмарні сервіси для наукових досліджень і комерційного використання. На момент написання статті квантові процесори мають недостатню кількість кубітів для заміни напівпровідникових комп'ютерів в універсальних обчисленнях. Пошук рішення задачі комбінаторної оптимізації виконується за допомогою досягнення мінімуму енергії системи пов'язаних кубітів, на яку відображається завдання, а дані є початковими умовами. Розглянуто підходи до вирішення задач комбінаторної оптимізації на квантових комп'ютерах та наведено результати розв'язання задачі пошуку максимальної незалежної множини на квантових комп'ютерах фірм IBM та D-wave.
Ключові слова: квантовий комп'ютер, квантова комп'ютерна математика, кубіт, максимальна незалежна множина для графа.
Цитувати так: Корольов В.Ю., Ходзінський О.М. Розв’язування задач комбінаторної оптимізації на квантових комп’ютерах. Cybernetics and Computer Technologies. 2020. 2. С. 5–13. https://doi.org/10.34229/2707-451X.20.2.1
Список літератури
1. Moran C.C. Mastering Quantum Computing with IBM QX. Birmingham: Packt, 2019.
2. Vos J. Quantum Computing for Developers: A Java-based introduction. New York: Manning, 2020.
3. Johnston E.R., Harrigan N., Gimeno-Segovia M. Programming Quantum Computers. Essential Algorithms and Code Samples. Sebastopol: O’Reilly, 2019.
4. Корольов В.Ю. Маршрутизація ланки крилатих ракет багаторазового використання. Управляющие системы и машины. 2019. 2. С. 16 – 24. https://doi.org/10.15407/usim.2019.02.016
5. Гуляницький Л.Ф., Корольов В.Ю., Огурцов М.І., Ходзінський О.М. Проблема маршрутизації груп БПЛА в задачах пошуку і моніторингу. Компьютерная математика. 2018. 2. С. 38 – 47. http://dspace.nbuv.gov.ua/handle/123456789/161884
6. Корольов В.Ю., Ходзінський О.М. Тополого-комбінаторна модель побудови мереж для транспортних засобів. Компьютерна математика. 2018. 1. С. 61 – 67. http://dspace.nbuv.gov.ua/handle/123456789/161850
7. Корольов В.Ю., Огурцов М.І. Транспортно-комунікаційна задача для груп безпілотних апаратів. Математичні машини і системи. 2017. 1. С. 82 – 89. http://dspace.nbuv.gov.ua/handle/123456789/117508
8. Корольов В.Ю., Поліновський В.В., Огурцов М.І. Моделювання мереж зв'язку рухомих дистанційно керованих систем на базі HLA. Вісник Хмельницького національного університету. 2017. 1 (245). С. 160 – 165. http://nbuv.gov.ua/j-pdf/Vchnu_tekh_2017_1_33.pdf
9. Asfaw A. Learn Quantum Computation using Qiskit. New York: IBM. 2019. URL: https://qiskit.org/textbook/ch-applications/qaoa.html (дата звернення: 15.03.2020).
10. Maximum Cut. URL: https://github.com/dwave-examples/maximum-cut (дата звернення: 15.03.2020).
11. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. Москва: Мир, 1982. 416 c.
12. Talbi E.-G. Metaheuristics: from design to implementation. New Jersey: Wiley & Sons, 2009. https://doi.org/10.1002/9780470496916
13. Гуляницький Л.Ф., Мулеса О.Ю. Прикладні методи комбінаторної оптимізації. Київ: Видавничо-поліграфічний центр "Київський університет", 2016. 142 c.
ISSN 2707-451X (Online)
ISSN 2707-4501 (Print)
Попередня | Повний текст | Наступна