2019/12/04 by Kamil Khadiev, Khadiev, Kamil, Yixin Shen +1
Computer Science · Physics and Astronomy · #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Physical sciences #Quantum Physics (quant-ph) #cs.CC #quant-ph
paper · pdf · doi:10.48550/arxiv.1912.02176
arxiv created 2020/02/18 · arxiv updated 2020/02/20
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 Dyckh. 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 Dyckh is star-free, it has quantum query complexity Θ(√(n)), where the hidden logarithm factors in Θ depend on h. Their proof does not give rise to an algorithm. When h is not a constant, Dyckh is not even context-free. We give an algorithm with O(√(n)log(n)0.5h) quantum queries for Dyckh for all h. This is better than the trival upper bound n when h=o((log(n))/(loglog n)). We also obtain lower bounds: we show that for every 0<ε≤ 0.37, there exists c>0 such that Q(Dyckclog(n)(n))=Ω(n1-ε). When h=ω(log(n)), the quantum query complexity is close to n, i.e. Q(Dyckh(n))=ω(n1-ε) for all ε>0. Furthermore when h=Ω(nε) for some ε>0, Q(Dyckh(n))=Θ(n).