Cymm writes:
> But once we develop quantum computers we'll probably find out: not only will
> they handle exponential problems in polynomial time - but they'll probably
> (in these weird scenarios) solve Turing Incomputable problems in polynomial
> time - or even flat time.
Actually, no, quantum computers are not expected to solve exponential
problems in polynomial time. More precisely, there are no problems
known to be exponential on classical computers which are polynomial on
quantum computers.
Quantum computers can cut the exponent down on search problems, which
are known to be exponential on both kinds of computers. The speedup
is potentially even greater on some special math problems (factoring
for example) but the true complexity of those problems on convential
computers is not known.
Quantum computers are not at all expected to solve Turing uncomputable
problems like the halting problem. From what I understand, they are
subject to the same proofs of uncomputability.
Hal
This archive was generated by hypermail 2b29 : Mon Oct 02 2000 - 17:36:52 MDT