Stanford Security Lunch

Abstract: In 2018, Urmila Mahadev gave the first protocol by which a classical computer can efficiently verify the outcome of a quantum computation, under standard cryptographic hardness assumptions. This breakthrough sparked a growing body of work on classical verification of quantum computations, including simpler protocols, new applications, and limitations on what such protocols can achieve. This talk will provide a high-level introduction to the field of classical verification of quantum computation. We will discuss existing approaches as well as open problems. Finally, we will turn to qubit tests: classical protocols that certify the presence of non-commuting quantum measurements, which play a central role in existing verification methods. We will present recent work showing that canonical forms of qubit tests imply strong cryptographic primitives, providing evidence that such protocols require substantial cryptographic structure. No background in quantum computing will be assumed.

Bio: Itay Shalit is a first-year Computer Science PhD student at Stanford University. His research interests lie in cryptography and complexity theory, particularly at their intersection with quantum computing.