Sci Rep. 2012;2:260. doi: 10.1038/srep00260. Epub 2012 Feb 10.
Quantum computers are known to be qualitatively more powerful than classical computers, but so far only a small number of different algorithms have been discovered that actually use this potential. It would therefore be highly desirable to develop other types of quantum algorithms that widen the range of possible applications. Here we propose an efficient and exact quantum algorithm for finding the square-free part of a large integer - a problem for which no efficient classical algorithm exists. The algorithm relies on properties of Gauss sums and uses the quantum Fourier transform. We give an explicit quantum network for the algorithm. Our algorithm introduces new concepts and methods that have not been used in quantum information processing so far and may be applicable to a wider class of problems.
量子计算机在性能上被认为优于经典计算机，但到目前为止，仅发现了少量实际利用这种潜力的不同算法。因此，开发其他类型的量子算法来拓宽可能的应用范围是非常可取的。在这里，我们提出了一种有效的、精确的量子算法，用于寻找大整数的无平方部分——对于这个问题，目前还没有有效的经典算法。该算法依赖于高斯和的性质，并使用量子傅里叶变换。我们给出了算法的显式量子网络。我们的算法引入了新的概念和方法，这些概念和方法迄今为止尚未在量子信息处理中使用，可能适用于更广泛的一类问题。
