The quantum query complexity of the semigroup product problem

Abstract

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 $\beta$: the smallest bound such that every input word has a subsequence of at most $\beta$ letters with the same product. For nontrivial finite commutative aperiodic monoids, the bounded-error quantum query complexity is $\Theta (\min \{n,\sqrt{n\beta }\})$, 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 $\beta =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}((\beta +2)\log (n+2){)}^{O(\log (\beta +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}^{\Omega (N^{1/3})}$ quantum queries in the relevant parameter range.

95 pages, 1 figure