LFCS Seminar: Monday, 27 June 2022 - Tom Gur

Note: this is a joint event with the Security, Privacy & Trust seminar: https://www.ed.ac.uk/informatics/blockchain/events/upcoming-events/27-june-2022-tom-gur

Speaker:       Tom Gur, University of Warwick https://www.dcs.warwick.ac.uk/~tomgur/

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  

Bio

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.

Tom Gur, University of Warwick https://www.dcs.warwick.ac.uk/~tomgur/