2011/08/30 by Jun Li, Xinhua Peng, Li, Jun +5
Computer Science · Mathematics · Physics and Astronomy · #Algorithm #Computer science #FOS: Physical sciences #Integer (computer science) #Mathematics #Physics #Quantum #Quantum Computing Algorithms and Architecture #Quantum Fourier transform #Quantum Information and Cryptography #Quantum Mechanics and Applications #Quantum Physics (quant-ph) #Quantum algorithm #Quantum computer #Quantum error correction #Quantum gate #Quantum mechanics #Quantum phase estimation algorithm #Quantum sort #quant-ph
paper · pdf · doi:10.48550/arxiv.1108.5848
published in arXiv (Cornell University) (Cornell University) · 19 pages, 9 figures
arxiv created 2011/08/30 · openalex publication_date 2011/08/30 · arxiv updated 2011/08/31 · openalex created_date 2016/06/24 · openalex updated_date 2026/07/28
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 deterministic 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.