论文标题
2D网格和戴克语言的量子下限和上限
Quantum Lower and Upper Bounds for 2D-Grid and Dyck Language
论文作者
论文摘要
我们研究了两个问题的量子查询复杂性。 首先，我们考虑确定一系列括号是否是正确平衡的问题（戴克单词），最多是$ k $的问题。我们将其称为$ dyck_ {k，n} $问题。我们证明了$ω（c^k \ sqrt {n}）$的下限，表明此问题的复杂性在$ k $中成倍增加。这里$ n $是单词的长度。当$ k $是一个常数时，这很有趣，这是无星语的代表性示例，令人惊讶的$ \ tilde {o}（\ sqrt {n}）$ query query Quantum算法最近由Aaronson等人构建。他们的证明不会引起一般算法。当$ k $不是常数时，$ dyck_ {k，n} $不是不含上下文的。我们使用$ o \ left（\ sqrt {n}（\ log {n}）^{0.5k} \ right）$ Quantum Quaries for $ dyck_ {k，n} $ for All $ K $。这比$ k = o \ left（\ frac {\ log（n）} {\ log \ log \ log n} \ right）$的Trival上限$ n $要好。 其次，如果网格的某些边缘可能丢失，我们将在两个维度的网格图上考虑连接性问题。通过将“平衡括号”问题嵌入到网格中，我们显示了有向的2D网格的$ω（n^{1.5-ε}）$的下限，而无方向性的2D网格则显示了$ω（N^{2-ε}）$。定向问题是一类经典动态编程策略，包括通常用于著名的编辑距离问题的黑框模型。我们还将该结果的概括分别为两个以上的维度。
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 \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 $Ω(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.
