Massachusetts Institute of Technology (MIT)
Talks by Shelby Kimmel
I will answer the question in the title. I will also describe a new quantum algorithm for Boolean formula evaluation and an improved analysis of an existing quantum algorithm for st-connectivity. Joint work with Stacey Jeffery.
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.
We can prove that for certain problems, quantum computers do better than classical computers. I will introduce the query complexity framework, which lets us compare classical and quantum computers, and then describe a problem where quantum computers do better than classical. The problem I will discuss is evaluating boolean trees with a promise on the input.