Date & Time: Thursday, March 28, 2013, 10:00-11:00
Venue: Ramanujan Hall
Title: Helping quantum computers classically
Speaker:Dr.Rajat Mittal, Institute for Quantum Computing, University of Waterloo
Abstract:In 1981, Richard Feynman gave the idea that quantum mechanical phenomena can be used to do computing. With the arrival of Shor's factoring algorithm and Grover's search algorithm, it became clear that this new computational model can give rise to much faster algorithms. Many of these speedups have been shown in the particular resource model called quantum query complexity.
The talk will focus on characterization of quantum query complexity using semidefinite programming. The characterization achieves two purposes. First, we can infer a lot about query complexity using properties of cone programming. Secondly, it gives us a classical approach for designing quantum query algorithms. In this talk, I will elaborate more on the second aspect and show various combinatorial and algebraic tools to construct quantum algorithms.