Quantum computers cannot solve NP-Complete problems in sub exponential time (we think). If we could measure the quantom state then they would be able to. Howeve

Quantum computers cannot solve NP-Complete problems in sub exponential time (we think). If we could measure the quantom state then they would be able to. However there is an exponentially small chance that when we make the measurement we will see the currect answer instead of no result (or simmiliar). Effectively, we need to repeat the computation an exponential amount of times to arrive at the answer. There is a genneral algorithm that could solve many (all?) NP-Complete problems in the square root of the time it takes classical algorithms, but that is still exponential.