of Vehicle Routing on Modern Quantum- Classical Cloud Services

Abstract

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. ing salesman problem Quantum computer, quantum computer mathematics, qubit, vehicle routing problem, travel-

1. Introduction

Quantum computers (QC) have the potential advantage over classical processors because, in addition to arithmetic and logic operations, quantum superposition is used in algorithms. The computing power of modern quantum processors, also known as "noisy quantum devices of intermediate scale", is significantly limited due to the small number of qubits and connections between them, imperfect control of qubit states, short coherence time, and poor error correction. The noise of quantum computing devices creates errors that affect both the state of qubits and the stability of the global minimum, prepared by the procedure of mapping the optimization problem to the quantum system. Another characteristic of QC is the ratio of the time of stability of qubits and couplings between them to the time of computational operations. This characteristic allows us to estimate how many arithmetic and logic operations can be performed during the existence of qubits. Hence, it shows the computational performance of a quantum system for performing algorithms.

Solving combinatorial optimization problems by the method of quantum annealing is widely used in materials science, chemistry, logistics, pharmaceuticals, bioinformatics, computational biology, in

2022 Copyright for this paper by its authors. depth training for neural network training, and in the financial sector. Solving optimization problems on hybrid quantum-classical computers and simulators (models) of QCs allows accelerating the solution of many known problems on graphs, clustering, optimization of an investment portfolio, vehicle routing, protein folding, scheduling, modeling of chemical reactions, drug research, etc.

QCs are evolving in the following directions:  increasing the number of qubits and the connections between them [ 1, 2 ] (up to 7,000 cubic meters in 2023);

 development of a complex of computer systems and information technologies [ 1, 3 ], which can simultaneously perform arithmetic and logic operations on quantum circles and annealing;  creation of universal QCs [ 4 ], which combine several physical qubits into logical ones to reduce calculation errors due to noise;  building hybrid cloud services from quantum and classical computers [ 1, 3, 4, 5 ].

The article studies common approaches to the use of quantum computing to solve certain types of combinatorial optimization problems [ 2, 7 - 10 ].

2. Physical principles for solving combinatorial optimization problems on quantum computers

Quantum annealing based on cloud services is based on some metaheuristic algorithms for solving combinatorial optimization problems using adiabatic quantum calculations [ 11, 12, 13 ]. Solving NPcomplex problems on quantum computers is based on the use of adiabatic quantum optimization and mapping the problem to the states of the quantum system according to the functional of the Hamiltonian H(t) [ 11 ]. Technologically, quantum annealing is performed by changing the state of the qubit system from the initial quantum state to the final quantum state by evolution within the model of Hamiltonian dynamics following the problem of combinatorial optimization [ 13 ]. The prepared quantum system then adiabatically changes to the required state for solving the problem in time T according to the formula [ 11 ]:

H t   1 Tt  H0  Tt HP , when T is large enough, and H0 is the state of the system with minimal energy, HP is the state of the system with the problem built into the qubit problem; then the system will remain in a state with minimum energy according to the adiabatic theorem of quantum mechanics. Problem-solving time for a system with N spins [ 11 ]:

T  O expN  ,

  where α, β are positive coefficients, N → ∞. It is unlikely that any NP-complete problems can be solved in polynomial time using adiabatic quantum optimization (AQO). However, if we construct a quantum system where the coefficients α, β are small values, then there is a possibility that the AQO algorithm will be faster than classical algorithms for some classes of problems.

3. Solving routing problems on quantum computers by the annealing method

Construction of algorithms for solving routing problems based on quantum computers is based on the use of the Hamilton-Ising model for NP-complex optimization problems [ 10, 11 ], which in the presence of many N spins si = ± 1 can be written as a special quadratic function the set N of spins si = ± 1. Variables are "turns up" spin (↑) and "turn down" spin (↓), i.e. states that correspond to the values +1 and −1. Relationships between spins are called couplings and from the point of view of probability theory can reflect correlations or anticorrelations. The objective function, expressed as a classical Ising model, has the form:

N H  s1,K , sN    Jij si s j   hi si , i  j i1 where si, sj, i = 1,…, N, are linear coefficients corresponding to the displacement of qubits - hi, (spin rotations), and square coefficients Ji,j correspond to the forces of connection between qubits. Computational quantum schemes for solving combinatorial optimization problems are based on the model of quadratic unconstrained binary optimization (QUBO), which is isomorphic to the Hamilton-Ising model:

