How do you get from Amsterdam to Den Haag as fast as possible? What is the shortest route that passes through several cities? Optimization problems like these are everywhere around us. CWI PhD student Sander Gribling studied if and how quantum computers can help solve such questions. He and his colleagues developed new quantum algorithms for basic classes of optimization problems, showing that quantum algorithms can help to solve some of them more efficiently. Gribling defends his PhD thesis, ‘Applications of optimization to factorization ranks and quantum information theory’ at Tilburg University on 30 September 2019.
Gribling says: "Given an optimization problem, a fundamental question is: how efficiently can we solve it on a computer? Historically, this question has been studied for so-called Turing machines, the computers we use today. However, the laws of physics offer a different model of computation, namely quantum computing. This model of computation offers speed-ups by exploiting quantum effects such as entanglement, superposition, and interference. A famous example of such a speed-up is Shor's algorithm for factoring prime numbers, which has major implications in cryptography". In his thesis Gribling studied the power and limitations of quantum computing for solving optimization problems, and he developed new algorithmic methods for hard problems in classical optimization and quantum information theory.
Quantum algorithms for classical optimization problems
With the recent progress on building quantum computers it becomes more relevant and urgent to study their power and limitations. With the abundance of real-world applications of optimization problems, a natural question is: how good are quantum computers at solving optimization problems?
Gribling and co-authors made progress on this question for several important classes of optimization problems: linear optimization, semidefinite optimization, and convex optimization in the black-box setting. They developed new quantum algorithms that are asymptotically faster than their classical counterparts. At the same time they explored the limitations of quantum computers for solving such problems: the speed-ups can be significant, but not exponentially large.
Classical optimization for quantum problems
One of the fundamental quantum effects is entanglement. Gribling and his co-authors explored the power of entanglement from the viewpoint of combinatorial optimization. Gribling: "Our research led to a beautiful connection between discrete mathematics and areas such as functional analysis and operator space theory. This connection often enabled us to improve, generalize, or unify existing bounds."
Sander Gribling did his research in the Networks & Optimization research group at CWI and was involved in the QuSoft research centre for quantum software. The work was funded by NWO.
More information
- homepage of CWI's N&O research group
- Promotores: Prof. Monique Laurent and Prof. Ronald de Wolf
- Sander Gribling's personal homepage
