Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Quantum Lower Bounds for 2D-Grid and Dyck Language   We show quantum lower bounds for 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$. It has been known that, for any $k$,
$\tilde{O}(\sqrt{n})$ queries suffice, with a $\tilde{O}$ term depending on
$k$. We prove a lower bound of $\Omega(c^k \sqrt{n})$, showing that the
complexity of this problem increases exponentially in $k$. 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.
  Second, we consider connectivity problems on directed/undirected grid 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.

14
The categories of this paper are: math-ph
2
The categories of this paper are: math
15
The categories of this paper are: nucl-ex
32
The categories of this paper are: atom-ph
11
The categories of this paper are: hep-lat
28
The categories of this paper are: alg-geom
16
The categories of this paper are: stat
31
The categories of this paper are: ao-sci
26
The categories of this paper are: bayes-an
24
The categories of this paper are: dg-ga
9
The categories of this paper are: nlin
22
The categories of this paper are: chao-dyn
3
The categories of this paper are: physics
23
The categories of this paper are: solv-int
25
The categories of this paper are: patt-sol
36
The categories of this paper are: cmp-lg