Quantum Walk Based Search Algorithms
Open accessThe DOI matches its Crossref record; 11 of the 11 references it cites were found in a registry or an index.
Abstract
In this survey paper we give an intuitive treatment of the discrete time quantization of classical Markov chains. Grover search and the quantum walk based search algorithms of Ambainis, Szegedy and Magniez et al. will be stated as quantum analogues of classical search procedures. We present a rather detailed description of a somewhat simplified version of the MNRS algorithm. Finally, in the query complexity model, we show how quantum walks can be applied to the following search problems: Element Distinctness, Matrix Product Verification, Restricted Range Associativity, Triangle, and Group Commutativity.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
A fast quantum mechanical algorithm for database search
Grover, L. K. (1996) · Proceedings of the twenty-eighth annual ACM symposium on Theory of computing - STOC '96 · doi:10.1145/237814.237866 · Cited by 8,830
Quantum amplitude amplification and estimation
Brassard, G., Høyer, P., Mosca, M., & Tapp, A. (2002) · Contemporary Mathematics · doi:10.1090/conm/305/05215 · Cited by 1,680 · cited 1×
“Grover search [16], and in general amplitude amplification [ 11 ] are well known quantum procedures which are provably faster than their classical counterpart.”
BackgroundStrengths and Weaknesses of Quantum Computing
Bennett, C. H., Bernstein, E., Brassard, G., & Vazirani, U. (1997) · SIAM Journal on Computing · doi:10.1137/s0097539796300933 · Cited by 1,470 · cited 1×
“…algorithm is the following simple procedure that satisfies the conditions of Theorem 5, but with a slightly higher complexity, of the order of S + [10,36], that | ψ i − | φ i ≤ O ( i 2 − k ). constant when k This implies that | ψ k i−| φ k is an arbitrarily small is chosen to be O(log(1 / √ ε ))…”
MethodQuantum random walks: An introductory overview
Kempe, J. (2003) · Contemporary Physics · doi:10.1080/00107151031000110776 · Cited by 1,413
Quantum random-walk search algorithm
Shenvi, N., Kempe, J., & Whaley, K. B. (2003) · Physical Review A · doi:10.1103/physreva.67.052307 · Cited by 1,150 · cited 1×
“The potential of discrete time quantum walks with respect to searching problems was first pointed out by Shenvi, Kempe, and Whaley [34] who designed a quantum walk based simulation of Grover search.”
BackgroundAharonov, D., Ambainis, A., Kempe, J., & Vazirani, U. (2001) · Proceedings of the thirty-third annual ACM symposium on Theory of computing · doi:10.1145/380752.380758 · Cited by 654 · cited 1×
“by Watrous in his works related to space bounded computations [37]. Different parameters related to quantum walks and possible speedups of classical algorithms were investigated by several researchers [30,8,3,29,19,32]. The potential of discrete time quantum walks with respect to searching problems was first pointed out…”
BackgroundQUANTUM WALKS AND THEIR ALGORITHMIC APPLICATIONS
AMBAINIS, A. (2003) · International Journal of Quantum Information · doi:10.1142/s0219749903000383 · Cited by 632 · cited 1×
“For a detailed introduction to quantum walks the reader is referred to the excellent surveys of Kempe [20] and Ambainis [5].”
Method(2004) · doi:10.1109/focs.2004.53 · Cited by 599
Ambainis, A., Bach, E., Nayak, A., Vishwanath, A., & Watrous, J. (2001) · Proceedings of the thirty-third annual ACM symposium on Theory of computing · doi:10.1145/380752.380757 · Cited by 562 · cited 1×
“by Watrous in his works related to space bounded computations [37]. Different parameters related to quantum walks and possible speedups of classical algorithms were investigated by several researchers [30,8,3,29,19,32]. The potential of discrete time quantum walks with respect to searching problems was first pointed out…”
BackgroundFrom quantum cellular automata to quantum lattice gases
Meyer, D. A. (1996) · Journal of Statistical Physics · doi:10.1007/bf02199356 · Cited by 556
Discrete Quantum Walks Hit Exponentially Faster
Kempe, J. (2005) · Probability Theory and Related Fields · doi:10.1007/s00440-004-0423-2 · Cited by 152
Cited by
Quantum algorithms: an overview
Montanaro, A. (2016) · npj Quantum Information · doi:10.1038/npjqi.2015.23 · Cited by 1,071
“This framework has been used to obtain quantum speedups for a variety of problems [85], ranging from determining whether a list of integers are all distinct [6] to (cid:12)nding triangles in graphs [61].”
Quantum walks: a comprehensive review
Venegas-Andraca, S. E. (2012) · Quantum Information Processing · doi:10.1007/s11128-012-0432-5 · Cited by 934
Quantum Algorithm Implementations for Beginners
J., A., Adedoyin, A., Ambrosiano, J., Anisimov, P., Casper, W., Chennupati, G., Coffrin, C., Djidjev, H., Gunter, D., Karra, S., et al. (2018) · arXiv · doi:10.48550/arxiv.1804.03719 · Cited by 256
Quantum speed-up for unsupervised learning
Aïmeur, E., Brassard, G., & Gambs, S. (2013) · Machine Learning · doi:10.1007/s10994-012-5316-5 · Cited by 214
“More recently, other algorithmic approaches based on quantum walks (Kempe 2003; Ambainis 2003) or quantum Markov chains (Szegedy 2004; Magniez et al. 2007; Sántha 2008) have emerged.”
BackgroundQuantum Search Algorithms for Wireless Communications
Botsinis, P., Alanis, D., Babar, Z., Nguyen, H. V., Chandra, D., Ng, S. X., & Hanzo, L. (2019) · IEEE Communications Surveys & Tutorials · doi:10.1109/comst.2018.2882385 · Cited by 149
Metadata
- Authors
- Santha, M.
- Venue
- Lecture Notes in Computer Science
- Publisher
- Springer Berlin Heidelberg
- Published
- 2008-04-29
- Pages
- 31-46
- OpenAlex
- W1905918643
- Cited by
- 177
- References
- 11
- FWCI
- 7.94
- Type
- conference paper
- Language
- en
- Open access
- green
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.