The travelling salesman problem may be the most well-known optimization problem. The problem challenges mathematicians to calculate the best route for a hypothetical salesperson. The more stops the salesperson makes in order to sell their goods, the more difficult it becomes to calculate the most efficient route that hits all the stops and ends back at the starting point. But this type of optimization problem isn't just relevant for calculating the most efficient routes for salespeople but can be found in various everyday situations. Optimization problems can be found, for example, when producing complex products or calculating a product's price.
Thankfully, computers can solve these problems in no time these days. Right? Not always. Even today, classical computers can only solve certain complex problems approximately – and often only after long computation times. The algorithms used in classical computing target real-world problems, using the structure of these problems to develop heuristics to increase computational efficiency. 'That works surprisingly well. Often the algorithms that are slower in theory are actually faster in practice,' explains Peter P. Orth, Professor of Theoretical Physics with special emphasis on Quantum Information Systems at Saarland University. But as good as these algorithms may be, they are often nonetheless just the best solution that can be found in a given situation. But Peter P. Orth and his colleague Professor Markus Bläser, who focuses on computational complexity and algorithms, alongside their industry partners Infineon and BMW and the quantum computer start-up planqc, want to find a better way.
Their new research project, 'QIAPO – Quanteninformierte approximative Optimierung auf NISQ und partiell fehlertoleranten Quantencomputern' (Quantum-informed approximative optimization of NISQ and partially fault-tolerant quantum computers) employs a new approach. Taking extremely complex logistics challenges that might come up in the production and distribution of cars or computer chips as an example, the problem is first simplified by a special type of computer – a neutral atom quantum computer – which is made by planqc in Garching. The quantum computer makes the problem small enough that regular computers, whose algorithms are particularly suited for real-world problems, are better able to tackle it. In some cases, quantum computers greatly outperform regular computers. The state of the computing units used by quantum computers, qubits, can be a superposition of the states 0 and 1. Regular computers, on the other hand, use bits, which can only take on the state of 0 or the state of 1. For that reason, quantum computers are well suited to solve or simplify complex mathematical problems that would overwhelm a classical computer.
Once the quantum computer has simplified a complex problem, the scientists can then use classical computers and apply the many algorithms that have proven successful and efficient in solving practical problems. Using these algorithms, the once extremely large problem, now simplified by the quantum computer, can be solved. Yet even with this new method, there are challenges that industrial companies are confronted with daily that still cannot be solved perfectly, according to Peter P. Orth – hence the name 'approximative optimization'. The researchers aim to use a combination of quantum computers and classical algorithms to find even better solutions than those that are currently possible. Here is an example of possible improvements using fictitious values. If a problem can only currently be solved with 80 percent accuracy, an approach using a combination of quantum and classical computing could enable the problem to be solved efficiently with 85 or 95 percent accuracy. 'Quantum computers can bridge the gap, allowing us to improve accuracy and achieve quantum advantage,' explains Peter P. Orth.
'The QIAPO project doesn't just show how far the development of quantum computers has come,' says Dr. Martin Kiffner, Head of Algorithms at planqc. 'We are also showing today how highly complex, industry-relevant challenges can be translated into quantum algorithms that can ultimately be tested on quantum computers.'
Physicist Peter P. Orth specifies the goal of the project, 'We won't be able to solve all the major problems straight away in the next three years. What we will likely be able to determine is whether we can solve this type of problem using our approach and if so, we will continue studying it.' Even if the approach only makes processes in industrial production and distribution slightly more efficient, the small improvement will make a big difference. As it says in the project's description, 'Even small savings in resources can generate significant efficiency gains and cost effects when production volumes are high.'
At a glance:
The QIAPO project (Quantum-informed approximative optimization of NISQ and partially fault-tolerant quantum computers) began in January 2026 and is receiving €2.33 million in funding over three years from the German Federal Ministry of Research, Technology and Space. Professor Dr. Peter P. Orth of Saarland University is coordinating the project. Professor Dr. Markus Bläser of Saarland University, the BMW Group, Infineon Technologies AG and planqc GmbH are also project partners. planqc develops neutral atom quantum computers – the fastest route to scalable quantum processes for industrial purposes. planqc is the first company to spin off the Max Planck Institute of Quantum Optics as a part of the Munich Quantum Valley initiative.