[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.