Achievement
Developed a framework to convert integer factorization problem to an Ising model for solution on D-Wave QPU.
Significance and Impact
This work presents a resource efficient methodology for mapping the integer factorization problem onto the D-Wave quantum annealing architecture. As more qubits become available, the larger the number able to be factored.
Research Details
- Developed methodology for mapping integer factorization onto an Ising hamiltonian
- Factored integers 15, 143, 59989, 376289
- Implemented using XACC quantum computing framework
Overview
We have developed a framework to convert an arbitrary integer factorization problem to an executable Ising model by first writing it as an optimization function then transforming the k-bit coupling (k ≥ 3) terms to quadratic terms using ancillary variables. Our resource-efficient method uses ????(log**2(????)) binary variables (qubits) for finding the factors of an integer N. We present how to factorize 15, 143, 59989, and 376289 using 4, 12, 59, and 94 logical qubits, respectively. This method was tested using the D-Wave 2000Q for finding an embedding and determining the prime factors for a given composite number. The method is general and could be used to factor larger integers as the number of available qubits increases or combined with other ad hoc methods to achieve better performances for specific numbers.
Last Updated: February 10, 2021 - 2:55 pm