JoshuaZ comments on Who thinks quantum computing will be necessary for AI? - Less Wrong

4 Post author: ChrisHallquist 28 May 2013 10:59PM

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

Comments (101)

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

Comment author: JoshuaZ 30 May 2013 01:20:44AM *  2 points [-]

So that is practically true, and in fact. EXPTIME is one of the few things we can show is large enough that we can even prove it properly contains P. But, in context this isn't as bad as it looks. The vast majority of interesting things we can do on quantum computers take in practice much less than exponential time (look at factoring for example). In fact, BQP actually lives inside PSPACE, so this shouldn't be that surprising.

But practical issues aside , most of the arguments about using quantum computers to do AI or consciousness involve claims that they are fundamentally necessary. The fact that we can simulate them with sufficient slow down demonstrates that at least that version of that thesis is false.