Reaping the benefits of quantum computing for mathematical optimization

Mr. Weissenbäck, as a result of the ongoing digital transformation, your specialist field of “mathematical optimization” has become increasingly relevant for a wide range of logistical and industrial applications. What are you hoping to achieve with quantum computing?

Markus Weissenbäck: In logistics, every day brings challenging optimization problems that need to be resolved, while the solutions are often not effective enough. So we resort to what is known as heuristics, or methods of approximating the optimal solution, thereby accepting the extremely long computation times these usually entail. This is precisely where we intend to capitalize on the advantages of quantum computing in the future.
 

What advantages are these and what are you pinning your hopes on?



Markus Weissenbäck: Back in the early 1990s, Shor’s algorithm for prime factorization and Grover’s algorithm for unstructured database search demonstrated that quantum computing may have a verifiable edge over classical computers.
 
Grover’s algorithm uses amplitude amplification to obtain quadratic speedups of numerous solution processes by means of dynamic programming, for example. Mathematically speaking, this means saving a “square root factor” in the complexity, based on the quantity of input data involved in the problem.
Shor’s algorithm is primarily based on the quantum Fourier transform, which uses exponential speedup to resolve, say, systems of linear equations.
 

These are mainly mathematical theories. But how can they be applied to real challenges?

 
Markus Weissenbäck: With today’s technology, you would need in excess of 10,000 qubits to perform realistic calculations of current optimization tasks. The newest quantum computer, IBM Q System One, has 27 qubits . That might not sound like much at first. But a number of problems can already be solved by the latest generation of hardware, known as NISQ (noisy intermediate-scale quantum) hardware. Admittedly, it’s not yet possible to achieve optimum speed in calculating all optimization variants using variational quantum algorithms (such as the QAOA algorithm) or heuristics, but in the future we will save a great deal of time compared to classical computers. It’ll probably be several years before it can actually be applied in industry. Having said that, we’re also interested in how we can use our optimization methods to make quantum computers more efficient, especially in terms of optimizing quantum circuits.