Harry Buhrman presents Quantum software with an application to position-based cryptography

On 2018-05-24 16:00:00 at S5, MFF UK Malostranske nam. 25, Prague 1
36. Prague Computer Science Seminar


Quantum computers hold great promise as the next generation hardware. They are
based on counter-intuitive phenomena from quantum mechanics, like
interference, and entanglement. The basic building block of a quantum computer
is a quantum bit or qubit, which unlike a classical bit can be in a quantum
superposition (a simultaneous combination) of both 0 and 1. In the 1990s it was
demonstrated that, for specific problems, quantum algorithms run on a quantum
computer can massively outperform classical computers. The famous quantum
algorithm of Peter Shor shows that a quantum computer can factor large numbers
and thus can break most of modern-day cryptography. Recent years have witnessed
important breakthroughs in the development of the hardware for a quantum
computer. IBM announced a 50 qubit machine and google recently advertised a 72
qubit device. With this growth rate we will have 100 -200 qubits within five
years and large-scale quantum computers are expected within 5-10 years.

What can we compute on a quantum computer and how can it be useful? In this
I will give a short introduction to quantum computing and quantum software and
will highlight an application to cryptography. On 20 July 1969, millions of
people held their breath as they watched, live on television, Neil Armstrong
foot on the Moon. Yet Fox Television has reported that a staggering 20 % of
Americans have had doubts about the Apollo 11 mission. Could it have been a
staged by Hollywood studios here on Earth? Position-based cryptography may
a solution. This kind of cryptography uses the geographic position of a party
its sole credential instead of digital keys or biometric features.


Harry Buhrman is a professor of algorithms, complexity theory, and quantum
computing at the University of Amsterdam (UvA), group leader of the Quantum
Computing Group at the Center for Mathematics and Informatics (CWI), and
executive director of QuSoft, a research center for quantum software, which he
co-founded in 2015. He built the quantum computing group at CWI, which was one
of the first groups worldwide and the first in the Netherlands working on
quantum information processing. Buhrman’s research focuses on quantum
computing, algorithms, and complexity theory. He co-developed the area of
quantum communication complexity (distributed computing), and demonstrated for
the first time that certain communication tasks can be solved (exponentially)
more efficiently with quantum resources. This showed that quantum computers can
not only speed up computation, but also communication – which opened up a
whole new application area of quantum information processing. Buhrman
co-developed a general method to establish the limitations of quantum
and a framework for the study of quantum query algorithms, which is now
material. He obtained a prestigious Vici-award and has coordinated several
national and international quantum computing projects. He is a member of the
Scientific Advisory Board of QUTE-EUROPE and QUIE2T (European) and of CIFAR,
IQC, INTRIQUE (Canadian). He started and chaired the first steering committee
for QIP, the main international conference on quantum information
Current research interests are: Quantum Computing, Quantum
Information Theory, Quantum Cryptography, Computational Complexity Theory,
Kolmogorov complexity, Distributed Computing, Computational Learning Theory,
Computational Biology.
Responsible person: Petr Pošík