Integer Factorization through Func-QAOA

• URL: http://arxiv.org/abs/2309.15162v1
• Date: Tue, 26 Sep 2023 18:00:25 GMT
• Title: Integer Factorization through Func-QAOA
• Authors: Mostafa Atallah, Haemanth Velmurugan, Rohan Sharma, Siddhant Midha, Shamim Al Mamun, Ludmila Botelho, Adam Glos, \"Ozlem Salehi
• Abstract summary: No efficient classical algorithm for cryptographic-time integer factorization has been found. We present the Func-QAOA approach for factorization, which premises overcoming some of the limitations of previous approaches.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• Solving the Independent Domination Problem by Quantum Approximate Optimization Algorithm [0.5919433278490629]
  Independent Domination Problem (IDP) has practical implications in various real-world scenarios. Existing classical algorithms for IDP are plagued by high computational complexity. This paper introduces a Quantum Approximate Optimization (QAOA)-based approach to address the IDP.
  arXiv  Detail & Related papers  (2024-10-22T17:49:00Z)
• Maximizing the practical achievability of quantum annealing attacks on factorization-based cryptography [0.0]
  This work focuses on quantum methods for cryptanalysis of schemes based on the integer factorization problem and the discrete logarithm problem. We demonstrate how to practically solve the largest instances of the factorization problem by improving an approach that combines quantum and classical computations.
  arXiv  Detail & Related papers  (2024-10-07T11:55:23Z)
• Metric Learning to Accelerate Convergence of Operator Splitting Methods for Differentiable Parametric Programming [46.26499759722771]
  This paper shows how differentiable optimization can enable the end-to-end learning of proximal metrics. Results illustrate a strong connection between the learned proximal metrics and active constraints at the optima.
  arXiv  Detail & Related papers  (2024-04-01T03:23:43Z)
• Efficient Model-Free Exploration in Low-Rank MDPs [76.87340323826945]
  Low-Rank Markov Decision Processes offer a simple, yet expressive framework for RL with function approximation. Existing algorithms are either (1) computationally intractable, or (2) reliant upon restrictive statistical assumptions. We propose the first provably sample-efficient algorithm for exploration in Low-Rank MDPs.
  arXiv  Detail & Related papers  (2023-07-08T15:41:48Z)
• A Review on Quantum Approximate Optimization Algorithm and its Variants [47.89542334125886]
  The Quantum Approximate Optimization Algorithm (QAOA) is a highly promising variational quantum algorithm that aims to solve intractable optimization problems. This comprehensive review offers an overview of the current state of QAOA, encompassing its performance analysis in diverse scenarios. We conduct a comparative study of selected QAOA extensions and variants, while exploring future prospects and directions for the algorithm.
  arXiv  Detail & Related papers  (2023-06-15T15:28:12Z)
• Iteration Complexity of Variational Quantum Algorithms [5.203200173190989]
  We argue that noise makes evaluations of the objective function via quantum circuits biased. We derive the missing guarantees and find that the rate of convergence is unaffected.
  arXiv  Detail & Related papers  (2022-09-21T19:18:41Z)
• A Constrained Optimization Approach to Bilevel Optimization with Multiple Inner Minima [49.320758794766185]
  We propose a new approach, which convert the bilevel problem to an equivalent constrained optimization, and then the primal-dual algorithm can be used to solve the problem. Such an approach enjoys a few advantages including (a) addresses the multiple inner minima challenge; (b) fully first-order efficiency without Jacobian computations.
  arXiv  Detail & Related papers  (2022-03-01T18:20:01Z)
• Variational Quantum Optimization with Multi-Basis Encodings [62.72309460291971]
  We introduce a new variational quantum algorithm that benefits from two innovations: multi-basis graph complexity and nonlinear activation functions. Our results in increased optimization performance, two increase in effective landscapes and a reduction in measurement progress.
  arXiv  Detail & Related papers  (2021-06-24T20:16:02Z)
• Hybrid Quantum Computing -- Tabu Search Algorithm for Partitioning Problems: preliminary study on the Traveling Salesman Problem [0.8434687648198277]
  We introduce a novel solving scheme coined as hybrid Quantum Computing - Tabu Search Algorithm. Main pillars of operation of the proposed method are a greater control over the access to quantum resources, and a considerable reduction of non-profitable accesses.
  arXiv  Detail & Related papers  (2020-12-09T11:21:50Z)
• Space-efficient binary optimization for variational computing [68.8204255655161]
  We show that it is possible to greatly reduce the number of qubits needed for the Traveling Salesman Problem. We also propose encoding schemes which smoothly interpolate between the qubit-efficient and the circuit depth-efficient models.
  arXiv  Detail & Related papers  (2020-09-15T18:17:27Z)

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.