Download pdf
An Overview of Regev’s Quantum Factoring Algorithm and Its Recent Developments
- 1 St Edmund Hall, University of Oxford, Oxford, United Kingdom
* Author to whom correspondence should be addressed.
Abstract
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 ), compared to Shor’s originalO(n^2 lo gn ) 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, generalize 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.
Keywords
Quantum computing, quantum algorithm, quantum factoring, shor’s algorithm.
[1]. Aharonov D, Regev O 2005 Lattice Problems in NP coNP [online] Available: https://cims.nyu. edu/~regev/papers/cvpconp.pdf
[2]. Ekerå M, Gärtner J 2024 Extending Regev’s Factoring Algorithm to Compute Discrete Logarithms Post-Quantum Cryptography Springer Nature Switzerland pp 211–242 ISBN 9783031627460 DOI 10.1007/978-3-031-62746-0_10 [online] Available: http://dx.doi.org/10. 1007/978-3-031-62746-0_10
[3]. Kiebert M 2024 Oded Regev’s Quantum Factoring Algorithm [online] Available: https:// vdwetering.name/pdfs/thesis-midas.pdf
[4]. Nielsen MA, Chuang IL 2000 Quantum Computation and Quantum Information Cambridge University Press
[5]. Pilatte C 2024 Unconditional correctness of recent quantum algorithms for factoring and computing discrete logarithms [online] Available: https://arxiv.org/pdf/2404.16450v1
[6]. Ragavan S, Vaikuntanathan V 2024 Space-Efficient and Noise-Robust Quantum Factoring arXiv:2310.00899 [quant-ph] [online] Available: https://arxiv.org/abs/2310.00899
[7]. Regev O 2023 An Efficient Quantum Factoring Algorithm arXiv:2308.06572 [quant-ph] [online] Available: https://arxiv.org/abs/2308.06572
[8]. Regev O 2004 Lecture 2: LLL Algorithm [online] Available: https://cims.nyu.edu/~regev/ teaching/lattices_fall_2004/ln/lll.pdf
[9]. Kaye P, Laflamme R, Mosca M 2007 An Introduction to Quantum Computing Oxford University Press
[10]. Harvey D, van der Hoeven J 2021 Integer multiplication in time O(n log n) Annals of Mathematics 2(193) 563–617
[11]. Shor PW 1994 Algorithms for quantum computation: Discrete logarithms and factoring 35th Annual Symposium on Foundations of Computer Science Santa Fe, New Mexico, USA IEEE Computer Society pp 124–134
[12]. Pomerance C 2001 The expected number of random elements to generate a finite abelian group Periodica Mathematica Hungarica 43(1-2) 191–198
[13]. Zeckendorf E 1972 Representations of natural numbers by a sum of Fibonacci numbers and Lucas numbers Bulletin of the Royal Society of Sciences of Liege 179–182
[14]. Kaliski BS Jr 2017 Targeted Fibonacci exponentiation arXiv preprint arXiv:1711.02491
[15]. Acciaro V 1996 The probability of generating some common families of finite groups Utilitas Mathematica 243–254
[16]. Regev O 2024 Presentation at Simons Institute: An Efficient Quantum Factoring Algorithm — Quantum Colloquium [online] Available: https://www.youtube.com/watch?v=Uzn93GjAfRg)
Cite this article
Chen,R.L. (2024). An Overview of Regev’s Quantum Factoring Algorithm and Its Recent Developments. Applied and Computational Engineering,110,161-169.
Data availability
The datasets used and/or analyzed during the current study will be available from the authors upon reasonable request.
Disclaimer/Publisher's Note
The statements, opinions and data contained in all publications are solely those of the individual author(s) and contributor(s) and not of EWA Publishing and/or the editor(s). EWA Publishing and/or the editor(s) disclaim responsibility for any injury to people or property resulting from any ideas, methods, instructions or products referred to in the content.
About volume
Volume title: Proceedings of CONF-MLA 2024 Workshop: Securing the Future: Empowering Cyber Defense with Machine Learning and Deep Learning
© 2024 by the author(s). Licensee EWA Publishing, Oxford, UK. This article is an open access article distributed under the terms and
conditions of the Creative Commons Attribution (CC BY) license. Authors who
publish this series agree to the following terms:
1. Authors retain copyright and grant the series right of first publication with the work simultaneously licensed under a Creative Commons
Attribution License that allows others to share the work with an acknowledgment of the work's authorship and initial publication in this
series.
2. Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the series's published
version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgment of its initial
publication in this series.
3. Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and
during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See
Open access policy for details).