© Fraunhofer IKS
What do the post office, garbage collection and cabs have in common? They all need to plan routes to deliver letters, empty containers and carry passengers respectively. However, every kilometer costs CO², time and money. In day-to-day business, experimenting is not possible – the logistics have to work safely and reliably.
Route planning, especially for several vehicles and hundreds of hubs, is a challenging optimization problem that classical computers can only solve approximately. Quantum computers can help here: Together with classical optimization algorithms, they comb through the many possible paths in search of the shortest route much faster. But it’s not quite that simple, the technology is in its infancy and can only be applied in collaboration with various experts from physics, mathematics, and computer science.
Hybrid solutions should do just that
Researchers at Fraunhofer IKS are trying to reduce this barrier with the QuaST (“Quantum-enabling Services & Tools for Industrial Applications”) research project. For this purpose, they are testing various hybrid solutions using quantum and classical hardware. By continuously cooperating with scientific partners such as Fraunhofer IIS, quantum computing companies such as parityQC and industrial end users such as Infineon, they are creating a decision tree that will ultimately serve as a guide through the jungle of possible solutions. The aim is to find the best method for each application without having to spend years manually putting it together again each time.
For more information, see the paper »Recommending Solution Paths for Solving Optimization Problems with Quantum Computing« byBenedikt Poggel, Nils Quetschlich, Lukas Burgholzer, Robert Wille, Jeanette Miriam Lorenz.
For this to work automatically, many tools have to work together and be integrated: At the beginning, there is the mathematical formulation that turns a use case (“How do I ensure that I empty all the bottle banks in Munich on time using as few vehicles as possible?”) into a concretely defined optimization problem. In this case, for example, it is the Traveling Salesperson problem. Therefore, a hybrid algorithm is to find out which route connects a given number of stops by the shortest distance.
To make the best use of the different technologies, the problem is then broken down into parts, some of which require a quantum computer, and others that can be solved more traditionally, say, with a supercomputer. But the quantum computer still does not know what it is actually supposed to compute: It first needs the problem encoded into a quantum system, and also needs to know which algorithm out of the many possible options it should run.
To make matters worse, different hardware technologies have distinct strengths and weaknesses. Superconducting qubits, for example, are relatively stable, but difficult to connect to one another in large quantities. Individual ions can be connected in any combination, but it takes much longer to perform computations with them. These properties affect the entire decision tree, making its automation extremely complex.
New methods for efficient route planning
Together with Infineon, Fraunhofer IKS scientists have taken a closer look at the problem of efficient route planning. In contrast to conventional methods, they focus on application-oriented indicators that can be used to assess the success or failure of an algorithm. After all, it is not the quantum energies that are of interest, but how long the calculated routes are now.
It turns out that many adjustments have to be made correctly to obtain meaningful results: For many of the algorithms tested, it is not easy to generate valid solutions: ones that can be put into practice in reality and do not, for example, require a vehicle to drive to two containers
at the same time.
Read more about quantum computing-assisted solutions to optimization problems in the paper »Quantum-Assisted Solution Paths for the Capacitated Vehicle Routing Problem« by Lilly Palackal, Benedikt Poggel, Matthias Wulff, Hans Ehm, Jeanette Miriam Lorenz, Christian B. Mendl.
The route planner at the waste disposal company does not care about any of that: It just want to be able to give its drivers their schedule quickly and reliably. That is why the QuaST consortium, led by Fraunhofer IKS, is developing a framework that makes it possible to compare different solutions on the basis of application-related indicators. To ensure that end users can trust the solution despite masking the underlying technical details, we are also investigating how its safety and reliability can be guaranteed despite experimental and theoretical uncertainties.
This project is being developed as part of the QuaST (Quantum-enabling services & tools for industrial applications) project funded by the Federal Ministry of Economic Affairs and Climate Action (BMWK) on the basis of a resolution by the German Bundestag.