{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T00:44:56Z","timestamp":1742949896545,"version":"3.40.3"},"publisher-location":"New York, NY","reference-count":37,"publisher":"Springer New York","isbn-type":[{"type":"print","value":"9781493928637"},{"type":"electronic","value":"9781493928644"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016]]},"DOI":"10.1007\/978-1-4939-2864-4_302","type":"book-chapter","created":{"date-parts":[[2016,4,22]],"date-time":"2016-04-22T00:03:50Z","timestamp":1461283430000},"page":"1683-1691","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Quantum Analogues of Markov Chains"],"prefix":"10.1007","author":[{"given":"Ashwin","family":"Nayak","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Peter C.","family":"Richter","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mario","family":"Szegedy","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2016,4,22]]},"reference":[{"issue":"4","key":"585_CR17170","doi-asserted-by":"publisher","first-page":"595","DOI":"10.1145\/1008731.1008735","volume":"51","author":"S Aaronson","year":"2004","unstructured":"Aaronson S, Shi Y (2004) Quantum lower bounds for the collision and the element distinctness problems. J ACM 51(4):595\u2013605","journal-title":"J ACM"},{"key":"585_CR17171","doi-asserted-by":"publisher","first-page":"50","DOI":"10.1145\/380752.380758","volume-title":"Proceedings of the thirty-third annual ACM Symposium on Theory of Computing, STOC \u201901","author":"D Aharonov","year":"2001","unstructured":"Aharonov D, Ambainis A, Kempe J, Vazirani U (2001) Quantum walks on graphs. In: Proceedings of the thirty-third annual ACM Symposium on Theory of Computing, STOC \u201901, New York. ACM, pp\u00a050\u201359"},{"issue":"1","key":"585_CR17172","doi-asserted-by":"publisher","first-page":"210","DOI":"10.1137\/S0097539705447311","volume":"37","author":"A Ambainis","year":"2007","unstructured":"Ambainis A (2007) Quantum walk algorithm for Element Distinctness. SIAM J Comput 37(1):210\u2013239","journal-title":"SIAM J Comput"},{"key":"585_CR17173","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1145\/380752.380757","volume-title":"Proceedings of the thirty-third annual ACM Symposium on Theory of Computing, STOC \u201901","author":"A Ambainis","year":"2001","unstructured":"Ambainis A, Bach E, Nayak A, Vishwanath A, Watrous J (2001) One-dimensional quantum walks. In: Proceedings of the thirty-third annual ACM Symposium on Theory of Computing, STOC \u201901, New York. ACM, pp\u00a037\u201349"},{"key":"585_CR17174","first-page":"1099","volume-title":"Proceedings of the sixteenth annual ACM-SIAM Symposium on Discrete Algorithms, SODA \u201905","author":"A Ambainis","year":"2005","unstructured":"Ambainis A, Kempe J, Rivosh A (2005) Coins make quantum walks faster. In: Proceedings of the sixteenth annual ACM-SIAM Symposium on Discrete Algorithms, SODA \u201905, Philadelphia. Society for Industrial and Applied Mathematics, pp\u00a01099\u20131108"},{"key":"585_CR17175","first-page":"207","volume-title":"Proceedings of the 53rd annual IEEE Symposium on Foundations of Computer Science","author":"A Belovs","year":"2012","unstructured":"Belovs A (2012) Learning-graph-based quantum algorithm for k-Distinctness. In: Proceedings of the 53rd annual IEEE Symposium on Foundations of Computer Science. IEEE Computer Society, Los Alamitos, pp\u00a0207\u2013216"},{"key":"585_CR17176","doi-asserted-by":"crossref","first-page":"77","DOI":"10.1145\/2213977.2213985","volume-title":"Proceedings of the forty-fourth annual ACM Symposium on Theory of Computing, STOC \u201912","author":"A Belovs","year":"2012","unstructured":"Belovs A (2012) Span programs for functions with constant-sized 1-certificates: extended abstract. In: Proceedings of the forty-fourth annual ACM Symposium on Theory of Computing, STOC \u201912, New York. ACM, pp\u00a077\u201384"},{"key":"585_CR17177","doi-asserted-by":"crossref","unstructured":"Belovs A, Childs AM, Jeffery S, Kothari R, Magniez F (2013) Time-efficient quantum walks for 3-Distinctness. In: Fomin FV, Freivalds R, Kwiatkowska M, Peleg D (eds) Automata, Languages, and Programming. Volume 7965 of Lecture Notes in Computer Science. Springer, Berlin\/Heidelberg, pp\u00a0105\u2013122","DOI":"10.1007\/978-3-642-39206-1_10"},{"key":"585_CR17178","doi-asserted-by":"crossref","unstructured":"Brassard G, H\u00f8yer P, Mosca M, Tapp A (2002) Quantum amplitude amplification and estimation. In: Quantum Computation and Information (Washington, DC, 2000). Volume 305 of Contemporary Mathematics. American Mathematical Society, Providence, pp\u00a053\u201374","DOI":"10.1090\/conm\/305\/05215"},{"key":"585_CR17179","doi-asserted-by":"publisher","first-page":"880","DOI":"10.1145\/1109557.1109654","volume-title":"Proceedings of the seventeenth annual ACM-SIAM Symposium on Discrete Algorithms, SODA \u201906","author":"H Buhrman","year":"2006","unstructured":"Buhrman H, \u0160palek R (2006) Quantum verification of matrix products. In: Proceedings of the seventeenth annual ACM-SIAM Symposium on Discrete Algorithms, SODA \u201906, Philadelphia. Society for Industrial and Applied Mathematics, pp\u00a0880\u2013889"},{"key":"585_CR17180","doi-asserted-by":"publisher","first-page":"022314","DOI":"10.1103\/PhysRevA.70.022314","volume":"70","author":"A Childs","year":"2004","unstructured":"Childs A, Goldstone J (2004) Spatial search by quantum walk. Phys Rev A 70:022314","journal-title":"Phys Rev A"},{"issue":"6","key":"585_CR17181","doi-asserted-by":"publisher","first-page":"1426","DOI":"10.1137\/110833026","volume":"41","author":"AM Childs","year":"2012","unstructured":"Childs AM, Kothari R (2012) Quantum query complexity of minor-closed graph properties. SIAM J Comput 41(6):1426\u20131450","journal-title":"SIAM J Comput"},{"key":"585_CR17182","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1145\/780542.780552","volume-title":"Proceedings of the thirty-fifth annual ACM Symposium on Theory of Computing, STOC \u201903","author":"AM Childs","year":"2003","unstructured":"Childs AM, Cleve R, Deotto E, Farhi E, Gutmann S, Spielman DA (2003) Exponential algorithmic speedup by a quantum walk. In: Proceedings of the thirty-fifth annual ACM Symposium on Theory of Computing, STOC \u201903, New York. ACM, pp\u00a059\u201368"},{"key":"585_CR17183","doi-asserted-by":"publisher","first-page":"339","DOI":"10.1098\/rspa.1998.0164","volume":"454","author":"R Cleve","year":"1969","unstructured":"Cleve R, Ekert A, Macchiavello C, Mosca M (1998) Quantum algorithms revisited. Proc R Soc A Math Phys Eng Sci 454(1969):339\u2013354","journal-title":"Proc R Soc A Math Phys Eng Sci"},{"key":"585_CR17184","doi-asserted-by":"publisher","first-page":"915","DOI":"10.1103\/PhysRevA.58.915","volume":"58","author":"E Farhi","year":"1998","unstructured":"Farhi E, Gutmann S (1998) Quantum computation and decision trees. Phys Rev A 58:915\u2013928","journal-title":"Phys Rev A"},{"key":"585_CR17185","doi-asserted-by":"crossref","unstructured":"Jeffery S, Kothari R, Magniez F (2012) Improving quantum query complexity of Boolean Matrix Multiplication using Graph Collision. In: Czumaj A, Mehlhorn K, Pitts A, Wattenhofer R (eds) Automata, Languages, and Programming. Volume 7391 of Lecture Notes in Computer Science. Springer, Berlin\/Heidelberg, pp\u00a0522\u2013532","DOI":"10.1007\/978-3-642-31594-7_44"},{"key":"585_CR17186","doi-asserted-by":"publisher","first-page":"1474","DOI":"10.1137\/1.9781611973105.106","volume-title":"Proceedings of the twenty-fourth annual ACM-SIAM Symposium on Discrete Algorithms, SODA \u201913","author":"S Jeffery","year":"2013","unstructured":"Jeffery S, Kothari R, Magniez F (2013) Nested quantum walks with quantum data structures. In: Proceedings of the twenty-fourth annual ACM-SIAM Symposium on Discrete Algorithms, SODA \u201913. SIAM, Philadelphia, pp\u00a01474\u20131485"},{"key":"585_CR17187","first-page":"482","volume-title":"Approximation algorithms for NP-hard problems","author":"M Jerrum","year":"1997","unstructured":"Jerrum M, Sinclair A (1997) The Markov Chain Monte Carlo method: an approach to approximate counting and integration. In: Hochbaum DS (ed) Approximation algorithms for NP-hard problems. PWS Publishing Co., Boston, pp\u00a0482\u2013520"},{"issue":"2","key":"585_CR17188","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1007\/s00440-004-0423-2","volume":"133","author":"J Kempe","year":"2005","unstructured":"Kempe J (2005) Discrete quantum walks hit exponentially faster. Probab Theory Relat Fields 133(2):215\u2013235","journal-title":"Probab Theory Relat Fields"},{"key":"585_CR17189","doi-asserted-by":"publisher","first-page":"042315","DOI":"10.1103\/PhysRevA.67.042315","volume":"67","author":"V Kendon","year":"2003","unstructured":"Kendon V, Tregenna B (2003) Decoherence can be useful in quantum walks. Phys Rev A 67:042315","journal-title":"Phys Rev A"},{"key":"585_CR17190","unstructured":"Kitaev A (1995) Quantum measurements and the Abelian stabilizer problem. Technical report. quant-ph\/9511026, arXiv.org"},{"key":"585_CR17191","unstructured":"Kothari R (2014) Efficient algorithms in quantum query complexity. PhD thesis, University of Waterloo, Waterloo"},{"key":"585_CR17192","doi-asserted-by":"crossref","unstructured":"Krovi H, Magniez F, Ozols M, Roland J (2014) Quantum walks can find a marked element on any graph. Technical report. arXiv:1002.2419v2, arXiv.org","DOI":"10.1007\/s00453-015-9979-8"},{"key":"585_CR17193","doi-asserted-by":"publisher","first-page":"1464","DOI":"10.1137\/1.9781611973099.116","volume-title":"Proceedings of the twenty-third annual ACM-SIAM Symposium on Discrete Algorithms, SODA \u201912","author":"F Gall Le","year":"2012","unstructured":"Le Gall F (2012) Improved output-sensitive quantum algorithms for boolean matrix multiplication. In: Proceedings of the twenty-third annual ACM-SIAM Symposium on Discrete Algorithms, SODA \u201912. SIAM, Philadelphia, pp\u00a01464\u20131476"},{"key":"585_CR17194","doi-asserted-by":"crossref","unstructured":"Le Gall F (2014) Improved quantum algorithm for triangle finding via combinatorial arguments. In: Proceedings of the 55th annual IEEE Symposium on Foundations of Computer Science, Los Alamitos, 18\u201321 Oct 2014. IEEE Computer Society Press, pp\u00a0216\u2013225","DOI":"10.1109\/FOCS.2014.31"},{"key":"585_CR17195","doi-asserted-by":"publisher","first-page":"1486","DOI":"10.1137\/1.9781611973105.107","volume-title":"Proceedings of the twenty-fourth annual ACM-SIAM Symposium on Discrete Algorithms, SODA \u201913","author":"T Lee","year":"2013","unstructured":"Lee T, Magniez F, Santha M (2013) Improved quantum query algorithms for triangle finding and associativity testing. In: Proceedings of the twenty-fourth annual ACM-SIAM Symposium on Discrete Algorithms, SODA \u201913. SIAM, Philadelphia, pp\u00a01486\u20131502"},{"issue":"3","key":"585_CR17196","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 (2007) Quantum complexity of testing group commutativity. Algorithmica 48(3):221\u2013232","journal-title":"Algorithmica"},{"issue":"2","key":"585_CR17197","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 (2007) Quantum algorithms for the triangle problem. SIAM J Comput 37(2):413\u2013424","journal-title":"SIAM J Comput"},{"key":"585_CR17198","doi-asserted-by":"publisher","first-page":"142","DOI":"10.1137\/090745854","volume":"40","author":"F Magniez","year":"2011","unstructured":"Magniez F, Nayak A, Roland J, Santha M (2011) Search via quantum walk. SIAM J Comput 40:142\u2013164","journal-title":"SIAM J Comput"},{"issue":"1","key":"585_CR17199","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1007\/s00453-011-9521-6","volume":"63","author":"F Magniez","year":"2012","unstructured":"Magniez F, Nayak A, Richter PC, Santha M (2012) On the hitting times of quantum versus random walks. Algorithmica 63(1):91\u2013116","journal-title":"Algorithmica"},{"key":"585_CR17200","doi-asserted-by":"crossref","unstructured":"Moore C, Russell A (2002) Quantum walks on the hypercube. In: Rolim JDP, Vadhan S (eds) Randomization and Approximation Techniques in Computer Science. Volume 2483 of Lecture Notes in Computer Science. Springer, Berlin\/Heidelberg, pp\u00a0164\u2013178","DOI":"10.1007\/3-540-45726-7_14"},{"key":"585_CR17201","unstructured":"Nayak A, Vishwanath A (2000) Quantum walk on the line. Technical report. quant-ph\/0010117, arXiv.org."},{"key":"585_CR17202","doi-asserted-by":"publisher","first-page":"042306","DOI":"10.1103\/PhysRevA.76.042306","volume":"76","author":"P Richter","year":"2007","unstructured":"Richter P (2007) Quantum speedup of classical mixing processes. Phys Rev A 76:042306","journal-title":"Phys Rev A"},{"key":"585_CR17203","doi-asserted-by":"publisher","first-page":"052307","DOI":"10.1103\/PhysRevA.67.052307","volume":"67","author":"N Shenvi","year":"2003","unstructured":"Shenvi N, Kempe J, Birgitta Whaley K (2003) Quantum random-walk search algorithm. Phys Rev A 67:052307","journal-title":"Phys Rev A"},{"key":"585_CR17204","doi-asserted-by":"publisher","first-page":"32","DOI":"10.1109\/FOCS.2004.53","volume-title":"Proceedings of the 45th annual IEEE Symposium on Foundations of Computer Science","author":"M Szegedy","year":"2004","unstructured":"Szegedy M (2004) Quantum speed-up of markov chain based algorithms. In: Proceedings of the 45th annual IEEE Symposium on Foundations of Computer Science. IEEE Computer Society, Los Alamitos, pp\u00a032\u201341"},{"key":"585_CR17205","doi-asserted-by":"publisher","first-page":"012310","DOI":"10.1103\/PhysRevA.78.012310","volume":"78","author":"A Tulsi","year":"2008","unstructured":"Tulsi A (2008) Faster quantum walk algorithm for the two dimensional spatial search. Phys Rev A 78:012310","journal-title":"Phys Rev A"},{"key":"585_CR17206","doi-asserted-by":"publisher","first-page":"645","DOI":"10.1109\/FOCS.2010.67","volume-title":"Proceedings of the 51st annual IEEE Symposium on Foundations of Computer Science, FOCS \u201910","author":"VV Williams","year":"2010","unstructured":"Williams VV, Williams R (2010) Subcubic equivalences between path, matrix and triangle problems. In: Proceedings of the 51st annual IEEE Symposium on Foundations of Computer Science, FOCS \u201910, Washington. IEEE Computer Society, pp\u00a0645\u2013654"}],"container-title":["Encyclopedia of Algorithms"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-1-4939-2864-4_302","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,6,18]],"date-time":"2022-06-18T10:26:04Z","timestamp":1655547964000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-1-4939-2864-4_302"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9781493928637","9781493928644"],"references-count":37,"URL":"https:\/\/doi.org\/10.1007\/978-1-4939-2864-4_302","relation":{},"subject":[],"published":{"date-parts":[[2016]]},"assertion":[{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}