[ivansavz]

I can't comment on the theory side of quantum computation (BQP vs the classical equivalent BPP), but I would like to make an engineering comment about why I think quantum computation will be very difficult to scale, maybe even impossible.

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.

However, to have good quantum computation (quick), you want strongly interacting qubits.

The two goals are diametrically opposite, so it's not clear how we can achieve both of them in a single system.

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.

[tedsanders]

It's a fair argument that the problem is unlikely to be solved because the solution wants to go in opposite directions (both weakly and strongly interacting). However, let me point out that there are many technologies that face strong tradeoffs and yet have been successful. Consider hard drive memory, for example. You want it to be easily switchable so that you can access bits quickly with little power. But you also want it to be hard to switch, so that it remembers your data for a long time. The engineering challenge is achieving both seemingly opposite goals at once. The success of memory technologies (among others) makes me optimistic that this is a solvable problem.

[gizmo686]

As a counterpoint, I would point to how far we have been able to scale classical computers (over almost a century of work). We have gotten to the point where we are pushing up against fairly fundamental limitations of the physics (speed of light, quantum effects, ETC).

Given enough time, we will (through incremental improvements) refine quantum computers towards their theoretical limits. We will likely see practical applications long before we reach these limitations.