Multidimensional Quantum Walks

Math/CS Seminar featuring Sebastian Zur (CWI, Amsterdam)

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)

Join Zoom Meeting
https://uwaterloo.zoom.us/j/95752336824?pwd=aWVwYzFQUnZ1NHRWT2VtVmRndVpIQT09

Meeting ID: 957 5233 6824
Passcode: 091266