Umesh Vazirani, Roger A. Strauch Professor of EECS, UC Berkeley
Quantum mechanics poses two novel challenges to the testing of quantum systems: a) The exponential computational power of quantum systems creates a great asymmetry between the system being tested and the (classical) experimentalist. b) Holevo's theorem imposes a severe constraint on the information about the system that can be accessed by the experimentalist. Indeed, one can even ask whether this poses a fundamental obstacle to the scientific method in this regime. After all how can one verify that the outcome of an experiment is consistent with the theory if the prediction takes exponential time to compute?
The theory of interactive proofs from computational complexity theory provides a beautiful way of getting around some of these obstacles. In addition to describing the basic principles behind this approach, I will also talk more generally about testing untrusted quantum devices in contexts such as certifiable random number generation and secure quantum cryptography.