# 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. – Yuval Filmus Dec 8 '19 at 23:30
• The specific problem you mention can likely be solved in polynomial time on a classical computer. – Yuval Filmus Dec 8 '19 at 23:31
• – D.W. Dec 9 '19 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 – nonopolarity Dec 9 '19 at 5:21

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.