Here, we present a method to reduce the number of actually needed qubits in Shor's algorithm to factor a composite number $N$. Exploiting the inherent probabilism of quantum computation we are able to substitute the continued fraction algorithm to find a certain unknown fraction by a simultaneous Diophantine approximation. While the continued fraction algorithm is able to find a Diophantine approximation to a single known fraction with a denominator greater than $N^2$, our simultaneous Diophantine approximation method computes in polynomial time unusually good approximations to known fractions with a denominator of size $N^{1+\varepsilon}$, where $\varepsilon$ is allowed to be an arbitrarily small positive constant.
As these unusually good approximations are almost unique we are able to recover an unknown denominator using fewer qubits in the quantum part of our algorithm.
Category / Keywords: foundations / factoring, quantum computing Date: received 18 Jul 2000 Contact author: Jean-Pierre Seifert at Infineon com Available format(s): Postscript (PS) | Compressed Postscript (PS.GZ) | BibTeX Citation Version: 20000718:170508 (All versions of this report) Short URL: ia.cr/2000/036