Award
Hybrid Quantum Algorithms: Do Classical Optimization Algorithms Perform Better with “Quantum Maps”?

The purpose of quantum computers is to help us solve problems in the future where classical methods reach their limits. These include, for example, more accurate simulations of molecules in quantum chemistry, the design of new materials, or the optimization of supply chains and production processes. An intensively researched proposal for how this can succeed are variational quantum algorithms.

Adelina Bärligea, former master's student at the Fraunhofer Institute for Cognitive Systems IKS, explains them: "You can imagine a driver who wants to reach his destination as quickly as possible and uses a special map for this. The driver represents the classical computer, but the navigation takes place via a 'quantum map' that can simultaneously represent many possible routes". In technical terms: A quantum processor provides information about a problem, while a classical optimizer uses this information to navigate toward the best possible solution. An example is finding the shortest route for a delivery service. Quantum and classical resources complement each other, therefore, these are called hybrid algorithms.

The central problem: The quantum map is never entirely sharp

For the results of her master's thesis, Adelina Bärligea was awarded the Quantum Future Award, presented by the Federal Ministry of Research, Technology and Space. In her work at Fraunhofer IKS, she investigated under which conditions the collaboration between conventional and quantum computers can prove beneficial. A central problem lies in the fact that the above-mentioned "quantum map" offers many advantages – it can, in a sense, explore all possible routes simultaneously – but it does not allow exact positioning. Due to the rules of quantum mechanics, information is only obtained through measurements, and each individual measurement can only provide a statistical estimate. Even if the same quantum calculation is performed many times in succession, some random fluctuations remain. This unavoidable uncertainty is known as "finite sampling noise." It occurs even on a perfect, fully error-corrected quantum computer.

In practical terms, this means: The driver looks at their map again and again, but instead of a clear GPS signal, they only receive a slightly blurred snapshot each time. Notwithstanding the imprecise information, the classical optimizer must how to proceed.

When does the statistical noise become too strong?

But: How much blurring can hybrid quantum algorithms tolerate? To answer this question, the researchers first created an "ideal" quantum map and then added controlled amounts of statistical noise to it. This allows to investigate systematically how accurate the quantum map must be for the classical "driver" to navigate reliably and find their destination. The result: Beyond a critical noise level, the success probability of the algorithm drops abruptly. And this threshold decreases as the problem size grows. Consequently, small problems stay manageable, but even at moderate sizes, the map becomes so blurred that the driver is essentially driving blind.

The noise thresholds obtained through the analysis can then be translated into concrete resource requirements. This quantifies how much the measurement overhead grows with problem size, and how quickly hybrid algorithms reach their limits as a result. The conclusion is sobering: For realistic problem sizes, the required number of measurements would be so high that a purely classical solution would not only be more efficient, but overall more sensible.

What does this mean for the future?

These results show: Many of the variational approaches discussed today do not fail primarily due to hardware errors – which current quantum computers are still struggling with on top – but even due to the unavoidable statistical blurring of quantum measurements. The driver therefore does not reach their destination with the quantum map as easily as one could hope.

Going beyond this diagnosis, the work provides an important tool: a statistically founded methodology with which any hybrid algorithms can be tested for their viability and scalability in the future. It makes it possible to recognize early and practically which forms of collaboration between classical and quantum computers have the potential to succeed. In times of ever more powerful quantum hardware, this question becomes increasingly urgent: Which algorithms can scale up, and which cannot?

The award-winning master's thesis brings us a step closer to the answer. It directs attention to which characteristics the future combination of hardware, algorithm, and application must possess in order to one day achieve a genuine industrial and societal benefit.

PD Dr. habil Jeanette Miriam Lorenz, Head of Quantum Computing Department at Fraunhofer IKS, is delighted about the award for Adelina Bärligea and congratulates her most warmly: »At the same time, the Quantum Future Award is recognition of the research work of the entire team. A truly gratifying conclusion to the quantum year 2025.«