undefined | Better HN

0 pointseynsham1y ago0 comments

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.

0 comments

Dylan168071y ago

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.

eynshamOP1y ago

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.

Dylan168071y ago

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.

1 more reply

andrewp1231y ago

I can't imagine you believe P=NP.

eynshamOP1y ago

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.

j / k navigate · click thread line to collapse

0 comments

Dylan168071y ago

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.

eynshamOP1y ago

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

Dylan168071y ago

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.

1 more reply

andrewp1231y ago

I can't imagine you believe P=NP.

eynshamOP1y ago

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.

j / k navigate · click thread line to collapse