Vehicles routed with efficient use of qubits

Which routes should a fleet of vehicles take to complete deliveries at all locations? Solving real-world versions of this problem with hundreds of variables would seem to need more qubits than current quantum computers have. CQT researchers may have an answer. Image credit: Shutterstock.com/Atiketta Sangasaeng

Current quantum computers are limited in tackling real-world problems because they have few and noisy qubits. CQT researchers and their collaborators have devised an approach to make efficient use of such qubits for the ‘vehicle routing problem’.

A common scenario in logistics, vehicle routing is a well explored optimisation problem. The goal is to manage and dispatch a fleet of vehicles to complete some tasks, such as deliveries or servicing customers, across a set of locations while minimising travel costs.

The team, led by CQT Principal Investigator Dimitris Angelakis, succeeded in going beyond the usual problem sizes possible on noisy intermediate-scale quantum (NISQ) devices, solving 128- and 3964-route problems using only up to 13 qubits. They formulated the problems based on realistic shipping scenarios provided by contacts at ExxonMobil, the multinational oil and gas corporation.

“With our minimal encoding, we pushed the boundary of what is feasible now with NISQ 200X at least,” says Dimitris.

The researchers detail their results in a paper published in Advanced Quantum Technologies on 21 April. Dimitris’s coauthors are collaborator Ioannis Leonidas from the Technical University of Crete and AngelQ, a quantum computing startup, and former group members Alexander Dukakis and Benjamin Tan. The project was supported by Singapore’s Quantum Engineering Programme.

The work builds on a qubit-efficient approach first introduced by the team in 2021. Their method involves mapping the problem’s variables to qubits using what they call ‘minimal encoding’.

Taking another route

In their work, the researchers re-formulate the problem as a Quadratic Unconstrained Binary Optimisation (QUBO) problem. QUBO problems have binary variables. In the case of the vehicle routing problem, the variables could represent whether possible routes taken by a vehicle should be travelled.

For example, imagine having six destinations A to F and two vehicles. After considering constraints such as long travel times and untraversable paths, a set of feasible routes that the vehicles can take could be four: x₁, going from A to B to C to D; x₂, going from E to F; x₃ going from D to B to A; and x₄, going from E to C to F. Each route would be one variable. In this 4-route toy problem, the optimal solution could be travelling x₃ and x₄ but not the other two such that costs are minimised and each destination is visited exactly once.

“For typical industrial applications, the vehicle routing problem involves numerous vehicles and possible routes, and enumerating through all possible solutions to find the optimal one is computationally unfeasible,” write the researchers in their paper.

Traditional quantum methods for solving QUBO problems such as quantum annealing or variational methods usually map one binary variable to one qubit. For the number of variables in industrially relevant problems, NISQ devices are short on qubits.

Dimitris and his team call the one-to-one mapping ‘full encoding’. By contrast, they use a minimal encoding that divides the qubits into an ancilla qubit, or small group of ancilla qubits, and a larger group of register qubits. The states of the register qubits identify the variables while the ancilla qubit (or qubits) are measured to determine what value each variable should take. This method reduces the total number of qubits needed.

Solving bigger problem sizes

Mathematically, for a problem with n number of variables, the team’s approach would need 1 + log₂(n) qubits as compared to n qubits with full encoding – an exponential reduction.

Running their algorithms on quantum processors from IBMQ, IonQ and Rigetti, accessible via cloud, the researchers found that both approaches gave solutions of similar quality despite minimal encoding requiring fewer qubits.

They further tested their approach on 128- and 3964-route problems. Whereas full encoding would have needed 128 and 3964 qubits, beyond what’s available, their method required just 8 and 13 qubits respectively. For both problems, they reached ‘decent’ solutions.

“In large multi-parameter optimisation problems, one hardly ever finds the exact optimal solution, only the area around it,” explains Dimitris. “Think of it as a landscape with valleys and hills, some very steep, and you are trying to locate the minimum by walking round (or flying around and looking down). If the landscape is very complex, and multidimensional, is gets very hard to locate the absolute minimum.”

The researchers highlight that the bigger problem naturally required more resources, i.e. the algorithm had to be run more times, to obtain decent solutions. This only has a polynomial overhead in the size of the problem, which makes the new approach interesting in the area using near term quantum computers for useful applications.