Speaker: Peter Høyer
91. Efficient quantum walk on the grid with multiple marked elements 2. Controlled quantum amplification
"1. We give a quantum algorithm for finding a marked element on the grid when there are multiple marked elements. Our algorithm uses quadratically fewer steps than a random walk on the grid, up to a logarithmic factor. This is the first known quantum walk that finds a marked element in a number of steps less than the square-root of the extended hitting time. We also give a new tighter upper bound on the extended hitting time of a marked subset, expressed in terms of the hitting times of its members. 2. We propose a new framework for turning quantum search algorithms that decide into quantum algorithms for finding a solution. Consider we are given an abstract quantum search algorithm A that can determine whether a target g exists or not. We give a general construction of another operator U that both determines and finds the target, whenever one exists. Our amplification method at most doubles the cost over using A, has little overhead, and works by controlling the evolution of A. This is the first known general framework to the open question of turning abstract quantum search algorithms into quantum algorithms for finding a solution.
We next apply the framework to quantum walks. We show that it finds a unique marked element quadratically faster than the classical hitting time H for any reversible walk. We show that the framework can simulate Grover’s search algorithm, amplitude amplification, and interpolated quantum walks. We use the framework to prove a relation between the quantum walk operator W and the search operator A. We use this relation to give a quantum algorithm that, up to logarithmic factors, finds a unique marked element using sqrt(H) checking operations and sqrt(1/eps) update operations, where eps is the probability that the stationary distribution is in the marked state. This is superior to existing algorithms. We also give a new classical random walk that finds a unique marked element using H update operations and 1/eps checking operations. Our classical algorithm is derived via quantum arguments."