Quantum Adversary Upper BoundShelby Kimmel
Center for Theoretical Physics, MIT
Tuesday, December 17, 2013 15:00-16:00,
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.
Contact: S. Jordan
Note: Visitors from outside NIST must contact Cathy Graham; (301) 975-3800; at least 24 hours in advance.