N N H  x  Qi,i xi   Qi, j xi x j ,

i1 i  j where Qi,i are the linear coefficients and Qi,j are the quadratic coefficients, i = 1,…, N. The QUBO model, which uses binary 02 and 12, is more convenient for writing code on traditional computers. The hardware and software of quantum computer developers convert the code of the algorithm for solving the optimization problem into the state of the quantum system.

The structure of the quantum processor is a physical implementation of an undirected graph with qubits as vertices and couplers (connectors) as edges between them. From the standpoint of solving the problems in formulation QUBO each qubit in the quantum processor represents the variable QUBO, and the connectors between the qubits represent the costs or edge weight associated with pairs of qubits mathematically described in the matrix Q.

3.1. Vehicle routing problem statement

Formulation of the problem.

Vehicle Routing Problem (VRP) tasks are determined by the set of customers to be serviced, their location and requirements, as well as other primary information such as the distance between two customers, the distance between each customer and the depot, the number of vehicles and their carrying capacity. This class of routing tasks combines several types of logistics problems [ 14, 15, 16 ].

Let M be the number of available vehicles and N be the number of customer orders. A complete weighted graph G = (V, A) is considered given. The set V = {v1, ..., vN+1} are vertices, the first N of which correspond to the clients, and vN+1 represents the depot.

The depot often represents the supplier and the customers the retailers. The weight of each edge of set A is related to the inherent cost of travel between incident vertices. Denote the cost of direct travel from vertex i to the vertex j as Ci,j. We can also determine Ci,N 1 and Ci,N+1 for i ∈ {1,2,...,N} as the cost of direct travel from the depot to the destinations of customers and from the destination of customers to the depot, respectively.

3.2. An example of solving a TSP test problem on a D-wave QC

Consider the computational scheme of the Traveling Salesman Problem (TSP) algorithm on a Dwave quantum computer. To do this, as input we use the weighted graph presented on Figure 1.

Initially, the problem is displayed as QUBO (Figure 2). To solve the problem with more than 4050 vertices, the company has developed procedures for decomposing problems; also, independent developers of algorithms have proposed several algorithms that take into account the load, delivery time, and schedule [ 17 ]. The solution of the TSP problem (Figure 1) is a route on vertices: 0→1→2→3.

The data obtained is transmitted to a quantum computer company D-wave and displayed on the qubits and couplings (Figure 3) with the next set of QC parameters [ 1, 2, 17 ]:

Parameters of the process of solving

NUMBER OF READS 1000 ANSWER MODE histogram Solution NUMBER OF SOURCE VARIABLES 16 NUMBER OF TARGET VARIABLES 79 MAX CHAIN LENGTH 6 CHAIN STRENGTH 2 CHAIN BREAK RESOLUTION METHOD

Timing

QPU ACCESS TIME (μs) 249811.1 QPU PROGRAMMING TIME (μs) 10871.1 QPU SAMPLING TIME (μs) 238940 TOTAL POST PROCESSING TIME (μs) 4133 POST PROCESSING OVERHEAD TIME (μs) 4133 SOLVER DETAILS NAME (CHIP ID) DW_2000Q_6 majority_vote

According to the quantum annealing procedure, a set of solutions is obtained, from which the most probable variant is chosen, which corresponds to the lowest energy level.

For the sample set histograms shown in Figure 4, the best solution has an energy level "-7". Other samples, which match to higher energy levels, correspond to local minimums.

3.1. Examples of solving a TSP, VRP test problems on IBM QC simulator

The process of solving the traveling salesman problem and the vehicle routing problem was also studied on the simulator of real IBM universal QC and also with the CPLEX library for solving optimization problems on classical computers. Simulation quantum systems of classical systems may require a large amount of random access memory. The solution of the TSP for four points on the IBM QC simulator and IBM Qiskit quantum processing library required 64 gigabytes of random access memory, which made it impossible to demonstrate it on a serial budget personal computer.

