Quantum algorithms a decade after shor
Abstract
In 1994, Peter Shor discovered a polynomial time quantum algorithm for factoring and discrete logarithm. Two years later, in 1996, Lov Grover discovered a search algorithm which is quadratically better than conventional search. By now, each of the two algorithms has developed into a line of research which goes well beyond the original algorithm. Shor's algorithm has inspired the study of quantum Fourier sampling which has resulted in more quantum algorithms for number-theoretic and group-theoretic problems. Grover's algorithm has developed into the area of quantum query algorithms.I will survey the developments in quantum query algorithms. The topics will include: applications of Grover's algorithm to element distinctness and other problems, lower bounds on quantum algorithms and the use of quantum random walks to design better search algorithm. I will also describe how some of techniques in this area can be used as "quantum black boxes" in an otherwise classical algorithm.