7 September 2006, PhD defense, Robert Spalek

In this thesis, we investigate fast quantum algorithms for several graph problems (such as finding a maximal bipartite matching, and a maximal flow in an integer network) and verification of matrix products. We also address quantum query lower bounds, i.e. proofs that certain tasks cannot be computed faster than some value. We prove the first known time-space tradeoffs for quantum computation, and most of them are tight.

For more information, see http://www.ucw.cz/~robert/papers/abs-phd-en.html