A quantum version of Pollard's Rho of which Shor's Algorithm is a particular case

• URL: http://arxiv.org/abs/2011.05355v2
• Date: Fri, 19 Jan 2024 16:31:04 GMT
• Title: A quantum version of Pollard's Rho of which Shor's Algorithm is a particular case
• Authors: Daniel Chicayban Bastos and Luis Antonio Kowada
• Abstract summary: Pollard's Rho is a method for solving the integer factorization problem. We show that Pollard's Rho is a generalization of Shor's algorithm.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Pollard's Rho is a method for solving the integer factorization problem. The strategy searches for a suitable pair of elements belonging to a sequence of natural numbers that given suitable conditions yields a nontrivial factor. In translating the algorithm to a quantum model of computation, we found its running time reduces to polynomial-time using a certain set of functions for generating the sequence. We also arrived at a new result that characterizes the availability of nontrivial factors in the sequence. The result has led us to the realization that Pollard's Rho is a generalization of Shor's algorithm, a fact easily seen in the light of the new result.

Related papers

• A Sample Efficient Alternating Minimization-based Algorithm For Robust Phase Retrieval [56.67706781191521]
  In this work, we present a robust phase retrieval problem where the task is to recover an unknown signal. Our proposed oracle avoids the need for computationally spectral descent, using a simple gradient step and outliers.
  arXiv  Detail & Related papers  (2024-09-07T06:37:23Z)
• Bregman-divergence-based Arimoto-Blahut algorithm [53.64687146666141]
  We generalize the Arimoto-Blahut algorithm to a general function defined over Bregman-divergence system. We propose a convex-optimization-free algorithm that can be applied to classical and quantum rate-distortion theory.
  arXiv  Detail & Related papers  (2024-08-10T06:16:24Z)
• Quantum Algorithms for Representation-Theoretic Multiplicities [0.0]
  We give quantum algorithms for computing Kostka, Littlewood-Richardson, Plethysm and Kronecker coefficients. We show that there is an efficient classical algorithm for computing the Littlewood-Richardson coefficients. We conjecture that our quantum algorithms lead to superpolynomial speedups.
  arXiv  Detail & Related papers  (2024-07-24T21:34:05Z)
• Extending Regev's factoring algorithm to compute discrete logarithms [0.0]
  Regev recently introduced a quantum factoring algorithm that may be perceived as a $d$-dimensional variation of Shor's factoring algorithm. In this work, we extend Regev's factoring algorithm to an algorithm for computing discrete logarithms in a natural way.
  arXiv  Detail & Related papers  (2023-11-09T17:45:28Z)
• An Optimal Algorithm for the Real-Valued Combinatorial Pure Exploration of Multi-Armed Bandit [65.268245109828]
  We study the real-valued pure exploration problem in the multi-armed bandit (R-CPE-MAB) Existing methods in the R-CPE-MAB can be seen as a special case of the so-called transductive linear bandits. We propose an algorithm named the gap-based exploration (CombGapE) algorithm, whose sample complexity matches the lower bound.
  arXiv  Detail & Related papers  (2023-06-15T15:37:31Z)
• Approximating a RUM from Distributions on k-Slates [88.32814292632675]
  We find a generalization-time algorithm that finds the RUM that best approximates the given distribution on average. Our theoretical result can also be made practical: we obtain a that is effective and scales to real-world datasets.
  arXiv  Detail & Related papers  (2023-05-22T17:43:34Z)
• An efficient quantum algorithm for lattice problems achieving subexponential approximation factor [2.3351527694849574]
  We give a quantum algorithm for solving the Bounded Distance Decoding (BDD) problem with a subexponential approximation factor on a class of integer lattices. The running time of the quantum algorithm is for one range of approximation factors and subexponential time for a second range of approximation factors. This view makes for a clean quantum algorithm in terms of finite abelian groups, uses relatively little from lattice theory, and suggests exploring approximation algorithms for lattice problems in parameters other than dimension alone.
  arXiv  Detail & Related papers  (2022-01-31T18:58:33Z)
• Polynomial-Time Approximation of Zero-Free Partition Functions [9.153066211741356]
  We give an algorithm-time algorithm for estimating classical and quantum partition functions specified by local Hamiltonians. Our result is based on a new abstract framework that extends and generalizes the approach of Patel and Regts.
  arXiv  Detail & Related papers  (2022-01-30T09:54:45Z)
• Using Shor's algorithm on near term Quantum computers: a reduced version [0.0]
  We introduce a reduced version of Shor's algorithm that proposes a step forward in increasing the range of numbers that can be factorized on noisy Quantum devices. In particular, we have found noteworthy results in most cases, often being able to factor the given number with only one of the proposed algorithm.
  arXiv  Detail & Related papers  (2021-12-23T15:36:59Z)
• Quantum algorithm for stochastic optimal stopping problems with applications in finance [60.54699116238087]
  The famous least squares Monte Carlo (LSM) algorithm combines linear least square regression with Monte Carlo simulation to approximately solve problems in optimal stopping theory. We propose a quantum LSM based on quantum access to a process, on quantum circuits for computing the optimal stopping times, and on quantum techniques for Monte Carlo.
  arXiv  Detail & Related papers  (2021-11-30T12:21:41Z)
• Accelerated Message Passing for Entropy-Regularized MAP Inference [89.15658822319928]
  Maximum a posteriori (MAP) inference in discrete-valued random fields is a fundamental problem in machine learning. Due to the difficulty of this problem, linear programming (LP) relaxations are commonly used to derive specialized message passing algorithms. We present randomized methods for accelerating these algorithms by leveraging techniques that underlie classical accelerated gradient.
  arXiv  Detail & Related papers  (2020-07-01T18:43:32Z)
• Solving Satisfiability of Polynomial Formulas By Sample-Cell Projection [0.8702432681310401]
  algorithm for deciding satisfiability of formulas over the reals is proposed. Key point of the algorithm is a new projection operator, called sample-cell projection operator, custom-made for Conflict-Driven Clause Learning (CDCL)-style search.
  arXiv  Detail & Related papers  (2020-03-01T05:36:09Z)
• Optimal Randomized First-Order Methods for Least-Squares Problems [56.05635751529922]
  This class of algorithms encompasses several randomized methods among the fastest solvers for least-squares problems. We focus on two classical embeddings, namely, Gaussian projections and subsampled Hadamard transforms. Our resulting algorithm yields the best complexity known for solving least-squares problems with no condition number dependence.
  arXiv  Detail & Related papers  (2020-02-21T17:45:32Z)

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.