3 ms·
I do not believe quantum computers can solve NP hard problems in polynomial time. According to https://en.wikipedia.org/wiki/BQP#Relationship_to_other_complexit
by dalke 10y ago
I do not believe quantum computers can solve NP hard problems in polynomial time. According to https://en.wikipedia.org/wiki/BQP#Relationship_to_other_complexity_classes https://en.wikipedia.org/wiki/BQP#Relationship_to_other_comp... , "The relation between BQP and NP is not known."
("BQP (bounded error quantum polynomial time) is the class of decision problems solvable by a quantum computer in polynomial time, with an error probability of at most 1/3 for all instances.")
- rlanday 10y agoRight, it’s not known. Although technically we don’t know for sure if classical computers can solve NP-hard problems in polynomial time either (that’s the P vs. NP problem).