This work establishes a new probabilistic bound on the number of elements needed 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 < \epsilon < 1 $, we prove that $ \varphi_k(G) \ge 1 - \epsilon $ if $ k \ge \operatorname{rank}(G) + \lceil \log_2(2/\epsilon) \rceil $ (a bound based on the group rank) or if $ k \ge \operatorname{len}(G) + \lceil \log_2(1/\epsilon) \rceil $ (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 \ge \lceil \log_2 |G| + \log_2(1/\epsilon) \rceil + 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.
Citation: Ziyuan Dong, Xiang Fan, Tengxun Zhong, Daowen Qiu. Probabilistic bounds on the number of elements to generate finite nilpotent groups and their applications to quantum algorithms[J]. AIMS Mathematics, 2026, 11(4): 9380-9397. doi: 10.3934/math.2026389
This work establishes a new probabilistic bound on the number of elements needed 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 < \epsilon < 1 $, we prove that $ \varphi_k(G) \ge 1 - \epsilon $ if $ k \ge \operatorname{rank}(G) + \lceil \log_2(2/\epsilon) \rceil $ (a bound based on the group rank) or if $ k \ge \operatorname{len}(G) + \lceil \log_2(1/\epsilon) \rceil $ (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 \ge \lceil \log_2 |G| + \log_2(1/\epsilon) \rceil + 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.
| [1] | A. Detinko, D. Flannery, E. O'Brien, Probabilistic group theory, combinatorics, and computing: lectures from the Fifth de Brún Workshop, Springer, 2013. |
| [2] | I. Pak, On probability of generating a finite group, Preprint, 1999. Available from: https://www.math.ucla.edu/pak/papers/sim.pdf. |
| [3] | E. Detomi, A. Lucchini, F. Morini, How many elements are needed to generate a finite group with good probability? Isr. J. Math., 132 (2002), 29–44. https://doi.org/10.1007/BF02784504 |
| [4] | C. Pomerance, The expected number of random elements to generate a finite abelian group, Period. Math. Hung., 43 (2002), 191–198. |
| [5] |
A. Lubotzky, The expected number of random elements to generate a finite group, J. Algebra, 257 (2002), 452–459. https://doi.org/10.1016/S0021-8693(02)00528-8 doi: 10.1016/S0021-8693(02)00528-8
|
| [6] |
A. Lucchini, The expected number of random elements to generate a finite group, Monatsh. Math., 181 (2016), 123–142. https://doi.org/10.1007/s00605-015-0789-5 doi: 10.1007/s00605-015-0789-5
|
| [7] | A. Yu. Kitaev, Quantum measurements and the abelian stabilizer problem, arXiv preprint, 1995. Available from: https://doi.org/10.48550/arXiv.quant-ph/9511026. |
| [8] | M. A. Nielsen, I. L. Chuang, Quantum computation and quantum information, Cambridge University Press, 2010. |
| [9] | P. Kaye, Raymond Laflamme, and Michele Mosca, An introduction to quantum computing, OUP Oxford, 2006. |
| [10] |
P. Koiran, V. Nesme, N. Portier, The quantum query complexity of the abelian hidden subgroup problem, Theor. Comput. Sci., 380 (2007), 115–126. https://doi.org/10.1016/j.tcs.2007.02.057 doi: 10.1016/j.tcs.2007.02.057
|
| [11] | C. Lomont, The hidden subgroup problem - review and open problems, arXiv preprint, 2004. https://doi.org/10.48550/arXiv.quant-ph/0411037. |
| [12] |
O. Regev, An efficient quantum factoring algorithm, J. ACM, 72 (2025), 1–13. https://doi.org/10.1145/3708471 doi: 10.1145/3708471
|
| [13] | T. W. Hungerford, Algebra, Graduate texts in mathematics, 73 (1980). https://doi.org/10.1007/978-1-4612-6101-8_11 |
| [14] | I. M. Isaacs, Finite group theory, American Mathematical Soc., 92 (2008). |
| [15] | J. D. Dixon, Problems in group theory, Courier Corporation, 2007. |
| [16] | V. Acciaro, The probability of generating some common families of finite groups, Utilitas Mathematica, 49 (1996), 243–254. |
| [17] | J. P. Serre, Linear representations of finite groups, Springer, 42 (1977). |
| [18] | Z. Dong, X. Fan, T. Zhong, D. Qiu, Revisiting finite Abelian hidden subgroup problem and its distributed exact quantum algorithm, arXiv preprint, 2025. https://doi.org/10.48550/arXiv.2512.22959 |
Ziyuan Dong, Xiang Fan, Tengxun Zhong, Daowen Qiu. Probabilistic bounds on the number of elements to generate finite nilpotent groups and their applications to quantum algorithms[J]. AIMS Mathematics, 2026, 11(4): 9380-9397. doi: 10.3934/math.2026389
DownLoad: