The DOI matches its Crossref record; 9 of the 9 references it cites were found in a registry or an index.
Quantum Walk Based Search Algorithms
Open accessAbstract
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
Strengths 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
Aharonov, 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
QUANTUM WALKS AND THEIR ALGORITHMIC APPLICATIONS
AMBAINIS, A. (2003) · International Journal of Quantum Information · doi:10.1142/s0219749903000383 · Cited by 632
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 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
Fast escape of a quantum walker from an integrated photonic maze
Caruso, F., Crespi, A., Ciriolo, A. G., Sciarrino, F., & Osellame, R. (2016) · Nature Communications · doi:10.1038/ncomms11682 · Cited by 105
Pal, S., Bhattacharya, M., Lee, S.-S., & Chakraborty, C. (2024) · Molecular Biotechnology · doi:10.1007/s12033-023-00765-4 · Cited by 103
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
- 9
- 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
How to cite
Cite CoChat for the checks on this page, and the paper for its own findings.
- This page
- CoChat. (2026). Citation check: Quantum Walk Based Search Algorithms. https://app.cochat.ai/papers/10.1007/978-3-540-79228-4_3
- The paper
- Santha, M. (2008). Quantum Walk Based Search Algorithms. Lecture Notes in Computer Science. https://doi.org/10.1007/978-3-540-79228-4_3
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.