Institute for Quantum Information Seminar

I'll talk about a new framework for designing quantum algorithms that extends the quantum walk framework of Magniez, Nayak, Roland, and Santha, by utilizing the idea of quantum data structures to construct an efficient method of nesting quantum walks.  The new framework extends the known quantum walk framework while retaining its advantages: simplicity, ease of use, and a straightforward understanding of all resources used by the algorithm, such as queries, time or space.

The new framework is also powerful.  In particular, the recently proposed learning graph framework of Belovs has yielded improved upper bounds for several problems, including the triangle finding problem and more general subgraph detection problems.  I will exhibit the power of the new framework by giving simple explicit constructions that reproduce both the O(n^{35/27}) and O(n^{9/7}) learning graph upper bounds (up to logarithmic factors) for triangle finding.

This is joint work with Stacey Jeffery and Frédéric Magniez.