Can quantum computing solve optimisation problems?

Quantum computing: a fast-growing field

The United Nations has declared 2025 the “International Year of Quantum Science and Technology”, highlighting the progress made in quantum physics since its inception a century ago. These advances are now spreading to fields beyond physics, including computing, with the emergence of new computational paradigms. 

In the 1990s, quantum computing theorist Peter Shor designed an algorithm that could be used by a future quantum computer to factor numbers much more efficiently than a conventional algorithm. Since then, the discipline of quantum algorithms has grown rapidly, offering new perspectives on other types of problem, such as optimisation, which is the focus of the Bonus project team at the Inria centre at the University of Lille.  

Optimisation to solve complex problems

Put simply, optimisation consists in finding solutions that maximise or minimise a particular quantity, defined by a mathematical function. When the exact solution to a problem cannot be found due to its complexity, “there has to be a compromise between the time it takes to calculate and the quality of the approximate solution found”, explains Zakaria Abdelmoiz Dahi, a researcher on the Bonus project team. 

One such problem is “multi-objective optimisation”, which involves optimising several quantities, often in contradiction with each other. For example, how do you ensure that a fleet of trucks serves the maximum number of customers while consuming as little fuel as possible?

Optimisation is used to solve a wide range of practical problems, from transport and energy networks to logistics. Optimisation algorithms already exist, such as NSGA-II. But could quantum computing design more efficient algorithms?

Quantum algorithms at the heart of challenges

First of all, it is not always possible to simply transpose a conventional algorithm into a quantum algorithm. The computing paradigms are radically different. For example, conventional computing is based on binary quantities, or bits, which can only take two values. In contrast, quantum physics allows the use of qubits (quantum bits) that can be placed in superpositions “both 0 and 1”, meaning they can take on a whole continuum of values. 

And the number of states that can be represented grows exponentially with the number of qubits, i.e. much faster than in conventional algorithms. Another quantum property, entanglement, offers the possibility of linking information between these qubits (correlations) in a way that is impossible with conventional bits.

The parallelism of quantum algorithms is therefore of a completely different nature and promises computing speeds far beyond what is possible with standard computers. “But these characteristics are not everything,” says Zakaria Abdelmoiz Dahi. “It’s all in the design of the algorithms.”

Quantum computers remain limited

Over the past decade or so, the first quantum computers have begun to emerge from laboratories, either through major players funding activities in the field (Google, IBM, etc.) or through spin-off companies from research groups. They use different technologies to create qubits (superconducting circuits, trapped atoms or ions, photons, etc.).

But while progress has been rapid, these are still prototypes whose qubits are limited in number and above all “noisy”, because quantum effects (superposition, entanglement) are very sensitive to disturbances and difficult to maintain and manipulate. 

Specialists use the term NISQ (Noisy Intermediate-Scale Quantum) machines to describe today’s quantum computers. “These problems must be taken into account, because a poor design renders the algorithm unusable”, says the researcher.

Towards multi-objective optimisation

Today, quantum algorithms for tackling optimisation problems already exist, in particular the QAOA (Quantum Approximate Optimization Algorithm). However, this algorithm can only be applied to “single-objective” problems. In a recent paper published with colleagues from the University of Malaga, Zakaria Abdelmoiz Dahi extended this algorithm, not to a specific practical problem, but to a class of multi-objective problems.

QAOA operates using a concept from quantum physics known as the adiabatic theorem. What does it involve? In physics, the concept of the “Hamiltonian” describes the total energy of an entire system (in this case, the state of all the qubits). The adiabatic theorem ensures that if the system is in its state of minimum energy and evolves in a sufficiently controlled way, then it will remain in its state of minimum energy even if its Hamiltonian changes. 

The principle of QAOA is to match the solution to the problem with this minimum energy state, which can be measured. The art of the algorithm is then to perform a series of operations (quantum logic gates) on the qubits to bring the system into the desired configuration. 

Strengths and weaknesses of quantum algorithms

Zakaria Abdelmoiz Dahi and his colleagues took several steps to generalise this algorithm. Firstly, they established a mathematical formulation that could incorporate all the objectives and be assimilated by the algorithm. They also achieved another goal: maintaining the optimality allowed by the adiabatic theorem. 

Above all, the scientists made sure that the algorithm was adapted to current machines and could be implemented. “This stage considerably increased the complexity of the work,” says the researcher. Finally, the algorithm was tested both on conventional supercomputers powerful enough to simulate the behaviour of a small quantum computer and on real 127-qubit quantum computers from IBM via the cloud.

The aim of this research was not to demonstrate a direct quantum advantage of this method over conventional algorithms, given the limited nature of current quantum computers. Rather, it was to lay the foundations for future applications on more powerful systems. Another goal was to assess the strengths, weaknesses and applicability of quantum algorithms in this particular case.

“Simulated quantum annealing” for optimisation

Building on their initial work, Zakaria Abdelmoiz Dahi and his colleagues have recently extended this research using another quantum computing paradigm. Instead of manipulating qubits through successive operations, the evolution here is continuous. This technique, known as “simulated quantum annealing”, is not as versatile as the technique using quantum logic gates, but it is very well suited to optimisation problems.

In collaboration with the QAR-lab laboratory at Ludwig Maximilian University in Munich, the optimisation algorithm was tested on the computers of the Canadian company D-Wave, which use this technique. "The results are very promising,” says Zakaria Abdelmoiz Dahi. “We hope to publish them soon.”