Controlled quantum operators can search

Peter Høyer - University of Calgary
 

We give a framework for studying arbitrary quantum operators that are being controlled by an ancilla. We show that controlled quantum operators can be used for searching. Controlled quantum operators can simulate existing search methods such as Grover's algorithm, amplitude amplification, quantum interpolated walks, and Szegedy's and Ambainis's quantum walks.

We apply the framework to quantum walks. We give the first known quantum algorithm for finding a unique solution that is quadratically faster  than a random walk in both the update and checking costs. We give an improved classical random walk as well. We define a new notion of quantum hitting time, which we use to prove our results.

Based on joint work with Cătălin Dohotaru.