Quantum Lower and Upper Bounds for 2D-Grid and Dyck Language
| Autor: | Ambainis, Andris, Balodis, Kaspars, Iraids, Jānis, Khadiev, Kamil, Kļevickis, Vladislavs, Prūsis, Krišjānis, Shen, Yixin, Smotrovs, Juris, Vihrovs, Jevgēnijs |
|---|---|
| Rok vydání: | 2020 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | 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 $\Omega(c^k \sqrt{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 $\tilde{O}(\sqrt{n})$ query quantum algorithm was recently constructed by Aaronson et al. 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\left(\sqrt{n}(\log{n})^{0.5k}\right)$ quantum queries for $Dyck_{k,n}$ for all $k$. This is better than the trival upper bound $n$ for $k=o\left(\frac{\log(n)}{\log\log n}\right)$. 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 $\Omega(n^{1.5-\epsilon})$ for the directed 2D grid and $\Omega(n^{2-\epsilon})$ 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. Comment: arXiv admin note: substantial text overlap with arXiv:1911.12638 |
| Databáze: | arXiv |
| Externí odkaz: |
|