2026-08-01T15:30:35Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:6990 2024-03-06T10:39:13Z ddc:004 open_access

Efficient Quantum Walk on the Grid with Multiple Marked Elements Hoyer, Peter Komeili, Mojtaba Quantum walks random walks query complexity spatial search We give a quantum algorithm for finding a marked element on the grid when there are multiple marked elements. Our algorithm uses quadratically fewer steps than a random walk on the grid, ignoring logarithmic factors. This is the first known quantum walk that finds a marked element in a number of steps less than the square-root of the extended hitting time. We also give a new tighter upper bound on the extended hitting time of a marked subset, expressed in terms of the hitting times of its members. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Peter Hoyer and Mojtaba Komeili 2017 Is Part Of LIPIcs, Volume 66, 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2017.42 urn:nbn:de:0030-drops-69902 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2017.42 eng https://creativecommons.org/licenses/by/3.0/legalcode