Can quantum computing help solve NP-Complete problems?

Question

i was just wondering if quantum computing has done any good so far in solving NP complete problems. I am aware that quantum computing does solve some NP problems which are classically hard in polynomial time but as far as i know none of those problems are NP complete.

So there are a few interesting questions one could ask here:

• Is there any proof or indication that such an algorithm is impossible/possible?

In this post (Why did Google not use an NP problem for their quantum supremacy experiment?) the top answer states:

However, quantum computers are not expected to be able to solve NP-complete problems significantly more "easily" than regular computers.

But it'd be nice to hear some reasoning why that is believed to be the case when other exponential time problems have already been reduced to polynomial time.

• If such an algorithm were to be found for any NP-Complete problem would that mean that any NP problem could be solved efficiently by quantum computers just like classically finding a polynomial solution to an NP hard problem would prove P = NP?

Answer 1

BQP (the quantum analog of BPP) is closed under polynomial time reductions, so if some NP-complete problem is in BQP, then all NP-complete problems are in BQP. For more arguments, check this Quora question or that Quora question.