[FOM] QM computing synopsis

Wed Oct 16 20:26:53 EDT 2002

hi all. Ive been following QM computing fairly closely
for a few years now. its really blossoming lately as
a field, both on the theoretical & practical levels.

what great synchronicity for this thread: I just found
this link today. sciam just came out with
a brand new issue on "quantum information science", QIS.
heres the cover story  by michael nielsen

http://www.sciam.com/article.cfm?articleID=0005C8BF-1B88-1D9B-815A809EC5880000

in a nutshell, QM computing is also called "spintronics", or
at least there is overlap. the simple way to visualize it is that
computing states are encoded in spins of the atom. a spin is
a continuous/analog variable, not a on/off bit, hence the
pun "qubit".

I highly recommend the book _the quest for the quantum computer_
by julian brown. I disrecommend _fabric of reality_ by deutsch.
(imho sections of it sound almost like they were written by a mad 
scientist, your mileage may vary)

its a very active area of research whether QM computers can
compute faster than "classic" architectures. it is known that
QM computers can factor large numbers in polynomial time via
the famous result of shor. there is also a result that they
can search a database in O(sqrt(n)) time. 

however the general question is not yet settled. it hinges 
on both subtle theoretical and practical issues. noise correction
in QM, also related to "preventing decoherence" (ie preserving the
highly sensitive QM spin states & insulating them from the
environment) are whitehot questions of theoretical & practical
inquiry.

I run a year-old group looking into QM foundations here, some may
be interested

http://groups.yahoo.com/group/qm2/

here a lot of neat links collected after a year
of traffic, youll probably find something interesting

http://groups.yahoo.com/group/qm2/message/3008/

also Ive collected quite a bit on QM computing, complexity
theory & spintronics in a section from the theory-edge FAQ here.
theres several tutorials & papers.

http://groups.yahoo.com/group/theory-edge/message/6090