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 $Dyck_h$. 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 $Dyck_h$ is star-free, it has quantum query complexity $\tildeΘ(\sqrt{n})$, where the hidden logarithm factors in $\tildeΘ$ depend on h. Their proof does not give rise to an algorithm. When h is not a constant, $Dyck_h$ is not even context-free. We give an algorithm with $O\left(\sqrt{n}\log(n)^{0.5h}\right)$ quantum queries for $Dyck_h$ for all h. This is better than the trival upper bound $n$ when $h=o(\frac{\log(n)}{\log\log n})$. We also obtain lower bounds: we show that for every $00$ such that $Q(\text{Dyck}_{c\log(n)}(n))=Ω(n^{1-ε})$. When $h=ω(\log(n))$, the quantum query complexity is close to $n$, i.e. $Q(\text{Dyck}_h(n))=ω(n^{1-ε})$ for all $ε>0$. Furthermore when $h=Ω(n^ε)$ for some $ε>0$, $Q(\text{Dyck}_{h}(n))=Θ(n)$.
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).
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 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 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.
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 several basic graph problems. 1) We prove a tight Θ(n3/2) bound for finding a maximum-out-degree vertex in an n-vertex tournament, resolving a conjecture of Mande, Paraashar, and Saurabh [FSTTCS'23]. 2) Using the same proof idea, we give a direct proof that finding a maximum-degree vertex in an n-vertex undirected graph requires Θ(n3/2) quantum queries, a bound implicit in the work of Apers and Lee [CCC'21]. Both lower bounds above hold even for computing only the maximum degree or maximum out-degree. 3) We also study Maximum (k,n−k)-Cut, which asks for the largest cut with one side of size k. For every constant k≥1, we give an O(n2−1/(k+1))-query quantum algorithm. 4) We establish a reduction to Maximum (k,n−k)-Cut involving k-Graph Collision, which asks whether the marked vertices of a known graph contain a k-clique. For k≥3, this yields unconditional lower bounds with exponents strictly larger than 3/2, showing that this problem is strictly harder than computing maximum degree. Additionally, under a conjecture we propose for k-Graph Collision, the reduction yields a lower bound matching our upper bound above.