{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T17:12:47Z","timestamp":1760202767305,"version":"3.41.0"},"reference-count":32,"publisher":"Springer Science and Business Media LLC","issue":"7","license":[{"start":{"date-parts":[[2018,5,19]],"date-time":"2018-05-19T00:00:00Z","timestamp":1526688000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100003593","name":"Conselho Nacional de Desenvolvimento Cient\u00edfico e Tecnol\u00f3gico","doi-asserted-by":"publisher","award":["303406\/2015-1"],"award-info":[{"award-number":["303406\/2015-1"]}],"id":[{"id":"10.13039\/501100003593","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Quantum Inf Process"],"published-print":{"date-parts":[[2018,7]]},"DOI":"10.1007\/s11128-018-1930-x","type":"journal-article","created":{"date-parts":[[2018,5,19]],"date-time":"2018-05-19T13:48:13Z","timestamp":1526737693000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["Element distinctness revisited"],"prefix":"10.1007","volume":"17","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-0894-4279","authenticated-orcid":false,"given":"Renato","family":"Portugal","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2018,5,19]]},"reference":[{"key":"1930_CR1","doi-asserted-by":"crossref","unstructured":"Yao, A.C.C.: Near-optimal time\u2013space tradeoff for element distinctness. In: Proceedings of 29th Annual Symposium on Foundations of Computer Science, pp. 91\u201397 (1988)","DOI":"10.1109\/SFCS.1988.21925"},{"issue":"4","key":"1930_CR2","doi-asserted-by":"publisher","first-page":"357","DOI":"10.1007\/BF01270387","volume":"6","author":"D Grigoriev","year":"1996","unstructured":"Grigoriev, D., Karpinski, M., Heide, F.M., Smolensky, R.: A lower bound for randomized algebraic decision trees. Comput. Complex. 6(4), 357\u2013375 (1996)","journal-title":"Comput. Complex."},{"issue":"2","key":"1930_CR3","doi-asserted-by":"publisher","first-page":"154","DOI":"10.1145\/636865.636867","volume":"50","author":"P Beame","year":"2003","unstructured":"Beame, P., Saks, M., Sun, X., Vee, E.: Time\u2013space trade-off lower bounds for randomized computation of decision problems. J. ACM 50(2), 154\u2013195 (2003)","journal-title":"J. ACM"},{"issue":"4","key":"1930_CR4","doi-asserted-by":"publisher","first-page":"595","DOI":"10.1145\/1008731.1008735","volume":"51","author":"S Aaronson","year":"2004","unstructured":"Aaronson, S., Shi, Y.: Quantum lower bounds for the collision and the element distinctness problems. J. ACM 51(4), 595\u2013605 (2004)","journal-title":"J. ACM"},{"key":"1930_CR5","doi-asserted-by":"publisher","first-page":"37","DOI":"10.4086\/toc.2005.v001a003","volume":"1","author":"A Ambainis","year":"2005","unstructured":"Ambainis, A.: Polynomial degree and lower bounds in quantum complexity: collision and element distinctness with small range. Theory Comput. 1, 37\u201346 (2005)","journal-title":"Theory Comput."},{"issue":"6","key":"1930_CR6","doi-asserted-by":"publisher","first-page":"1324","DOI":"10.1137\/S0097539702402780","volume":"34","author":"H Buhrman","year":"2005","unstructured":"Buhrman, H., D\u00fcrr, C., Heiligman, M., H\u00f8yer, P., Magniez, F., Santha, M., de Wolf, R.: Quantum algorithms for element distinctness. SIAM J. Comput. 34(6), 1324\u20131330 (2005)","journal-title":"SIAM J. Comput."},{"key":"1930_CR7","doi-asserted-by":"crossref","unstructured":"Ambainis, A.: Quantum walk algorithm for element distinctness. In: FOCS\u201904: Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, pp. 22\u201331, Washington, DC (2004)","DOI":"10.1109\/FOCS.2004.54"},{"issue":"1","key":"1930_CR8","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 J. Comput. 37(1), 210\u2013239 (2007)","journal-title":"SIAM J. Comput."},{"key":"1930_CR9","doi-asserted-by":"crossref","unstructured":"Szegedy, M.: Quantum speed-up of Markov chain based algorithms. In: Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, FOCS\u201904, pp. 32\u201341, Washington, DC (2004)","DOI":"10.1109\/FOCS.2004.53"},{"issue":"2","key":"1930_CR10","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 J. Comput. 37(2), 413\u2013424 (2007)","journal-title":"SIAM J. Comput."},{"issue":"7","key":"1930_CR11","first-page":"593","volume":"5","author":"AM Childs","year":"2005","unstructured":"Childs, A.M., Eisenberg, J.M.: Quantum algorithms for subset finding. Quantum Inf. Comput. 5(7), 593\u2013604 (2005)","journal-title":"Quantum Inf. Comput."},{"key":"1930_CR12","doi-asserted-by":"publisher","first-page":"29","DOI":"10.4086\/toc.2005.v001a002","volume":"1","author":"S Kutin","year":"2005","unstructured":"Kutin, S.: Quantum lower bound for the collision problem with small range. Theory Comput. 1, 29\u201336 (2005)","journal-title":"Theory Comput."},{"key":"1930_CR13","doi-asserted-by":"crossref","unstructured":"Brassard, G., H\u00f8yer, P., Tapp, A.: Quantum cryptanalysis of hash and claw-free functions. In: Proceedings of LATIN\u201998: Theoretical Informatics: Third Latin American Symposium, Campinas, pp. 163\u2013169 (1998)","DOI":"10.1007\/BFb0054319"},{"key":"1930_CR14","doi-asserted-by":"crossref","unstructured":"Santha, M.: Quantum walk based search algorithms. In: Proceedings of Theory and Applications of Models of Computation: 5th International Conference, TAMC 2008, Xi\u2019an, pp. 31\u201346 (2008)","DOI":"10.1007\/978-3-540-79228-4_3"},{"issue":"2","key":"1930_CR15","doi-asserted-by":"publisher","first-page":"581","DOI":"10.1007\/s00220-009-0930-1","volume":"294","author":"AM Childs","year":"2010","unstructured":"Childs, A.M.: On the relationship between continuous- and discrete-time quantum walk. Commun. Math. Phys. 294(2), 581\u2013603 (2010)","journal-title":"Commun. Math. Phys."},{"key":"1930_CR16","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.: Quantum computation and decision trees. Phys. Rev. A 58, 915\u2013928 (1998)","journal-title":"Phys. Rev. A"},{"key":"1930_CR17","doi-asserted-by":"crossref","unstructured":"Belovs, A.: Learning-graph-based quantum algorithm for $$k$$ k -distinctness. In: Proceedings of 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science, pp. 207\u2013216 (2012)","DOI":"10.1109\/FOCS.2012.18"},{"key":"1930_CR18","doi-asserted-by":"crossref","unstructured":"Belovs, A., Childs, A.M., Jeffery, S., Kothari, R., Magniez, F.: Time-efficient quantum walks for 3-distinctness. In: Proceedings of Automata, Languages, and Programming: 40th International Colloquium, ICALP 2013, Riga, pp. 105\u2013122 (2013)","DOI":"10.1007\/978-3-642-39206-1_10"},{"key":"1930_CR19","first-page":"2014","volume":"4","author":"A Rosmanis","year":"2014","unstructured":"Rosmanis, A.: Quantum adversary lower bound for element distinctness with small range. Chic. J. Theor. Comput. Sci. 4, 2014 (2014)","journal-title":"Chic. J. Theor. Comput. Sci."},{"key":"1930_CR20","doi-asserted-by":"publisher","first-page":"71","DOI":"10.4213\/mvk185","volume":"7","author":"M Kaplan","year":"2016","unstructured":"Kaplan, M.: Quantum attacks against iterated block ciphers. Mat. Vopr. Kriptogr. 7, 71\u201390 (2016)","journal-title":"Mat. Vopr. Kriptogr."},{"issue":"2","key":"1930_CR21","doi-asserted-by":"publisher","first-page":"509","DOI":"10.1007\/s00453-016-0206-z","volume":"79","author":"S Jeffery","year":"2017","unstructured":"Jeffery, S., Magniez, F., de Wolf, R.: Optimal parallel quantum query algorithms. Algorithmica 79(2), 509\u2013529 (2017)","journal-title":"Algorithmica"},{"issue":"1","key":"1930_CR22","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1007\/s11128-015-1149-z","volume":"15","author":"R Portugal","year":"2016","unstructured":"Portugal, R., Santos, R.A.M., Fernandes, T.D., Gon\u00e7alves, D.N.: The staggered quantum walk model. Quantum Inf. Process. 15(1), 85\u2013101 (2016)","journal-title":"Quantum Inf. Process."},{"issue":"4","key":"1930_CR23","doi-asserted-by":"publisher","first-page":"1387","DOI":"10.1007\/s11128-015-1230-7","volume":"15","author":"R Portugal","year":"2016","unstructured":"Portugal, R.: Establishing the equivalence between Szegedy\u2019s and coined quantum walks using the staggered model. Quantum Inf. Process. 15(4), 1387\u20131409 (2016)","journal-title":"Quantum Inf. Process."},{"key":"1930_CR24","doi-asserted-by":"publisher","first-page":"062335","DOI":"10.1103\/PhysRevA.93.062335","volume":"93","author":"R Portugal","year":"2016","unstructured":"Portugal, R.: Staggered quantum walks on graphs. Phys. Rev. A 93, 062335 (2016)","journal-title":"Phys. Rev. A"},{"key":"1930_CR25","unstructured":"Abreu, A.S.: Tessela\u00e7 oes em grafos e suas aplica\u00e7 oes em computa\u00e7 ao qu\u00e2ntica. Master\u2019s thesis, UFRJ (2017)"},{"issue":"5","key":"1930_CR26","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., Whaley, K.B.: A quantum random walk search algorithm. Phys. Rev. A 67(5), 052307 (2003)","journal-title":"Phys. Rev. A"},{"key":"1930_CR27","unstructured":"Ambainis, A., Kempe, J., Rivosh, A.: Coins make quantum walks faster. In: Proceedings of Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pp. 1099\u20131108 (2005)"},{"key":"1930_CR28","doi-asserted-by":"publisher","first-page":"042331","DOI":"10.1103\/PhysRevA.86.042331","volume":"86","author":"A Tulsi","year":"2012","unstructured":"Tulsi, A.: General framework for quantum search algorithms. Phys. Rev. A 86, 042331 (2012)","journal-title":"Phys. Rev. A"},{"key":"1930_CR29","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4614-6336-8","volume-title":"Quantum Walks and Search Algorithms","author":"R Portugal","year":"2013","unstructured":"Portugal, R.: Quantum Walks and Search Algorithms. Springer, New York (2013)"},{"key":"1930_CR30","volume-title":"Introduction to Graph Theory","author":"DB West","year":"2000","unstructured":"West, D.B.: Introduction to Graph Theory. Prentice Hall, Upper Saddle River (2000)"},{"key":"1930_CR31","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898719796","volume-title":"Graph Classes: A Survey","author":"A Brandst\u00e4dt","year":"1999","unstructured":"Brandst\u00e4dt, A., Le, V.B., Spinrad, J.P.: Graph Classes: A Survey. SIAM, Philadelphia (1999)"},{"key":"1930_CR32","doi-asserted-by":"publisher","DOI":"10.21236\/AD0705364","volume-title":"Graph Theory","author":"F Harary","year":"1969","unstructured":"Harary, F.: Graph Theory. Addison-Wesley, Boston (1969)"}],"container-title":["Quantum Information Processing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s11128-018-1930-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11128-018-1930-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11128-018-1930-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,7,4]],"date-time":"2025-07-04T16:50:49Z","timestamp":1751647849000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s11128-018-1930-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,5,19]]},"references-count":32,"journal-issue":{"issue":"7","published-print":{"date-parts":[[2018,7]]}},"alternative-id":["1930"],"URL":"https:\/\/doi.org\/10.1007\/s11128-018-1930-x","relation":{},"ISSN":["1570-0755","1573-1332"],"issn-type":[{"type":"print","value":"1570-0755"},{"type":"electronic","value":"1573-1332"}],"subject":[],"published":{"date-parts":[[2018,5,19]]},"assertion":[{"value":"5 December 2017","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"9 May 2018","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 May 2018","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"163"}}