Buhrman receives the KNAW membership for his exceptional scientific achievements. His research focusses on the interface of computer science, mathematics and physics. The common thread in his career is the understanding of the computing power and possibilities of computers and communication networks. Buhrman achieves this by designing new algorithms and communication protocols, and by developing techniques that demonstrate their optimality. He gained international fame for his work on quantum communication and quantum lower bounds.

Programming future computers

Back in the early 1990's, mathematician Peter Shor was the first to come up with a useful and practical algorithm for a quantum computer, allowing to crack codes faster. From that moment on, this area of quantum research gained tremendous momentum.

Buhrman became fascinated by the possibilities of quantum computers and quantum communication. He discovered that quantum bits, the building blocks of quantum computers, can also be instrumental when used as information carriers. Despite that it was already known that it is impossible to compress a random message into fewer quantumbits than conventional classical bits he showed that some distributing problems can be solved with less quantum communication than classical communication.

One example is the agenda problem, where two parties want to make an appointment and are able to do so with much less quantum than classical communication. An efficient quantum solution of the well-known Doodle.

Dijkstra devised algorithms and applications that could not yet be run on a computer, since they were at that time not available. An example is Dijkstra’s algorithm that calculates the shortest route from A to B. Nowadays, all navigation systems work with a variant of his algorithm. “It is also very important nowadays to already write programs and come up with applications for quantum computers that are not yet here.”

Quantum view