Prime Factorization Based on Multiple Quantum Annealings on Partial Constraints with Analytical Variable Reduction
Xinyi Guo, Geguang Miao, Shinichi Nishizawa, Shinji Kimura · 2023
Factorization of a large semiprime is a hard problem on classical computers, and quantum annealing is one way to solve the prime factorization problem by converting to a combinatorial optimization problem. A conversion method using the block-wise sum of partial products has been proposed but that works well up to numbers with 21-bit. To enhance the input bit width of the prime factorization, the paper introduces three proposals for prime factorization based on quantum annealing. First one is to divide the original problem into several sub-problems and solve them using multiple annealings. Second and third ones are analytical variable reduction of LSB and MSB parts. The proposals have been implemented on Python for Fixstars Amplify Annealing Engine (AE) and can factorize numbers with 46-bit or less. The proposals can also factorize numbers up to 57-bit but with a lot of trials for each number.