An Overview of Regevs Quantum Factoring Algorithm and Its Recent Developments

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, Shors 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 Shors algorithm over the last three decades, significant breakthroughs remained elusive until Regevs 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 ), compared to Shors originalO(n^2 lo gn ) gate complexity. Although Regevs 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 Regevs factoring algorithm, including a review of Shors 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, generalize Regevs 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.