Exact search algorithm to factorize large biprimes and a triprime on IBM quantum computer

Abstract

Factoring large integers using a quantum computer is an outstanding research problem that can illustrate true quantum advantage over classical computers. Exponential time order is required in order to find the prime factors of an integer by means of classical computation. However, the order can be drastically reduced by converting the factorization problem to an optimization one and solving it using a quantum computer. Recent works involving both theoretical and experimental approaches use Shor's algorithm, adiabatic quantum computation and quantum annealing principles to factorize integers. However, our work makes use of the generalized Grover's algorithm as proposed by Liu, with an optimal version of classical algorithm/analytic algebra. We utilize the phase-matching property of the above algorithm for only amplitude amplification purposes to avoid an inherent phase factor that prevents perfect implementation of the algorithm. Here we experimentally demonstrate the factorization of two bi-primes, 4088459 and 966887 using IBM's 5- and 16-qubit quantum processors, hence making those the largest numbers that have been factorized on a quantum device. Using the above 5-qubit processor, we also realize the factorization of a tri-prime integer 175, which had not been achieved to date. We observe good agreement between experimental and theoretical results with high fidelities. The difficulty of the factorization experiments has been analyzed and it has been concluded that the solution to this problem depends on the level of simplification chosen, not the size of the number factored. In principle, our results can be extended to factorize any multi-prime integer with minimum quantum resources.

arXiv comment13 pages, 5 figures

References in corpus (9)

• Experimental realization of Shor's quantum factoring algorithm using nuclear magnetic resonance
• Quantum advantage with shallow circuits
• Experimental realisation of Shor's quantum factoring algorithm using qubit recycling
• A Quantum Adiabatic Algorithm for Factorization and Its Experimental Implementation
• Pretending to factor large numbers on a quantum computer
• Factoring with Qutrits: Shor's Algorithm on Ternary and Metaplectic Quantum Architectures
• Prime factorization using quantum annealing and computational algebraic geometry
• Experimental Adiabatic Quantum Factorization under Ambient Conditions Based on a Solid-State Single Spin System
• High-fidelity adiabatic quantum computation using the intrinsic Hamiltonian of a spin system: Application to the experimental factorization of 291311

Cited by in corpus (10)

• Quantum Circuit Design Methodology for Multiple Linear Regression
• Experimental Demonstration of Quantum Tunneling in IBM Quantum Computer
• Quantum Simulation of Klein Gordon Equation and Observation of Klein Paradox in IBM Quantum Computer
• Demonstration of a general fault-tolerant quantum error detection code for (2n+1)-qubit entangled state on IBM 16-qubit quantum computer
• Hard instance learning for quantum adiabatic prime factorization
• Application of quantum scrambling in Rydberg atom on IBM quantum computer
• Design and Analysis of Communication Protocols using Quantum Resources
• Spin-Boson Model to Demonstrate Quantum Tunneling in Biomolecules using IBM Quantum Computer
• A Fast Finite Field Multiplier for SIKE
• Alternative Paradigms of Computation