Please join us on Wednesday, November 20 at 4pm in the Time room for a quantum information seminar by Shelby Kimmel.
Title: Quantum Adversary (Upper) Bound
Speaker: Shelby Kimmel (MIT)
Abstract: I discuss a technique - the quantum adversary upper bound - that uses the structure of quantum algorithms to gain insight into the quantum query complexity of Boolean functions. Using this bound, I show that there must exist an algorithm for a certain Boolean formula that uses a constant number of queries. Since the method is non-constructive, it does not give information about the form of the algorithm. After describing the technique and applying it to a class of functions, I will outline quantum algorithms that match the non-constructive bound.
Date: Wednesday, November 20, 2013.Time: 16:00Location: Time room (294)-Gus