27 June 2022 - Dr. Tom Gur

Speaker

Dr. Tom Gur

Title

Quantum delegation of computation in sublinear-time

Abstract

Suppose we have a quantum computer which is capable of solving problems that are intractable for a classical computer, it is natural to ask whether a classical computer can delegate the computation to the quantum machine and efficiently verify its solution. We will discuss the notion of quantum proofs of proximity, which are protocols that allow a quantum prover to convince a classical verifier of the correctness of the computation in sublinear-time. We will see a concrete example of how to construct such protocols, as well as discuss a paradigm that admits such protocols for large classes of natural problems. The talk is meant for a broad audience, and will not assume quantum/crypto preliminaries.

Paper: Quantum Proofs of Proximity, TQC 2021 https://arxiv.org/pdf/2105.03697.pdf

About the speaker

Dr Gur is Associate Professor in the Department of Computer Science at University of Warwick , with expertise in complexity theory, cryptography, algorithms, coding theory, and learning theory. He has received the Even prize in theoretical computer science and a 7-year UKRI Future Leaders Fellowship.