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.

Article Navigation

Comments (101)

Comments (101)

You are viewing a single comment's thread.

Comment author: JoshuaZ 29 May 2013 04:02:10PM 2 points [-]

Quantum computers can be simulated on classical computers with exponential slow down. So even if you think the human mind uses quantum computation, this doesn't mean that the same thing can't be done on a classical machine. Note also that BQP (the set of efficiently computable problems by a quantum computer) is believed (although not proven) to not contain any NP complete problems.

Note also that at a purely practical level, since quantum computers can do a lot of things better than classical computers and our certainty about their strength is much lower, trying to run an AI on a quantum computer is a really bad idea if you take the threat of AI going FOOM seriously.

Comment author: jsteinhardt 29 May 2013 05:30:48PM 4 points [-]

So even if you think the human mind uses quantum computation, this doesn't mean that the same thing can't be done on a classical machine.

An exponential slowdown basically means that it can't be done. If you have an oracle for EXPTIME then you're basically already set for most problems you could want to solve.

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.

Powered by Reddit Powered by Reddit