Comment

Comment by mofeing

No. As far as we know, no realization of a quantum algorithm can solve NP-complete problems in polynomial many steps.

Some people that worked on this topic told me that there seems to be some improvements on the quasi-optimal solution found, but that due to the scale of current quantum computers, it just have been tried out on small-sized problems.

Theoretically, there are some papers suggesting that there are problems in BQP (the computational model of quantum computers) outside of NP [1] and even, the PH [2] (Polynomial Hierarchy, the infinite hierarchy of composition of NP and co-NP problems), which is why we cannot still satisfactorily say whether quantum computers can or cannot solve NP-complete problems.

The Wikipedia page for BQP [3] does a good job showing what is currently known.

[1] https://arxiv.org/abs/2209.10398 [2] https://eccc.weizmann.ac.il/report/2018/107/ [3] https://en.wikipedia.org/wiki/BQP#Relationship_to_other_comp...

parent mofeing 4 months ago

Discussion

Live from the official Hacker News API

A modern reader for Hacker News · SvelteKit + Skeleton