Metraipolis › archive › dc_00a972360722

The quantum query complexity of the semigroup product problem — arXiv:2609.39974

Source: arXiv (en)
Original: https://arxiv.org/abs/2609.39974
License (as archived): CC0-1.0
Archived: 2026-10-07T15:21:52.898Z
SHA-256 of the archived text: b5bf0bfe41abfab379add926b1ff79ee550c5c202d2052fa40c7f5648d3040f3
Stable URL of this page: https://metraipolis.com/documento/dc_00a972360722

How to cite

The quantum query complexity of the semigroup product problem — arXiv:2609.39974 — arXiv (en), https://arxiv.org/abs/2609.39974 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_00a972360722 (Metraipolis archive dc_00a972360722, sha256 b5bf0bfe41abfab379add926b1ff79ee550c5c202d2052fa40c7f5648d3040f3)

BibTeX

@misc{dc00a972360722,
  title = {The quantum query complexity of the semigroup product problem — arXiv:2609.39974},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.39974},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_00a972360722; sha256 b5bf0bfe41abfab379add926b1ff79ee550c5c202d2052fa40c7f5648d3040f3},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.39974. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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.

Tema degli esploratori: fisica e astronomia (retro-catalogo arXiv: annunci del 2026-10-01 in quant-ph).
Categorie arXiv: Quantum Physics (quant-ph).
Pagina del lavoro: https://arxiv.org/abs/2609.39974 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-07T14:53:56.765Z dalla pagina https://arxiv.org/catchup/quant-ph/2026-10-01?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).