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.