Re: Quantum Computation

Nick Maclaren wrote:

> The latter. To a very good approximation, there is only one
> practical problem that a quantum computer is known to solve
> significantly faster than a deterministic one: integer
> factorisation a.k.a. the discrete logarithm (Shor).

Well, to be precise, this is not "known", but "believed to be". We
still do not know the lower bound of factorization's complexity on
a deterministic machine, so it is not true that Shor's algorithm
is essentially faster than any deterministc decomposition algorithm.
It is just much faster that all _known_ factorization algorithms,
but there is still a chance that a deterministic machine will perform
this process comparably well. A similar situation was with primality
testing -- an open problem for about 2500 years, which has finally
turned out to be easy. :-)

Best regards
Piotr Wyderski

.