The Taub Faculty of Computer Science Events and Talks

From carefully crafted quantum algorithms to information-theoretic security in cryptography, a quantum computer can achieve impressive feats with no classical analogue. Can their correct realization be verified? When the power of the device greatly surpasses that of the user, computationally as well as cryptographically, what means of control remain available to the user? Recent lines of work in quantum cryptography and complexity develop approaches to this question based on the notion of an interactive proof. Generally speaking an interactive proof models any interaction whereby a powerful device aims to convince a restricted user of the validity of an agree-upon statement -- such as that the machine generates perfect random numbers or executes a specific quantum algorithm. Two models have emerged in which large-scale verification has been shown possible: either by placing reasonable computational assumptions on the quantum device, or by requiring that it consists of isolated components across which Bell tests can be performed. In the talk I will discuss recent advances on the verification power of interactive proof systems between a quantum device and a classical user, focusing on the certification of quantum randomness from a single device, under cryptographic assumptions. Bio: Thomas Vidick is professor of Computer Science at the Weizmann Institute of Science, which he joined in 2022. Between 2014 and 2022 he was Assistant Professor, and then Professor, at the California Institute of Technology. Prior to joining Caltech, Vidick earned a B.A. in pure mathematics from Ecole Normale Superieure in Paris, a Masters in Computer Science from Universite Paris 7 and a Ph.D. from UC Berkeley. In 2020-2022 he was a postdoctoral scholar at the Massachusetts Institute of Technology, supervised by Scott Aaronson. Vidick's Ph.D. thesis was awarded the Bernard Friedman memorial prize in applied mathematics. In 2017 he was named a CIFAR Azrieli Global Scholar. In 2019 he received a Presidential Early-Career Award (PECASE). In 2021 he was named a Simons Investigator, and in 2023 he was awarded the Held prize from the US National Academy of Sciences. Vidick's research is situated at the interface of theoretical computer science, quantum information and cryptography. He has investigated the role of entanglement in multiprover interactive proof systems and in quantum cryptography, making important contributions to both areas.