Search via quantum walk
The DOI matches its Crossref record; 9 of the 9 references it cites were found in a registry or an index.
Abstract
We propose a new method for designing quantum search algorithms forfinding a "marked" element in the state space of a classical Markovchain. The algorithm is based on a quantum walk à la Szegedy [25] that is defined in terms of the Markov chain. The main new idea is to apply quantum phase estimation to the quantumwalk in order to implement an approximate reflection operator. Thisoperatoris then used in an amplitude amplification scheme. As a result weconsiderably expand the scope of the previous approaches ofAmbainis [6] and Szegedy [25]. Our algorithm combines the benefits of these approaches in terms of beingable to find marked elements, incurring the smaller cost of the two,and being applicable to a larger class of Markov chain. In addition,it is conceptually simple, avoids several technical difficulties in the previous analyses, and leads to improvements in various aspects of several algorithms based on quantum walk.
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×
“This operator may then be used within amplitude amplification algorithms [16, 10, 17] for search.”
MethodStrengths 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
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 3×
“Shenvi, Kempe, and Whaley [24] pointed out the algorithmic potential of quantum walks by designing a walk based algorithm to emulate Grover Search [16].”
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×
“Afterwards notions related to quantum walks, such as mixing time, and deviation from starting state, were studied for restricted graphs by several researchers [22, 7, 3, 23], suggesting the possibility of speedup of classical algorithms based on random walk.”
Background(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×
“Afterwards notions related to quantum walks, such as mixing time, and deviation from starting state, were studied for restricted graphs by several researchers [22, 7, 3, 23], suggesting the possibility of speedup of classical algorithms based on random walk.”
BackgroundSelf-citationFrom quantum cellular automata to quantum lattice gases
Meyer, D. A. (1996) · Journal of Statistical Physics · doi:10.1007/bf02199356 · Cited by 556
Spatial search and the Dirac equation
Childs, A. M., & Goldstone, J. (2004) · Physical Review A · doi:10.1103/physreva.70.042312 · Cited by 146
Cited by
Quantum walks: a comprehensive review
Venegas-Andraca, S. E. (2012) · Quantum Information Processing · doi:10.1007/s11128-012-0432-5 · Cited by 934
On the Relationship Between Continuous- and Discrete-Time Quantum Walk
Childs, A. M. (2010) · Communications in Mathematical Physics · doi:10.1007/s00220-009-0930-1 · Cited by 411
“This approach was later generalized [35, 50] and applied to quantum algorithms for triangle finding [36], checking matrix multiplication [10], and testing group commutativity [34].”
MethodQuantum algorithms for algebraic problems
Childs, A. M., & van Dam, W. (2010) · Reviews of Modern Physics · doi:10.1103/revmodphys.82.1 · Cited by 344
“et al., 2005; Childs and Goldstone, 2004a,b; Shenvi et al., 2003), Ambainis (2007) gave an optimal quantum algorithm for the element distinctness problem. This approach was subsequently generalized (Magniez et al., 2007; Szegedy, 2004) and applied to other problems in query complexity,namelytriangle finding( Magniez et…”
MethodQuantum 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.”
BackgroundAny AND-OR Formula of Size N Can Be Evaluated in Time $N^{1/2+o(1)}$ on a Quantum Computer
Ambainis, A., Childs, A. M., Reichardt, B. W., Špalek, R., & Zhang, S. (2010) · SIAM Journal on Computing · doi:10.1137/080712167 · Cited by 122
Metadata
- Authors
- Magniez, F., Nayak, A., Roland, J., & Santha, M.
- Venue
- Proceedings of the thirty-ninth annual ACM symposium on Theory of computing
- Publisher
- ACM
- Published
- 2007-06-11
- Pages
- 575-584
- OpenAlex
- W2066651691
- Cited by
- 126
- References
- 9
- FWCI
- 9.98
- Type
- conference paper
- Language
- en
- Open access
- closed
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: Search via quantum walk. https://app.cochat.ai/papers/10.1145/1250790.1250874
- The paper
- Magniez, F., Nayak, A., Roland, J., & Santha, M. (2007). Search via quantum walk. Proceedings of the thirty-ninth annual ACM symposium on Theory of computing. https://doi.org/10.1145/1250790.1250874
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.