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

CronoDAS 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: 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.