Quantum prime factorization algorithms using binary carry propagation

• URL: http://arxiv.org/abs/2506.16799v1
• Date: Fri, 20 Jun 2025 07:34:16 GMT
• Title: Quantum prime factorization algorithms using binary carry propagation
• Authors: Arim Ryou, Kiwoong Kim, Kyungtaek Jun,
• Abstract summary: The RSA cryptosystem relies on the computational difficulty of prime factorization.<n>We propose a quantum annealing based approach to integer factorization using both high order unconstrained binary optimization (HUBO) and constrained quadratic model (CQM)<n>Results show that applying global product constraints enhances factorization accuracy and consistency across all tested instances.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.

Related papers

• Learning Feasible Quantum States for Quadratic Constrained Binary Optimization Problems [41.23247424467223]
  We develop a variational approach that creates an equal superposition of quantum states that satisfy constraints in a QCBO.<n>The resulting equal superposition can be used as an initial state for quantum algorithms that solve QUBOs/QCBOs.
  arXiv  Detail & Related papers  (2025-08-04T16:44:53Z)
• Quantum-Classical Hybrid Quantized Neural Network [7.759760132559044]
  We present a novel Quadratic Binary Optimization (QBO) model for quantized neural network training, enabling the use of arbitrary activation and loss functions.<n>We employ the Quantum Gradient Conditional Descent (QCGD) algorithm, which leverages quantum computing to directly solve the QCBO problem.<n> Experimental results using a coherent Ising machine (CIM) demonstrate a 94.95% accuracy on the Fashion MNIST classification task, with only 1.1-bit precision.
  arXiv  Detail & Related papers  (2025-06-23T02:12:36Z)
• VQC-MLPNet: An Unconventional Hybrid Quantum-Classical Architecture for Scalable and Robust Quantum Machine Learning [60.996803677584424]
  Variational Quantum Circuits (VQCs) offer a novel pathway for quantum machine learning.<n>Their practical application is hindered by inherent limitations such as constrained linear expressivity, optimization challenges, and acute sensitivity to quantum hardware noise.<n>This work introduces VQC-MLPNet, a scalable and robust hybrid quantum-classical architecture designed to overcome these obstacles.
  arXiv  Detail & Related papers  (2025-06-12T01:38:15Z)
• Improving adiabatic quantum factorization via chopped random-basis optimization [1.1409483429861258]
  We apply the chopped random-basis (CRAB) optimization technique to enhance adiabatic quantum factorization algorithms.<n>We demonstrate the effectiveness of CRAB by applying it to factor the integers ranging from 21 to 2479.<n>This performance improvement shows resilience in the presence of dephasing noise, highlighting CRAB's practical utility in noisy quantum systems.
  arXiv  Detail & Related papers  (2025-05-22T03:06:02Z)
• An Efficient Quantum Classifier Based on Hamiltonian Representations [50.467930253994155]
  Quantum machine learning (QML) is a discipline that seeks to transfer the advantages of quantum computing to data-driven tasks.<n>We propose an efficient approach that circumvents the costs associated with data encoding by mapping inputs to a finite set of Pauli strings.<n>We evaluate our approach on text and image classification tasks, against well-established classical and quantum models.
  arXiv  Detail & Related papers  (2025-04-13T11:49:53Z)
• Qubit-Efficient Quantum Annealing for Stochastic Unit Commitment [4.2251752131402585]
  Unit Commitment (SUC) has been proposed to manage the uncertainties driven by the integration of renewable energy sources.<n>This paper introduces the Powell-Hestenes-Rockafellar Augmented Lagrangian Multiplier (PHR-ALM) method to eliminate the need for slack variables.<n>To further reduce the qubit overhead, quantum ADMM is applied to break large-scale SUC into smaller blocks and enables a sequential solution.
  arXiv  Detail & Related papers  (2025-02-21T20:15:40Z)
• QUBO Refinement: Achieving Superior Precision through Iterative Quantum Formulation with Limited Qubits [3.2995359570845912]
  Quantum algorithms are capable of solving linear equations and eigenvalues, surpassing the pace of classical computers. By exploiting this technology, quantum optimization models have been proposed for applications, such as linear systems, eigenvalue problems, RSA cryptosystems, and CT image reconstruction. The accuracies of the existing Qiskit simulator, D-Wave system simulator, and hybrid solver are limited to two decimal places. We propose a new iterative algorithm that sequentially progresses from the highest to the lowest exponent in binarizing each number.
  arXiv  Detail & Related papers  (2024-11-25T06:56:00Z)
• Early Fault-Tolerant Quantum Computing [0.0]
  We develop a model for the performance of early fault-tolerant quantum computing (EFTQC) architectures. We show that, for the canonical task of phase estimation, in a regime of moderate scalability and using just over one million physical qubits, the reach'' of the quantum computer can be extended.
  arXiv  Detail & Related papers  (2023-11-24T19:12:47Z)
• Quantum Annealing for Single Image Super-Resolution [86.69338893753886]
  We propose a quantum computing-based algorithm to solve the single image super-resolution (SISR) problem. The proposed AQC-based algorithm is demonstrated to achieve improved speed-up over a classical analog while maintaining comparable SISR accuracy.
  arXiv  Detail & Related papers  (2023-04-18T11:57:15Z)
• Analyzing Prospects for Quantum Advantage in Topological Data Analysis [35.423446067065576]
  We analyze and optimize an improved quantum algorithm for topological data analysis. We show that super-quadratic quantum speedups are only possible when targeting a multiplicative error approximation. We argue that quantum circuits with tens of billions of Toffoli can solve seemingly classically intractable instances.
  arXiv  Detail & Related papers  (2022-09-27T17:56:15Z)
• Quantum Robustness Verification: A Hybrid Quantum-Classical Neural Network Certification Algorithm [1.439946676159516]
  In this work, we investigate the verification of ReLU networks, which involves solving a robustness many-variable mixed-integer programs (MIPs) To alleviate this issue, we propose to use QC for neural network verification and introduce a hybrid quantum procedure to compute provable certificates. We show that, in a simulated environment, our certificate is sound, and provide bounds on the minimum number of qubits necessary to approximate the problem.
  arXiv  Detail & Related papers  (2022-05-02T13:23:56Z)
• A Hybrid Quantum-Classical Algorithm for Robust Fitting [47.42391857319388]
  We propose a hybrid quantum-classical algorithm for robust fitting. Our core contribution is a novel robust fitting formulation that solves a sequence of integer programs. We present results obtained using an actual quantum computer.
  arXiv  Detail & Related papers  (2022-01-25T05:59:24Z)
• Realization of arbitrary doubly-controlled quantum phase gates [62.997667081978825]
  We introduce a high-fidelity gate set inspired by a proposal for near-term quantum advantage in optimization problems. By orchestrating coherent, multi-level control over three transmon qutrits, we synthesize a family of deterministic, continuous-angle quantum phase gates acting in the natural three-qubit computational basis.
  arXiv  Detail & Related papers  (2021-08-03T17:49:09Z)
• Error mitigation and quantum-assisted simulation in the error corrected regime [77.34726150561087]
  A standard approach to quantum computing is based on the idea of promoting a classically simulable and fault-tolerant set of operations. We show how the addition of noisy magic resources allows one to boost classical quasiprobability simulations of a quantum circuit.
  arXiv  Detail & Related papers  (2021-03-12T20:58:41Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.