A. Ambainis
Skip Abstract Section
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.
- S. Aaronson. Lower bounds for local search by quantum arguments. Proceedings of STOC'04, to appear, also quant-ph/0307149. Google Scholar
Digital Library
- S. Aaronson and A. Ambainis. Quantum search of spatial regions. In Proceedings of FOCS'03, pp. 200--209, 2003. Also quant-ph/0303041. Google ScholarDigital Library
- D. Aldous. Minimization algorithm and random walk on the d-cube. Annals of Probability, 11(2):403--413, 1983.Google ScholarCross Ref
- A. Ambainis. Quantum lower bounds by quantum arguments. Journal of Computer and System Sciences, 64(4): 750--767, 2002. Also STOC'00 and quant-ph/0002066. Google ScholarDigital Library
- A. Ambainis. Quantum walk algorithm for element distinctness. quant-ph/03110001.Google Scholar
- A. Ambainis. Quantum walks and their algorithmic applications. quant-ph/0403120.Google Scholar
- A. Ambainis, J. Kempe, A. Rivosh. Coins make quantum walks faster. quant-ph/0402107. Google ScholarDigital Library
- C. Bennett, E. Bernstein, G. Brassard, U. Vazirani. Strengths and weaknesses of quantum computing. SIAM Journal of Computing, 26(5): 1510--1523, 1997. Also quant-ph/9701001. Google ScholarDigital Library
- R. Beals, H. Buhrman, R. Cleve, M. Mosca, R. de Wolf. Quantum lower bounds by polynomials. Journal of the ACM, 48(4): 778--797, 2001. Also FOCS'98 and quant-ph/9802049. Google ScholarDigital Library
- 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.Google Scholar
- M. Boyer, G. Brassard, P. Høyer, A. Tapp. Tight bounds on quantum searching. Fortsch. Phys. 46:493--506, 1998. Also quant-ph/9605034.Google ScholarCross Ref
- G. Brassard, P. Høyer, A. Tapp. Quantum cryptanalysis of hash and claw-free functions. Proceedings of LATIN'98, pp. 163--169. Also quant-ph/9705002. Google ScholarDigital Library
- G. Brassard, P. Høyer, A. Tapp. Quantum counting. Proceedings of ICALP'98, pp. 820--831. Also quant-ph/9805082. Google ScholarDigital Library
- 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.Google ScholarCross Ref
- H. Buhrman, C. Dürr, M. Heiligman, P. Høyer, F. Magniez, M. Santha, R. de Wolf. Quantum algorithms for element distinctness. Proceedings of Complexity'01, pp. 131--137. Also quant-ph/0007016. Google ScholarDigital Library
- H. Buhrman, R. Spalek. manuscript, 2003.Google Scholar
- H. Buhrman, R. de Wolf. Complexity measures and decision tree complexity: a survey. Theoretical Computer Science, 288:21--43, 2002. Google ScholarDigital Library
- A. M. Childs and J. M. Eisenberg. Quantum algorithms for subset finding. quant-ph/0311038. Google ScholarDigital Library
- C. Dürr, P. Høyer. A quantum algorithm for finding the minimum. quant-ph/9607014.Google Scholar
- C. Dürr, M. Heiligman, P. Høyer, M. Mhalla. Quantum query complexity of some graph problems. quant-ph/0401091.Google Scholar
- 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.Google ScholarCross Ref
- L. Grover. A fast quantum mechanical algorithm for database search. In Proceeding of STOC'96, pp. 212--219. Also quant-ph/9605043. Google ScholarDigital Library
- L. Grover. A framework for fast quantum mechanical algorithms. Proceedings of STOC'98, pp. 53--62. Also quant-ph/9711043. Google ScholarDigital Library
- 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.Google ScholarCross Ref
- T. Hofmeister, U. Schöning, R. Schuler, O. Watanabe. A probabilistic 3-SAT algorithm further improved. Proceedings of STACS'02, pp. 192--202. Google ScholarDigital Library
- J. Kempe. Quantum random walks - an introductory overview, Contemporary Physics, 44 (4):307--327, 2003. Also quant-ph/0303081.Google ScholarCross Ref
- F. Magniez, M. Santha, and M. Szegedy. Quantum algorithms for the triangle problem. quant-ph/0310134. Google ScholarDigital Library
- G. Midrijānis. Exact quantum query complexity for total Boolean functions. quant-ph/0403168.Google Scholar
- A. Nayak, F. Wu. The quantum query complexity of approximating the median and related statistics. Proceedings of STOC'99, pp. 384--393. Also quant-ph/9804066. Google ScholarDigital Library
- M. Nielsen, I. Chuang. Quantum Computation and Quantum Information, Cambridge University Press, 2000. Google ScholarDigital Library
- D. Rolf. 3 -- SAT ε RT IM E(1.32971n). Diploma thesis, Humboldt-Universität zu Berlin, 2003.Google Scholar
- T. Rudolph, L. Grover. How significant are the known collision and element distinctness quantum algorithms? quant-ph/0309123. Google ScholarDigital Library
- U. Schöning. A probabilistic algorithm for k-SAT and constraint satisfaction problems. Proceedings of FOCS'99, pp. 410--414. Google ScholarDigital Library
- Y. Shi. Quantum lower bounds for the collision and the element distinctness problems. Proceedings of FOCS'02, pp. 513--519. Also quant-ph/0112086. Google ScholarDigital Library
- P. Shor. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Journal on Computing, 26(5): 1484--1509, 1997. Also FOCS'94. Google ScholarDigital Library
- M. Szegedy. Spectra of quantized walks and a √Δε rule, quant-ph/0401053.Google Scholar
- C. Zalka. Grover's quantum searching algorithm is optimal. Physical Review A, 60:27462751, 1999. Also quant-ph/9711070.Google ScholarCross Ref
Index Terms
- Quantum search algorithms
Index terms have been assigned to the content through auto-classification.
Recommendations
A review on quantum search algorithms
The use of superposition of states in quantum computation, known as quantum parallelism, has significant advantage in terms of speed over the classical computation. It is evident from the early invented quantum algorithms such as Deutsch's algorithm, ...
Photonic scheme of quantum phase estimation for quantum algorithms via quantum dots
AbstractVarious quantum algorithms depend on quantum phase estimation (QPE) as basic blocks or main subroutines to leverage superposition and entanglement during quantum computations. The QPE algorithm estimates the unknown phase of an eigenvalue ...
Comments