0
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ Answering the question in the title: No it doesn’t. It’s just a popular misconception. $\endgroup$ – Yuval Filmus Dec 8 '19 at 23:30
  • 1
    $\begingroup$ The specific problem you mention can likely be solved in polynomial time on a classical computer. $\endgroup$ – Yuval Filmus Dec 8 '19 at 23:31
  • 1
    $\begingroup$ cs.stackexchange.com/q/51469/755, smbc-comics.com/comic/the-talk-3 $\endgroup$ – D.W. Dec 9 '19 at 4:21
  • $\begingroup$ @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 $\endgroup$ – nonopolarity Dec 9 '19 at 5:21
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.