Skip to main content

27 June 2022 - Tom Gur


Tom Gur



Quantum delegation of computation in sublinear-time



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


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.