From: Michael Nielsen (mnielsen@theory.caltech.edu)
Date: Sun Nov 22 1998 - 12:23:40 MST
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
This archive was generated by hypermail 2.1.5 : Fri Nov 01 2002 - 14:49:49 MST