Testing quantum systems in the high-complexity regime
Abstract: 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 results 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 (arXiv:1804.00640) and the verification of arbitrarily complex computations using two devices (arXiv:2001.04383).
Bio: Thomas Vidick is Professor of Computing and Mathematical Sciences at the California Institute of Technology. He received a B.A. in pure mathematics from École Normale Supérieure in Paris, a Masters in Computer Science from Université Paris 7 and a Ph.D. from UC Berkeley. His Ph.D. thesis was awarded the Bernard Friedman memorial prize in applied mathematics. Before joining Caltech he was a postdoctoral associate at the Massachusetts Institute of Technology. His paper “A multi-prover interactive proof for NEXP sound against entangled provers”, with Tsuyoshi Ito, was co-awarded the best paper award at FOCS’12. His is the recipient of a Presidential Early-Career Award (PECASE, 2019), an FSMP research chair (2020) and a Simons Investigator Award (2021-). Vidick's research is situated at the interface of theoretical computer science, quantum information and cryptography. He is interested in applying techniques from computer science, such as complexity theory, to study problems in quantum computing. He is most well-known for his work on the study of entanglement in interactive proof systems, through the complexity class MIP*. He made multiple contributions to quantum cryptography, including the first proof of security of device-independent quantum key distribution. He is also known for developing the first polynomial-time algorithm for computing ground states of gapped one-dimensional quantum spin systems.
To watch online go to the IQUIST youtube channel: https://www.youtube.com/channel/UCCzAySwQXF8J4kRolUzg2ww
For Zoom link you may check the IQUIST calendar weekly email or contact Hannah Stites (firstname.lastname@example.org). To subscribe to our weekly email for event announcements, please go to https://lists.illinois.edu/lists/subscribe/iquist-announcements.