QuICS Special Seminar: Sebastian Zur

Mon, Jun 12, 2023 3:00 pm - 4:00 pm


Title:  Multidimensional Quantum Walks
Speaker:  Sebastian Zur (CWI)
Time:  Monday, June 12, 2023 - 3:00pm
Location:  ATL 3100A and Virtual Via Zoom: https://umd.zoom.us/j/97019450095?pwd=Z1JZZzVyY2Zsa0MwM004THlXVUJSZz09

While quantum walk frameworks make it easy to design quantum algorithms, as evidenced by their wide application across domains, the major drawback is that they can achieve at most a quadratic speedup over the best classical algorithm.  In this work, we generalise the electric network framework – the most general of quantum walk frameworks, into a new framework that we call the multidimensional quantum walk framework, which no longer suffers from the aforementioned drawback, while still maintaining the original classical walk intuition. We then apply this framework to the k-distinctness problem, to obtain a time complexity that matches the currently best known query complexity by Belovs(2012), as well as to the welded trees problem, where we can solve the problem in a linear number of queries.

This talk will focus on the application to welded trees.

Joint work with Stacey Jeffery (2208.13492)