{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,8]],"date-time":"2026-01-08T05:13:44Z","timestamp":1767849224123,"version":"3.49.0"},"reference-count":29,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2015,3,3]],"date-time":"2015-03-03T00:00:00Z","timestamp":1425340800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2016,2]]},"DOI":"10.1007\/s00453-015-9979-8","type":"journal-article","created":{"date-parts":[[2015,3,2]],"date-time":"2015-03-02T15:36:51Z","timestamp":1425310611000},"page":"851-907","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":59,"title":["Quantum Walks Can Find a Marked Element on Any Graph"],"prefix":"10.1007","volume":"74","author":[{"given":"Hari","family":"Krovi","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Fr\u00e9d\u00e9ric","family":"Magniez","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Maris","family":"Ozols","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"J\u00e9r\u00e9mie","family":"Roland","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,3,3]]},"reference":[{"issue":"1","key":"9979_CR1","doi-asserted-by":"crossref","first-page":"210","DOI":"10.1137\/S0097539705447311","volume":"37","author":"A Ambainis","year":"2007","unstructured":"Ambainis, A.: Quantum walk algorithm for element distinctness. SIAM J. Comput. 37(1), 210\u2013239 (2007)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"9979_CR2","doi-asserted-by":"crossref","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 J. Comput. 37(2), 413\u2013424 (2007)","journal-title":"SIAM J. Comput."},{"key":"9979_CR3","doi-asserted-by":"crossref","unstructured":"Buhrman, H., \u0160palek, R: Quantum verification of matrix products. In: Proceedings of the 17th ACM-SIAM symposium on discrete algorithms (SODA\u201906), pp. 880\u2013889. ACM (2006)","DOI":"10.1145\/1109557.1109654"},{"issue":"3","key":"9979_CR4","doi-asserted-by":"crossref","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 48(3), 221\u2013232 (2007)","journal-title":"Algorithmica"},{"issue":"4","key":"9979_CR5","doi-asserted-by":"crossref","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 Comput. 1(4), 47\u201379 (2005)","journal-title":"Theory Comput."},{"issue":"5","key":"9979_CR6","doi-asserted-by":"crossref","first-page":"052307","DOI":"10.1103\/PhysRevA.67.052307","volume":"67","author":"N Shenvi","year":"2003","unstructured":"Shenvi, N., Kempe, J., Whaley, B.K.: Quantum random-walk search algorithm. Phys. Rev. A 67(5), 052307 (2003)","journal-title":"Phys. Rev. A"},{"issue":"4","key":"9979_CR7","doi-asserted-by":"crossref","first-page":"042312","DOI":"10.1103\/PhysRevA.70.042312","volume":"70","author":"AM Childs","year":"2004","unstructured":"Childs, A.M., Goldstone, J.: Spatial search and the Dirac equation. Phys. Rev. A 70(4), 042312 (2004)","journal-title":"Phys. Rev. A"},{"key":"9979_CR8","unstructured":"Ambainis, A., Kempe, J., Rivosh, A.: Coins make quantum walks faster. In: Proceedings of the 16th ACM-SIAM symposium on discrete algorithms (SODA\u201905), pp. 1099\u20131108. SIAM (2005)"},{"issue":"2","key":"9979_CR9","doi-asserted-by":"crossref","first-page":"215","DOI":"10.1007\/s00440-004-0423-2","volume":"133","author":"J Kempe","year":"2005","unstructured":"Kempe, J.: Discrete quantum walks hit exponentially faster. Probab. Theory Relat. Fields 133(2), 215\u2013235 (2005)","journal-title":"Probab. Theory Relat. Fields"},{"key":"9979_CR10","doi-asserted-by":"crossref","unstructured":"Szegedy, M.: Quantum speed-up of Markov chain based algorithms. In: Proceedings of the 45th IEEE symposium on foundations of computer science (FOCS\u201904), pp. 32\u201341. IEEE Computer Society Press (2004)","DOI":"10.1109\/FOCS.2004.53"},{"issue":"3","key":"9979_CR11","doi-asserted-by":"crossref","first-page":"032341","DOI":"10.1103\/PhysRevA.73.032341","volume":"73","author":"H Krovi","year":"2006","unstructured":"Krovi, H., Brun, T.A.: Hitting time for quantum walks on the hypercube. Phys. Rev. A 73(3), 032341 (2006)","journal-title":"Phys. Rev. A"},{"key":"9979_CR12","doi-asserted-by":"crossref","unstructured":"Magniez, F., Nayak, A., Roland, J., Santha, M.: Search via quantum walk. In: Proceedings of the 39th ACM symposium on theory of computing (STOC\u201907), pp. 575\u2013584. ACM Press (2007)","DOI":"10.1145\/1250790.1250874"},{"issue":"1","key":"9979_CR13","doi-asserted-by":"crossref","first-page":"91","DOI":"10.1007\/s00453-011-9521-6","volume":"63","author":"F Magniez","year":"2012","unstructured":"Magniez, F., Nayak, A., Richter, P., Santha, M.: On the hitting times of quantum versus random walks. Algorithmica 63(1), 91\u2013116 (2012)","journal-title":"Algorithmica"},{"issue":"2","key":"9979_CR14","doi-asserted-by":"crossref","first-page":"022324","DOI":"10.1103\/PhysRevA.78.022324","volume":"78","author":"M Varbanov","year":"2008","unstructured":"Varbanov, M., Krovi, H., Brun, T.A.: Hitting time for the continuous quantum walk. Phys. Rev. A 78(2), 022324 (2008)","journal-title":"Phys. Rev. A"},{"issue":"1","key":"9979_CR15","doi-asserted-by":"crossref","first-page":"012310","DOI":"10.1103\/PhysRevA.78.012310","volume":"78","author":"A Tulsi","year":"2008","unstructured":"Tulsi, A.: Faster quantum-walk algorithm for the two-dimensional spatial search. Phys. Rev. A 78(1), 012310 (2008)","journal-title":"Phys. Rev. A"},{"key":"9979_CR16","doi-asserted-by":"crossref","unstructured":"Krovi, H., Magniez, F., Ozols, M., Roland, J.: Finding is as easy as detecting for quantum walks. In: Automata, Languages and Programming, Lecture Notes in Computer Science, vol. 6198, pp. 540\u2013551. Springer, Berlin-Heidelberg (2010)","DOI":"10.1007\/978-3-642-14165-2_46"},{"issue":"2","key":"9979_CR17","doi-asserted-by":"crossref","first-page":"022314","DOI":"10.1103\/PhysRevA.70.022314","volume":"70","author":"AM Childs","year":"2004","unstructured":"Childs, A.M., Goldstone, J.: Spatial search by quantum walk. Phys. Rev. A 70(2), 022314 (2004)","journal-title":"Phys. Rev. A"},{"key":"9979_CR18","volume-title":"Lecture Notes in Computer Science","author":"A Ambainis","year":"2013","unstructured":"Ambainis, A., Ba\u010dkurs, A., Nahimovs, N., Ozols, R., Rivosh, A.: Lecture Notes in Computer Science, vol. 7582. Springer, Berlin (2013)"},{"issue":"2","key":"9979_CR19","doi-asserted-by":"crossref","first-page":"022333","DOI":"10.1103\/PhysRevA.82.022333","volume":"82","author":"H Krovi","year":"2010","unstructured":"Krovi, H., Ozols, M., Roland, J.: Adiabatic condition and the quantum hitting time of Markov chains. Phys. Rev. A 82(2), 022333 (2010)","journal-title":"Phys. Rev. A"},{"key":"9979_CR20","volume-title":"Introduction to Probability","author":"CM Grinstead","year":"1997","unstructured":"Grinstead, C.M., Snell, J.L.: Introduction to Probability, 2nd edn. American Mathematical Society, Providence (1997)","edition":"2"},{"key":"9979_CR21","series-title":"Undergraduate Texts in Mathematics","volume-title":"Finite Markov Chains","author":"JG Kemeny","year":"1960","unstructured":"Kemeny, J.G., Snell, J.L.: Finite Markov Chains. Undergraduate Texts in Mathematics. Springer, Berlin (1960)"},{"key":"9979_CR22","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-540-68829-7","volume-title":"Theory of Probability and Random Processes","author":"LB Koralov","year":"2007","unstructured":"Koralov, L.B., Sinai, Y.G.: Theory of Probability and Random Processes. Springer, Berlin (2007)"},{"key":"9979_CR23","volume-title":"Markov Chains and Mixing Times","author":"DA Levin","year":"2009","unstructured":"Levin, D.A., Peres, Y., Wilmer, E.L.: Markov Chains and Mixing Times. American Mathematical Society, Providence (2009)"},{"key":"9979_CR24","volume-title":"Matrix Analysis","author":"RA Horn","year":"1990","unstructured":"Horn, R.A., Johnson, C.R.: Matrix Analysis. Cambridge University Press, Cambridge (1990)"},{"key":"9979_CR25","doi-asserted-by":"crossref","unstructured":"Meyer, C.D.: Matrix Analysis and Applied Linear Algebra, vol. 1. SIAM (Society for Industrial and Applied Mathematics), Philadelphia (2000)","DOI":"10.1137\/1.9780898719512"},{"issue":"1969","key":"9979_CR26","doi-asserted-by":"crossref","first-page":"339","DOI":"10.1098\/rspa.1998.0164","volume":"454","author":"R Cleve","year":"1998","unstructured":"Cleve, R., Ekert, A., Macchiavello, C., Mosca, M.: Quantum algorithms revisited. Proc. R. Soc. Lond. 454(1969), 339\u2013354 (1998)","journal-title":"Proc. R. Soc. Lond."},{"key":"9979_CR27","doi-asserted-by":"crossref","unstructured":"H\u00f8yer, P., Mosca, M., de Wolf, R.: Quantum search on bounded-error inputs. In: Proceedings of the 30th international colloquium on automata, languages and programming (ICALP\u201903), volume 2719 of lecture notes in computer science, pp. 291\u2013299. Springer (2003)","DOI":"10.1007\/3-540-45061-0_25"},{"issue":"5","key":"9979_CR28","doi-asserted-by":"crossref","first-page":"1001","DOI":"10.1137\/S0097539791195877","volume":"23","author":"U Feige","year":"1994","unstructured":"Feige, U., Raghavan, P., Peleg, D., Upfal, E.: Computing with noisy information. SIAM J. Comput. 23(5), 1001\u20131018 (1994)","journal-title":"SIAM J. Comput."},{"issue":"5516","key":"9979_CR29","doi-asserted-by":"crossref","first-page":"472","DOI":"10.1126\/science.1057726","volume":"292","author":"E Farhi","year":"2001","unstructured":"Farhi, E., Goldstone, J., Gutmann, S., Lapan, J., Lundgren, A., Preda, D.: A quantum adiabatic evolution algorithm applied to random instances of an NP-complete problem. Science 292(5516), 472\u2013475 (2001)","journal-title":"Science"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-015-9979-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-015-9979-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-015-9979-8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,5,1]],"date-time":"2022-05-01T04:18:05Z","timestamp":1651378685000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-015-9979-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,3,3]]},"references-count":29,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2016,2]]}},"alternative-id":["9979"],"URL":"https:\/\/doi.org\/10.1007\/s00453-015-9979-8","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,3,3]]}}}