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.
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.
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.
The RSA cryptosystem, which relies on the computational difficulty of prime factorization, faces growing challenges with the advancement of quantum computing. In this study, we propose a quantum annealing based approach to integer factorization using both high order unconstrained binary optimization (HUBO) and constrained quadratic model (CQM) formulations. We begin by modeling binary multiplication with explicit carry propagation, translating this into a HUBO representation and subsequently reducing it to a quadratic unconstrained binary optimization form compatible with current quantum solvers. To address scalability limitations, we implement a CQM approach with constraint relaxation and global product consistency. While the HUBO model successfully factors small semiprimes, it exhibits exponential memory growth, making it impractical for inputs larger than 10 bits. In contrast, the CQM model achieves accurate factorization of semiprimes up to 60 bits including N = 1152921423002469787 demonstrating significantly improved scalability. Experimental results further show that applying global product constraints enhances factorization accuracy and consistency across all tested instances. This work highlights both the promise and current limitations of quantum-assisted factorization and establishes a foundation for evaluating RSA security in the emerging quantum era.
Quantum annealing is a metaheuristic method aimed at finding the global minimum of a pseudo-Boolean quadratic function. To solve a problem by a quantum annealer, it must be restated as a QUBO (quadratic unconstrained binary optimization) problem, the standard format acceptable to an annealer. However, there are many natural problems that turn out be of cubic or higher order, yet promising solutions can be obtained for many instances using quantum annealers, after converting to the QUBO format, using order reduction criteria. Accordingly, quadratization becomes a crucial preprocessing step in order to make use of present-day quantum annealing hardware that relies on coupling technology, which can only process interactions of at most degree two. A critical challenge is that quadratization methods often require many additional variables, degrading the performance of the annealers. A number of algorithmic and heuristic quadratization techniques have been proposed and used for annealing in the literature, affecting the performance of the annealers differently. We examine a number of such quadratization techniques, focusing on their efficiency, compactness, and applicability. We analyze the approaches motivated by diverse goals and highlight the transition from foundational approaches to more recent compact approaches. An evaluation of the current usage of different quadratization methods in the literature is carried out at the end of the survey. Further, we comment on the limitations on usage and show possible opportunities to enhance the performance of annealers.
Recent advancements in quantum computing have demonstrated significant potential for solving combinatorial optimization problems, like the quadratic knapsack problem, a constrained binary optimization problem. However, current quantum and quantum-inspired algorithms often require transforming these constrained problems into an unconstrained form, known as Quadratic Unconstrained Binary Optimization (QUBO). Such transformations can significantly impact the algorithms’ speed and efficiency. In this study, we evaluate five existing transformation methods and propose four novel approaches. We assess all nine methods using Simulated Annealing and find that three of our approaches outperform existing methods in terms of execution time and the quality and quantity of feasible solutions found. Additionally, we tested these transformations on quantum annealers, which were unable to solve even small problem instances, due to limitations in connectivity and error rates. However, our results highlight the advantages of the new approaches, which reduce the total number of variables in the QUBO representation. This is a critical factor for enhanced performance on emerging quantum hardware, since it also reduces the required number of qubits and the embedding chain lengths.
Recent advancements in quantum computing have demonstrated significant potential for solving combinatorial optimization problems, like the quadratic knapsack problem, a constrained binary optimization problem. However, current quantum and quantum-inspired algorithms often require transforming these constrained problems into an unconstrained form, known as Quadratic Unconstrained Binary Optimization (QUBO). Such transformations can significantly impact the algorithms’ speed and efficiency. In this study, we evaluate five existing transformation methods and propose four novel approaches. We assess all nine methods using Simulated Annealing and find that three of our approaches outperform existing methods in terms of execution time and the quality and quantity of feasible solutions found. Additionally, we tested these transformations on quantum annealers, which were unable to solve even small problem instances, due to limitations in connectivity and error rates. However, our results highlight the advantages of the new approaches, which reduce the total number of variables in the QUBO representation. This is a critical factor for enhanced performance on emerging quantum hardware, since it also reduces the required number of qubits and the embedding chain lengths.
Recent advancements in quantum computing have demonstrated significant potential for solving combinatorial optimization problems, like the quadratic knapsack problem, a constrained binary optimization problem. How- ever, current quantum and quantum-inspired algorithms often require transforming these constrained problems into an unconstrained form, known as Quadratic Unconstrained Binary Optimization (QUBO). Such transfor- mations can significantly impact the algorithms’ speed and efficiency. In this study, we evaluate five existing transformation methods and propose four novel approaches. We assess all nine methods using Simulated An- nealing and find that three of our approaches outperform existing methods in terms of execution time and the quality and quantity of feasible solutions found. Additionally, we tested these transformations on quantum annealers, which were unable to solve even small problem instances, due to limitations in connectivity and error rates. However, our results highlight the advantages of the new approaches, which reduce the total num- ber of variables in the QUBO representation. This is a critical factor for enhanced performance on emerging quantum hardware, since it also reduces the required number of qubits and the embedding chain lengths.