[eynsham]

Since quantum computers can stimulate classical computers, presumably they can solve NP-complete problems, since classical computers, by definition, can. Perhaps you mean that they can’t solve NP-complete problems in polynomial time, but we don’t even know that of classical computers, so you would presumably have shown that P≠NP, which would be fairly impressive.

[Dylan16807]

So you're nitpicking it for being too strong of a statement and too weak of a statement at the same time?

How about this, they can't do the thing NP stands for. They can't run a generic polynomial-time algorithm in a nondeterministically-branching way, and then pick the winner.

[eynsham]

I considered multiple readings of the claim. Obviously different readings may differ in strength. I do not exclude a reading that is neither too strong nor too weak; the comment is an invitation to give one, which you appear to have taken up.

I do not see the distinction between what you have written in the second paragraph and the claim that P≠NP.

[Dylan16807]

If P=NP, then there must exist a deterministic polynomial solution for any NP problem.

Because it is deterministic, that means it's using a different algorithm than the straightforward nondeterministic solution.

So any Turing machine can solve the problem, but it will have to use the former algorithm. It can't use the latter algorithm.

A lot of people think of quantum computers as basically a nondeterministic Turing machine, and the wording in the parent post is an attempt to correct that misconception.

[eynsham]

Well, I also suspect BQP≠NP, but we don’t know that yet either.

I still don’t understand what is meant by ’straightforward nondeterministic solution’. If you mean that QTMs or quantum circuits aren’t formally the same as NTMs, I agree. But nor are two-tape (D)TMs and single-tape DTMs, and yet we have linear speedup. Presumably there is a stronger claim here, but I do not understand what that is.

[Dylan16807]

> I still don’t understand what is meant by ’straightforward nondeterministic solution’.

I'm not sure how much better I can phrase it than "run a generic polynomial-time algorithm in a nondeterministically-branching way, and then pick the winner."

Let me lay out a scenario:

You have a problem with 2^n potential answers.

You have a fast polynomial algorithm you can apply to each potential answer, and you want to find the right answer.

A lot of people think that if you use a quantum computer, it will check every answer in parallel and quickly find the answer at polynomial speed.

But it doesn't work like that. To some extent it does check every answer in parallel, but you need to do a lot more to make the correct answer show up out of the noise. Let's say you need to use Grover's algorithm. That cuts 2^n down to 2^(n/2), which is a remarkable speedup but it's still exponential.

It's possible that P=NP and there's a totally different solution for both classical and quantum computers that isn't exponential. But that's a side issue. The important thing here is that it's not being quantum that lets you escape exponential purgatory.

> If you mean that QTMs or quantum circuits aren’t formally the same as NTMs, I agree.

Kind of?

But it's not really about formal equivalences. It's that tons of people think a QTM is literally a NTM.

[andrewp123]

I can't imagine you believe P=NP.

[eynsham]

I believe that it is an open question. Were I a betting man, I’d bet that P≠NP. I believe it would also be significant to show that P≠NP implies BQP≠NP but that may already be known.