From: Eliezer S. Yudkowsky (sentience@pobox.com)
Date: Mon Sep 14 1998 - 11:57:04 MDT
Hal Finney wrote:
>
> Quantum computing does extend the class of problems known to be solvable
> in polynomial time, but it does not establish that P=NP using such
> machines. Factoring has not been shown to be NP-complete.
NP stands for Nondeterministic Polynomial. Given the right physical
architecture (each eigenstate is a separate thread, just like reality itself),
then each qubit could directly represent the magic-coin-flip bit of an NP algorithm.
Although, as far as I know, nobody has demonstrated that P=NP for
qubit-manipulation (non-branching) languages like QCL. I presume that's what
you meant. Anyway, sorry for the confusion; I should have specified that I
meant the eigenstate-branching version instead of the modern qubit-chunk version.
> Robin Hanson had an interesting article on the polymath list speculating
> that quantum computing could theoretically speed up AI very dramatically.
> This only works if AI can be expressed as a massive search problem,
> consolidating many small problems into very large superproblems. Search
> of n items for an optimum can be done in sqrt(n) time using QCs so it
> is necessary to work on very large problems to get effective speedups.
As far as I can tell, qubit-chunk QC doesn't help AI at all. If Hanson can
figure out how to get sqrt(n) out of it, he's way ahead of me. I haven't
finished the QCL language spec, but I can't visualize doing anything but very
dense mathematical problems. Maybe some network-optimization problems could
be encoded, but I can't see, say, quantum Deep Blue.
--
sentience@pobox.com Eliezer S. Yudkowsky
http://pobox.com/~sentience/AI_design.temp.html
http://pobox.com/~sentience/sing_analysis.html
Disclaimer: Unless otherwise specified, I'm not telling you
everything I think I know.
This archive was generated by hypermail 2.1.5 : Fri Nov 01 2002 - 14:49:34 MST