2020/11/10 by Daniel Chicayban Bastos, Bastos, Daniel Chicayban, Luis Antônio Brasil Kowada +1
Computer Science · #FOS: Physical sciences #Quantum Computing Algorithms and Architecture #Quantum Physics (quant-ph)
paper · pdf · doi:10.48550/arxiv.2011.05355
openalex publication_date 2020/11/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.