(CWI.nl) CWI researcher Joran van Apeldoorn in his PhD thesis provides evidence that quantum computers could indeed solve specific types of optimisation problem much faster.
In mathematics and computer science, optimisation problems revolve around the idea of finding the best solution from a huge amount of feasible solutions. Van Apeldoorn focussed on so-called convex optimisation 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?”
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.”