Solving the Problem of Vehicle Routing on Modern Quantum-Classical Cloud Services
Selected Papers of the VIII International Scientific Conference “Information Technology and Implementation" (IT&I-2021). Conference Proceedings Kyiv, Ukraine, December 01-03, 2021. p. 281-289.
Hybrid quantum-classical services for solving optimization problems are already used by leading international corporations in competition, and achieving "quantum superiority" is an absolute global trend. The use of quantum computing allows accelerating the solution of several economic problems, logistics, virology, and many high technologies, which determines the financing of this area's basic research around the world. The goal of the article is to study algorithms for solving routing problems on quantum computers.
It should be noted that modern quantum computers have significant limitations on both the number of qubits and the number of connections between qubits or the limited depth of the circuit. In addition, modern quantum computers can give only approximate solutions to combinatorial optimization problems, which is a consequence of the imperfection of technologies for creating and maintaining the stability of quantum states and many other physical limitations. This means that many routing algorithms will not soon be able to run on quantum computers.
Therefore, the authors limited the review of quantum algorithms for solving the problem of vehicle routing to a list of algorithms that have been tested on real quantum computers and for which the source code for programs is given by their developers. Algorithms and computational schemes for solving the problem of vehicle routing on modern hybrid quantum-classical cloud services of IBM and D-wave, as well as quantum computer simulators, are studied and discussed.
Ключові слова: Quantum computer, quantum computer mathematics, qubit, vehicle routing problem, traveling salesman problem.