Distinguished CS Colloquium Talk by Prof. Harry Buhrman on Nov 15th

Title: Quantum Position Verification, Quantum Nonlocal Computation, and Surprising Connections with Holography and classical cryptography

Speaker: Prof. Harry Buhrman, University of Amsterdam and CWI

When: Wednesday, November 15, 2023 @ 11am 
Where: CDS 1750

Quantum position verification (QPV) plays a crucial role in secure quantum communication and nonlocal quantum computation. It ensures that a party involved in a communication protocol is at its claimed location, which is essential for secure communication, distributed computing, and location-based services. In 2012, we established a tight connection between the security of QPV schemes and the entanglement usage in quantum nonlocal computation. Quantum nonlocal computation is the task of performing a unitary operation U on a bipartite quantum state φ_AB held by two parties, Alice and Bob. They can simultaneously send a single message to each other, after which they should hold the state ψ_AB = Uφ_AB. It is always possible to apply U in this manner, but the entanglement usage for arbitrary U’s remains unknown. The best known upper bound is exponential, while the best known lower bound is linear. In this talk, we will discuss recent advances and surprising connections with other fields, such as holography, functional analysis, and classical primitives like conditional disclosure of secrets (CDS) and secure message passing (SMP). This work is joint work  with Rene Allerstorfer, Florian Speelman, Philip Verduyn Lunel, and Alex May.

Harry Buhrman is 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 founding executive director of QuSoft, a research center for quantum software, which he co-founded in 2015. In 2020 he was elected as a member of the Royal Netherlands Academy of Arts and Sciences. 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 efficient with quantum resources. This showed that quantum computers can not only speed up computations, 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 the Max Planck Institute for quantum optics, WACQT (Sweden), and IQC (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.