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.
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.
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.
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.
In this essay, we examine the feasibility of quantum computation of Gr\"obner basis which is a fundamental tool of algebraic geometry. The classical method for computing Gr\"obner basis is based on Buchberger's algorithm, and our question is how to adopt quantum algorithm there. A Quantum algorithm for finding the maximum is usable for detecting head terms of polynomials, which are required for the computation of S-polynomials. The reduction of S-polynomials with respect to a Gr\"obner basis could be done by the quantum version of Gauss-Jordan elimination of matrices which represents polynomials. However, the frequent occurrence of zero-reductions of polynomials is an obstacle to the effective application of quantum algorithms. This is because zero-reductions of polynomials occur in non-full-rank matrices, for which quantum linear systems algorithms (through the inversion of matrices) are inadequate, as ever-known quantum linear solvers (such as Harrow-Hassidim-Lloyd) require the clandestine computations of the inverses of eigenvalues. Such algorithms should be used in limited situations with the guarantee that the matrices could be inverted. For example, the transformation from the non-reduced Gr\"obner basis to the reduced one is of this sort, and the quantum algorithms surely achieve the partial speedup of the computations.
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.