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.