Quantum Lower and Upper Bounds for 2D-Grid and Dyck Language

Understand

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$.