Skip to content
Preprint

The quantum query complexity of the semigroup product problem

Sep 2026 · 0 citations
Physics

TL;DR

It is proved that for monoids with a stable partial order in which the identity is the minimum element, the bounded-error quantum query complexity is at most $\sqrt{n+1}((\beta+2)\log(n+2))^{O(\log(\beta+2))}$.

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.

View source

Similar papers

Preprint Oct 2026

Optimal query complexity for fractional quantum evolution

The argument reduces any $N$-query circuit to the approximation of $e^{it\theta}$ by a trigonometric polynomial with degree bounded by $O(N)$ by a trigonometric polynomial with degree bounded by $O(N)$ together with Remez inequality to establish a matching lower bound for arbitrary query algorithms.

A. Liu, Adam Wesołowski, Jayne Thompson et al. · 0 citations
Preprint Sep 2026

Quantum Query Algorithms for the Constructive Diagonal Ramsey Theorem

The constructive diagonal Ramsey problem asks, given adjacency-oracle access to an $N$-vertex graph, for a clique or independent set of the order guaranteed by Ramsey's theorem. We give a bounded-error quantum algorithm that, for every $K\ge2$ and $N\ge4^{K-1}$, finds and verifies a homogeneous $K$-set using $O\!\left(...

Xin Cheng · 0 citations
Preprint Oct 2026

Distributional Quantum Query Complexity

This work gives distributional joint computation lower bounds for the composition, direct sum, and direct product problems, and introduces some new tools for handling quantum query lower bounds, including a new ``Shaltiel-free''measure of quantum query complexity, which characterizes the composition behavior of distrib...

S. Ben-David, M. H. Ebtehaj · 0 citations
Preprint Sep 2026

Quantum Query Advantage Requires Space

The separation is obtained through a one-bit filtered-parity construction and a space-sensitive quantum lower bound based on compressed-oracle capacity and a new parity-to-capacity inequality, which may be of independent interest.

Minbo Gao, Zheng-Feng Ji, Zi-Yi Xie · 0 citations
Preprint Sep 2026

Improved Quantum Query Bounds for Boolean Matrix Product Verification

We prove the first non-trivial upper bound for the quantum query complexity of Boolean Matrix Product Verification ($\mathsf{BMPV}$), answering a longstanding open question in quantum query complexity. For $n\times n$ matrices, our upper bound is $\widetilde O(n^{17/12})$, improving on the standard $O(n^{3/2})$ bound o...

Amin Shiraz Gilani, François Le Gall, Xing-Yu Zhou · 0 citations
Preprint Oct 2026

Quantum Submodular Maximization

We study the quantum query complexity of maximizing a non-negative submodular function, considering both the unconstrained setting and, for monotone functions, a cardinality constraint $k$ on an $n$-element ground set. In the exact reversible digital value-oracle model, our unconstrained algorithm achieves an expected...

Yong-Gang Jiang, Xiao-Ming Sun, Peng-Hui Yao et al. · 0 citations

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.