On Figure 5 it is shown the graph for the TSP test problem. The solution on an emulator of QC gives two feasible solutions 0→2 →1; 0→1→2, shown in Figure 6, and gave an erroneous one: 2→0→1. Figure 7 is shown solving the vehicle routing problem on the simulator of IBM universal QC (Figure 7 a) and also with the CPLEX library (Figure 7 b) for solving optimization problems on classical computers.

A variational quantum eigenvalue solver [ 10 ] is essentially a heuristic algorithm based on the quantum processing formulation of Ising Hamiltonian model. The local minimum in a quantum processing formulation may be the same as the solution on a classical computer. Although in some small-scale examples it is probable to find optimal solutions for the formulation of quantum processing, which match the optimum solution on a classical computer. Finding optimal solutions for integer linear programming is a more complicated task than finding local minimum for quantum processing formulation at large, which sequentially is more difficult than finding feasible solutions for integer linear programming. Variational quantum eigenmode solver is more dependable than integer linear programming and promises feasible solutions for specific variational forms.

The depot is shown with a star, and the calculated routes for vehicles are shown with arrows. In this particular case, one can find an optimal solution in quantum processing formulation, which coincides with the optimal solution for integer linear programming.

3.2. An overview of algorithms for solving the problem of vehicle routing on QC 3.2.1.

Full QUBO Solver (FQS).

Proposed formulation [ 11, 12 ] for the problem of routing of loaded vehicles (CVRP) as a problem of quadratic unlimited binary optimization (QUBO). First, let's define the basic QUBO formula that is used to solve VRP instances. Problem definition is based on a similar problem statement for TSP in [ 12, 18 ]. We introduce the binary function:

n n n A y1,..., yn     2 yi y j   yi ,

i1 ji1 i1 where yi ∈ {0, 1} for i ∈ {1 ,. . . , n}, n – number of vertices . It is easy to prove that the minimum value of A(y1,...,yn) is “−1”, and this value can be achieved only if exactly one of y1,..., yn is equal to 1.

According to the definition of VRP, the problem of minimizing the total cost can be defined as minimizing the function:

M N M N M N 1 N 1 N 1 C    xm,n,1CN 1,n    xm,n,N Cn,N 1      xm,i,n xm, j,n1Ci, j .

m1n1 m1n1 m1 n1 i1 j1 (1)

The first component in (1) of the sum C is the sum of all travel costs of vehicles from the depot the first part of the route of each vehicle. The second component is the cost of the last final part of the routes (return to the depot) in a particular case, when one car serves all N orders (only in this case the component can be greater than 0), the last part – this determines the total weight of the cost of all other sections of the ribs included in the route. a b

Figure 7. VRP problem solution in QUBO formulation on IBM QC simulator (a) and VRP problem solution in IBM CPLEX optimization library for classical computer (b)

To ensure that each delivery is serviced by one vehicle and only once and that each vehicle is exactly in one place at a certain time, the next term (in which all components A are “-1” only in such desirable cases) should be included in our QUBO formula:

N M N Q   A x1,k,1, x2,k,1,K , x1,k,2 ,K , xM ,k,N     A xm,k,n , xm,2,n ,K , xm,N 1,n  .

k1 m1n1 By definition, VRP, QUBO-representation of such an optimization problem can be

QUBOVRP = В1 ∙ C + В2 ∙ Q, where the values of the constants B1 and B2 should be chosen so that the solution relationship found by the quantum annealer would minimize Q (which should be "−N−NM") to meet the above restrictions (according to the results of tests [ 18 ]), constants acquired the following values: B1 = 1, B2 = 107).

A group of researchers from Poland proposed several algorithms and their modifications [ 18 ] for solving VPR / CVRP problems based on the developed FQS computational scheme, as well as known CVRP algorithms for classical and hybrid quantum-classical computers from D-Wave [ 18 ]. 3.2.2.

Average Partition Solver

Average Partition Solver (APS) - is a Full QUBO Solver variant that reduces the number of variables for each vehicle, assuming that each vehicle handles approximately the same number of orders. 3.2.3.

DBSCAN Solver (DBSS)

DBSS allows you to use a quantum approach in combination with the classical algorithm. This particular algorithm is inspired by recursive DBSCAN. DBSS uses recursive DBSCAN as a clustering algorithm with a limited cluster size. The TSP problem is then solved for each cluster separately using FQS. The DBSCAN algorithm can solve the CVRP if all the payloads of the vehicles are equal.

