Quantum Adversary Upper Bound

I discuss a technique - the quantum adversary upper bound - that uses the structure of quantum algorithms to gain insight into their performance. Using this bound, I show that there must exist a quantum algorithm for a class of Boolean formulas that uses a constant number of queries. Since the method is non-constructive, it does not give information about the form of the algorithm, but I will outline algorithms that have been found to match the non-constructive bound.

Speaker Bio: Shelby Kimmel is a graduate student in the Center for Theoretical Physics at MIT where her advisor is Eddie Farhi. She is interested in algorithms for quantum computers and in quantum tomography problems.

Note: Visitors from outside NIST must contact Cathy Graham; (301) 975-3800; at least 24 hours in advance.