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

Попередня  |  Повний текст  |  Наступна

 

УДК 004.4:519.684

Розв’язування задач комбінаторної оптимізації на квантових комп’ютерах

В.Ю. Корольов 1 ORCID ID favicon Big,   О.М. Ходзінський 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. С. 1624. 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)

Попередня  |  Повний текст  |  Наступна

 

 

 

© Вебсайт та оформлення. 2019-2022,

Інститут кібернетики імені В.М. Глушкова НАН України,

Національна академія наук України.