Multidimensional Quantum Walks

What is it about?

We study algorithms for quantum computers, aiming for a speedup in asymptotic runtime compared to conventional computers. One approach considers quantum walk frameworks, which make it easy to design quantum algorithms because of their relation to classical random walks, which are quite intuitive in use. As a result quantum walk algorithms have been widely applied in many domains, but they do come with a drawback: the existing frameworks can achieve at most a quadratic speedup over the best classical random walk. In this work, we generalise the current most powerful (discrete) quantum walk frameworks, into a new framework. This new framework still maintains the the original classical walk intuition and we use this to create the current fastest algorithm to decide whether an list of integers contains multiple copies of the same integer. We also apply this to a contrived graph problem where we show an exponential speed up, which shows that our discrete quantum walks can in fact exhibit exponential speed ups.

Featured Image

Photo by Michael Dziedzic on Unsplash

Photo by Michael Dziedzic on Unsplash

Why is it important?

When we create quantum algorithms, our goal is to make them as fast as possible compared to their classical counterparts, hopefully even achieving an exponential speed up. Whenever such a big speed up is achieved, it is therefore very relevant to see if we can learn from it and whether it can help us to find such speed ups for other problems. In that perspective, our framework is a step in the right direction, as it gives an exponential speed up originating from an intuitive framework, meaning that it is a good contender to try and find more such speedups.