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

[Ryan Ingram]

On 12/30/07, Miguel Mitrofanov <miguelimo38 at yandex.ru> wrote:

> > 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.
>
> No! Moreover, there is a hypothesis that the only problems quantum
> computer can solve in polynomial time are those that the usual
> computer can.


 According to http://en.wikipedia.org/wiki/Quantum_computer

The class of problems that can be efficiently solved by quantum computers is
called BQP, for "bounded error, quantum, polynomial time". Quantum computers
only run probabilistic algorithms, so BQP on quantum computers is the
counterpart of BPP on classical computers. It is defined as the set of
problems solvable with a polynomial-time algorithm, whose probability of
error is bounded away from one quarter.[18] A quantum computer is said to
"solve" a problem if, for every instance, its answer will be right with high
probability. If that solution runs in polynomial time, then that problem is
in BQP.

BQP is suspected to be disjoint from NP-complete and a strict superset of P,
but that is not known. Both integer factorization and discrete log are in
BQP. Both of these problems are NP problems suspected to be outside BPP, and
hence outside P. Both are suspected to not be NP-complete.


---

So, if you come up with a polynomial-time algorithm for integer
factorization that doesn't use quantum computers, you could probably make a
lot of money cracking people's RSA keys.

  -- ryan
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell-cafe/attachments/20071230/18fe1fba/attachment.htm