Paper 2000/036

Using fewer Qubits in Shor's Factorization Algorithm via Simultaneous Diophantine Approximation

Jean-Pierre Seifert

Abstract

While quantum computers might speed up in principle certain computations dramatically, in pratice, though quantum computing technology is still in its infancy. Even we cannot clearly envison at present what the hardware of that machine will be like. Nevertheless, we can be quite confident that it will be much easier to build any practical quantum computer operating on a few number of quantum bits rather than one operating on a huge number of of quantum bits. It is therefore of big practical impact to use the resource of quantum bits very spare, i.e., to find quantum algorithms which use as few as possible quantum bits. 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.

Metadata
Available format(s)
PS
Category
Foundations
Publication info
Published elsewhere. Unknown where it was published
Keywords
factoringquantum computing
Contact author(s)
Jean-Pierre Seifert @ infineon com
History
2000-07-18: received
Short URL
https://ia.cr/2000/036
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2000/036,
      author = {Jean-Pierre Seifert},
      title = {Using fewer Qubits in Shor's Factorization Algorithm via Simultaneous Diophantine Approximation},
      howpublished = {Cryptology {ePrint} Archive, Paper 2000/036},
      year = {2000},
      url = {https://eprint.iacr.org/2000/036}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.