The quantum query complexity of the semigroup product problem
Abstract
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,√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) quantum queries in the relevant parameter range.
Related
- Strong Selective and List-Decoding Direct Product Theorems for Quantum Query Complexity
- The power of oracle access: Optimal sample and query complexity of the abelian state hidden subgroup problem
- Near-Optimal Separations of Certificate Complexity from Randomized and Quantum Query Complexity
- Improved Quantum Query Bounds for Boolean Matrix Product Verification
- Quantum Query Complexity Beyond the Worst Case
BibTeX
@misc{lee2026quantum,
title = {{The quantum query complexity of the semigroup product problem}},
author = {Troy Lee and Miklos Santha},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.39974},
eprint = {2609.39974},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.39974},
}
RIS
TY - UNPB
TI - The quantum query complexity of the semigroup product problem
AU - Troy Lee
AU - Miklos Santha
PY - 2026
DA - 2026/09/30
PB - arXiv
DO - 10.48550/arxiv.2609.39974
UR - https://arxiv.org/abs/2609.39974
AB - We study the quantum query complexity of computing a semigroup product x_1⋯ 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 √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 x^k=x^k+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,√n log^O((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^Ω(N^1/3) quantum queries in the relevant parameter range.
ER -