Implementation and Analysis of Regev's Quantum Factorization Algorithm

• URL: http://arxiv.org/abs/2502.09772v1
• Date: Thu, 13 Feb 2025 21:02:15 GMT
• Title: Implementation and Analysis of Regev's Quantum Factorization Algorithm
• Authors: Przemysław Pawlitko, Natalia Moćko, Marcin Niemiec, Piotr Chołda,
• Abstract summary: We present our implementation of Regev's algorithm for factoring composite numbers. Despite Regev's theoretical advantage, our implementation exhibited execution times longer than Shor's algorithm for small integer factorization.
• Score: 0.2874893537471256
• License:
• Abstract: Quantum computing represents a significant advancement in computational capabilities. Of particular concern is its impact on asymmetric cryptography through, notably, Shor's algorithm and the more recently developed Regev's algorithm for factoring composite numbers. We present our implementation of the latter. Our analysis encompasses both quantum simulation results and classical component examples, with particular emphasis on comparative cases between Regev's and Shor's algorithms. Our experimental results reveal that Regev's algorithm indeed outperforms Shor's algorithm for certain composite numbers in practice. However, we observed significant performance variations across different input values. Despite Regev's algorithm's theoretical asymptotic efficiency advantage, our implementation exhibited execution times longer than Shor's algorithm for small integer factorization in both quantum and classical components. These findings offer insights into the practical challenges and performance characteristics of implementing Regev's algorithm in realistic quantum computing scenarios.

Related papers

• Performance Benchmarking of Quantum Algorithms for Hard Combinatorial Optimization Problems: A Comparative Study of non-FTQC Approaches [0.0]
  This study systematically benchmarks several non-fault-tolerant quantum computing algorithms across four distinct optimization problems. Our benchmark includes noisy intermediate-scale quantum (NISQ) algorithms, such as the variational quantum eigensolver. Our findings reveal that no single non-FTQC algorithm performs optimally across all problem types, underscoring the need for tailored algorithmic strategies.
  arXiv  Detail & Related papers  (2024-10-30T08:41:29Z)
• A high-level comparison of state-of-the-art quantum algorithms for breaking asymmetric cryptography [0.0]
  We compare Regev's quantum algorithm with Ekeraa-G"artner's extensions on the one hand, and existing state-of-the-art quantum algorithms for factoring and computing discrete logarithms on the other. Our conclusion is that Regev's algorithm without the space-saving optimizations may achieve a per-run advantage, but not an overall advantage, if non-computational quantum memory is cheap.
  arXiv  Detail & Related papers  (2024-05-23T09:59:00Z)
• On the Finite-Time Performance of the Knowledge Gradient Algorithm [1.713291434132985]
  The knowledge gradient (KG) algorithm is a popular and effective algorithm for the best arm identification (BAI) problem. We present new theoretical results about the finite-time performance of the KG algorithm.
  arXiv  Detail & Related papers  (2022-06-14T13:42:05Z)
• Performance Evaluations of Noisy Approximate Quantum Fourier Arithmetic [1.1140384738063092]
  We implement QFT-based integer addition and multiplications on quantum computers. These operations are fundamental to various quantum applications. We evaluate these implementations based on IBM's superconducting qubit architecture.
  arXiv  Detail & Related papers  (2021-12-17T06:51:18Z)
• Amortized Implicit Differentiation for Stochastic Bilevel Optimization [53.12363770169761]
  We study a class of algorithms for solving bilevel optimization problems in both deterministic and deterministic settings. We exploit a warm-start strategy to amortize the estimation of the exact gradient. By using this framework, our analysis shows these algorithms to match the computational complexity of methods that have access to an unbiased estimate of the gradient.
  arXiv  Detail & Related papers  (2021-11-29T15:10:09Z)
• Quantum algorithms for group convolution, cross-correlation, and equivariant transformations [9.134244356393665]
  Group convolutions and cross-correlations are commonly used in mathematics to analyze or take advantage of symmetries inherent in a given problem setting. Here, we provide efficient quantum algorithms for performing linear group convolutions and cross-correlations on data stored as quantum states.
  arXiv  Detail & Related papers  (2021-09-23T12:21:31Z)
• Detailed Account of Complexity for Implementation of Some Gate-Based Quantum Algorithms [55.41644538483948]
  In particular, some steps of the implementation, as state preparation and readout processes, can surpass the complexity aspects of the algorithm itself. We present the complexity involved in the full implementation of quantum algorithms for solving linear systems of equations and linear system of differential equations.
  arXiv  Detail & Related papers  (2021-06-23T16:33:33Z)
• Fractal Structure and Generalization Properties of Stochastic Optimization Algorithms [71.62575565990502]
  We prove that the generalization error of an optimization algorithm can be bounded on the complexity' of the fractal structure that underlies its generalization measure. We further specialize our results to specific problems (e.g., linear/logistic regression, one hidden/layered neural networks) and algorithms.
  arXiv  Detail & Related papers  (2021-06-09T08:05:36Z)
• Provably Faster Algorithms for Bilevel Optimization [54.83583213812667]
  Bilevel optimization has been widely applied in many important machine learning applications. We propose two new algorithms for bilevel optimization. We show that both algorithms achieve the complexity of $mathcalO(epsilon-1.5)$, which outperforms all existing algorithms by the order of magnitude.
  arXiv  Detail & Related papers  (2021-06-08T21:05:30Z)
• Coded Distributed Computing with Partial Recovery [56.08535873173518]
  We introduce a novel coded matrix-vector multiplication scheme, called coded computation with partial recovery (CCPR) CCPR reduces both the computation time and the decoding complexity by allowing a trade-off between the accuracy and the speed of computation. We then extend this approach to distributed implementation of more general computation tasks by proposing a coded communication scheme with partial recovery.
  arXiv  Detail & Related papers  (2020-07-04T21:34:49Z)
• Approximation Algorithms for Sparse Principal Component Analysis [57.5357874512594]
  Principal component analysis (PCA) is a widely used dimension reduction technique in machine learning and statistics. Various approaches to obtain sparse principal direction loadings have been proposed, which are termed Sparse Principal Component Analysis. We present thresholding as a provably accurate, time, approximation algorithm for the SPCA problem.
  arXiv  Detail & Related papers  (2020-06-23T04:25:36Z)

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.