QuSoft PhD-student Jordi Weggemans wins Lorentz graduation prize.

Weggemans conducted his research in 2020 and published his graduation thesis under the title ‘Solving Correlation Clustering with the Quantum Approximate Optimisation Algorithm‘. The research also resulted in a scientific article that he submitted together with eight fellow authors for publication in the journal Quantum. It can be read online at arXiv.org. Weggemans graduated from the University of Twente (UT), and was supervised by the UT, the UvA, CWI and QuSoft.

 

Although quantum computers still exist only in rudimentary form in the lab, once they become powerful enough they can solve some computational problems that would take far too much time for classical computers. Finding out which problems these are is an important research area of the CWI group Algorithms & Complexity and of QuSoft.

 

Weggemans investigated whether a quantum computer can offer a solution to the so-called clustering problem. “In essence, this problem revolves around sorting things into groups that are similar to each other,” Weggemans explains. “Suppose you organise a Zoom meeting with a hundred participants and in between the main programme you want to let the participants discuss with each other in groups. Which groups you form depends on the criteria you use. Finding an optimal arrangement is an example of a clustering problem.” 

 

The clustering problem has many applications, including in the field of machine learning, a branch of artificial intelligence. For this reason Weggemans also worked together with Alexander Rausch from the German company Bosch. Rausch: “At Bosch we are investigating the clustering problem for the development of robust object detection algorithms that can be used in cars with automatic driving assistance.”

 

It has been mathematically proven that, based on very plausible assumptions in theoretical computer science, there is no efficient classical algorithm to solve this problem. The currently best classical algorithm can, in the worst case, arrive at only a fraction 0.7666 of the best solution.

 

Would a quantum computer be able to do better? was the question Weggemans wanted to answer. He investigated a quantum algorithm that was first applied to another clustering problem in 2014: the Quantum Approximate Optimization Algorithm (QAOA). “When I started my research, little was known about it,” says Weggemans, “but a year later, more than a hundred publications had already appeared on it. So in a short time a lot of researchers have started working on it.”

 

Weggemans developed several formalisms to solve the sorting problem with the QAOA quantum algorithm. “The conclusion is that it cannot be ruled out that this quantum algorithm does better,” Weggemans concludes, “but that it has not been confirmed either. Of course we hoped that we could prove that the quantum algorithm does better, but if not, then that too is an important insight. For that matter, it is still possible that there are other quantum algorithms that do solve the clustering problem faster than a classical computer.”