Shalev Ben-David: Thesis Defense: Quantum Speedups in Query Complexity
Speaker: Shalev Ben-David
Host: Scott Aaronson
Date: Thursday, June 29, 2017
Time: 3:00 PM to 4:30 PM
Refreshments Time: 2:45 PM
Location: G575
Abstract:
In this thesis, we study randomized and quantum algorithms in the query complexity model.
We investigate when and by how much quantum algorithms provide a speedup over the best
possible classical algorithm in the query complexity setting.
We introduce a total Boolean function that exhibits a power 2.5 quantum speedup compared
to the best possible randomized algorithm. In the process, we introduce the "cheat
sheet" method for turning partial Boolean functions into total Boolean functions, and
examine some of its other applications.
We also study lower bound techniques for randomized algorithms. We introduce a measure
called randomized sabotage complexity which lower bounds randomized query complexity
and behaves well under compositions. This tool for controlling the randomized query
complexity of composed functions combines nicely with the cheat sheet technique, which
often features composed functions in its applications.
Finally, we characterize the total Boolean functions that exhibit exponential quantum
speedups when their domain is restricted to an arbitrarily chosen set. We show that such a
"sculpting" of a quantum speedup is possible if and only if the original total
function has many inputs with large certificate complexity. Along the way, we also show
that functions defined on very small domains or that are very unbalanced can display at
most a quadratic quantum speedup.
Advisor: Scott Aaronson
Committee Members: Aram Harrow and Ryan Williams
Relevant URL:
For more information please contact: Deborah Goodwin, 617.324.7303, <a
href="mailto:dlehto@csail.mit.edu">dlehto@csail.mit.edu</a>
_______________________________________________
qip mailing list
qip(a)mit.edu
http://mailman.mit.edu/mailman/listinfo/qip