Quantum Query Complexity of Dyck Languages with Bounded Height

Abstract

We consider the problem of determining if a sequence of parentheses is well parenthesized, with a depth of at most h. We denote this language as $Dyc{k}_h$. We study the quantum query complexity of this problem for different h as function of the length n of the word. It has been known from a recent paper by Aaronson et al. that, for any constant h, since $Dyc{k}_h$ is star-free, it has quantum query complexity $\tilde{\Theta }(\sqrt{n})$, where the hidden logarithm factors in $\tilde{\Theta }$ depend on h. Their proof does not give rise to an algorithm. When h is not a constant, $Dyc{k}_h$ is not even context-free. We give an algorithm with $O\left(\sqrt{n}\log (n{)}^{0.5h}\right)$ quantum queries for $Dyc{k}_h$ for all h. This is better than the trival upper bound $n$ when $h=o(\frac{\log (n)}{\log \log n})$. We also obtain lower bounds: we show that for every $0<\epsilon \le 0.37$, there exists $c>0$ such that $Q({\text{Dyck}}_{c\log (n)}(n))=\Omega (n^{1-\epsilon })$. When $h=\omega (\log (n))$, the quantum query complexity is close to $n$, i.e. $Q({\text{Dyck}}_h(n))=\omega (n^{1-\epsilon })$ for all $\epsilon >0$. Furthermore when $h=\Omega (n^{\epsilon })$ for some $\epsilon >0$, $Q({\text{Dyck}}_h(n))=\Theta (n)$.