Promising Optimization Method tested on an Industrially Reliable Quantum Device

The proposed hybrid quantum-classical algorithm holds the potential to solve intractable problems for classical computers, such as the scheduling problem, macromolecular docking, or designing water distribution networks.  

In the quest for quantum advantage, testing novel hybrid quantum-classical algorithms to tackle problems inaccessible to classical computers is a crucial step. A relevant case of an inaccessible problem, ubiquitous across all industries, appears when we must find the best option out of many combinations to make the most of the available resources.

Let’s take, for instance, the scheduling challenge. Suppose you are the manager of a delivery company in charge of loading a large fleet of trucks. There are so many trucks under your responsibility that it is impossible to load them in a one-time slot. You also need to distribute the loading tasks so that your employees do not interfere with one another, maximizing employee fairness and satisfaction, and minimizing the number of temporary workers your company needs to hire. It would be great if you could achieve all that! But it is actually far from easy.

The scheduling challenge, as well as many other combinatorial optimization problems—such as macromolecular docking or designing water distribution networks—scale exponentially in computing time with the number of combinations. These problems are called intractable for a reason: in real-world scenarios, beyond a few hundred trucks and loading tasks the classical computing capacities becomes largely saturated. We could be talking about millions of years of classical computer time!

Enterprises closely follow quantum computing developments, emerging to play an essential role in the next generation of supercomputers. Quantum algorithms, designed to work in synergy with classical methods, are expected to escalate reasonably (at most polynomial) with the number of combinations, finding reliable solutions. One of the most promising hybrid classical-quantum approaches to solving combinatorial optimization problems uses the so-called Quantum Approximate Optimization Algorithm (QAOA).

For a few years, the QAOA method has been tested on different experimental quantum platforms, such as neutral atom arrays, superconducting processors, and trapped ions simulators.

This year, researchers from the University of Bologna, supported by CINECA, have implemented a QAOA method on Fresnel, Pasqal’s first commercial device. This is the first time a hybrid quantum-classical method involving the QAOA has been tested on an industrially reliable quantum device. Further more, the classical routine running on an HPC (High Performance Computing) center collaborated with the quantum device in a flawless, automated way.

“It was very impressive that we did not need to run many trials for our algorithm [on the Pasqal machine],” said Simone Tibaldi, PhD student in quantum information and computation, supervised by professor Elisa Ercolessi, from the University of Bologna. “Usually, these kinds of optimizations take a lot of trials. When using other types of platforms there is more time for noise reconstructions and error mitigation techniques, but with Fresnel, we only had to run a few shots and immediately worked and got a solution.”

‍

‍

Combinatorial optimization problems represented by graphs

The team from the University of Bologna used their novel approach to the hybrid algorithm to represent a combinatorial problem using graphs. A graph is a drawing composed of dots called nodes, representing entities, and lines, called edges, that connect the nodes, representing the relationship between the nodes.

For instance, the delivery scheduling problem can be mapped into a graph in the following way: Let us consider three different timeslots, the first load must be done from 2:00 to 5:00 pm, then the second load from 4:00 to 10:00 pm, and the third from 9:00 to 11: 00 pm. The first load does not overlap with the third, but the first and second do. If the timeslots are represented by nodes in a graph, then the overlapping will be represented by the edges.

To optimize this graph-based problem we need to find the maximum number of nodes that are not connected by an edge. In other words, given a graph, we want to find the largest number of nodes that are not connected by an edge, thus avoiding overlapping in the timeslots. This largest set of nodes not connected by an edge is called the Maximum Independent Set (MIS). The QAOA is one of the most promising hybrid methods to address the MIS problem and help find the closest-as-possible best solutions to the scheduling challenge and many other combinatorial optimization graph-based problems.

QAOA implemented on a neutral atom device

QAOA is a versatile method that can be implemented on both digital and analog quantum platforms. In digital quantum computing, the computer executes algorithms in various steps using quantum gates, while with the analog method the quantum computer evolves towards an answer continuously in a single step. While digital computing is universal, the risk of errors increases for each gate created. This is because individual gates are noisy and errors compound. In contrast, the analog mode is less susceptible to noise.

Among the few available quantum platforms, neutral atom computers have been shown to be the best candidate to address graph-based problems using the analog mode, efficiently tackling combinatorial optimization problems. For this reason, the researchers from the University of Bologna chose Fresnel to test their hybrid QAOA method. They successfully solved the MIS problems for graphs from 6 to 15 nodes.

Furthermore, the novel approach presented by Elisa Ercolessi and Simone Tibaldi, from the University of Bologna, implemented a novel classical approach that significantly reduces the number of calls to the quantum device, adding an essential layer of efficiency to their method.

“Our results are objectively successful, we got exactly the solution to the problem, even with 15 qubits representing a 15-nodegraph. We also ran a simulation of the same problem and the solution obtained on the real quantum device is actually better than the quantum simulation,” Simone Tibaldi remarked.

The future of quantum optimization algorithms

Quantum computing holds the promise to rescue impossible-to-solve challenges and turn them into problems that can be solved in reasonable time, which is precisely the case of combinatorial optimization. Hybrid quantum-classical algorithms such as the QAOA are expected to dramatically help speed up computations.

Emulations of the QAOA on classical devices using tensor networks show that already with over 50 qubits we should be starting to see better performance over some naive approximate pure classical algorithms.

“This hybrid algorithm [implemented by the University of Bologna team] is also useful when you are dealing with a function to optimize on a device that might be a bit noisy,” Lucas Leclerc, quantum software engineer at Pasqal.

The current Pasqal commercial device operates with 100+ qubits and we are expecting to release soon this year the next generation that will run with more than 1000 qubits. With such power, we expect to solve problems such as the scheduling challenge, offering different industries (energy, transportation, communications, healthcare…) effective ways to use their resources.

References

• Tibaldi, S., Vodola, D., Tignone, E.,& Ercolessi, E. (2023). Bayesian Optimization for QAOA. IEEE Transactions on Quantum Engineering, 4, 1–11. https://doi.org/10.1109/tqe.2023.3325167
• Tibaldi, S., Vodola, D., Tignone,E., & Ercolessi, E. (2024). Analog QAOA with Bayesian Optimization on Rydberg atoms’ QPU. In progress.

‍

‍