- Home »
- Quantum Adversary (Upper) Bound

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.

Collection/Series:

Event Type:

Seminar

Scientific Area(s):

Speaker(s):

Event Date:

Wednesday, November 20, 2013 - 16:00 to 17:30

Location:

Time Room

Room #:

294

©2012 Perimeter Institute for Theoretical Physics