[Tyr42]

>Quantum Computers have been proved to be more powerful than classical. wrong.

I take issue with that claim.

Take for example, the Deutsch-Jozsa problem. Given some function f, on n bits to one bit, such that f is either {zero on all the possible inputs, or one on all inputs}, or f is zero on half the inputs and one on the other half. To tell which of those cases it is, it requires 2^(n-1) + 1 tests of f. You have to test it on half the inputs, plus one.

With the added power of a quantum computer, we can solve it with only one call to f.

Boom, there is exponential speedup with quantum computing. This is similar to what lies behind Shor's algorithm for factoring.

Check it out, wikipedia has diagrams that I can't put in here.

http://en.wikipedia.org/wiki/Deutsch%E2%80%93Jozsa_algorithm

EDIT: It seems he addresses this exact problem here http://rjlipton.wordpress.com/2011/10/26/quantum-chocolate-b...

I apologize, I was a bit hasty to call him out, he does know what he is talking about.

[dirtyaura]

If I understood correctly, in the posted article he addressed the class of black box problems, of which Deutsch–Jozsa is a subclass, calling it an unfair setting.

Specifically:

The fair comparison is to allow the classic machine the same ability to see the circuit representation of the box. The trouble now is the proof disappears.

[lauraura]

Isn't "quantum computers are proven to be more powerful than classical" proof that BQP != P, which would imply P != PSPACE, which hasn't yet been proven?

[gizmo686]

Not quite. Suppose there is some problem, whose best classical algorithm C, and whose best quantum algorithm is Q, with Q in o(c) [0]. Given that this relationship cannot exist in reverse (that is, quantum computers are at least as powerful as classical ones), this would mean that quantum computers are more powerful.

The statement BQP!=P means that there exists a problem that a quantum computer can solve in polynomial time, but a classical computer cannot. This is a stronger requirement.

For example, consider Shoore's algorithm, which can search an unsorted list in O(sqrt(n)) time, strictly better than the O(n) time it takes a classical algorithm.

[0] Note that the little-o means strictly less, whereas big-O means less than or equal to.

[j2kun]

> Note that the little-o means strictly less, whereas big-O means less than or equal to.

Aaahhh! Please don't say that when you're clarifying a technical point about theory!

Besides, it's explicitly stated in that article that "more powerful" is to be interpreted as P != BQP.