# Does quantum computing convert any O(2^n) algorithm into a polynomial running time and how?

For example, if it is a $$O(2^n)$$ algorithm that loops through 0 to $$2^n - 1$$ and check whether the number of 1 bits is divisible by 3, 5, 7, 9, 11, does quantum computing reduce it to non-exponential time and how?

• Answering the question in the title: No it doesn’t. It’s just a popular misconception. Dec 8, 2019 at 23:30
• The specific problem you mention can likely be solved in polynomial time on a classical computer. Dec 8, 2019 at 23:31
• – D.W.
Dec 9, 2019 at 4:21
• @YuvalFilmus just saying if it is a brute-force algorithm... can't think of a better example except the traveling salesman but that is more complicated... I wanted to just give a simple $2^n$ loop Dec 9, 2019 at 5:21

No it does not. I mean probably. Because no-one really knows.

What do I mean by we don't know? We're not even 100 % sure whether P=NP or not and if it does, sure a quantum computer can solve any NP problem in polynomial time, same as a deterministic Turing machine.

However we assume that is not the case and we also expect the classes of NP and BQP (bounded-error quantum polynomial-time) to overlap, but each may contain problems the other one does not (i.e. neither contains the other). If NP contains something BQP does not, it surely has to be at least all NP-complete problems, including the TSP you mentioned in one of your comments. With these assumptions quantum computer cannot solve TSP in polynomial time (even with a given probability).

What we do have right now is Grover's algorithm, which provides quadratic speedup for black-box problems. Which means if the best we can come up with is brute force in $$O(2^n)$$ steps, Grover can solve it in $$O(2^{(n/2)})=O(\sqrt{2}^n)$$ steps with a given probability. That is it gives a quadratic speed-up, not exponential.