GIULIO MALAVOLTA: Efficient Verification of Quantum Computation

Seminars - Occasional seminars
GIULIO MALAVOLTA, Max Planck Institute for Security and Privacy, Bochum
12:00 - 13:00
Room 3-E4-SR03 (Rontgen) / Zoom



Can the result of a quantum computation be verified more efficiently than redoing the computation from scratch? 


In this talk we describe how, using suitable cryptographic tools, one can verify the validity of any quantum computation in time poly-logarithmic in the runtime of the original computation. Furthermore, the verification procedure is entirely classical. As a central technical ingredient, we develop a complete “Heisenberg-like” proof of soundness for a protocol to classically verify quantum operations. 


We then discuss the computational assumptions needed for constructing the necessary cryptographic machinery, and we outline some outstanding open problems that remain.


Based on the following work: (Crypto’22).