Solving Prime Factorization Using Quantum Ising Model

Quantum algorithms demonstrate good proficiency in solving combinatorial problems, a challenge faced by many optimization and cryptographic systems. Prime factorization is one of the hard problems and an efficient solver can significantly benefit those systems. In this regard, Shor’s algorithm utilizing quantum Fourier Transform has been proven to factor numbers exponentially faster than classical methods. However, it relies on finding the period of a function, which can sometimes be a challenging task. This study proposes another idea without that dependency to solve prime factorization through the construction of a quantum Ising model. The goal is to optimize or minimize Hamiltonian energy like the widely adopted approach of modeling NP-hard Ising spin glasses. This developed paradigm can benefit software practitioners to solve more and bigger scale combinatorial problems. Our methodology is a procedure of three steps. Step one formulates mathematical formulas based on the couplings of atomic Ising spins to model the range and product of numerical values. The second step accounts for the input value to construct observable operators that form a large matrix for quantum modeling through Pauli gates. The final step identifies the prime factors by computing the minimum eigenvalue of the matrix. This approach is validated through the execution of quantum approximate optimization algorithm (QAOA) combined with the constrained optimization by linear approximation (COBYLA) optimizer available in the IBM Qiskit SDK. Experimental results are presented to verify the degree of correctness.