{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T02:35:29Z","timestamp":1760236529498,"version":"build-2065373602"},"reference-count":30,"publisher":"MDPI AG","issue":"12","license":[{"start":{"date-parts":[[2021,11,28]],"date-time":"2021-11-28T00:00:00Z","timestamp":1638057600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Symmetry"],"abstract":"<jats:p>Maze-solving by natural phenomena is a symbolic result of the autonomous optimization induced by a natural system. We present a method for finding the shortest path on a maze consisting of a bipartite graph using a discrete-time quantum walk, which is a toy model of many kinds of quantum systems. By evolving the amplitude distribution according to the quantum walk on a kind of network with sinks, which is the exit of the amplitude, the amplitude distribution remains eternally on the paths between two self-loops indicating the start and the goal of the maze. We performed a numerical analysis of some simple cases and found that the shortest paths were detected by the chain of the maximum trapped densities in most cases of bipartite graphs. The counterintuitive dependence of the convergence steps on the size of the structure of the network was observed in some cases, implying that the asymmetry of the network accelerates or decelerates the convergence process. The relation between the amplitude remaining and distance of the path is also discussed briefly.<\/jats:p>","DOI":"10.3390\/sym13122263","type":"journal-article","created":{"date-parts":[[2021,12,1]],"date-time":"2021-12-01T03:12:40Z","timestamp":1638328360000},"page":"2263","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Maze Solving by a Quantum Walk with Sinks and Self-Loops: Numerical Analysis"],"prefix":"10.3390","volume":"13","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5657-4458","authenticated-orcid":false,"given":"Leo","family":"Matsuoka","sequence":"first","affiliation":[{"name":"Faculty of Engineering, Hiroshima Institute of Technology, Hiroshima 731-5193, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kenta","family":"Yuki","sequence":"additional","affiliation":[{"name":"Independent Researcher, Tokyo 160-0023, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7868-106X","authenticated-orcid":false,"given":"Hynek","family":"Lavi\u010dka","sequence":"additional","affiliation":[{"name":"Blocksize Capital GmbH, 60329 Frankfurt am Main, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1285-5252","authenticated-orcid":false,"given":"Etsuo","family":"Segawa","sequence":"additional","affiliation":[{"name":"Graduate School of Environment Information Sciences, Yokohama National University, Yokohama 240-8501, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2021,11,28]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"269","DOI":"10.1007\/BF01386390","article-title":"A note on two problems in connexion with graphs","volume":"1","author":"Dijkstra","year":"1959","journal-title":"Numer. Math."},{"unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., and Stein, C. (2009). Introduction to Algorithms, The MIT Press. [3rd ed.].","key":"ref_2"},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"868","DOI":"10.1126\/science.267.5199.868","article-title":"Navigating Complex Labyrinths: Optimal Paths from Chemical Waves","volume":"267","author":"Steinbock","year":"1995","journal-title":"Science"},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"470","DOI":"10.1038\/35035159","article-title":"Maze-solving by an amoeboid organism","volume":"407","author":"Nakagaki","year":"2000","journal-title":"Nature"},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"113","DOI":"10.1039\/b200589a","article-title":"Glow discharge in microfluidic chips for visible analog computing","volume":"2","author":"Reyes","year":"2002","journal-title":"Lab Chip"},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"11682","DOI":"10.1038\/ncomms11682","article-title":"Fast escape of a quantum walker from an integrated photonic maze","volume":"7","author":"Caruso","year":"2016","journal-title":"Nat. Commun."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"1015","DOI":"10.1007\/s11128-012-0432-5","article-title":"Quantum walks: A comprehensive review","volume":"11","year":"2012","journal-title":"Quantum Inf. Process"},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"339","DOI":"10.1080\/00107510902734722","article-title":"Quantum random walks: An introductory overview","volume":"50","author":"Kempe","year":"2009","journal-title":"Contemp. Phys."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"47","DOI":"10.4086\/toc.2005.v001a004","article-title":"Quantum search of spatial regions","volume":"1","author":"Aaronson","year":"2005","journal-title":"Theory Comput."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"022314","DOI":"10.1103\/PhysRevA.70.022314","article-title":"Spatial search by quantum walk","volume":"70","author":"Childs","year":"2004","journal-title":"Phys. Rev. A"},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"052307","DOI":"10.1103\/PhysRevA.67.052307","article-title":"A Quantum Random Walk Search Algorithm","volume":"67","author":"Shenvi","year":"2002","journal-title":"Phys. Rev. A"},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"325","DOI":"10.1103\/PhysRevLett.79.325","article-title":"Quantum Mechanics Helps in Searching for a Needle in a Haystack","volume":"79","author":"Grover","year":"1997","journal-title":"Phys. Rev. Lett."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"032314","DOI":"10.1103\/PhysRevA.68.032314","article-title":"Quantum walks based on an interferometric analogy","volume":"68","author":"Hillery","year":"2003","journal-title":"Phys. Rev. A"},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"395202","DOI":"10.1088\/1751-8121\/ab370b","article-title":"A dynamical system induced by quantum walk","volume":"52","author":"Higuchi","year":"2019","journal-title":"J. Phys. A Math. Theor."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"032113","DOI":"10.1103\/PhysRevA.101.032113","article-title":"Counterintuitive role of geometry in transport by quantum walks","volume":"101","author":"Jex","year":"2020","journal-title":"Phys. Rev. A"},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"603","DOI":"10.1007\/s10955-020-02591-3","article-title":"Electric Circuit Induced by Quantum Walk","volume":"181","author":"Higuchi","year":"2020","journal-title":"J. Stat. Phys."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"93","DOI":"10.4204\/EPTCS.315.9","article-title":"Quantum Walk and Dressed Photon","volume":"315","author":"Hamano","year":"2020","journal-title":"Electron. Proc. Theor. Comput. Sci."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"012308","DOI":"10.1103\/PhysRevA.97.012308","article-title":"Finding paths in tree graphs with a quantum walk","volume":"97","author":"Koch","year":"2018","journal-title":"Phys. Rev. A"},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"032323","DOI":"10.1103\/PhysRevA.96.032323","article-title":"Finding paths with quantum walks or quantum walking through a maze","volume":"96","author":"Reitzner","year":"2017","journal-title":"Phys. Rev. A"},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"095301","DOI":"10.1088\/1751-8121\/abde79","article-title":"Finding more than one path through a simple maze with a quantum walk","volume":"54","author":"Hillery","year":"2021","journal-title":"J. Phys. A Math. Theor."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"012323","DOI":"10.1103\/PhysRevA.79.012323","article-title":"Quantum searches on highly symmetric graphs","volume":"79","author":"Reitzner","year":"2009","journal-title":"Phys. Rev. A"},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"062324","DOI":"10.1103\/PhysRevA.81.062324","article-title":"Searching via walking: How to find a marked clique of a complete graph using quantum walks","volume":"81","author":"Hillery","year":"2010","journal-title":"Phys. Rev. A"},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"040301(R)","DOI":"10.1103\/PhysRevA.82.040301","article-title":"Finding structural anomalies in graphs by means of quantum walks","volume":"82","author":"Feldman","year":"2010","journal-title":"Phys. Rev. A"},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"062325","DOI":"10.1103\/PhysRevA.85.062325","article-title":"Quantum walks as a probe of structural anomalies in graphs","volume":"85","author":"Hillery","year":"2012","journal-title":"Phys. Rev. A"},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"030501","DOI":"10.1103\/PhysRevLett.112.030501","article-title":"Finding Structural Anomalies in Star Graphs Using Quantum Walks","volume":"112","author":"Cottrell","year":"2014","journal-title":"Phys. Rev. Lett."},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"035304","DOI":"10.1088\/1751-8113\/48\/3\/035304","article-title":"Finding structural anomalies in star graphs using quantum walks: A general approach","volume":"48","author":"Cottrell","year":"2015","journal-title":"J. Phys. A Math. Theor."},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"012330","DOI":"10.1103\/PhysRevA.99.012330","article-title":"Scattering quantum random walks on square grids and randomly generated mazes","volume":"99","author":"Koch","year":"2019","journal-title":"Phys. Rev. A"},{"doi-asserted-by":"crossref","unstructured":"Konno, N., Segawa, E., and \u0160tefa\u0148\u00e1k, M. (2021). Relation between Quantum Walks with Tails and Quantum Walks with Sinks on Finite Graphs. Symmetry, 13.","key":"ref_28","DOI":"10.3390\/sym13071169"},{"unstructured":"Yuki, K. (2021, November 18). GitHub Repository. Available online: https:\/\/github.com\/kyuki-rp\/qw-maze-solving.","key":"ref_29"},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"190046","DOI":"10.29026\/oea.2020.190046","article-title":"History, current developments, and future directions of near-field optical science","volume":"3","author":"Ohtsu","year":"2020","journal-title":"Opto-Electron. Adv."}],"container-title":["Symmetry"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2073-8994\/13\/12\/2263\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T07:36:52Z","timestamp":1760168212000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2073-8994\/13\/12\/2263"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,11,28]]},"references-count":30,"journal-issue":{"issue":"12","published-online":{"date-parts":[[2021,12]]}},"alternative-id":["sym13122263"],"URL":"https:\/\/doi.org\/10.3390\/sym13122263","relation":{},"ISSN":["2073-8994"],"issn-type":[{"type":"electronic","value":"2073-8994"}],"subject":[],"published":{"date-parts":[[2021,11,28]]}}}