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.
AI Summary
The paper asks how algebraic structure controls the quantum query complexity of computing $x_1\cdots x_n$ in a known semigroup, when one query reveals an entire input element. It focuses on aperiodic monoids, for which existing results give $\widetilde O_M(\sqrt n)$ complexity but hide dependence on the monoid.
The organizing parameter is product breadth $\beta$: every word has a product-preserving subsequence of at most $\beta$ letters. For nontrivial finite commutative aperiodic monoids, the paper proves the characterization $Q=\Theta(\min\{n,\sqrt{n\beta}\})$, with universal constants. For aperiodicity index $k$, it establishes $\beta=O(k\log(|M|+1)\log\log(|M|+2))$. The upper bound uses an essential-width adversary theorem for order-independent incremental summaries; a matching adversary lower bound hides an irreducible product among identities. Applications include minimum-weight bases of known rank-$r$ matroids in $O(\min\{n,\sqrt{nr}\})$ queries.
For stably ordered monoids with minimum identity, including infinite ones, sampling and tree-search constructions give $\sqrt{n+1}((\beta+2)\log(n+2))^{O(\log(\beta+2))}$ queries, capped by $n$. Polynomial dependence on breadth remains open. Breadth alone is insufficient without structural assumptions: bounded-depth Dyck examples require exponential overhead in $\beta$.
For arbitrary finite aperiodic monoids of size $N$, the bound improves to $\min\{n,\sqrt n\log^{O((N\log(N+2))^{1/3})}(n+2)\}$. The proof combines localized AGS recursion, irreducible matrix representations, quotient reductions, and nilpotent-radical lifting. Dyck examples require $\sqrt n\,2^{\Omega(N^{1/3})}$ queries in the stated parameter regime; the logarithmic overhead remains unmatched. These are query bounds, not runtime guarantees.
Likely largely AI-generatedAI use disclosed
AI tools also helped draft proof overviews, reorganize arguments, develop examples, search the literature, and check claims against source papers.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
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\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 n2Ω(N1/3) quantum queries in the relevant parameter range.
The paper asks how algebraic structure controls the quantum query complexity of computing x1⋯xn in a known semigroup, when one query reveals an entire input element. It focuses on aperiodic monoids, for which existing results give OM(n) complexity but hide dependence on the monoid.
The organizing parameter is product breadth β: every word has a product-preserving subsequence of at most β letters. For nontrivial finite commutative aperiodic monoids, the paper proves the characterization Q=Θ(min{n,nβ}), with universal constants. For aperiodicity index k, it establishes β=O(klog(∣M∣+1)loglog(∣M∣+2)). The upper bound uses an essential-width adversary theorem for order-independent incremental summaries; a matching adversary lower bound hides an irreducible product among identities. Applications include minimum-weight bases of known rank-r matroids in O(min{n,nr}) queries.
For stably ordered monoids with minimum identity, including infinite ones, sampling and tree-search constructions give n+1((β+2)log(n+2))O(log(β+2)) queries, capped by n. Polynomial dependence on breadth remains open. Breadth alone is insufficient without structural assumptions: bounded-depth Dyck examples require exponential overhead in β.
For arbitrary finite aperiodic monoids of size N, the bound improves to min{n,nlogO((Nlog(N+2))1/3)(n+2)}. The proof combines localized AGS recursion, irreducible matrix representations, quotient reductions, and nilpotent-radical lifting. Dyck examples require n2Ω(N1/3) queries in the stated parameter regime; the logarithmic overhead remains unmatched. These are query bounds, not runtime guarantees.
We present quantum query complexity bounds for testing algebraic properties. For a set S and a binary operation on S, we consider the decision problem whether S is a semigroup or has an identity element. If S is a monoid, we want to decide whether S is a group. We present quantum algorithms for these problems that improve the best known classical complexity bounds. In particular, we give the first application of the new quantum random walk technique by Magniez, Nayak, Roland, and Santha that improves the previous bounds by Ambainis and Szegedy. We also present several lower bounds for testing algebraic properties.
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).
Quantum query complexity enjoys a variety of pleasing joint computation properties: for example, a composition theorem asserting Q(f∘g)=Θ(Q(f)Q(g)) for all Boolean functions f and g; a direct sum theorem asserting that computing k copies of a function (or search problem) costs Ω(k) times as much as the cost of computing one copy; and a direct product theorem asserting that for Boolean functions, even succeeding at the direct sum problem with exponentially small probability still requires Ω(k) times the cost of computing one copy to bounded error.
However, all of these results are strictly for worst-case quantum query complexity. For example, if we have a fixed distribution μ over inputs, the direct sum theorem says nothing about the quantum query complexity of computing k copies of f when the input comes from the product distribution μk instead of being worst-case. (Note that while a standard Yao-type minimax theorem guarantees a hard distribution for the direct sum problem, there's no guarantee that this hard distribution is a product distribution.) A similar problem occurs for the direct product theorem and the composition theorem: none of these results respect distributions.
In this work, we give distributional joint computation lower bounds for the composition, direct sum, and direct product problems. Along the way, we introduce some new tools for handling quantum query lower bounds, including (a) a new ``multiplicative'' variant of the γ2 norm (which we use in place of the multiplicative adversary method for proving the direct product theorem), and (b) a new ``Shaltiel-free'' measure of quantum query complexity, which we show characterizes the composition behavior of distributional quantum query complexity and satisfies pleasing properties.
We prove the first non-trivial upper bound for the quantum query complexity of Boolean Matrix Product Verification (BMPV), answering a longstanding open question in quantum query complexity. For n×n matrices, our upper bound is O(n17/12), improving on the standard O(n3/2) bound obtained using Grover search by Buhrman and Špalek [SODA 2006]. We complement this result by showing an Ω(n5/4) lower bound, which improves over the previous best known lower bound of Ω(n19/18) by Childs, Kimmel, and Kothari [ESA 2012]. Our approach centers on a connection with Orthogonal Vectors (OV), which asks whether an indexed list of n Boolean vectors of dimension n contains two vectors with disjoint supports. In particular, we prove equivalences between OV and BMPV and establish the above bounds for OV. We also prove a tight Θ(n3/2) bound for a variant of BMPV that asks whether the product contains a given row vector. Together, these results imply a polynomial separation between the quantum query complexities of deciding whether a graph has radius at most two and whether it has diameter at most two.
We reformulate quantum query complexity in terms of inequalities and equations for a set of positive semidefinite matrices. Using the new formulation we: 1) show that the workspace of a quantum computer can be limited to at most n+k qubits (where n and k are the number of input and output bits respectively) without reducing the computational power of the model; 2) give an algorithm that on input the truth table of a partial Boolean function and an integer t runs in time polynomial in the size of the truth table and estimates, to any desired accuracy, the minimum probability of error that can be attained by a quantum query algorithm attempts to evaluate f in t queries; 3) use semidefinite programming duality to formulate a dual SDP P/spl circ/(f, t, /spl epsi/) that is feasible if and only if f cannot be evaluated within error /spl epsi/ by a t-step quantum query algorithm. Using this SDP, we derive a general lower bound for quantum query complexity that encompasses a lower bound method of Ambainis and its generalizations; 4) give an interpretation of a generalized form of branching in quantum computation.
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.