Problems in Quantum Computational Complexity

November 19, 2008 - 5:10-5:35pm

RLE Conference Center 36-428

Abstract

In 1994 Peter Shor discovered efficient quantum computer algorithms for factoring integers and computing discrete logarithms -- problems that are conjectured not to be efficiently solvable using ordinary classical computers. These algorithms are the most well-known among several examples that suggest quantum information has a profound effect on the general notion of computational difficulty. Quantum computational complexity studies this topic in a variety of settings that include concepts of efficient quantum computations, quantum proofs, quantum interactions of various types, and their relationships to analogous classical concepts. In this talk I will discuss some current topics of research in quantum computational complexity, with a focus on a selection of open problems within these topics.

Bio

John Watrous is an Associate Professor in the School of Computer Science, and a member of the Institute for Quantum Computing, at the University of Waterloo. He is a Fellow of the Canadian Institute for Advanced Research, and is an affiliate member of the Perimeter Institute for Theoretical Physics. Dr. Watrous's research focuses on the theory of quantum information and its applications to complexity theory, algorithms, and theoretical cryptography. Specific topics of his research include quantum interactive proof systems and zero-knowledge, quantum variants of random walks and Markov chains, and the theory of entanglement.