ITLApplied  Computational Mathematics Division
ACMD Seminar Series
Attractive Image NIST
 
Up


Quantum Adversary Upper Bound

Shelby Kimmel
Center for Theoretical Physics, MIT

Tuesday, December 17, 2013 15:00-16:00,
Building 225, Room B111
Gaithersburg
Tuesday, December 17, 2013 13:00-14:00,
Room 1-4058
Boulder

Abstract:

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.



Privacy Policy | Disclaimer | FOIA
NIST is an agency of the U.S. Commerce Department.
Last updated: 2013-12-04.
Contact