3.2.4. Algorithm for isolating solutions from TSP (Solution Partitioning Solver - SPS)

Since adding vehicle capacity limitations to the model is not an easy task, it is possible [ 18 ] to find a solution based on the results obtained by DBSS. The SPS algorithm divides the solution of the TSP problem found by another algorithm (for example, DBSS) into successive intervals, which are the solution to the CVRP problem. The effectiveness of algorithms from mediocre to the best of the following: FQS, APS, DBSS, SPS [ 18 ]. 3.2.5.

CVRP routing algorithm with scheduling

Researchers from Japan have formulated a statement of the CVRP problem, which takes into account the schedule [ 19 ] and describes the changes in the status of the vehicle in time for each vehicle during the trip [ 19 ]. There are restrictions on capacity (load), which are allowed to increase and decrease the load according to the cities (have not used this concept before) in which vehicles arrive. Description of vehicle status allows you to set different travel rules depending on the condition of each vehicle.

3.2.6. A hybrid method for solving the routing problem for vehicles with different capacities using a quantum annealer

A series of articles presents a way to decompose CVRP into smaller problems of the optimization problem, which are solved sequentially [ 12 ]: clustering and routing. Vehicle clustering is formulated in terms of the Knapsack problem. The Euclidean distance between the clients for the vehicle is stated as minimal. Routing within the resulting clusters is seen as a problem by the traveling salesman (TSP). The developed hybrid algorithm [ 12 ] uses a classic computer to solve the backpack problem and a D-Wave quantum annealer to solve the TSP, but it is also possible to solve the whole problem on the QC if the number of qubits is sufficient. The basis of the computational algorithm is the QUBO scheme. 3.2.7.

Routing algorithm based on a variational search of eigenvalues

Variational Quantum Eigensolver (VQE), implemented for IBM quantum computers [ 20 ], combines classical and quantum optimization algorithms and quantum operators and logic gates, also called quantum variation forms [ 10 ]. The limited number of qubits and connections in the existing quantum computers and their imperfections make it difficult to determine the acceleration of the algorithm because the resulting algorithm is essentially heuristic. Because IBM's quantum computer is universal, not specialized, like D-wave, the developers built the Hamilton-Ising model using quantum logic gates and operators and then translated it into the QUBO model. That is, they reduced the problem to the one already solved. The quality of the routing problem on an IBM quantum computer is about the same as that of a D-wave quantum computer without a hybrid calculator.

4. Resume

Quantum approximate optimization algorithms belong to the class of quantum-classical hybrid variational algorithms by the annealing method. Such calculators can run algorithms only with a limited depth of the quantum scheme, because the principle of operation of such annealers is based on adiabatic evolution in time of the quantum system for a limited number of steps. The quantum ground state is built on the Ising-Hamilton model used to solve combinatorial optimization problems.

Since the problem of the Ising problem is NP-complex, the integration of other combinatorial optimization problems into the corresponding system can also demonstrate a quantum advantage. An approximate quantum optimization algorithm is used to solve the VRP problem with a finite number of steps of adiabatic evolution and does not guarantee that the resulting solution corresponds to the global optimal solution of the original problem.

This is because in an approximate quantum optimization algorithm, instead of gradually following the evolution of the adiabatic state, it tries to guess it using a limited number of steps and heuristics. On the other hand, inaccuracies in the operation of approximate quantum optimization algorithms at higher values of the number of steps in the evolution of the adiabatic state form more local minima in the energy landscape of the solution. This fact makes it difficult to find the minimum, so the required number of steps should be selected according to the heuristic principle and empirical approaches. The developed routing algorithms provide an approximate solution of TSP or VRP problems on D-wave quantum computers in about 3 seconds. Algorithms may not find a solution or may provide a solution with lost points to visit.

The direction of further development of solving the problem of routing on quantum computers is to build new algorithms that are not based on the Ising model, but use other quantum principles or models that can be implemented on universal quantum computers. 5. References

References

[1] Lardinois F. D-Wave plans to build a gate-model quantum computer https ://techcrunch.com/ 2021 /10/05/d-wave -plans-to-build-a-gate-model-quantum-computer/

