  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$. 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
$\Omega(n^{1.5-\epsilon})$ for the directed 2D grid and
$\Omega(n^{2-\epsilon})$ 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.
