Fugu-MT 論文翻訳(概要): The quantum query complexity of the semigroup product problem

論文の概要: The quantum query complexity of the semigroup product problem

arxiv url: http://arxiv.org/abs/2609.39974v1
Date: Wed, 30 Sep 2026 15:36:00 GMT
ステータス: 翻訳完了
システム内更新日: 2026-10-01 18:57:27.98248
Title: The quantum query complexity of the semigroup product problem
Title（参考訳）: 半群積問題の量子クエリ複雑性
Abstract要約: 大きさが$N-1$の有限非周期半群の場合、半群のサイズへの依存はほとんどきつい。非自明な有限可換な周期的モノイドに対して、有界エラー量子クエリ複雑性は$(minn,sqrtn)$である。恒等式が最小元である安定な部分順序のモノイドに対しては、有界エラー量子クエリの複雑性が少なくとも$sqrtn+1((+2)log(n+2))O(log(+2)であることが証明される。
参考スコア（独自算出の注目度）: 0.11458853556386794
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
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.
Abstract（参考訳）: 半群積 $x_1\cdots x_n$ の量子クエリの複雑性について検討する。大きさ$N-1$の有限周期半群に対して、アーロンソン、グリアー、シェーファーの議論は、$\sqrt n\,(N\log(nN+2))^{O(N)}$クエリの上限を与える。代数構造を反映したクエリ境界を得るために、積幅$β$:すべての入力語が同じ積を持つ少なくとも$β$文字の列を持つような最小境界を求める。非自明な有限可換な非周期的モノイドに対して、有界エラー量子クエリの複雑性は$(\min\{n,\sqrt{nβ}\})$であり、したがって積幅によって特徴づけられる。さらに、そのようなモノイド$M$が非周期性指数$k$(すべての$x\in M$に対して$x^k=x^{k+1}$を満たす最小正の整数)を持つならば、$β=O(k\log(|M|+1)\log(|M|+2))$である。恒等式が最小元である安定な部分順序のモノイドに対して、有界誤り量子クエリの複雑性は、少なくとも$\sqrt{n+1}((β+2)\log(n+2))^{O(\log(β+2))}$であることを示す。位数$N-1$の任意の有限周期半群に対して、アーロンソン、グリアー、シェーファーの境界を改善し、最大で \[[ \min\left\{n,\sqrt n\, \log^{O((N\log(N+2)^{1/3})}(n+2)\right\} の有界な量子クエリ複雑性を得る。アンバイニス等における有界深度ダイクの下界は、関連するパラメータ範囲における量子クエリに対して$\sqrt n\,2^{Ω(N^{1/3})} を必要とする非周期モノイドを生じる。

論文の概要: The quantum query complexity of the semigroup product problem

関連論文リスト