| 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 |
| Předmět: |
|
| Zdroj: |
Quantum Information Processing; May2023, Vol. 22 Issue 5, p1-29, 29p |
| Abstrakt: |
We study the quantum query complexity of two problems. First, we consider the problem of determining whether a sequence of parentheses is a properly balanced one (a Dyck word), with a depth of at most k. We call this the D Y C K 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 O ~ (n) query quantum algorithm was recently constructed by Aaronson et al. (Electron Colloquium Comput Complex (ECCC) 26:61, 2018). Their proof does not give rise to a general algorithm. When k is not a constant, D Y C K k , n is not context-free. We give an algorithm with O n (log n) 0.5 k quantum queries for D Y C K k , n for all k. This is better than the trivial 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. We present two algorithms for particular cases of the problem. 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 [ABSTRACT FROM AUTHOR] |
| Databáze: |
Complementary Index |
| Externí odkaz: |
|
|
Nepřihlášeným uživatelům se plný text nezobrazuje |
K zobrazení výsledku je třeba se přihlásit.
|
