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.

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’.

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 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.

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.