**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.