The advantages and limitations of quantum computing over classic computing have become clearer once again. PhD candidate Joran van Apeldoorn shows that a specific type of optimization problem can be solved much faster by quantum computers. Today, he will defend his thesis at the University of Amsterdam.
As quantum computing gradually makes its first steps into real-world applications, a deeper insight in its advantages and limitations is much needed. In his PhD thesis, CWI researcher Joran van Apeldoorn provides evidence that quantum computers could indeed solve specific types of optimization problem much faster.
In mathematics and computer science, optimization problems revolve around the idea of finding the best solution from a huge amount of feasible solutions. Van Apeldoorn focussed on so-called convex optimization problems, which feature widely applied methods like the least squares analysis, linear programming, and geometric programming. “One very useful feature that they have in common, is that a local minimum is also a global minimum”, he says. “This allows you to solve these problems by repeatedly making small steps in the direction of the largest decrease you can find. One question is: how do you find the largest decrease?”
Exponentially faster
Van Apeldoorn’s research shows, among other things, that quantum computers can calculate the largest decrease exponentially faster than classic computers. His research also exposed limitations of quantum computers in the field of convex optimization. “For example, we showed that our quantum algorithm for linear programming is optimal and that there is no generally exponential acceleration for convex optimization”, says Van Apeldoorn.
Widely applicable
Though mainly a theoretical endeavour, Van Apeldoorn expects his research could help bringing quantum computing to further fruition. “It is theoretical in the sense that we cannot yet build quantum computers. Furthermore, during my research I wondered what is the best guarantee that an algorithm can provide for all situations you can think of. On the other hand, in reality, algorithms are generally gauged by how fast and good they are for some practical problems.”
Still, his results can teach us more about the ultimate possibilities and limitations of quantum computers, says Van Apeldoorn. Furthermore, the techniques that he and his collaborators developed are more widely applicable. “It is possible that our techniques can also be used to speed up heuristic classical methods of optimization that work well for practical problems. But in order to do this, large quantum computers need to be developed first to experiment with.”
Interesting results
“Many questions about convex optimization on quantum computers remain to be solved”, says Van Apeldoorn. “After all, science has started to investigate this subject quite recently. Our research group at CWI was one of the very first to investigate this subject. I certainly expect a lot of interesting results in the years ahead.”
Best Student Paper Award
Van Apeldoorn performed his PhD research at CWI’s research group Algorithms and Complexity. Together with fellow CWI researcher András Gilyén, he won the Best Student Paper Award at the ICALP 2019 conference for their paper Improvements in Quantum SDP-Solving with Applications.
Today, Van Apeldoorn will defend his thesis A Quantum View on Convex Optimization at the University of Amsterdam. His research was supervised by Ronald de Wolf (CWI/UvA) and Monique Laurent (CWI/Tilburg University).
Van Apeldoorn continues his scientific career as a postdoc, studying the societal and legal impact of quantum computing at Institute for Information Law (IViR), part of the University of Amsterdam. For this research, he will continue to work closely with QuSoft and at CWI.
