2014

2015

2016

2017

2018

2019

2020

2022

2023

2024

The thirty-sixth meeting of the Prague computer science seminar

Harry Buhrman

Quantum software with an application to position-based cryptography

Quantum computers hold great promise as the next generation hardware. They are based on counter-intuitive phenomena from quantum mechanics, like superposition, 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.

Annotation Lecturer

2024
2023
2022
2020
2019
2018
2017
2016
2015
2014

Play record

May 24, 2018

4:00pm

Auditorium S5, MFF UK
Malostranské nám. 25, Praha 1
Show on the map

Quantum computers hold great promise as the next generation hardware. They are based on counter-intuitive phenomena from quantum mechanics, like superposition, 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 talk 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 set 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 hoax staged by Hollywood studios here on Earth? Position-based cryptography may offer a solution. This kind of cryptography uses the geographic position of a party as its sole credential instead of digital keys or biometric features.

Harry Buhrman

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 computers, and a framework for the study of quantum query algorithms, which is now textbook 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 processing. Current research interests are: Quantum Computing, Quantum Information Theory, Quantum Cryptography, Computational Complexity Theory, Kolmogorov complexity, Distributed Computing, Computational Learning Theory, and Computational Biology.

Its program consists of a one-hour lecture followed by a discussion. The lecture is based on an (internationally) exceptional or remarkable achievement of the lecturer, presented in a way which is comprehensible and interesting to a broad computer science community. The lectures are in English.

The seminar is organized by the organizational committee consisting of Roman Barták (Charles University, Faculty of Mathematics and Physics), Jaroslav Hlinka (Czech Academy of Sciences, Computer Science Institute), Michal Chytil, Pavel Kordík (CTU in Prague, Faculty of Information Technologies), Michal Koucký (Charles University, Faculty of Mathematics and Physics), Jan Kybic (CTU in Prague, Faculty of Electrical Engineering), Michal Pěchouček (CTU in Prague, Faculty of Electrical Engineering), Jiří Sgall (Charles University, Faculty of Mathematics and Physics), Vojtěch Svátek (University of Economics, Faculty of Informatics and Statistics), Michal Šorel (Czech Academy of Sciences, Institute of Information Theory and Automation), Tomáš Werner (CTU in Prague, Faculty of Electrical Engineering), and Filip Železný (CTU in Prague, Faculty of Electrical Engineering)

The idea to organize this seminar emerged in discussions of the representatives of several research institutes on how to avoid the undesired fragmentation of the Czech computer science community.