Received 03.04.2020; Revised 17.04.2020; Accepted 30.06.2020

Published 24.07.2020; First Online 27.07.2020

https://doi.org/10.34229/2707-451X.20.2.1

Previous  |  Full text (in Ukrainian)  |  Next

 

MSC 90C27, 68Q12

Solving Combinatorial Optimization Problems on Quantum Computers

Vyacheslav Korolyov ¹ ,   Oleksandr Khodzinskyi ^{1 *}

¹ V.M. Glushkov Institute of Cybernetics of the NAS of Ukraine, Kyiv

^* Correspondence: This email address is being protected from spambots. You need JavaScript enabled to view it.

 

Introduction. Quantum computers provide several times faster solutions to several NP-hard combinatorial optimization problems in comparison with computing clusters. The trend of doubling the number of qubits of quantum computers every year suggests the existence of an analog of Moore's law for quantum computers, which means that soon they will also be able to get a significant acceleration of solving many applied large-scale problems.

The purpose of the article is to review methods for creating algorithms of quantum computer mathematics for combinatorial optimization problems and to analyze the influence of the qubit-to-qubit coupling and connections strength on the performance of quantum data processing.

Results. The article offers approaches to the classification of algorithms for solving these problems from the perspective of quantum computer mathematics. It is shown that the number and strength of connections between qubits affect the dimensionality of problems solved by algorithms of quantum computer mathematics. It is proposed to consider two approaches to calculating combinatorial optimization problems on quantum computers: universal, using quantum gates, and specialized, based on a parameterization of physical processes. Examples of constructing a half-adder for two qubits of an IBM quantum processor and an example of solving the problem of finding the maximum independent set for the IBM and D-wave quantum computers are given.

Conclusions. Today, quantum computers are available online through cloud services for research and commercial use. At present, quantum processors do not have enough qubits to replace semiconductor computers in universal computing. The search for a solution to a combinatorial optimization problem is performed by achieving the minimum energy of the system of coupled qubits, on which the task is mapped, and the data are the initial conditions. Approaches to solving combinatorial optimization problems on quantum computers are considered and the results of solving the problem of finding the maximum independent set on the IBM and D-wave quantum computers are given.

 

Keywords: quantum computer, quantum computer mathematics, qubit, maximal independent set for a graph.

 

Cite as: Korolyov V., Khodzinskyi O. Solving Combinatorial Optimization Problems on Quantum Computers. Cybernetics and Computer Technologies. 2020. 2. P. 5–13. (in Ukrainian) https://doi.org/10.34229/2707-451X.20.2.1

 

References

           1.     Moran C.C. Mastering Quantum Computing with IBM QX. Packt: Birmingham, 2019.

           2.     Vos J. Quantum Computing for Developers: A Java-based introduction. Manning: Shelter Island, 2020.

           3.     Johnston E.R., Harrigan N., Gimeno-Segovia M. Programming Quantum Computers. Essential Algorithms and Code Samples. O'Reilly: Sebastopol, 2019.

           4.     Korolyov V.Yu. Multiple-use cruise missile group routing. Upravlyayushchye systemy i mashyny. 2019. 2. P. 16 – 24. (in Ukrainian) https://doi.org/10.15407/usim.2019.02.016

           5.     Hulyanitsky LF, Korolyov V.Yu., Ogurtsov M.I., Khodzinskiy O.M. The problem of routing UAV groups in the search and monitoring problems. Kompʹyuternaya matematyka. 2018. 2. P. 38 – 47. (in Ukrainian) http://dspace.nbuv.gov.ua/handle/123456789/161884

           6.     Korolyov V.Yu., Khodzinskiy O.M. Topological-combinatorial model of network construction for transportation facilities. Kompʹyuternaya matematyka. 2018. 1. P. 61 – 67. (in Ukrainian) http://dspace.nbuv.gov.ua/handle/123456789/161850

           7.     Korolyov V.Yu., Ogurtsov M.I. Transport-communication problem for groups of unmanned aerial vehicles. Matematychni mashyny i systemy. 2017. 1. P. 82 – 89. (in Ukrainian) http://dspace.nbuv.gov.ua/handle/123456789/117508

           8.     Korolyov V.Yu., Polinovsky V.V., Ogurtsov M.I. Simulation of communication networks of mobile remote-controlled systems based on HLA. Visnyk Khmel'nyts'koho natsional'noho universytetu. 2017. 1 (245). P. 160 - 165. (in Ukrainian) http://nbuv.gov.ua/j-pdf/Vchnu_tekh_2017_1_33.pdf

           9.     Asfaw A. Learn Quantum Computation using Qiskit [Online]; IBM: New York, 2019; https://qiskit.org/textbook/ch-applications/qaoa.html (accessed March 15, 2020).

       10.     Maximum Cut. https://github.com/dwave-examples/maximum-cut (accessed March 15, 2020).

       11.     Gary M., Johnson D. Computing machines and difficult-to-solve problems. Mir: Moscow, 1982. (in Russian)

       12.     Talbi E.-G. Metaheuristics: from design to implementation. Wiley: Hoboken, 2009. https://doi.org/10.1002/9780470496916

       13.     Hulyanitsky L.F., Mulesa O.Yu. Applied methods of combinatorial optimization. Publishing center "Kyiv University": Kiev, 2016. (in Ukrainian)

 

 

ISSN 2707-451X (Online)

ISSN 2707-4501 (Print)

Previous  |  Full text (in Ukrainian)  |  Next