Seminar by Rajat Mittal

Helping Quantum Computers Classically

Rajat Mittal
Univ. of Waterloo

    Date:    Tuesday, April 2nd, 2013
    Time:    5PM
    Venue:   CS102.

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.

Back to Seminars in 2012-13