University of Tartu - ©2011 Rafik Chaabouni - Last update: 16.12.2012 02:50
Date: 19/12/2012 Location: J. Liivi 2, room 317 (next to the coffee room)
Speaker: Aleksandrs Belovs (Invited speaker)
Title: Learning graphs and quantum query algorithms
Abstract:
Query complexity is one of the most popular complexity measures of quantum algorithms, mostly because of the existence of powerful tools for proving upper and lower bounds. One of these tools is the adversary bound. Stated as a semi-definite program, it serves as both upper and lower bound for quantum query complexity. In this talk, we describe a recent framework of learning graphs for proving upper bounds using the adversary method, and survey its applications.