Re: Quantum computing

Eliezer S. Yudkowsky (
Mon, 14 Sep 1998 12:57:04 -0500

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.

--         Eliezer S. Yudkowsky

Disclaimer:  Unless otherwise specified, I'm not telling you
everything I think I know.