TY  - JOUR
AU  - Dong, Ziyuan
AU  - Fan, Xiang
AU  - Zhong, Tengxun
AU  - Qiu, Daowen
PY  - 2026
TI  - Probabilistic bounds on the number of elements to generate finite nilpotent groups and their applications to quantum algorithms
JO  - AIMS Mathematics
SP  - 9380
EP  - 9397
VL  - 11
IS  - 4
AB  - This work establishes a new probabilistic bound on the number of elements needed to generate finite nilpotent groups. Let        φ    k    (  G  ) denote the probability that    k random elements generate a finite nilpotent group    G. For any    0  <  ϵ  <  1, we prove that        φ    k    (  G  )  ≥  1  −  ϵ if    k  ≥  rank  ⁡  (  G  )  +  ⌈      log    2    ⁡  (  2      /    ϵ  )  ⌉ (a bound based on the group rank) or if    k  ≥  len  ⁡  (  G  )  +  ⌈      log    2    ⁡  (  1      /    ϵ  )  ⌉ (a bound based on the composition length). Moreover, these bounds are shown to be nearly tight. Both bounds sharpen the previously known requirement of    k  ≥  ⌈      log    2    ⁡      |    G      |    +      log    2    ⁡  (  1      /    ϵ  )  ⌉  +  2. Our results provide a foundational tool to analyze probabilistic algorithms, thereby 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.
UR  - https://doi.org/10.3934/math.2026389
DO  - 10.3934/math.2026389