{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,13]],"date-time":"2026-03-13T16:01:13Z","timestamp":1773417673923,"version":"3.50.1"},"reference-count":60,"publisher":"Cambridge University Press (CUP)","issue":"3","license":[{"start":{"date-parts":[[2018,5,16]],"date-time":"2018-05-16T00:00:00Z","timestamp":1526428800000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Struct. Comp. Sci."],"published-print":{"date-parts":[[2019,3]]},"abstract":"<jats:p>We carry out a numerical study of the quantum walk search algorithm of Shenvi, Kempe and Whaley Shenvi <jats:italic>et al.<\/jats:italic> (2003) and the factors that affect its efficiency in finding an individual state from an unsorted set. Previous work has focused purely on the effects of the dimensionality of the dataset to be searched. In the current paper we consider the effects of interpolating between dimensions, the connectivity of the dataset and the possibility of disorder in the underlying substrate: all these factors affect the efficiency of the search algorithm. We show that in addition to the strong dependence on the spatial dimension of the structure to be searched, there are also secondary dependencies on the connectivity and symmetry of the lattice, with greater connectivity providing a more efficient algorithm. We also show that the algorithm can tolerate a non-trivial level of disorder in the underlying substrate.<\/jats:p>","DOI":"10.1017\/s0960129518000051","type":"journal-article","created":{"date-parts":[[2018,5,16]],"date-time":"2018-05-16T07:54:33Z","timestamp":1526457273000},"page":"389-429","source":"Crossref","is-referenced-by-count":9,"title":["The quantum walk search algorithm: factors affecting efficiency"],"prefix":"10.1017","volume":"29","author":[{"given":"NEIL B.","family":"LOVETT","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"MATTHEW","family":"EVERITT","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"ROBERT M.","family":"HEATH","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"VIV","family":"KENDON","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2018,5,16]]},"reference":[{"key":"S0960129518000051_ref44","unstructured":"Magniez F. , Santha M. and Szegedy M. (2005) Quantum algorithms for the triangle problem. In: Proceedings of the 16th annual ACM\u2013SIAM symposium on discrete algorithms (SODA) 1109\u20131117."},{"key":"S0960129518000051_ref60","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.60.2746"},{"key":"S0960129518000051_ref42","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973068.10"},{"key":"S0960129518000051_ref45","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.82.042341"},{"key":"S0960129518000051_ref6","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2004.54"},{"key":"S0960129518000051_ref14","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.102.180501"},{"key":"S0960129518000051_ref34","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.74.042334"},{"key":"S0960129518000051_ref28","doi-asserted-by":"publisher","DOI":"10.1080\/00107151031000110776"},{"key":"S0960129518000051_ref32","article-title":"Fractional scaling of quantum walks on percolation lattices","volume":"286","author":"Kendon","year":"2011","journal-title":"Journal of Physics: Conference Series"},{"key":"S0960129518000051_ref30","doi-asserted-by":"publisher","DOI":"10.1017\/S0960129507006354"},{"key":"S0960129518000051_ref52","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-79228-4_3"},{"key":"S0960129518000051_ref58","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.78.012310"},{"key":"S0960129518000051_ref26","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.76.012315"},{"key":"S0960129518000051_ref25","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.69.052323"},{"key":"S0960129518000051_ref24","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.82.012326"},{"key":"S0960129518000051_ref48","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.82.032330"},{"key":"S0960129518000051_ref7","doi-asserted-by":"publisher","DOI":"10.1145\/380752.380757"},{"key":"S0960129518000051_ref31","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.67.042315"},{"key":"S0960129518000051_ref3","unstructured":"Abal G. , Donangelo R. , Marquezino F. L. , Oliveira A. C. and Portugal R. (2009) Decoherence in Search Algorithms. In: Proceedings of the 29th Brazilian computer society congress (SEMISH) 293\u2013306."},{"key":"S0960129518000051_ref29","doi-asserted-by":"publisher","DOI":"10.1142\/S0219749906002195"},{"key":"S0960129518000051_ref21","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.69.026119"},{"key":"S0960129518000051_ref27","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-45198-3_30"},{"key":"S0960129518000051_ref23","doi-asserted-by":"publisher","DOI":"10.1088\/1751-8113\/42\/8\/085303"},{"key":"S0960129518000051_ref22","doi-asserted-by":"publisher","DOI":"10.1145\/237814.237866"},{"key":"S0960129518000051_ref36","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-14165-2_46"},{"key":"S0960129518000051_ref16","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.70.042312"},{"key":"S0960129518000051_ref50","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.79.012325"},{"key":"S0960129518000051_ref2","doi-asserted-by":"publisher","DOI":"10.1017\/S0960129510000332"},{"key":"S0960129518000051_ref5","doi-asserted-by":"publisher","DOI":"10.1142\/S0219749903000383"},{"key":"S0960129518000051_ref35","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.75.062332"},{"key":"S0960129518000051_ref4","doi-asserted-by":"publisher","DOI":"10.1145\/380752.380758"},{"key":"S0960129518000051_ref12","doi-asserted-by":"publisher","DOI":"10.1090\/conm\/305\/05215"},{"key":"S0960129518000051_ref13","unstructured":"Buhrman H. and Spalek R. (2004) Quantum verification of matrix products. In: Proceedings of the 17th annual ACM\u2013SIAM symposium on discrete algorithms (SODA) 880\u2013889."},{"key":"S0960129518000051_ref46","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45726-7_14"},{"key":"S0960129518000051_ref9","unstructured":"Ambainis A. , Kempe J. and Rivosh A. (2005) Coins make quantum walks faster. In: Proceedings of the 16th annual ACM\u2013SIAM symposium on discrete algorithms (SODA) 1099\u20131108."},{"key":"S0960129518000051_ref17","doi-asserted-by":"publisher","DOI":"10.1088\/0305-4470\/15\/8\/006"},{"key":"S0960129518000051_ref38","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.81.042330"},{"key":"S0960129518000051_ref41","doi-asserted-by":"publisher","DOI":"10.1007\/11523468_106"},{"key":"S0960129518000051_ref40","doi-asserted-by":"publisher","DOI":"10.1088\/0305-4470\/35\/12\/304"},{"key":"S0960129518000051_ref19","doi-asserted-by":"publisher","DOI":"10.1088\/0305-4470\/17\/2\/005"},{"key":"S0960129518000051_ref18","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.58.915"},{"key":"S0960129518000051_ref47","unstructured":"Nayak A. and Vishwanath A. (2000) Quantum walk on the line. DIMACS Technical Report 2000-43. Arxiv preprint arXiv:0010117."},{"key":"S0960129518000051_ref51","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.79.012323"},{"key":"S0960129518000051_ref53","doi-asserted-by":"publisher","DOI":"10.1142\/S0219749910006605"},{"key":"S0960129518000051_ref10","doi-asserted-by":"publisher","DOI":"10.1090\/conm\/305\/05212"},{"key":"S0960129518000051_ref54","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.67.052307"},{"key":"S0960129518000051_ref55","volume-title":"Introduction to percolation theory","author":"Stauffer","year":"1992"},{"key":"S0960129518000051_ref56","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2004.53"},{"key":"S0960129518000051_ref57","doi-asserted-by":"publisher","DOI":"10.1088\/1367-2630\/5\/1\/383"},{"key":"S0960129518000051_ref37","doi-asserted-by":"publisher","DOI":"10.1088\/1367-2630\/12\/12\/123018"},{"key":"S0960129518000051_ref59","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.82.042304"},{"key":"S0960129518000051_ref8","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-35656-8_7"},{"key":"S0960129518000051_ref11","doi-asserted-by":"crossref","first-page":"1510","DOI":"10.1137\/S0097539796300933","article-title":"Strengths and weaknesses of quantum computing.","volume":"26","author":"Bernstein","year":"1997","journal-title":"SIAM Journal of Computing"},{"key":"S0960129518000051_ref1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2003.1238194"},{"key":"S0960129518000051_ref49","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.82.032331"},{"key":"S0960129518000051_ref43","doi-asserted-by":"publisher","DOI":"10.1145\/1250790.1250874"},{"key":"S0960129518000051_ref39","doi-asserted-by":"publisher","DOI":"10.1007\/s11047-011-9279-4"},{"key":"S0960129518000051_ref20","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.72.047102"},{"key":"S0960129518000051_ref15","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.70.022314"},{"key":"S0960129518000051_ref33","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.73.032341"}],"container-title":["Mathematical Structures in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0960129518000051","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,12]],"date-time":"2019-04-12T00:32:51Z","timestamp":1555029171000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0960129518000051\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,5,16]]},"references-count":60,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2019,3]]}},"alternative-id":["S0960129518000051"],"URL":"https:\/\/doi.org\/10.1017\/s0960129518000051","relation":{},"ISSN":["0960-1295","1469-8072"],"issn-type":[{"value":"0960-1295","type":"print"},{"value":"1469-8072","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,5,16]]}}}