Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1912.02176

Quantum Query Complexity of Dyck Languages with Bounded Height

Kamil Ravilevich Khadiev, Yixin Shen

Published Dec 4, 2019• 0 citations
arXivHTMLPDF

Abstract

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

DOI
10.48550/arxiv.1912.02176

Related papers

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

Andris Ambainis, Kaspars Balodis, Jānis Iraids +6 more

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

arXiv:2007.03402•Leibniz international proceedings in informatics•Jan 1, 2020•26 citations

Quantum Lower Bounds for 2D-Grid and Dyck Language

Andris Ambainis, Kaspars Balodis, Jānis Iraids +2 more

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.

arXiv:1911.12638•Nov 28, 2019•1 citation

The quantum query complexity of the semigroup product problem

Troy Lee, Miklos Santha

We study the quantum query complexity of computing a semigroup product $x_1\cdots x_n$, 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 $\sqrt n\,(N\log(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,\sqrt{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 $x^k=x^{k+1}$ for every $x\in M$), then $β=O(k\log(|M|+1)\log\log(|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 $\sqrt{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\left\{n,\sqrt n\, \log^{O((N\log(N+2))^{1/3})}(n+2)\right\}. \] The dependence on semigroup size is nearly tight: the bounded-depth Dyck lower bound of Ambainis et al. yields aperiodic monoids requiring $\sqrt n\,2^{Ω(N^{1/3})}$ quantum queries in the relevant parameter range.

quant-pharXiv:2609.39974•Oct 1, 2026•0 citations

A Quantum Query Complexity Trichotomy for Regular Languages

Scott Aaronson, Daniel Grier, Luke Schaeffer

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.

Annual Symposium on Foundations of Computer Science•Nov 1, 2019•22 citations

Quantum Query Complexity of Maximum Degree and its Generalizations

Amin Shiraz Gilani, Nikhil S. Mande, Subhasree Patro +1 more

We study the quantum query complexity of several basic graph problems. 1) We prove a tight $Θ(n^{3/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 $Θ(n^{3/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\geq 1$, we give an $O(n^{2-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\geq 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.

quant-pharXiv:2610.13906•Oct 12, 2026•2 citations

Quantum query complexity of Hurwitz stability testing

Maxwell Fitzsimmons, Mohamed Serry, Meenu Kumari +1 more

Determining whether every trajectory of the linear system $\dot{x}=Ax$ converges to zero (or, equivalently, whether $A$ is Hurwitz stable) is a fundamental problem in control theory. It arises, for example, in verifying the stability of feedback controllers and state observers, as well as of linearized dynamical models. We study the quantum query complexity of deciding whether a matrix $A\in\mathbb{C}^{n\times n}$ is Hurwitz stable, given an exact normalized block-encoding of $A$. The query complexity is characterized in terms of the system dimension $n$ and a supplied lower bound $0<ν\leq ω_A$ on the imaginary-axis distance $ω_A:=\min_{t\in\mathbb{R}}σ_{\min}(A-\mathrm{i}tI)$, where $σ_{\min}(A)$ is the smallest singular value of $A$. We prove a query-complexity lower bound of $Ω(\sqrt{n}/ν)$, which holds even when $A$ is restricted to be real and diagonal. For general matrices with nonzero $ω_A$, we encode an approximation of the right-half-plane spectral projector $\operatorname{sign}^+(A):=(I+\operatorname{sign}(A))/2$ as a block of a matrix inverse, where $A$ is Hurwitz if and only if the projector is zero. To test this, we produce a quantum algorithm which determines if a $(β,b,1/(4\sqrt{n}))$-block-encoded projector matrix (like $\operatorname{sign}^+(A)$) is zero or not; for constant success probability, it has complexity $Θ(β\sqrt{n})$. When the zero test is applied to specific approximations of $\operatorname{sign}^+(A)$, this yields an upper bound of $O(\sqrt{n}ν^{-2}\log(\sqrt{n}/ν))$ queries in the general case, and $O(\sqrt{n}ν^{-1}\log n)$ when $A$ is Hermitian or normal. The latter upper bound matches the lower bound up to a logarithmic factor. Thus the dimension dependence of quantum Hurwitz testing is nearly optimal, while the remaining factor in the non-normal case isolates an open conditioning gap.

quant-pharXiv:2610.41180•Nov 2, 2026•0 citations
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 DyckhDyck_hDyckh​. 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 DyckhDyck_hDyckh​ is star-free, it has quantum query complexity Θ~(n)\tildeΘ(\sqrt{n})Θ~(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, DyckhDyck_hDyckh​ is not even context-free. We give an algorithm with O(nlog⁡(n)0.5h)O\left(\sqrt{n}\log(n)^{0.5h}\right)O(n​log(n)0.5h) quantum queries for DyckhDyck_hDyckh​ for all h. This is better than the trival upper bound nnn when h=o(log⁡(n)log⁡log⁡n)h=o(\frac{\log(n)}{\log\log n})h=o(loglognlog(n)​). We also obtain lower bounds: we show that for every 000000 such that Q(Dyckclog⁡(n)(n))=Ω(n1−ε)Q(\text{Dyck}_{c\log(n)}(n))=Ω(n^{1-ε})Q(Dyckclog(n)​(n))=Ω(n1−ε). When h=ω(log⁡(n))h=ω(\log(n))h=ω(log(n)), the quantum query complexity is close to nnn, i.e. Q(Dyckh(n))=ω(n1−ε)Q(\text{Dyck}_h(n))=ω(n^{1-ε})Q(Dyckh​(n))=ω(n1−ε) for all ε>0ε>0ε>0. Furthermore when h=Ω(nε)h=Ω(n^ε)h=Ω(nε) for some ε>0ε>0ε>0, Q(Dyckh(n))=Θ(n)Q(\text{Dyck}_{h}(n))=Θ(n)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 kkk. We call this the Dyckk,nDyck_{k,n}Dyckk,n​ problem. We prove a lower bound of Ω(ckn)Ω(c^k \sqrt{n})Ω(ckn​), showing that the complexity of this problem increases exponentially in kkk. Here nnn is the length of the word. When kkk is a constant, this is interesting as a representative example of star-free languages for which a surprising O~(n)\tilde{O}(\sqrt{n})O~(n​) query quantum algorithm was recently constructed by Aaronson et al. Their proof does not give rise to a general algorithm. When kkk is not a constant, Dyckk,nDyck_{k,n}Dyckk,n​ is not context-free. We give an algorithm with O(n(log⁡n)0.5k)O\left(\sqrt{n}(\log{n})^{0.5k}\right)O(n​(logn)0.5k) quantum queries for Dyckk,nDyck_{k,n}Dyckk,n​ for all kkk. This is better than the trival upper bound nnn for k=o(log⁡(n)log⁡log⁡n)k=o\left(\frac{\log(n)}{\log\log n}\right)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−ε)Ω(n^{1.5-ε})Ω(n1.5−ε) for the directed 2D grid and Ω(n2−ε)Ω(n^{2-ε})Ω(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 kkk. It has been known that, for any kkk, O~(n)\tilde{O}(\sqrt{n})O~(n​) queries suffice, with a O~\tilde{O}O~ term depending on kkk. We prove a lower bound of Ω(ckn)Ω(c^k \sqrt{n})Ω(ckn​), showing that the complexity of this problem increases exponentially in kkk. This is interesting as a representative example of star-free languages for which a surprising O~(n)\tilde{O}(\sqrt{n})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−ε)Ω(n^{1.5-ε})Ω(n1.5−ε) for the directed 2D grid and Ω(n2−ε)Ω(n^{2-ε})Ω(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⋯xnx_1\cdots x_nx1​⋯xn​, when one query reveals one input element and the multiplication table is given. For a finite aperiodic semigroup of size N−1N-1N−1, the argument of Aaronson, Grier, and Schaeffer gives an upper bound of n (Nlog⁡(nN+2))O(N)\sqrt n\,(N\log(nN+2))^{O(N)}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β})Θ(\min\{n,\sqrt{nβ}\})Θ(min{n,nβ​}), and is thus characterized by product breadth. We further show that if such a monoid MMM has aperiodicity index kkk (the least positive integer satisfying xk=xk+1x^k=x^{k+1}xk=xk+1 for every x∈Mx\in Mx∈M), then β=O(klog⁡(∣M∣+1)log⁡log⁡(∣M∣+2))β=O(k\log(|M|+1)\log\log(|M|+2))β=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))\sqrt{n+1}((β+2)\log(n+2))^{O(\log(β+2))}n+1​((β+2)log(n+2))O(log(β+2)). For arbitrary finite aperiodic semigroups of order N−1N-1N−1, we improve the bound of Aaronson, Grier, and Schaeffer, obtaining a bounded-error quantum query complexity of at most min⁡{n,n log⁡O((Nlog⁡(N+2))1/3)(n+2)}. \min\left\{n,\sqrt n\, \log^{O((N\log(N+2))^{1/3})}(n+2)\right\}. min{n,n​logO((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 n 2Ω(N1/3)\sqrt n\,2^{Ω(N^{1/3})}n​2Ω(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 study the quantum query complexity of several basic graph problems. 1) We prove a tight Θ(n3/2)Θ(n^{3/2})Θ(n3/2) bound for finding a maximum-out-degree vertex in an nnn-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 nnn-vertex undirected graph requires Θ(n3/2)Θ(n^{3/2})Θ(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)(k,n-k)(k,n−k)-Cut, which asks for the largest cut with one side of size kkk. For every constant k≥1k\geq 1k≥1, we give an O(n2−1/(k+1))O(n^{2-1/(k+1)})O(n2−1/(k+1))-query quantum algorithm. 4) We establish a reduction to Maximum (k,n−k)(k,n-k)(k,n−k)-Cut involving kkk-Graph Collision, which asks whether the marked vertices of a known graph contain a kkk-clique. For k≥3k\geq 3k≥3, this yields unconditional lower bounds with exponents strictly larger than 3/23/23/2, showing that this problem is strictly harder than computing maximum degree. Additionally, under a conjecture we propose for kkk-Graph Collision, the reduction yields a lower bound matching our upper bound above.
Determining whether every trajectory of the linear system x˙=Ax\dot{x}=Axx˙=Ax converges to zero (or, equivalently, whether AAA is Hurwitz stable) is a fundamental problem in control theory. It arises, for example, in verifying the stability of feedback controllers and state observers, as well as of linearized dynamical models. We study the quantum query complexity of deciding whether a matrix A∈Cn×nA\in\mathbb{C}^{n\times n}A∈Cn×n is Hurwitz stable, given an exact normalized block-encoding of AAA. The query complexity is characterized in terms of the system dimension nnn and a supplied lower bound 0<ν≤ωA0<ν\leq ω_A0<ν≤ωA​ on the imaginary-axis distance ωA:=min⁡t∈Rσmin⁡(A−itI)ω_A:=\min_{t\in\mathbb{R}}σ_{\min}(A-\mathrm{i}tI)ωA​:=mint∈R​σmin​(A−itI), where σmin⁡(A)σ_{\min}(A)σmin​(A) is the smallest singular value of AAA. We prove a query-complexity lower bound of Ω(n/ν)Ω(\sqrt{n}/ν)Ω(n​/ν), which holds even when AAA is restricted to be real and diagonal. For general matrices with nonzero ωAω_AωA​, we encode an approximation of the right-half-plane spectral projector sign⁡+(A):=(I+sign⁡(A))/2\operatorname{sign}^+(A):=(I+\operatorname{sign}(A))/2sign+(A):=(I+sign(A))/2 as a block of a matrix inverse, where AAA is Hurwitz if and only if the projector is zero. To test this, we produce a quantum algorithm which determines if a (β,b,1/(4n))(β,b,1/(4\sqrt{n}))(β,b,1/(4n​))-block-encoded projector matrix (like sign⁡+(A)\operatorname{sign}^+(A)sign+(A)) is zero or not; for constant success probability, it has complexity Θ(βn)Θ(β\sqrt{n})Θ(βn​). When the zero test is applied to specific approximations of sign⁡+(A)\operatorname{sign}^+(A)sign+(A), this yields an upper bound of O(nν−2log⁡(n/ν))O(\sqrt{n}ν^{-2}\log(\sqrt{n}/ν))O(n​ν−2log(n​/ν)) queries in the general case, and O(nν−1log⁡n)O(\sqrt{n}ν^{-1}\log n)O(n​ν−1logn) when AAA is Hermitian or normal. The latter upper bound matches the lower bound up to a logarithmic factor. Thus the dimension dependence of quantum Hurwitz testing is nearly optimal, while the remaining factor in the non-normal case isolates an open conditioning gap.