Integer factorization is a computational problem of fundamental importance in cybersecurity and secure communications, as its difficulty form the basis of modern public-key cryptography. While Shor's algorithm can solve this problem efficiently on a universal quantum computer, near-term devices require alternative approaches. The Adiabatic Factorization Algorithm and its digitized counterparts offer a promising NISQ-era pathway but suffer from high-order many-body interactions that are difficult to implement. In this work, we propose a modified QAOA-based factorization protocol that simplifies the interacting Hamiltonian to include only two-body terms, significantly reducing its experimental complexity. Numerical simulations show that this method achieves comparable or higher fidelities than the standard protocol, while requiring fewer quantum resources and converging more rapidly for problem instances up to eight qubits. We analyze the characteristic fidelity behavior introduced by the Hamiltonian modification. Additionally, we report on simulations with alternative cost-function definitions that frequently yielded improved performance.
Integer factorization is a computational problem of fundamental importance in cybersecurity and secure communications, as its difficulty form the basis of modern public-key cryptography. While Shor's algorithm can solve this problem efficiently on a universal quantum computer, near-term devices require alternative approaches. The Adiabatic Factorization Algorithm and its digitized counterparts offer a promising NISQ-era pathway but suffer from high-order many-body interactions that are difficult to implement. In this work, we propose a modified QAOA-based factorization protocol that simplifies the interacting Hamiltonian to include only two-body terms, significantly reducing its experimental complexity. Numerical simulations show that this method achieves comparable or higher fidelities than the standard protocol, while requiring fewer quantum resources and converging more rapidly for problem instances up to eight qubits. We analyze the characteristic fidelity behavior introduced by the Hamiltonian modification. Additionally, we report on simulations with alternative cost-function definitions that frequently yielded improved performance.
Digitized adiabatic quantum factorization is a hybrid algorithm that exploits the advantage of digitized quantum computers to implement efficient adiabatic algorithms for factorization through gate decompositions of analog evolutions. In this paper, we harness the flexibility of digitized computers to derive a digitized adiabatic algorithm able to reduce the gate-demanding costs of implementing factorization. To this end, we propose a new approach for adiabatic factorization by encoding the solution of the problem in the kernel subspace of the problem Hamiltonian, instead of using ground-state encoding considered in the standard adiabatic factorization proposed by Peng etal. [Phys. Rev. Lett. 101, 220405 (2008)]. Our encoding enables the design of adiabatic factorization algorithms belonging to the class of Quadratic Unconstrained Binary Optimization (QUBO) methods, instead the Polinomial Unconstrained Binary Optimization (PUBO) used by standard adiabatic factorization. We illustrate the performance of our QUBO algorithm by implementing the factorization of integers N up to 8 bits. The results demonstrate a substantial improvement over the PUBO formulation, both in terms of reduced circuit complexity and increased fidelity in identifying the correct solution.
Abstract Factoring integers is considered as a computationally hard problem for classical methods, whereas there exists polynomial-time Shor’s quantum algorithm for solving this task. However, requirements for running Shor’s algorithm for realistic tasks, which are beyond the capabilities of existing and upcoming generations of quantum computing devices, motivate to search for alternative approaches. In this work, we experimentally demonstrate factoring of the integer with a trapped ion quantum processor using the Schnorr approach and a modified version of the quantum approximate optimization algorithm (QAOA). The key difference of our approach in comparison with the recently proposed QAOA-based factoring method is the use of the fixed-point feature, which relies on the use of universal parameters. We present experimental results on factoring 1591 = 37 × 43 using 6 qubits as well as simulation results for 74425657 = 9521 × 7817 with 10 qubits and 35183361263263 = 4194191 × 8388593 with 15 qubits. Although we present all the necessary details for reproducing our results and analysis of the performance of the factoring method, the scalability of this approach in both the classical and quantum domains still requires further studies.
Integer factorization is a significant problem, with implications for the security of widely-used cryptographic schemes. No efficient classical algorithm for polynomial-time integer factorization has been found despite extensive research. Although Peter Shor's breakthrough quantum algorithm offers a viable solution, current limitations of noisy intermediate-scale quantum (NISQ) computers hinder its practical implementation. To address this, researchers have explored alternative methods for factorization suitable for NISQ devices. One such method is the Quantum Approximate Optimization Algorithm, which treats factoring as an optimization problem defined over binary bits, resulting in various problematic aspects. In this paper, we explore the Func-QAOA approach for factorization, which premises overcoming some of the limitations of previous approaches and allows the incorporation of more advanced factorization techniques. After reviewing the most promising quantum implementations for integer arithmetics, we present a few illustrative examples to demonstrate the efficacy of the Func-QAOA approach and discuss methods to reduce the search space to speed up the optimization process.
Quantum computers pose a fundamental threat to widely deployed public-key cryptosystems, such as RSA and ECC, by enabling efficient integer factorization using Shor's algorithm. Theoretical resource estimates suggest that 2048-bit RSA keys could be broken using Shor's algorithm with fewer than a million noisy qubits. Although such machines do not yet exist, the availability of smaller, cloud-accessible quantum processors and open-source implementations of Shor's algorithm raises the question of what key sizes can realistically be factored with today's platforms. In this work, we experimentally investigate Shor's algorithm on several cloud-based quantum computers using publicly available implementations. Our results reveal a substantial gap between the capabilities of current quantum hardware and the requirements for factoring cryptographically relevant integers. In particular, we observe that circuit constructions still need to be highly specific for each modulus, and that machine fidelities are unstable, with high and fluctuating error rates.
Digital quantum computing paradigm offers highly desirable features such as universality, scalability, and quantum error correction. However, physical resource requirements to implement useful error-corrected quantum algorithms are prohibitive in the current era of NISQ devices. As an alternative path to performing universal quantum computation, within the NISQ era limitations, we propose to merge digital single-qubit operations with analog multiqubit entangling blocks in an approach we call digital-analog quantum computing (DAQC). Along these lines, although the techniques may be extended to any resource, we propose to use unitaries generated by the ubiquitous Ising Hamiltonian for the analog entangling block and we prove its universal character. We construct explicit DAQC protocols for efficient simulations of arbitrary inhomogeneous Ising, two-body, and M-body spin Hamiltonian dynamics by means of single-qubit gates and a fixed homogeneous Ising Hamiltonian. Additionally, we compare a sequential approach where the interactions are switched on and off (stepwise DAQC) with an always-on multiqubit interaction interspersed by fast single-qubit pulses (banged DAQC). Finally, we perform numerical tests comparing purely digital schemes with DAQC protocols, showing a remarkably better performance of the latter. The proposed DAQC approach combines the robustness of analog quantum computing with the flexibility of digital methods.
Factoring large integers has long been a computationally difficult problem in classical computing, forming the foundation of widely used encryption methods like RSA. In 1994, Shor’s quantum algorithm introduced a revolutionary method for factoring integers exponentially faster than classical algorithms, laying the groundwork for quantum cryptography. Despite numerous attempts to enhance Shor’s algorithm over the last three decades, significant breakthroughs remained elusive until Regev’s discovery in 2023. Regev introduced a novel, multi-dimensional version of the quantum factoring algorithm, achieving a substantial improvement by reducing the required number of quantum gates to O(n^2 lo gn )(n^(3/2) logn ), compared to Shor’s originalO(n^2 lo gn )original O(n^2 logn ) gate complexity. Although Regev’s approach offers a significant speedup, it comes with increased qubit requirements and relies on an unproven number theory assumption. This paper presents an overview of Regev’s factoring algorithm, including a review of Shor’s work for context, followed by an examination of key recent developments and follow-up research. These include efforts to reduce the qubit count, improve error resilience, generalizegeneralise Regev’s algorithm to related problems, and validate the number theory assumption. This review serves as an accessible entry point for researchers interested in the rapidly evolving field of quantum computing and factoring algorithms.