[2] Korolyov V. Yu ., Khodzinskyi O.M. “ Rozvʺyazuvannya zadach kombinatornoyi optymizatsiyi na kvantovykh komp'yuterakh” [Solving combinatorial optimization problems on quantum computers] . Cybernetics and Computer Technologies . 2020 . 2 . С. 5- 13 . (in Ukrainian) https://doi.org/10.34229/ 2707 - 451X . 20 . 2 . 1

[3] Moran C.C. Mastering Quantum Computing with IBM QX . Birmingham: Packt, 2019 .

[4] Lucero E. Unveiling our new Quantum AI campus . URL: https://blog.google/technology/ai/unveiling-our -new-quantum-ai-campus/

[5] List of quantum processors . URL: https://en.wikipedia.org/wiki/List_of_quantum_processors

[6] Moran C.C. Mastering Quantum Computing with IBM QX . Birmingham: Packt, 2019 .

[7] Nielsen M.A. , Chuang I.L. Quantum Computation and Quantum Information . Cambridge: University Press, 2012 . https://doi.org/10.1017/CBO9780511976667

[8] Norlen H. Quantum Computing in Practice with Qiskit® and IBM Quantum Experience . Birmingham: Packt , 2020 .

[9] Kommadi B. Quantum Computing Solutions. Solving Real-World Problems Using Quantum Computing and Algorithms . New York: Apress, 2020 . https://doi.org/10.1007/978-1- 4842 - 6516-1

[10] Asfaw A. Learn Quantum Computation using Qiskit . URL: https://qiskit.org/textbook/chapplications/qaoa.html (accessed 06 /21/ 2021 ).

[11] Lucas A ( 2014 ) Ising formulations of many NP problems . Front. Physics 2 :5. doi: 10 .3389/fphy. 2014 .00005

[12] Feld S. , Roch C. , Gabor T. , Seidel C. , Neukart F. , Galter I. , Mauerer W. , Linnhoff-Popien C. ( 2019 ) A Hybrid Solution Method for the Capacitated Vehicle Routing Problem Using a Quantum Annealer . Front. ICT 6 :13. doi: 10 .3389/fict. 2019 .00013

[13] Harikrishnakumar R. , Nannapaneni S. , Nguyen N.H. , Steck J.E. , Behrman E.C. A Quantum Annealing Approach for Dynamic Multi-Depot Capacitated Vehicle Routing Problem . http://arxiv.org/abs/ 2005 .12478v2

[14] Toth P. , Vigo D. ( 2014 ). Vehicle Routing: Problems, Methods, and Applications, Second Edition, MOS-SIAM Series on Optimization 18. SIAM , Philadelphia

[15] Golden , B.L. , Raghavan , S. , & Wasil , E. A. (Eds.). ( 2008 ). The vehicle routing problem: latest advances and new challenges (Vol. 43 ). Springer Science & Business Media.

[16] Hulyanitskyi L.F. “ Problema optimizatsii marshrutov transportnykh sredstv s vremennymi oknami” [The problem of optimizing the routes of vehicles with temporary windows] . Computer Mathematics . 2007 . 1. P. 122 - 132 . (in Ukrainian)

[17] D-Wave Hybrid Solver Service: An Overview . URL: https://www.dwavesys.com/sites/default/files/14-1039A-A_ DWave_Hybrid_Solver_Service_An_Overview .pdf

[18] Borowski M. et al. ( 2020 ) New Hybrid Quantum Annealing Algorithms for Solving Vehicle Routing Problem . In: Krzhizhanovskaya V. et al. (eds) Computational Science - ICCS 2020 . ICCS 2020. Lecture Notes in Computer Science , vol 12142 . pp. 546 - 561 . Springer, Cham. https://doi.org/10.1007/978-3- 030 -50433-5_ 42

[19] Irie H. , Wongpaisarnsin G. , Terabe M. , Miki A. , Taguchi S. ( 2019 ) Quantum Annealing of Vehicle Routing Problem with Time, State and Capacity . In: Feld S., Linnhoff-Popien C . (eds) Quantum Technology and Optimization Problems . QTOP 2019. Lecture Notes in Computer Science , vol 11413 . pp. 145 - 156 , 2019 . Springer, Cham. https://doi.org/10.1007/978-3- 030 - 14082-3_ 13

[20] Vehicle Routing Optimization https://qiskit.org/documentation/tutorials/optimization/7_examples_vehicle_routing.html