__
TR00-078 | 18th July 2000 00:00
__

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

**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.