The following are a few comments on quantum computing which I thought might be of some interest to members of these lists.
Hardware
A large number of proposals have been made. Several of the proposals are merely for quantum logic, and do not satisfactorily discuss some of the other big issues: (a) state preparation; (b) readout of the result; (c) scalability of the architecture.
There is no architecture known which satisfactorily addresses all of these issues. Several candidates are under investigation. Many researchers believe that solid state rather than optical approches are the correct path to take, because of human experience in scaling solid state systems. Unfortunately, historically, nearly all our experience in manipulating single quantum systems has involved photons (and that only for 20-30 years).
In practice, what this means is that solid state approaches which may eventually prove viable will take a lot of work to get to the same levels of control as we can now see with atom-optical systems. The hope is that once they get to that level of control they will prove to be much more scalable.
Most of the progress in hardware over the past couple of years has been based upon Nuclear Magnetic Resonance (NMR). While fine for small scale demonstrations, it is extremely unlikely that NMR will scale up at a later date, without several major revolutions in NMR.
In short, there is certainly no cure-all on the horizon, however I am pleased by the fact that many of the requisite properties can be found in existing systems, albeit _different_ systems.
Algorithms
Our understanding of algorithms is still pretty limited. Broadly speaking, two classes of algorithms are known.
The first is algorithms based upon finding the stabilizer of an Abelian group. Applications include the factoring and discrete log problems, which enable several well-known cryptosystems to be broken. These algorithms provide a spectacular exponential speed-up.
The second class is algorithms based upon a "search" heuristic. These algorithms provide a quadratic speedup to essentially any algorithm based upon an unstructured sort, and to some algorithms based upon a more structured sort.
A third "class" of algorithms is for doing quantum simulation. I don't think anybody doubts that quantum computers will be good at simulating quantum systems, however it is not yet quite clear what _precisely_ they will be used to do.
Still, four years after Shor announced quantum factoring, that's a respectable list. It should not be surprising that we find it a lot more difficult to think up quantum algorithms than classical, given the domain in which we develop our intuition.
Limits
As in the classical case, there is very little known about limits to quantum computation. Most of the bounds known are proved in "oracle" models of computation, which are of dubious value. Essentially, what these bounds tell you is that it is no good trying to solve a problem in a certain specific way. They do not rule out other approaches to the problem. There is, however, an impressively large amount known about bounds in the oracle model, which is useful for people trying to develop algorithms.
As to the power of quantum computers in the general model, it is very much an open question. The class BQP of problems efficiently soluble on a quantum computer is not known to have an especially clean relation to any class in classical complexity theory. We do know that BQP is contained within PSPACE, the class of problems soluble in polynomial _space_ on a classical computer, but not many other non-trivial results are known.
In fact, more to the point, we don't even have a very good idea of what makes quantum computers powerful. Is it entanglement? Superposition? The large size of Hilbert space? All of the above?
In my opinion, one of the most interesting open problems is to investigate models of computation which go beyond the standard quantum computing model. Does general relativity buy you anything? What about quantum field theories? String theory? These are, by and large, open questions.
Michael Nielsen