论文标题
Pollard的Rho的量子版本是Shor的算法是一种特殊情况
A quantum version of Pollard's Rho of which Shor's Algorithm is a particular case
论文作者
论文摘要
Pollard的Rho是解决整数分解问题的一种方法。该策略搜索属于一系列自然数的合适元素，这些元素给定适当条件的序列产生了非平凡因素。在将算法转换为量子模型的计算模型时，我们发现其运行时间使用一组生成序列的功能将其运行时间降低为多项式时间。我们还得出了一个新的结果，该结果表征了序列中非平凡因素的可用性。结果使我们意识到Pollard的Rho是Shor算法的概括，这是根据新结果很容易看到的事实。
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.
