論文の概要: Probabilistic Bounds on the Number of Elements to Generate Finite Nilpotent Groups and Their Applications
- arxiv url: http://arxiv.org/abs/2511.19494v1
- Date: Sun, 23 Nov 2025 12:30:46 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-11-26 17:37:04.041766
- Title: Probabilistic Bounds on the Number of Elements to Generate Finite Nilpotent Groups and Their Applications
- Title（参考訳）: 有限零群を生成する要素数に関する確率的境界とその応用
- Authors: Ziyuan Dong, Xiang Fan, Tengxun Zhong, Daowen Qiu,
- Abstract要約: varphi_k(G) ge 1 - $ if $k ge operatornamerank(G) + lceil log(2/) rceil$ (グループランクに基づく境界) あるいは $k ge operatornamelen(G) + lceil log (1/) rceil$ (グループチェーンの長さに基づく境界) が証明される。
- 参考スコア（独自算出の注目度）: 4.250782756734906
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: This work establishes a new probabilistic bound on the number of elements to generate finite nilpotent groups. Let $\varphi_k(G)$ denote the probability that $k$ random elements generate a finite nilpotent group $G$. For any $0 < ε< 1$, we prove that $\varphi_k(G) \ge 1 - ε$ if $k \ge \operatorname{rank}(G) + \lceil \log_2(2/ε) \rceil$ (a bound based on the group rank) or if $k \ge \operatorname{len}(G) + \lceil \log_2(1/ε) \rceil$ (a bound based on the group chain length). Moreover, these bounds are shown to be nearly tight. Both bounds sharpen the previously known requirement of $k \ge \lceil \log_2 |G| + \log_2(1/ε) \rceil + 2$. Our results provide a foundational tool for analyzing probabilistic algorithms, enabling a better estimation of the iteration count for the finite Abelian hidden subgroup problem (AHSP) standard quantum algorithm and a reduction in the circuit repetitions required by Regev's factoring algorithm.
- Abstract（参考訳）: この研究は、有限零群を生成するために要素の数に新しい確率的境界を確立する。
$\varphi_k(G)$ は、$k$ランダムな元が有限零群 $G$ を生成する確率を表す。
任意の$0 < ε< 1$ に対して、$\varphi_k(G) \ge 1 - ε$ if $k \ge \operatorname{rank}(G) + \lceil \log_2(2/ε) \rceil$ (群階数に基づく有界) あるいは $k \ge \operatorname{len}(G) + \lceil \log_2(1/ε) \rceil$ (群鎖長に基づく有界) が証明される。
さらに、これらの境界はほぼきついことが示される。
どちらの境界も、既知の$k \ge \lceil \log_2 |G| + \log_2(1/ε) \rceil + 2$ を満たす。
本研究では,確率論的アルゴリズムを解析するための基本ツールを提供し,有限アベリア隠れ部分群問題(AHSP)標準量子アルゴリズムの繰り返し数をよりよく推定し,Regevの因数分解アルゴリズムが要求する回路繰り返しの低減を実現する。
関連論文リスト
- An Efficient Computational Framework for Discrete Fuzzy Numbers Based on Total Orders [41.99844472131922]
我々は、$textitpos$関数を計算するために、合計(許容可能な)順序の構造を利用するアルゴリズムを導入する。
提案手法は、下層の鎖の大きさの2乗である$mathcalO(n2 m log n)$の複雑さを実現する。
その結果、この定式化は計算コストを大幅に削減することを示した。
論文 参考訳（メタデータ） (2025-11-21T09:35:07Z) - Quantum Search With Generalized Wildcards [0.4310167974376404]
我々は、コスト$O(sqrtn log n)$の量子アルゴリズムと、ほぼ一致する$Omega(sqrtn)$の低い境界を示す。
以下に示すように、$calQ$が有界サイズセット、連続ブロック、プレフィックス、フルセットのみである場合に、ほぼタイトなバウンダリを表示する。
論文 参考訳（メタデータ） (2025-11-06T18:55:05Z) - Overcomplete Tensor Decomposition via Koszul-Young Flattenings [56.82556231289414]
最小ランク1項の和として$n_times n times n_3$ tensorを分解する新しいアルゴリズムを与える。
次数-d$s のさらに一般的なクラスは、定数 $C = C(d)$ に対して階数 $Cn$ を超えることができないことを示す。
論文 参考訳（メタデータ） (2024-11-21T17:41:09Z) - Low-degree learning and the metric entropy of polynomials [44.99833362998488]
少なくとも$Omega(sqrtvarepsilon)2dlog n leq log mathsfM(mathscrF_n,d,|cdot|_L,varepsilon)は2辺の推定値$c(1-varepsilon)2dlogを満たす。
論文 参考訳（メタデータ） (2022-03-17T23:52:08Z) - Computational Complexity of Normalizing Constants for the Product of
Determinantal Point Processes [12.640283469603357]
正規化定数の計算における計算複雑性について検討する。
例えば、$sum_Sdet(bf A_S,S)p$は、すべての(固定された)正の偶数に対して、$p$ が UP-hard で Mod$_3$P-hard であることを示す。
論文 参考訳（メタデータ） (2021-11-28T14:08:25Z) - Learning low-degree functions from a logarithmic number of random
queries [77.34726150561087]
任意の整数 $ninmathbbN$, $din1,ldots,n$ および任意の $varepsilon,deltain(0,1)$ に対して、有界関数 $f:-1,1nto[-1,1]$ に対して、少なくとも$d$ の次数を学ぶことができる。
論文 参考訳（メタデータ） (2021-09-21T13:19:04Z) - Deterministic Algorithms for the Hidden Subgroup Problem [3.2590610391507444]
隠れ部分群問題に対する決定論的アルゴリズムを提案する。
アーベル群の場合、第1のアルゴリズムは最適なランダム化アルゴリズムと同じ最悪のクエリ複雑性を達成する。
非アーベル群に対する類似アルゴリズムは、最適ランダム化クエリの複雑さの$sqrt log n$ factorの範囲内にある。
論文 参考訳（メタデータ） (2021-04-29T15:55:15Z) - $k$-Forrelation Optimally Separates Quantum and Classical Query
Complexity [3.4984289152418753]
我々は、$N$ビット上の任意の部分関数は、$q$量子クエリを作れば、ランダムな推測よりも$delta$で計算できることを示した。
我々はまた、$k$-Forrelation問題 -- $q = lceil k/2 rceil$量子クエリで計算できる部分関数 -- を予想した。
論文 参考訳（メタデータ） (2020-08-16T21:26:46Z) - Tight Quantum Lower Bound for Approximate Counting with Quantum States [49.6558487240078]
Aaronson, Kothari, Kretschmer, Thaler (2020) が考える数え上げ問題の次の変種に対する厳密な下界を証明する。
このタスクは、入力セット$xsubseteq [n]$が$k$か$k'=(1+varepsilon)k$であるかどうかを識別する。
論文 参考訳（メタデータ） (2020-02-17T10:53:50Z) - On the Complexity of Minimizing Convex Finite Sums Without Using the
Indices of the Individual Functions [62.01594253618911]
有限和の有限ノイズ構造を利用して、大域オラクルモデルの下での一致する$O(n2)$-upper境界を導出する。
同様のアプローチを踏襲したSVRGの新規な適応法を提案し、これはオラクルと互換性があり、$tildeO(n2+nsqrtL/mu)log (1/epsilon)$と$O(nsqrtL/epsilon)$, for $mu>0$と$mu=0$の複雑さ境界を実現する。
論文 参考訳（メタデータ） (2020-02-09T03:39:46Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。