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.

REFERENCES

• 1: Ambainis. Quantum query algorithms and lower bounds, Trends in Logic, to appear. Also available from http://www. cs. berkeley. edu/ ambainis/ps/qs. ps. Surveys results in the field until 2001.
• 2: Andris Ambainis, Polynomial Degree vs. Quantum Query Complexity, Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, p.230, October 11-14, 2003
• 3: A. Ambainis. Quantum walk algorithm for element distinctness. arxiv e-print, http://www. arxiv. org/abs/quant-ph/0311001.
• 4: Harry Buhrman , Ronald de Wolf , Christoph Dürr , Mark Heiligman , Peter Hyer , Frédéric Magniez , Miklos Santha, Quantum Algorithms for Element Distinctness, Proceedings of the 16th Annual Conference on Computational Complexity, p.131, June 18-21, 2001
• 5: G. Brassard, P. Hoyer, M. Mosca, and A. Tapp. Quantum amplitude amplification and estimation. Quantum computation and information (Washington, DC, 2000), volume 305 of Contemporary Mathematics, pages 53--74. AMS, 2002.
• 6: Lov K. Grover, A fast quantum mechanical algorithm for database search, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.212-219, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.237866]
• 7: F. Magniez, M. Santha, and M. Szegedy. Quantum algorithms for the triangle problem. arxiv e-print, http://www. arxiv. org/abs/quant-ph/0310134.