HiveBrain v1.2.0
Get Started
← Back to all entries
patternModerate

Is it proven that quantum computation is no better at solving NP complete problems than classical computation?

Submitted by: @import:stackexchange-cs··
0
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.