I can't comment on the theory side of quantum computation (BQP vs the classical equivalent BPP), but I would like to make an <i>engineering</i> comment about why I think quantum computation will be <i>very</i> difficult to scale, maybe even impossible.<p>To have good quantum registers (long memory time), you want each qubit to interact as little as possible with its environment. This means isolation (qubits far apart) or encoding the information in systems that interact weakly with each other.<p>However, to have good quantum computation (quick), you want strongly interacting qubits.<p>The two goals are diametrically opposite, so it's not clear how we can achieve both of them in a single system.<p>IMHO, the first interesting things that will come from quantum information science will be about quantum simulations of physical systems and quantum communication. Computation might come later... but I'm sure, by then, we'll have moved away from RSA and ElGamal.
> <i>The obvious solution is to write down the initial vector of size N=2^50 and start applying the quantum gates to the vector. […] The size is “just” a petabyte—or actually 1/8 of a petabyte.</i><p>Um, NO. A quantum system is described by the <i>complex probability</i> of being in any of those states. You need more like 2^57 bits to represent that. 16 petabytes.<p>Source: I've written a 24-qubit quantum simulator.
>Quantum Computers have been proved to be more powerful than classical. <i>wrong</i>.<p>I take issue with that claim.<p>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.<p>With the added power of a quantum computer, we can solve it with only one call to f.<p>Boom, there is exponential speedup with quantum computing. This is similar to what lies behind Shor's algorithm for factoring.<p>Check it out, wikipedia has diagrams that I can't put in here.<p><a href="http://en.wikipedia.org/wiki/Deutsch%E2%80%93Jozsa_algorithm" rel="nofollow">http://en.wikipedia.org/wiki/Deutsch%E2%80%93Jozsa_algorithm</a><p>EDIT:
It seems he addresses this exact problem here
<a href="http://rjlipton.wordpress.com/2011/10/26/quantum-chocolate-boxes/" rel="nofollow">http://rjlipton.wordpress.com/2011/10/26/quantum-chocolate-b...</a><p>I apologize, I was a bit hasty to call him out, he does know what he is talking about.
Interesting title. It is wordplay on the old movie title "Sex, Lies, and Videotape", where 'videotape' gets changed to the topic under discussion.<p>Of those three, " videotape " is the only one that is obsolete, while the others are timeless. While the original phrase goes increasingly obscure, the wordplay remains fresh because the obsolete part is invisible.
> "With all due apologies to Soderbergh his title seems perfect for our discussion. There may be no sex, but there is plenty of sizzle surrounding quantum computation."<p>Right, the title "sex, lies and videotape" is perfect for the discussion. There's no sex, and there are no videotapes, but there are quantum computers, and the author's desperate attempt to cram some whimsy into his post.<p>I'll sum up the problem as I see it. The problem is that we're comparing real (and thus limited by the reality of manufacturing etc.) classical computers, with theoretically perfect quantum computers.<p>Well the idea of something is always better, faster and sexier (see, I worked back sex into this) than reality, because as we get closer and closer to building computers with a larger qubit number we'll start hitting all sorts of engineering issues that would distance us from that perfect theoretical ideal of a 100% efficient quantum computer.<p>And it may turn out that idealism is all the advantage quantum computers had in the first place. It was all for naught. Not that we'll stop trying of course.