Quantum Query Complexity of Dyck Languages with Bounded Height

Kamil Khadiev, Yixin Shen

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 quer…