2026-07-22T17:01:29Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:12677 2024-03-06T10:50:33Z ddc:004 open_access

Quantum Lower and Upper Bounds for 2D-Grid and Dyck Language Ambainis, Andris Balodis, Kaspars Iraids, Jānis Khadiev, Kamil Kļevickis, Vladislavs Prūsis, Krišjānis Shen, Yixin Smotrovs, Juris Vihrovs, Jevgēnijs Quantum query complexity Quantum algorithms Dyck language Grid path We study the quantum query complexity of two problems. First, we consider the problem of determining if a sequence of parentheses is a properly balanced one (a Dyck word), with a depth of at most k. We call this the Dyck_{k,n} problem. We prove a lower bound of Ω(c^k √n), showing that the complexity of this problem increases exponentially in k. Here n is the length of the word. When k is a constant, this is interesting as a representative example of star-free languages for which a surprising Õ(√n) query quantum algorithm was recently constructed by Aaronson et al. [Scott Aaronson et al., 2018]. Their proof does not give rise to a general algorithm. When k is not a constant, Dyck_{k,n} is not context-free. We give an algorithm with O(√n(log n)^{0.5k}) quantum queries for Dyck_{k,n} for all k. This is better than the trival upper bound n for k = o({log(n)}/{log log n}). Second, we consider connectivity problems on grid graphs in 2 dimensions, if some of the edges of the grid may be missing. By embedding the "balanced parentheses" problem into the grid, we show a lower bound of Ω(n^{1.5-ε}) for the directed 2D grid and Ω(n^{2-ε}) for the undirected 2D grid. The directed problem is interesting as a black-box model for a class of classical dynamic programming strategies including the one that is usually used for the well-known edit distance problem. We also show a generalization of this result to more than 2 dimensions. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Andris Ambainis and Kaspars Balodis and Jānis Iraids and Kamil Khadiev and Vladislavs Kļevickis and Krišjānis Prūsis and Yixin Shen and Juris Smotrovs and Jevgēnijs Vihrovs 2020 Is Part Of LIPIcs, Volume 170, 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2020.8 urn:nbn:de:0030-drops-126774 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2020.8 eng https://creativecommons.org/licenses/by/3.0/legalcode