PIRSA Logo


PERIMETER INSTITUTE RECORDED SEMINAR ARCHIVE

Pirsa: 13110090 - Quantum Adversary (Upper) Bound

Speaker(s):

Shelby Kimmel

Playing this video requires MP4 / H.264 support to be configured and enabled in your browser.

Download link (right click and 'save-as') for playing in VLC or other compatible player.

Download Video

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.
Valid XHTML 1.0!