Quantum Lower and Upper Bounds for 2D-Grid and Dyck Language
Quantum Lower and Upper Bounds for 2D-Grid and Dyck Language
复制标题
2D 网格和 Dyck 语言的量子下界和上限
DOI：
--
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
J. Vihrovs
中科院分区：
文献类型：
--
作者：
A. Ambainis;K. Balodis;Janis Iraids;K. Khadiev;Vladislavs Klevickis;Krisjanis Prusis;Yixin Shen;Juris Smotrovs;J. Vihrovs
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 $ ilde{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 $Oleft(sqrt{n}(log{n})^{0.5k}
ight)$ quantum queries for $Dyck_{k,n}$ for all $k$. This is better than the trival upper bound $n$ for $k=oleft(frac{log(n)}{loglog n}
ight)$.
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.
在真正的次二次时间中近似编辑距离：Quantum 和 MapReduce
影响因子：
2.5
作者：
Boroujeni, Mahdi;Ehsani, Soheil;Ghodsi, Mohammad;Hajiaghayi, Mohammadtaghi;Seddighin, Saeed
通讯作者：
Seddighin, Saeed