We investigate prime factorization from two perspectives: quantum annealing and computational algebraic geometry, specifically Gröbner bases. We present a novel autonomous algorithm which combines the two approaches and leads to the factorization of all bi-primes up to just over 200000, the largest number factored to date using a quantum processor. We also explain how Gröbner bases can be used to reduce the degree of Hamiltonians.
We investigate prime factorization from two perspectives: quantum annealing and computational algebraic geometry, specifically Gröbner bases. We present a novel autonomous algorithm which combines the two approaches and leads to the factorization of all bi-primes up to just over 200000, the largest number factored to date using a quantum processor. We also explain how Gröbner bases can be used to reduce the degree of Hamiltonians.
Objective: to study the transformational potential of quantum annealing in solving the problem of simple factorization. Research method(s): the approach includes a comprehensive review of recent experimental breakthroughs and theoretical innovations. In particular, we analyze techniques such as surface code memory, HUBO and QUBO formulations, range-dependent Hamiltonian algorithms, modular locally structured embedding methods, and a modified multiplication table method random number. Research Output(s): the study evaluates the application of quantum annealing to factorization of primes, showing that advanced problem mapping techniques, such as the HUBO and QUBO formulations, significantly improve the efficiency of representing complex factorization problems on quantum hardware. Notably, the inclusion of surface code memory increases the stability of qubit states during annealing, reducing errors and improving computational accuracy It also demonstrates that Hamiltonian's range-dependent algorithms and modular, locally structured embedding methods help optimize qubit interaction, enabling a more accurate factorization process. A modified multiplication table method is presented, providing an optimized computational strategy, especially effective for large composite numbers. Preliminary experiments with random numbers confirm the theoretical conclusions, indicating that these integrated methods allow for better performance than traditional approaches. Taken together, the results highlight the potential of quantum annealing as a solid foundation for solving complex cryptographic problems and lay the foundation for future research into scalable quantum algorithms and hardware implementations. Scientific novelty: the work combines several advanced quantum annealing techniques for factorization of prime numbers, combining experimental innovations with theoretical developments to propose a new framework that improves the efficiency of cryptographic computing.
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.
This paper investigates novel techniques to solve prime factorization by quantum annealing (QA). First, we present a very-compact modular encoding of a multiplier circuit into the architecture of current D-Wave QA devices. The key contribution is a compact encoding of a controlled full-adder into an 8-qubit module in the Pegasus topology, which we synthesized using Optimization Modulo Theories. This allows us to encode up to a 21 × 12-bit multiplier (and a 22 × 8-bit one) into the Pegasus 5760-qubit topology of current annealers. To the best of our knowledge, these are the largest factorization problems ever encoded into a quantum annealer. Second, we investigated the problem of actually solving encoded PF problems by running an extensive experimental evaluation on a D-Wave Advantage 4.1 quantum annealer. In the experiments we introduced different approaches to initialize the multiplier qubits and adopted several performance enhancement techniques. Overall, 8,219,999 = 32,749 × 251 was the highest prime product we were able to factorize within the limits of our QPU resources. To the best of our knowledge, this is the largest number which was ever factorized by means of a quantum annealer; also, this is the largest number which was ever factorized by means of any quantum device without relying on external search or preprocessing procedures run on classical computers.
Prime factorization (P = M × N) is a promising application for quantum computing. Shor's algorithm is a key concept for breaking the limit for analyzing P, which cannot be effectively solved by classical computation; however, the algorithm requires error-correctable logical qubits. Here, we describe a quantum annealing method for solving prime factorization. A superconducting quantum circuit with native implementation of the multiplier Hamiltonian provides combinations of M and N as a solution for number P after annealing. This circuit is robust and can be expanded easily to scale up the analysis. We present an experimental and theoretical exploration of the multiplier unit. We demonstrate the 2-bit factorization in a circuit simulation and experimentally at 10 mK. We also explain how the current conditions can be used to obtain high success probability and all candidate factorized elements.
Factorization of a large semiprime is a hard problem on classical computers, and quantum annealing is one way to solve the prime factorization problem by converting to a combinatorial optimization problem. A conversion method using the block-wise sum of partial products has been proposed but that works well up to numbers with 21-bit. To enhance the input bit width of the prime factorization, the paper introduces three proposals for prime factorization based on quantum annealing. First one is to divide the original problem into several sub-problems and solve them using multiple annealings. Second and third ones are analytical variable reduction of LSB and MSB parts. The proposals have been implemented on Python for Fixstars Amplify Annealing Engine (AE) and can factorize numbers with 46-bit or less. The proposals can also factorize numbers up to 57-bit but with a lot of trials for each number.
Factorization of large semiprimes remains one of the most challenging problems for classical computers. Shor’s algorithm offers a quantum approach that reduces computational complexity, but its practical application is currently limited by hardware constraints. Meanwhile, as a provisional approach, quantum annealing (QA) has been explored through formulations of the quadratic unconstrained binary optimization (QUBO) problem. Among existing methods, the blockwise partial-product approach effectively reduced the QUBO variable count but was limited to semiprimes up to 21 bits. To extend factorization to larger semiprimes, this paper addresses key engineering challenges in constructing efficient QUBO formulations for prime factorization. We propose five techniques to reduce variable counts and improve scalability with current QA hardware: (1) dividing the problem into subproblems with partial constraints; (2) applying analytical reductions near the LSB; (3) applying analytical reductions near the MSB; (4) exploiting special patterns in semiprimes, with odd bit widths and long MSB-side zero sequences; and (5) balancing variable usage across both sides of the subproblem. Integrated into a QUBO converter, these methods enable stable factorization of semiprimes up to 47-bits within 20 seconds and can extend to special 2049-bit instances with 1001 consecutive MSB-side zeros.