{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,11]],"date-time":"2026-06-11T10:47:05Z","timestamp":1781174825445,"version":"3.54.1"},"reference-count":46,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2024,12,18]],"date-time":"2024-12-18T00:00:00Z","timestamp":1734480000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100003593","name":"CNPq","doi-asserted-by":"crossref","award":["140897\/2020-8"],"award-info":[{"award-number":["140897\/2020-8"]}],"id":[{"id":"10.13039\/501100003593","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100004586","name":"FAPERJ","doi-asserted-by":"crossref","award":["CNE E-26\/202.872\/2018"],"award-info":[{"award-number":["CNE E-26\/202.872\/2018"]}],"id":[{"id":"10.13039\/501100004586","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100003593","name":"CNPq","doi-asserted-by":"crossref","award":["308923\/2019-7"],"award-info":[{"award-number":["308923\/2019-7"]}],"id":[{"id":"10.13039\/501100003593","id-type":"DOI","asserted-by":"crossref"}]},{"name":"JST SPRING","award":["JPMJSP2114"],"award-info":[{"award-number":["JPMJSP2114"]}]},{"name":"JSPS KAKENHI","award":["JP20K03551, JP23K03064"],"award-info":[{"award-number":["JP20K03551, JP23K03064"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Transactions on Quantum Computing"],"published-print":{"date-parts":[[2024,12,31]]},"abstract":"<jats:p>\n            The quantum-walk-based spatial search problem aims to find a marked vertex using a quantum walk on a graph with marked vertices. We describe a framework for determining the computational complexity of spatial search by continuous-time quantum walk on arbitrary graphs by providing a recipe for finding the optimal running time and the success probability of the algorithm. The quantum walk is driven by a Hamiltonian derived from the adjacency matrix of the graph modified by the presence of the marked vertices. The success of our framework depends on the knowledge of the eigenvalues and eigenvectors of the adjacency matrix. The spectrum of the Hamiltonian is subsequently obtained from the roots of the determinant of a real symmetric matrix\n            <jats:italic>M<\/jats:italic>\n            , the dimensions of which depend on the number of marked vertices. The eigenvectors are determined from a basis of the kernel of\n            <jats:italic>M<\/jats:italic>\n            . We show each step of the framework by solving the spatial searching problem on the Johnson graphs with a fixed diameter and with two marked vertices. Our calculations show that the optimal running time is\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(O(\\sqrt {N})\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            with an asymptotic probability of 1+\n            <jats:italic>o<\/jats:italic>\n            (1), where\n            <jats:italic>N<\/jats:italic>\n            is the number of vertices.\n          <\/jats:p>","DOI":"10.1145\/3706064","type":"journal-article","created":{"date-parts":[[2024,11,27]],"date-time":"2024-11-27T09:50:58Z","timestamp":1732701058000},"page":"1-20","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["Multimarked Spatial Search by Continuous-Time Quantum Walk"],"prefix":"10.1145","volume":"5","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-2316-445X","authenticated-orcid":false,"given":"Pedro","family":"Lug\u00e3o","sequence":"first","affiliation":[{"name":"Federal Center for Technological Education Celso Suckow da Fonseca, Petr\u00f3polis, Brazil"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0894-4279","authenticated-orcid":false,"given":"Renato","family":"Portugal","sequence":"additional","affiliation":[{"name":"Laborat\u00f3rio Nacional de Computa\u00e7\u00e3o Cient\u00edfica, Petropolis, Brazil"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9440-6236","authenticated-orcid":false,"given":"Mohamed","family":"Sabri","sequence":"additional","affiliation":[{"name":"Open University of Sri Lanka, Nugegoda, Sri Lanka"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5958-0375","authenticated-orcid":false,"given":"Hajime","family":"Tanaka","sequence":"additional","affiliation":[{"name":"Research Center for Pure and Applied Mathematics, Graduate School of Information Sciences, Tohoku University, Sendai, Japan"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2024,12,18]]},"reference":[{"key":"e_1_3_4_2_2","doi-asserted-by":"crossref","unstructured":"J. Abhijith and A. Patel. 2018. Spatial search on graphs with multiple targets using flip-flop quantum walk. Quant. Inf. Comput. 18 15\u201316 (2018) 1295\u20131331.","DOI":"10.26421\/QIC18.15-16-3"},{"key":"e_1_3_4_3_2","doi-asserted-by":"publisher","DOI":"10.1145\/3357713.3384252"},{"key":"e_1_3_4_4_2","first-page":"1099","volume-title":"16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201905)","author":"Ambainis A.","year":"2005","unstructured":"A. Ambainis, J. Kempe, and A. Rivosh. 2005. Coins make quantum walks faster. In 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201905). 1099\u20131108."},{"key":"e_1_3_4_5_2","doi-asserted-by":"publisher","unstructured":"Simon Apers Shantanav Chakraborty Leonardo Novo and J\u00e9r\u00e9mie Roland. 2022. Quadratic speedup for spatial search by continuous-time quantum walk. Phys. Rev. Lett. 129 16 (Oct.2022) 160502. DOI:10.1103\/PhysRevLett.129.160502","DOI":"10.1103\/PhysRevLett.129.160502"},{"key":"e_1_3_4_6_2","volume-title":"Algebraic Combinatorics I","author":"Bannai E.","year":"1984","unstructured":"E. Bannai and T. Ito. 1984. Algebraic Combinatorics I. Benjamin\/Cummings, Menlo Park, CA."},{"key":"e_1_3_4_7_2","doi-asserted-by":"publisher","unstructured":"Claudia Benedetti Dario Tamascelli Matteo G. A. Paris and Andrea Crespi. 2021. Quantum spatial search in two-dimensional waveguide arrays. Phys. Rev. Appl. 16 5 (2021) 054036. DOI:10.1103\/PhysRevApplied.16.054036","DOI":"10.1103\/PhysRevApplied.16.054036"},{"key":"e_1_3_4_8_2","unstructured":"P. Benioff. 2002. Space searches with a quantum robot. AMS Contemp. Math Series 305 (2002). Retrieved from http:\/\/www.citebase.org\/abstract?id=oai:arXiv.org:quant-ph\/0003006"},{"key":"e_1_3_4_9_2","doi-asserted-by":"publisher","unstructured":"G. A. Bezerra P. H. G. Lug\u00e3o and R. Portugal. 2021. Quantum-walk-based search algorithms with multiple marked vertices. Phys. Rev. A 103 6 (2021) 062202. DOI:10.1103\/PhysRevA.103.062202","DOI":"10.1103\/PhysRevA.103.062202"},{"key":"e_1_3_4_10_2","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-0653-8","volume-title":"Matrix Analysis","author":"Bhatia Rajendra","year":"1997","unstructured":"Rajendra Bhatia. 1997. Matrix Analysis. Vol. 169. Springer."},{"key":"e_1_3_4_11_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-74341-2"},{"key":"e_1_3_4_12_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4614-1939-6"},{"key":"e_1_3_4_13_2","doi-asserted-by":"publisher","unstructured":"Marco Cattaneo Matteo A. C. Rossi Matteo G. A. Paris and Sabrina Maniscalco. 2018. Quantum spatial search on graphs subject to dynamical noise. Phys. Rev. A 98 5 (2018) 052347. DOI:10.1103\/PhysRevA.98.052347","DOI":"10.1103\/PhysRevA.98.052347"},{"key":"e_1_3_4_14_2","doi-asserted-by":"publisher","unstructured":"B. Chagas R. Portugal S. Boettcher and E. Segawa. 2018. Staggered quantum walk on hexagonal lattices. Phys. Rev. A 98 5 (2018) 052310. DOI:10.1103\/PhysRevA.98.052310","DOI":"10.1103\/PhysRevA.98.052310"},{"key":"e_1_3_4_15_2","doi-asserted-by":"publisher","unstructured":"S. Chakraborty L. Novo A. Ambainis and Y. Omar. 2016. Spatial search by quantum walk is optimal for almost all graphs. Phys. Rev. Lett. 116 10 (2016) 100501. DOI:10.1103\/PhysRevLett.116.100501","DOI":"10.1103\/PhysRevLett.116.100501"},{"key":"e_1_3_4_16_2","doi-asserted-by":"publisher","unstructured":"S. Chakraborty L. Novo and J. Roland. 2020. Finding a marked node on any graph via continuous-time quantum walks. Phys. Rev. A 102 2 (2020) 022227. DOI:10.1103\/PhysRevA.102.022227","DOI":"10.1103\/PhysRevA.102.022227"},{"key":"e_1_3_4_17_2","doi-asserted-by":"publisher","unstructured":"S. Chakraborty L. Novo and J. Roland. 2020. Optimality of spatial search via continuous-time quantum walks. Phys. Rev. A 102 3 (2020) 032214. DOI:10.1103\/PhysRevA.102.032214","DOI":"10.1103\/PhysRevA.102.032214"},{"key":"e_1_3_4_18_2","doi-asserted-by":"publisher","unstructured":"A. M. Childs E. Farhi and S. Gutmann. 2002. An example of the difference between quantum and classical random walks. Quant. Inf. Process. 1 1 (2002) 35\u201343. DOI:10.1023\/A:1019609420309","DOI":"10.1023\/A:1019609420309"},{"key":"e_1_3_4_19_2","doi-asserted-by":"publisher","unstructured":"Andrew M. Childs and Jeffrey Goldstone. 2004. Spatial search by quantum walk. Phys. Rev. A 70 2 (Aug.2004) 022314. DOI:10.1103\/PhysRevA.70.022314","DOI":"10.1103\/PhysRevA.70.022314"},{"key":"e_1_3_4_20_2","doi-asserted-by":"publisher","unstructured":"Michele Delvecchio Caspar Groiseau Francesco Petiziol Gil S. Summy and Sandro Wimberger. 2020. Quantum search with a continuous-time quantum walk in momentum space. J. Phys. B: Atom. Molec. Optic. Phys. 53 6 (2020) 065301. DOI:10.1088\/1361-6455\/ab63ad","DOI":"10.1088\/1361-6455\/ab63ad"},{"key":"e_1_3_4_21_2","doi-asserted-by":"crossref","unstructured":"E. Farhi and S. Gutmann. 1998. Quantum computation and decision trees. Phys. Rev. A 58 (1998) 915\u2013928.","DOI":"10.1103\/PhysRevA.58.915"},{"key":"e_1_3_4_22_2","doi-asserted-by":"publisher","unstructured":"L. K. Grover. 1997. Quantum mechanics helps in searching for a needle in a haystack. Phys. Rev. Lett. 79 2 (1997) 325\u2013328. DOI:10.1103\/PhysRevLett.79.325","DOI":"10.1103\/PhysRevLett.79.325"},{"key":"e_1_3_4_23_2","doi-asserted-by":"publisher","unstructured":"Rebekah Herrman and Travis S. Humble. 2019. Continuous-time quantum walks on dynamic graphs. Phys. Rev. A 100 1 (2019) 012306. DOI:10.1103\/PhysRevA.100.012306","DOI":"10.1103\/PhysRevA.100.012306"},{"key":"e_1_3_4_24_2","volume-title":"Matrix Analysis (2nd ed.)","author":"Horn Roger A.","year":"2013","unstructured":"Roger A. Horn and Charles R. Johnson. 2013. Matrix Analysis (2nd ed.). Cambridge University Press, Cambridge."},{"key":"e_1_3_4_25_2","volume-title":"Function Theory of Several Complex Variables (2nd ed.)","author":"Krantz Steven G.","year":"1992","unstructured":"Steven G. Krantz. 1992. Function Theory of Several Complex Variables (2nd ed.). AMS Chelsea Publishing, Providence."},{"key":"e_1_3_4_26_2","doi-asserted-by":"crossref","unstructured":"H. Krovi F. Magniez M. Ozols and J. Roland. 2016. Quantum walks can find a marked element on any graph. Algorithmica 74 (2016) 851\u2013907.","DOI":"10.1007\/s00453-015-9979-8"},{"key":"e_1_3_4_27_2","doi-asserted-by":"publisher","unstructured":"Xi Li Hanwu Chen Yue Ruan Zhihao Liu and Wenjie Liu. 2019. Continuous-time quantum walks on strongly regular graphs with loops and its application to spatial search for multiple marked vertices. Quant. Inf. Process. 18 6 (2019) 195. DOI:10.1007\/s11128-019-2250-5","DOI":"10.1007\/s11128-019-2250-5"},{"key":"e_1_3_4_28_2","doi-asserted-by":"publisher","unstructured":"Pedro H. G. Lug\u00e3o and Renato Portugal. 2024. Quantum search by continuous-time quantum walk on t-designs. Quant. Inf. Process. 23 4 (05 Apr.2024) 140. DOI:10.1007\/s11128-024-04355-4","DOI":"10.1007\/s11128-024-04355-4"},{"key":"e_1_3_4_29_2","doi-asserted-by":"crossref","unstructured":"Fr\u00e9d\u00e9ric Magniez Ashwin Nayak Peter C. Richter and Miklos Santha. 2012. On the hitting times of quantum versus random walks. Algorithmica 63 1-2 (June2012) 91\u2013116.","DOI":"10.1007\/s00453-011-9521-6"},{"key":"e_1_3_4_30_2","doi-asserted-by":"publisher","unstructured":"F. Magniez A. Nayak J. Roland and M. Santha. 2011. Search via quantum walk. SIAM J. Comput. 40 1 (2011) 142\u2013164. DOI:10.1137\/090745854","DOI":"10.1137\/090745854"},{"key":"e_1_3_4_31_2","doi-asserted-by":"crossref","unstructured":"W. J. Martin and H. Tanaka. 2009. Commutative association schemes. Eur. J. Combinat. 30 6 (2009) 1497\u20131525.","DOI":"10.1016\/j.ejc.2008.11.001"},{"key":"e_1_3_4_32_2","doi-asserted-by":"publisher","unstructured":"Matteo G. A. Paris Claudia Benedetti and Stefano Olivares. 2021. Improving quantum search on simple graphs by pretty good structured oracles. Symmetry 13 1 (2021). DOI:10.3390\/sym13010096","DOI":"10.3390\/sym13010096"},{"key":"e_1_3_4_33_2","doi-asserted-by":"publisher","unstructured":"Pascal Philipp Lu\u00eds Tarrataca and Stefan Boettcher. 2016. Continuous-time quantum search on balanced trees. Phys. Rev. A 93 3 (2016) 032305. DOI:10.1103\/PhysRevA.93.032305","DOI":"10.1103\/PhysRevA.93.032305"},{"key":"e_1_3_4_34_2","doi-asserted-by":"publisher","unstructured":"R. Portugal and T. D. Fernandes. 2017. Quantum search on the two-dimensional lattice using the staggered model with Hamiltonians. Phys. Rev. A 95 4 (2017) 042341. DOI:10.1103\/PhysRevA.95.042341","DOI":"10.1103\/PhysRevA.95.042341"},{"key":"e_1_3_4_35_2","doi-asserted-by":"publisher","unstructured":"Dengke Qu Samuel Marsh Kunkun Wang Lei Xiao Jingbo Wang and Peng Xue. 2022. Deterministic search on star graphs via quantum walks. Phys. Rev. Lett. 128 5 (2022) 050501. DOI:10.1103\/PhysRevLett.128.050501","DOI":"10.1103\/PhysRevLett.128.050501"},{"key":"e_1_3_4_36_2","doi-asserted-by":"crossref","unstructured":"N. Shenvi J. Kempe and K. B. Whaley. 2003. A quantum random walk search algorithm. Phys. Rev. A 67 5 (2003) 052307.","DOI":"10.1103\/PhysRevA.67.052307"},{"key":"e_1_3_4_37_2","volume-title":"Introduction to the Theory of Computation","author":"Sipser M.","year":"2012","unstructured":"M. Sipser. 2012. Introduction to the Theory of Computation. Cengage Learning. 2012938665 Retrieved from https:\/\/books.google.com.br\/books?id=H94JzgEACAAJ"},{"key":"e_1_3_4_38_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-11470-0_1"},{"key":"e_1_3_4_39_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2004.53"},{"key":"e_1_3_4_40_2","doi-asserted-by":"publisher","unstructured":"H. Tanaka M. Sabri and R. Portugal. 2022. Spatial search on Johnson graphs by continuous-time quantum walk. Quant. Inf. Process. 21 2 (Jan.2022) 74. DOI:10.1007\/s11128-022-03417-9","DOI":"10.1007\/s11128-022-03417-9"},{"key":"e_1_3_4_41_2","doi-asserted-by":"publisher","unstructured":"Paul Terwilliger. 2005. Two linear transformations each tridiagonal with respect to an eigenbasis of the other; comments on the parameter array. Des. Codes Cryptog. 34 2-3 (2005) 307\u2013332. DOI:10.1007\/s10623-004-4862-7","DOI":"10.1007\/s10623-004-4862-7"},{"key":"e_1_3_4_42_2","doi-asserted-by":"publisher","unstructured":"E. R. van Dam J. H. Koolen and H. Tanaka. 2016. Distance-regular graphs. Electron. J. Combinat. Dynam. Surv. DS22 (2016). DOI:10.37236\/4925","DOI":"10.37236\/4925"},{"key":"e_1_3_4_43_2","doi-asserted-by":"publisher","unstructured":"Kunkun Wang Yuhao Shi Lei Xiao Jingbo Wang Yogesh N. Joglekar and Peng Xue. 2020. Experimental realization of continuous-time quantum walks on directed graphs and their application in PageRank. Optica 7 11 (2020) 1524\u20131530. DOI:10.1364\/OPTICA.396228","DOI":"10.1364\/OPTICA.396228"},{"key":"e_1_3_4_44_2","doi-asserted-by":"publisher","unstructured":"Yunkai Wang Shengjun Wu and Wei Wang. 2019. Controlled quantum search on structured databases. Phys. Rev. Res. 1 3 (2019) 033016. DOI:10.1103\/PhysRevResearch.1.033016","DOI":"10.1103\/PhysRevResearch.1.033016"},{"key":"e_1_3_4_45_2","doi-asserted-by":"publisher","unstructured":"Thomas G. Wong. 2016. Quantum walk search on Johnson graphs. J. Phys. A: Math. Theoret. 49 19 (2016) 195303. DOI:10.1088\/1751-8113\/49\/19\/195303","DOI":"10.1088\/1751-8113\/49\/19\/195303"},{"key":"e_1_3_4_46_2","doi-asserted-by":"publisher","unstructured":"Thomas G. Wong. 2016. Spatial search by continuous-time quantum walk with multiple marked vertices. Quant. Inf. Process. 15 4 (01 Apr.2016) 1411\u20131443. DOI:10.1007\/s11128-015-1239-y","DOI":"10.1007\/s11128-015-1239-y"},{"key":"e_1_3_4_47_2","doi-asserted-by":"publisher","unstructured":"Thomas G. Wong Lu\u00eds Tarrataca and Nikolay Nahimov. 2016. Laplacian versus adjacency matrix in quantum walk search. Quant. Inf. Process. 15 10 (2016) 4029\u20134048. DOI:10.1007\/s11128-016-1373-1","DOI":"10.1007\/s11128-016-1373-1"}],"container-title":["ACM Transactions on Quantum Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3706064","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3706064","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T01:18:13Z","timestamp":1750295893000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3706064"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,12,18]]},"references-count":46,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2024,12,31]]}},"alternative-id":["10.1145\/3706064"],"URL":"https:\/\/doi.org\/10.1145\/3706064","relation":{},"ISSN":["2643-6809","2643-6817"],"issn-type":[{"value":"2643-6809","type":"print"},{"value":"2643-6817","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,12,18]]},"assertion":[{"value":"2023-06-02","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-10-31","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-12-18","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}