Quantum search algorithms

ABSTRACT

We review some of quantum algorithms for search problems: Grover's search algorithm, its generalization to amplitude amplification, the applications of amplitude amplification to various problems and the recent quantum algorithms based on quantum walks.

REFERENCES

• 1: Scott Aaronson, Lower bounds for local search by quantum arguments, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, p.465-474, June 13-16, 2004, Chicago, IL, USA [doi>10.1145/1007352.1007358]
• 2: Scott Aaronson , Andris Ambainis, Quantum Search of Spatial Regions, Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, p.200, October 11-14, 2003
• 3: D. Aldous. Minimization algorithm and random walk on the d-cube. Annals of Probability, 11(2):403--413, 1983.
• 4: Andris Ambainis, Quantum lower bounds by quantum arguments, Journal of Computer and System Sciences, v.64 n.4, p.750-767, June 2002 [doi>10.1006/jcss.2002.1826]
• 5: A. Ambainis. Quantum walk algorithm for element distinctness. quant-ph/03110001.
• 6: A. Ambainis. Quantum walks and their algorithmic applications. quant-ph/0403120.
• 7: A. Ambainis, J. Kempe, A. Rivosh. Coins make quantum walks faster. quant-ph/0402107.
• 8: Charles H. Bennett , Ethan Bernstein , Gilles Brassard , Umesh Vazirani, Strengths and Weaknesses of Quantum Computing, SIAM Journal on Computing, v.26 n.5, p.1510-1523, Oct. 1997 [doi>10.1137/S0097539796300933]
• 9: Robert Beals , Harry Buhrman , Richard Cleve , Michele Mosca , Ronald de Wolf, Quantum lower bounds by polynomials, Journal of the ACM (JACM), v.48 n.4, p.778-797, July 2001 [doi>10.1145/502090.502097]
• 10: P. Benioff. Space searches with a quantum robot. In Quantum computation and information (Washington, DC, 2000), volume 305 of AMS Series on Contemporary Mathematics, pp. 1--12. Also quant-ph/0003006.
• 11: M. Boyer, G. Brassard, P. Høyer, A. Tapp. Tight bounds on quantum searching. Fortsch. Phys. 46:493--506, 1998. Also quant-ph/9605034.
• 12: Gilles Brassard , Peter Høyer , Alain Tapp, Quantum Cryptanalysis of Hash and Claw-Free Functions, Proceedings of the Third Latin American Symposium on Theoretical Informatics, p.163-169, April 20-24, 1998
• 13: Gilles Brassard , Peter Høyer , Alain Tapp, Quantum Counting, Proceedings of the 25th International Colloquium on Automata, Languages and Programming, p.820-831, July 13-17, 1998
• 14: G. Brassard. P. Høyer, M. Mosca, A. Tapp. Quantum amplitude amplification and estimation. Quantum Computation and Quantum Information Science, AMS Contemporary Math Series, vol. 305, pp. 53--74. Also quant-ph/0005055.
• 15: 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
• 16: H. Buhrman, R. Spalek. manuscript, 2003.
• 17: Harry Buhrman , Ronald de Wolf, Complexity measures and decision tree complexity: a survey, Theoretical Computer Science, v.288 n.1, p.21-43, 9 October 2002 [doi>10.1016/S0304-3975(01)00144-X]
• 18: A. M. Childs and J. M. Eisenberg. Quantum algorithms for subset finding. quant-ph/0311038.
• 19: C. Dürr, P. Høyer. A quantum algorithm for finding the minimum. quant-ph/9607014.
• 20: C. Dürr, M. Heiligman, P. Høyer, M. Mhalla. Quantum query complexity of some graph problems. quant-ph/0401091.
• 21: E. Farhi, J. Goldstone, S. Gutmann, J. Lapan, A. Lundgren and D. Preda, A quantum adiabatic evolution algorithm applied to random instances of an NP-complete problem, Science 292, 472 (2001), quant-ph/0104129.
• 22: 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]
• 23: Lov K. Grover, A framework for fast quantum mechanical algorithms, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.53-62, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276712]
• 24: P. Høyer, J. Neerbek, Y. Shi. Quantum complexities of ordered searching, sorting, and element distinctness. Algorithmica, 34(4): 429--448, 2002. Also quant-ph/0102078.
• 25: Thomas Hofmeister , Uwe Schöning , Rainer Schuler , Osamu Watanabe, A Probabilistic 3-SAT Algorithm Further Improved, Proceedings of the 19th Annual Symposium on Theoretical Aspects of Computer Science, p.192-202, March 14-16, 2002
• 26: J. Kempe. Quantum random walks - an introductory overview, Contemporary Physics, 44 (4):307--327, 2003. Also quant-ph/0303081.
• 27: F. Magniez, M. Santha, and M. Szegedy. Quantum algorithms for the triangle problem. quant-ph/0310134.
• 28: G. Midrijānis. Exact quantum query complexity for total Boolean functions. quant-ph/0403168.
• 29: Ashwin Nayak , Felix Wu, The quantum query complexity of approximating the median and related statistics, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.384-393, May 01-04, 1999, Atlanta, Georgia, United States [doi>10.1145/301250.301349]
• 30: Quantum computation and quantum information, Cambridge University Press, New York, NY, 2000
• 31: D. Rolf. 3 -- SAT ε RT IM E(1.32971n). Diploma thesis, Humboldt-Universität zu Berlin, 2003.
• 32: T. Rudolph, L. Grover. How significant are the known collision and element distinctness quantum algorithms? quant-ph/0309123.
• 33: Uwe Schöning, A Probabilistic Algorithm for k-SAT and Constraint Satisfaction Problems, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.410, October 17-18, 1999
• 34: Yaoyun Shi, Quantum Lower Bounds for the Collision and the Element Distinctness Problems, Proceedings of the 43rd Symposium on Foundations of Computer Science, p.513-519, November 16-19, 2002
• 35: Peter W. Shor, Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer, SIAM Journal on Computing, v.26 n.5, p.1484-1509, Oct. 1997 [doi>10.1137/S0097539795293172]
• 36: M. Szegedy. Spectra of quantized walks and a √Δε rule, quant-ph/0401053.
• 37: C. Zalka. Grover's quantum searching algorithm is optimal. Physical Review A, 60:27462751, 1999. Also quant-ph/9711070.