arXiv preprint ·
The quantum query complexity of the semigroup product problem
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
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 $β$: 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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Quantum Physics
Exponential separation in sensing continuous signals via squeezing
Complexity study of the Hartle-Hawking state in JT gravity
Polarisation-resolved identification of spontaneous four-wave mixing processes in a multimode fused tapered fibre coupler
Beyond IP = PSPACE and QIP = PSPACE: Interactive Proofs in Arbitrary Physical Theories
A Separation Between Types of Quantum Oracle Separations
Get the few papers worth your time in Quantum Physics every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.