General integer factorization algorithm based on Ising machine
Zhang Luo, Yifan Yuan, Zhicheng Wang, Mingche Lai, Pingjing Lu · EPJ Quantum Technology · 2025
Integer factorization, a fundamental problem in computational mathematics, holds critical significance for modern cryptography, particularly in RSA encryption. Traditional approaches such as the number field sieve face exponential complexity limitations, while Shor’s quantum algorithm remains impractical due to hardware constraints. This study proposes a universal algorithm for integer factorization based on Ising machines by transforming the problem into a Quadratic Unconstrained Binary Optimization (QUBO) formulation. The algorithm introduces an optimal reduction formula to optimize the parameter ranges of local field coefficients ( h ) and coupling coefficients ( J ) in the Ising model. Additionally, a non-uniform column grouping method is employed to resolve the conflict between coefficient ranges and carry auxiliary quantum bits(qubits), minimizing the number of auxiliary qubits with minimal compromise on coefficient ranges. Using this approach, we successfully factorized the 22-bit integer 2,093,809 with only 118 qubits. Extrapolating to existing photonic Ising machines with 100,000 qubits, our method demonstrates the potential to factorize 631-bit integers, highlighting its promise for efficient large-scale integer factorization. All results presented in this paper are obtained from simulations on Fixstars Amplify and D-Wave simulators.