patternModerate
Is it proven that quantum computation is no better at solving NP complete problems than classical computation?
Viewed 0 times
solvingcomputationclassicalthanbettercompletethatprovenproblemsquantum
Problem
Is it proven that quantum computation is no better at solving NP complete problems than classical computation or it's just believed?
Solution
It is suspected that NP-complete problems cannot be solved in quantum polynomial time (i.e., that they are not in BQP), but this hasn't been proved. We don't expect a proof in the near future, since this would imply that P is different from NP.
Context
StackExchange Computer Science Q#69233, answer score: 11
Revisions (0)
No revisions yet.