Less Wrong is a community blog devoted to refining the art of human rationality. Please visit our About page for more information.

JoshuaZ comments on That Alien Message - Less Wrong

111 Post author: Eliezer_Yudkowsky 22 May 2008 05:55AM

You are viewing a comment permalink. View the original post to see all comments and the full post content.

Comments (164)

Sort By: Old

You are viewing a single comment's thread. Show more comments above.

Comment author: JoshuaZ 03 May 2012 06:13:21AM *  1 point [-]

With a quantum computer, all we would have to do is feed it data about the universe and it would almost instantly spit out hypotheses ranked in order of probability, with suggested tests for sorting through them.

Calculating consistent probabilities is in general NP-hard (if one has probabilities that are all 0 or 1 then it easily mimics SAT, and one can without too much effort extend this to a proof for the general case). It is unknown at present if quantum computers provide any sort of speed-up for NP hard problems in the general case, and the suspicion by most in the field seems to be that the answer is "no" or at least that it doesn't provide enough speed up to matter that much unless in fact P=NP outright (essentially, assuming that P!=NP, it is likely that BQP does not contain NP). So you probably can't do this. That said, the bounds of what quantum computers can do efficiently are not well-understood and even drastic improvements in constants could be bad. Running a poorly understood AI on a quantum computer or having access to a quantum computer would thus be a really bad idea.

Comment author: CronoDAS 03 May 2012 06:47:50AM 2 points [-]

Indeed. A quantum computer can't brute force NP-hard problems in polynomial time simply by being a quantum computer. It is indeed faster than a classical computer, but it's still not fast enough. A quantum computer can brute force a problem in the square root of the time it takes a classical computer to do so, but the square root of an exponential function is still exponential. If the classical computer brute forces a problem of size n in 2^n time, then the quantum computer takes (sqrt(2))^n time.