arXiv:2312.10054 [physics.gen-ph]
S. Whitlock1, T. D. Kieu2
We present a quantum algorithm for factoring products of prime numbers which exploits Grover search to factor any n-bit biprime using 2n-5 qubits or less. The algorithm doesn’t depend on any properties of the number to be factored, has guaranteed convergence, and doesn’t require complex classical pre or post-processing. Large scale simulations confirm a success probability asymptotically reaching 100% for > 800 random biprimes with 5 < n < 35 (corresponding to 5 — 65 qubits) with the largest being 30398263859=7393*4111763. We also present a variant of the algorithm based on digital adiabatic quantum computing and show that Grover based factorization requires quadratically fewer iteration steps in most cases.
1European Center for Quantum Sciences (CESQ-ISIS, UMR 7006), University of Strasbourg and CNRS.
2Centre for Quantum Technology Theory and Optical Sciences Centre, Swinburne University of Technology, Victoria, Australia.
