5
$\begingroup$

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?
Improve this question
$\endgroup$
1
  • $\begingroup$ BQP is closed under polynomial time reductions. $\endgroup$
    – Yuval Filmus
    Sep 24, 2020 at 12:20

1 Answer 1

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ While this is strong, it doesn't feel it is particularly compelling to me since in classical computers we also have "solve one NP-complete then solve all", i.e. we have the intuition that all NP-complete are hard. We just have the same situation for quantum, and the best reason we seem to have in both cases is "we haven't found any fast algorithm yet, so likely there isn't one". $\endgroup$
    – Ciro Santilli OurBigBook.com
    Aug 23, 2021 at 10:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.