{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,14]],"date-time":"2026-07-14T23:53:12Z","timestamp":1784073192570,"version":"3.55.0"},"publisher-location":"Berlin, Heidelberg","reference-count":37,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540792277","type":"print"},{"value":"9783540792284","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-79228-4_3","type":"book-chapter","created":{"date-parts":[[2008,4,29]],"date-time":"2008-04-29T05:07:56Z","timestamp":1209445676000},"page":"31-46","source":"Crossref","is-referenced-by-count":78,"title":["Quantum Walk Based Search Algorithms"],"prefix":"10.1007","author":[{"given":"Miklos","family":"Santha","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"3_CR1","doi-asserted-by":"crossref","unstructured":"Aaronson, S., Shi, Y.: Quantum lower bounds for the collision and the element distinctness problems. Journal of the ACM, 595\u2013605 (2004)","DOI":"10.1145\/1008731.1008735"},{"key":"3_CR2","doi-asserted-by":"publisher","first-page":"47","DOI":"10.4086\/toc.2005.v001a004","volume":"1","author":"S. Aaronson","year":"2005","unstructured":"Aaronson, S., Ambainis, A.: Quantum search of spatial regions. Theory of Computing\u00a01, 47\u201379 (2005)","journal-title":"Theory of Computing"},{"key":"3_CR3","doi-asserted-by":"crossref","unstructured":"Aharonov, D., Ambainis, A., Kempe, J., Vazirani, U.: Quantum walks on graphs. In: Proc. of the 33rd ACM Symposium on Theory of Computing, pp. 50\u201359 (2001)","DOI":"10.1145\/380752.380758"},{"key":"3_CR4","doi-asserted-by":"crossref","unstructured":"Aleliunas, R., Karp, R., Lipton, R., Lov\u00e1sz, L., Rackoff, C.: Random Walks, Universal Traversal Sequences, and the cComplexity of Maze Problems. In: Proc. of the 20th Symposium on Foundations of Computer Science, pp. 218\u2013223 (1979)","DOI":"10.1109\/SFCS.1979.34"},{"issue":"4","key":"3_CR5","doi-asserted-by":"publisher","first-page":"507","DOI":"10.1142\/S0219749903000383","volume":"1","author":"A. Ambainis","year":"2003","unstructured":"Ambainis, A.: Quantum walks and their algorithmic applications. International Journal of Quantum Information\u00a01(4), 507\u2013518 (2003)","journal-title":"International Journal of Quantum Information"},{"issue":"2","key":"3_CR6","doi-asserted-by":"publisher","first-page":"22","DOI":"10.1145\/992287.992296","volume":"35","author":"A. Ambainis","year":"2004","unstructured":"Ambainis, A.: Quantum search algorithms. SIGACT News\u00a035(2), 22\u201335 (2004)","journal-title":"SIGACT News"},{"key":"3_CR7","doi-asserted-by":"publisher","first-page":"210","DOI":"10.1137\/S0097539705447311","volume":"37","author":"A. Ambainis","year":"2007","unstructured":"Ambainis, A.: Quantum Walk Algorithm for Element Distinctness. SIAM Journal on Computing\u00a037, 210\u2013239 (2007)","journal-title":"SIAM Journal on Computing"},{"key":"3_CR8","doi-asserted-by":"crossref","unstructured":"Ambanis, A., Bach, E., Nayak, A., Vishwanath, A., Watrous, J.: One-dimensional quantum walks. In: Proc. of the 33rd ACM Symposium on Theory of computing, pp. 37\u201349 (2001)","DOI":"10.1145\/380752.380757"},{"key":"3_CR9","unstructured":"Ambainis, A., Kempe, J., Rivosh, A.: Coins make quantum walks faster. In: Proc. of the 16th ACM-SIAM Symposium on Discrete Algorithms, pp. 1099\u20131108 (2005)"},{"issue":"5","key":"3_CR10","doi-asserted-by":"publisher","first-page":"1510","DOI":"10.1137\/S0097539796300933","volume":"26","author":"C. Bennett","year":"1997","unstructured":"Bennett, C., Bernstein, E., Brassard, G., Vazirani, U.: Strengths and weaknesses of quantum computing. SIAM Journal on Computing\u00a026(5), 1510\u20131523 (1997)","journal-title":"SIAM Journal on Computing"},{"key":"3_CR11","doi-asserted-by":"crossref","unstructured":"Brassard, G., H\u00f8yer, P., Mosca, M., Tapp, A.: Quantum amplitude amplification and estimation. In: Lomonaco Jr., S.J., Brandt, H.E. (eds.) Quantum Computation and Quantum Information: A Millennium Volume, American Mathematical Society. Contemporary Mathematics Series, vol.\u00a0305, pp. 53\u201374 (2002)","DOI":"10.1090\/conm\/305\/05215"},{"key":"3_CR12","doi-asserted-by":"crossref","unstructured":"Buhrman, H., Spalek, R.: Quantum verification of matrix products. In: Proc. of the 17th ACM-SIAM Symposium on Discrete Algorithms, pp. 880\u2013889 (2006)","DOI":"10.1145\/1109557.1109654"},{"key":"3_CR13","doi-asserted-by":"crossref","unstructured":"Cleve, R., Ekert, A., Macchiavello, C., Mosca, M.: Quantum algorithms revisited. In: Proc. of the Royal Society A: Mathematical, Physical and Engineering Sciences, vol.\u00a0454(1969), pp. 339\u2013354 (1998)","DOI":"10.1098\/rspa.1998.0164"},{"key":"3_CR14","unstructured":"Cormen, T., Leiserson, C., Rivest, R., Stein, C.: Introduction to Algorithms, 2nd edn. The MIT Press and McGraw-Hill (2001)"},{"key":"3_CR15","doi-asserted-by":"crossref","unstructured":"D\u00f6rn, S., Thierauf, T.: The Quantum Query Complexity of Algebraic Properties. In: Proc. of the 16th International Symposium on Fundamentals of Computation Theory, pp. 250\u2013260 (2007)","DOI":"10.1007\/978-3-540-74240-1_22"},{"key":"3_CR16","doi-asserted-by":"crossref","unstructured":"Grover, L.: A fast quantum mechanical algorithm for database search. In: Proc. of the 28th ACM Symposium on the Theory of Computing, pp. 212\u2013219 (1996)","DOI":"10.1145\/237814.237866"},{"key":"3_CR17","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-6387-6","volume-title":"Finite-dimensional vector spaces","author":"P. Halmos","year":"1974","unstructured":"Halmos, P.: Finite-dimensional vector spaces. Springer, Heidelberg (1974)"},{"key":"3_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"291","DOI":"10.1007\/3-540-45061-0_25","volume-title":"Automata, Languages and Programming","author":"P. H\u00f8yer","year":"2003","unstructured":"H\u00f8yer, P., Mosca, M., de Wolf, R.: Quantum search on bounded-error inputs. In: Baeten, J.C.M., Lenstra, J.K., Parrow, J., Woeginger, G.J. (eds.) ICALP 2003. LNCS, vol.\u00a02719, pp. 291\u2013299. Springer, Heidelberg (2003)"},{"key":"3_CR19","doi-asserted-by":"crossref","unstructured":"Kempe, J.: Discrete Quantum Walks Hit Exponentially Faster. In: Proc. of the International Workshop on Randomization and Approximation Techniques in Computer Science, pp. 354\u2013369 (2003)","DOI":"10.1007\/978-3-540-45198-3_30"},{"issue":"4","key":"3_CR20","doi-asserted-by":"publisher","first-page":"307","DOI":"10.1080\/00107151031000110776","volume":"44","author":"J. Kempe","year":"2003","unstructured":"Kempe, J.: Quantum random walks \u2013 an introductory survey. Contemporary Physics\u00a044(4), 307\u2013327 (2003)","journal-title":"Contemporary Physics"},{"key":"3_CR21","unstructured":"Kitaev, A.: Quantum measurements and the abelian stabilizer problem. Electronic Colloquium on Computational Complexity (ECCC)\u00a03 (1996)"},{"key":"3_CR22","series-title":"The Art of Computer Programming","volume-title":"Sorting and Searching","author":"D. Knuth","year":"1973","unstructured":"Knuth, D.: Sorting and Searching. The Art of Computer Programming, vol.\u00a03. Addison-Wesley, Reading (1973)"},{"issue":"3","key":"3_CR23","doi-asserted-by":"publisher","first-page":"221","DOI":"10.1007\/s00453-007-0057-8","volume":"48","author":"F. Magniez","year":"2007","unstructured":"Magniez, F., Nayak, A.: Quantum complexity of testing group commutativity. Algorithmica\u00a048(3), 221\u2013232 (2007)","journal-title":"Algorithmica"},{"key":"3_CR24","unstructured":"Magniez, F., Nayak, A.: Personal communication (2008)"},{"key":"3_CR25","doi-asserted-by":"crossref","unstructured":"Magniez, F., Nayak, A., Roland, J., Santha, M.: Search via quantum walk. In: Proc. of the 39th ACM Symposium on Theory of Computing, pp. 575\u2013584 (2007)","DOI":"10.1145\/1250790.1250874"},{"issue":"2","key":"3_CR26","doi-asserted-by":"publisher","first-page":"413","DOI":"10.1137\/050643684","volume":"37","author":"F. Magniez","year":"2007","unstructured":"Magniez, F., Santha, M., Szegedy, M.: Quantum Algorithms for the Triangle Problem. SIAM Journal of Computing\u00a037(2), 413\u2013427 (2007)","journal-title":"SIAM Journal of Computing"},{"issue":"5-6","key":"3_CR27","doi-asserted-by":"publisher","first-page":"551","DOI":"10.1007\/BF02199356","volume":"85","author":"D. Meyer","year":"1996","unstructured":"Meyer, D.: From quantum cellular automata to quantum lattice gases. Journal of Statistical Physics\u00a085(5-6), 551\u2013574 (1996)","journal-title":"Journal of Statistical Physics"},{"issue":"5","key":"3_CR28","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1016\/S0375-9601(96)00745-1","volume":"223","author":"D. Meyer","year":"1996","unstructured":"Meyer, D.: On the abscence of homogeneous scalar unitary cellular automata. Physical Letter A\u00a0223(5), 337\u2013340 (1996)","journal-title":"Physical Letter A"},{"key":"3_CR29","doi-asserted-by":"crossref","unstructured":"Moore, C., Russell, A.: Quantum Walks on the Hypercube. In: Proc. of the 6th International Workshop on Randomization and Approximation Techniques in Computer Science, pp. 164\u2013178 (2002)","DOI":"10.1007\/3-540-45726-7_14"},{"key":"3_CR30","unstructured":"Nayak, A., Vishwanath, A.: Quantum walk on the line. Technical Report quant-ph\/0010117, arXiv (2000)"},{"key":"3_CR31","unstructured":"Pak, I.: Testing commutativity of a group and the power of randomization (2000), Electronic version http:\/\/www-math.mit.edu\/~pak\/research.html"},{"key":"3_CR32","doi-asserted-by":"crossref","unstructured":"Richter, P.: Almost uniform sampling via quantum walks. New Journal of Physics (to appear)","DOI":"10.1088\/1367-2630\/9\/3\/072"},{"issue":"4","key":"3_CR33","doi-asserted-by":"publisher","first-page":"615","DOI":"10.1007\/s00453-001-0094-7","volume":"32","author":"U. Sch\u00f6ning","year":"2002","unstructured":"Sch\u00f6ning, U.: A Probabilistic Algorithm for k -SAT Based on Limited Local Search and Restart. Algorithmica\u00a032(4), 615\u2013623 (2002)","journal-title":"Algorithmica"},{"key":"3_CR34","doi-asserted-by":"crossref","unstructured":"Shenvi, N., Kempe, J., Whaley, K.B.: Quantum random-walk search algorithm. Physical Review A\u00a067(052307) (2003)","DOI":"10.1103\/PhysRevA.67.052307"},{"key":"3_CR35","doi-asserted-by":"crossref","unstructured":"Szegedy, M.: Quantum Speed-Up of Markov Chain Based Algorithms. In: Proc. of the 45th IEEE Symposium on Foundations of Computer Science, pp. 32\u201341 (2004)","DOI":"10.1109\/FOCS.2004.53"},{"key":"3_CR36","doi-asserted-by":"publisher","first-page":"1759","DOI":"10.1098\/rsta.1998.0247","volume":"356","author":"U. Vazirani","year":"1998","unstructured":"Vazirani, U.: On the power of quantum computation. Philosophical Transactions of the Royal Society of London, Series\u00a0A\u00a0356, 1759\u20131768 (1998)","journal-title":"Philosophical Transactions of the Royal Society of London, Series\u00a0A"},{"issue":"2","key":"3_CR37","doi-asserted-by":"publisher","first-page":"376","DOI":"10.1006\/jcss.2000.1732","volume":"62","author":"J. Watrous","year":"2001","unstructured":"Watrous, J.: Quantum simulations of classical random walks and undirected graph connectivity. Journal of Computer and System Sciences\u00a062(2), 376\u2013391 (2001)","journal-title":"Journal of Computer and System Sciences"}],"container-title":["Lecture Notes in Computer Science","Theory and Applications of Models of Computation"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-79228-4_3.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T11:14:17Z","timestamp":1619522057000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-79228-4_3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540792277","9783540792284"],"references-count":37,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-79228-4_3","relation":{},"subject":[]}}