[Haskell-cafe] Re: Wikipedia on first-class object

[ajb at spamcop.net]

G'day all.

I think it was Ketil Malde who said:

>> If I understand correctly, a quantum computer might solve problems in
>> NP in polynomial time, which is assumed not to be possible for
>> deterministic computers.

Quoting Miguel Mitrofanov <miguelimo38 at yandex.ru>:

> No! Moreover, there is a hypothesis that the only problems quantum
> computer can solve in polynomial time are those that the usual computer
> can.

"Problems in NP" is not the same as "NP-hard".  We know that a quantum
computer can solve problems in NP in polynomial time, since every
problem in P is also in NP.  Moreover, we know of at least one problem
not known to be in P which can be sort-of solved by a quantum computer in
polynomial time (prime factoring).  In that sense, the "understanding" is
more or less correct.

But yeah, it seems likely that the best that a quantum computer can do
is bring "almost intractable" problems down to "barely tractable".

Cheers,
Andrew Bromage