Turing Compliant?

[Stephan Houben]

On Thu, 09 Sep 1999 19:52:22 GMT, jhefferon at my-deja.com 
<jhefferon at my-deja.com> wrote:
>
>Somebody else in this thread mentioned quantum computation.  I've tried
>to read up on it, but I'm afraid I didn't get it.  Is it the case that
>anything quantum computable is Turing computable, that is, quantum
>computability may go faster but doesn't add anything actually new?

I'm not an expert, but anyhow:

The current idea is that a quantum computer roughly corresponds
in capabilities with a nondeterministic Turing-machine, while
an ordinary computer is a deterministic Turing machine.

Both are equivalent WRT what they can theoretically solve.
But there might be a difference in how efficient they can do it.

The class of problems a deterministic TM can solve in polynomial
time (i.e. before the heat death of the Universe for larger input
sizes) is commonly called P. The class of problems a non-deterministic
TM can solve in polynomial time is called NP.

It's trivial to show that P <= NP, but it is unknown if P and NP
are in fact equal. The common conjecture is that they are NOT.
In that case, a quantum computer can solve problems in reasonable
time which an ordinary computer could only solve in many times
the lifetime of the universe.

Greetings,

Stephan