QLunch: Searching faster using quantum walks

Speaker: Peter Høyer from University of Calgary

Title: Searching faster using quantum walks

Abstract: A quantum walk is a quantum analogue of a random walk. Random walks are commonly used for searching, sampling, and simulations. We give an overview of how quantum walks are used for searching. A search problem may have a unique solution or multiple solutions. The objective of a search is to find and output a solution. We give an optimal quantum walk and an optimal random walk for searching when there is a unique solution. We discuss the challenges in constructing an optimal quantum walk when there are multiple solutions. 

This is based in part on joint work with Dante Bencivenga, Xining Chen, Cătălin Dohotaru, and Mojtaba Komeili.