Le contenu de cette page n’est pas disponible en français. Veuillez nous en excuser.
 

Quantum Adversary (Upper) Bound



Playing this video requires the latest flash player from Adobe.

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


Recording Details

Speaker(s): 
Scientific Areas: 
PIRSA Number: 
13110090

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.