Quantum Annealing for Prime Factorization

Abstract

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 and then transforming the k-bit coupling ($k\ge 3$) terms to quadratic terms using ancillary variables. The method is efficient and uses $\mathcal{O}({\text{log}}^2(N))$ binary variables (qubits) for finding the factors of integer $N$. The method was tested using the D-Wave 2000Q for finding an embedding and determining the prime factors for a given composite number. As examples, we present quantum annealing results for factoring 15, 143, 59989, and 376289 using 4, 12, 59, and 94 logical qubits respectively. The method is general and could be used to factor larger numbers

References in corpus (13)

• A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem
• Experimental realization of Shor's quantum factoring algorithm using nuclear magnetic resonance
• Adiabatic Quantum Computing
• Shor's quantum factoring algorithm on a photonic chip
• Experimental realisation of Shor's quantum factoring algorithm using qubit recycling
• Experimental demonstration of Shor's algorithm with quantum entanglement
• Computing prime factors with a Josephson phase qubit quantum processor
• Demonstration of Shor's quantum factoring algorithm using photonic qubits
• Undecidability of the Spectral Gap (short version)
• A practical heuristic for finding graph minors
• A Quantum Adiabatic Algorithm for Factorization and Its Experimental Implementation
• Factoring Safe Semiprimes with a Single Quantum Query
• The role of symmetries in adiabatic quantum algorithms

Cited by in corpus (3)

• Quantum Computing: An Overview Across the System Stack
• Solving SAT and MaxSAT with a Quantum Annealer: Foundations, Encodings, and Preliminary Results
• Quantum Annealing Algorithm for Expected Shortfall based Dynamic Asset Allocation