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 $Ω(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 $Ω(n^{1.5-ε})$ for the directed 2D grid and $Ω(n^{2-ε})$ 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.
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, O~(n) queries suffice, with a O~ term depending on k. We prove a lower bound of Ω(ckn), 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 O~(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 Ω(n1.5−ε) for the directed 2D grid and Ω(n2−ε) 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.
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 Dyckk,n problem. We prove a lower bound of Ω(ckn), 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 O~(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, Dyckk,n is not context-free. We give an algorithm with O(n(logn)0.5k) quantum queries for Dyckk,n for all k. This is better than the trival upper bound n for k=o(loglognlog(n)). 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 Ω(n1.5−ε) for the directed 2D grid and Ω(n2−ε) 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.
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(nlog(n)0.5h) quantum queries for Dyckh for all h. This is better than the trival upper bound n when h=o(loglognlog(n)). We also obtain lower bounds: we show that for every 00 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).
The Tarski fixed-point problem asks for a fixed point of a monotone map on a k-dimensional grid lattice of width n and has applications in game theory, economics, and verification. Substantial gaps remain between the known upper and lower bounds on its quantum query complexity.
We prove two hardness bootstrapping theorems for quantum query lower bounds. Starting from a hard instance family whose instances have pair-wise incomparable unique fixed points, and a lower bound established by the nonnegative adversary method, we bootstrap this lower bound by (i) a factor of Ω(t) when the dimension is multiplied by t and the width remains unchanged, and (ii) a factor of Ω(logm) when the width is multiplied by m and the dimension is doubled. Applying these theorems, we obtain three consequences: (i) an Ω(klog2n) lower bound for k≥4, improving previously best-known classical and quantum lower bounds; (ii) for every fixed constant α>0, there exists a constant δ(α)>0 such that Qε(Tarski(n,k))=Ω(knδ(α)) whenever k>nα, and in particular, an Ω(kn0.0072) lower bound for k>n2/203, the first lower bound with simultaneous linear dependence on the dimension and polynomial dependence on the width; and (iii) a superpolynomial lower bound of (k/logk)Ω(logk) for exponentially wide grids, where n=2Θ(k). The last result rules out a route to polynomial-time algorithms for simple stochastic games and ARRIVAL through generic polynomial-query black-box Tarski solvers.
We present a trichotomy theorem for the quantum query complexity of regular languages. Every regular language has quantum query complexity Θ(1), Θ̃(√ n), or Θ(n). The extreme uniformity of regular languages prevents them from taking any other asymptotic complexity. This is in contrast to even the context-free languages, which we show can have query complexity Θ(nc) for all computable c [1/2,1]. Our result implies an equivalent trichotomy for the approximate degree of regular languages, and a dichotomy-either Θ(1) or Θ(n)-for sensitivity, block sensitivity, certificate complexity, deterministic query complexity, and randomized query complexity. The heart of the classification theorem is an explicit quantum algorithm which decides membership in any star-free language in Õ(√n) time. This well-studied family of the regular languages admits many interesting characterizations, for instance, as those languages expressible as sentences in first-order logic over the natural numbers with the less-than relation. Therefore, not only do the star-free languages capture functions such as OR, they can also express functions such as "there exist a pair of 2's such that everything between them is a 0." Thus, we view the algorithm for star-free languages as a nontrivial generalization of Grover's algorithm which extends the quantum quadratic speedup to a much wider range of string-processing algorithms than was previously known. We show a variety of applications-new quantum algorithms for dynamic constant-depth Boolean formulas, balanced parentheses nested constantly many levels deep, binary addition, a restricted word break problem, and path-discovery in narrow grids-all obtained as immediate consequences of our classification theorem.
We present a trichotomy theorem for the quantum query complexity of regular languages. Every regular language has quantum query complexity Theta(1), ~Theta(sqrt n), or Theta(n). The extreme uniformity of regular languages prevents them from taking any other asymptotic complexity. This is in contrast to even the context-free languages, which we show can have query complexity Theta(n^c) for all computable c in [1/2,1]. Our result implies an equivalent trichotomy for the approximate degree of regular languages, and a dichotomy---either Theta(1) or Theta(n)---for sensitivity, block sensitivity, certificate complexity, deterministic query complexity, and randomized query complexity. The heart of the classification theorem is an explicit quantum algorithm which decides membership in any star-free language in ~O(sqrt n) time. This well-studied family of the regular languages admits many interesting characterizations, for instance, as those languages expressible as sentences in first-order logic over the natural numbers with the less-than relation. Therefore, not only do the star-free languages capture functions such as OR, they can also express functions such as "there exist a pair of 2's such that everything between them is a 0." Thus, we view the algorithm for star-free languages as a nontrivial generalization of Grover's algorithm which extends the quantum quadratic speedup to a much wider range of string-processing algorithms than was previously known. We show a variety of applications---new quantum algorithms for dynamic constant-depth Boolean formulas, balanced parentheses nested constantly many levels deep, binary addition, a restricted word break problem, and path-discovery in narrow grids---all obtained as immediate consequences of our classification theorem.
We study the quantum query complexity of computing a semigroup product x1⋯xn, when one query reveals one input element and the multiplication table is given. For a finite aperiodic semigroup of size N−1, the argument of Aaronson, Grier, and Schaeffer gives an upper bound of n(Nlog(nN+2))O(N) queries.
To obtain query bounds that reflect algebraic structure, we study the product breadth β: the smallest bound such that every input word has a subsequence of at most β letters with the same product.
For nontrivial finite commutative aperiodic monoids, the bounded-error quantum query complexity is Θ(min{n,nβ}), and is thus characterized by product breadth. We further show that if such a monoid M has aperiodicity index k (the least positive integer satisfying xk=xk+1 for every x∈M), then β=O(klog(∣M∣+1)loglog(∣M∣+2)).
For monoids with a stable partial order in which the identity is the minimum element, we prove that the bounded-error quantum query complexity is at most n+1((β+2)log(n+2))O(log(β+2)).
For arbitrary finite aperiodic semigroups of order N−1, we improve the bound of Aaronson, Grier, and Schaeffer, obtaining a bounded-error quantum query complexity of at most min{n,nlogO((Nlog(N+2))1/3)(n+2)}. The dependence on semigroup size is nearly tight: the bounded-depth Dyck lower bound of Ambainis et al. yields aperiodic monoids requiring n2Ω(N1/3) quantum queries in the relevant parameter range.