[FOM] QM computing links

Thu Oct 17 01:08:17 EDT 2002

hi all. more quantum synchronicity;
just after I posted I ran across a beautiful new 
scientific reference on QM computing from comp.theory by black et al, 
appended below. I find it really
impressive how many **extremely** good presentations of QM computing
are freely available on the web.

an addendum to my last note on the key issue raised
by the original poster SS. afaik, nobody in QM computing is claiming
that the systems will solve undecidable problems (although there
are papers that argue some physical systems are capable of solving
undecidable problems). 

so QM computing is focused around improved performance issues. however, 
it is potentially revolutionary in that regard. some speculate 
on a revolution in computing power possibly on the technological & 
economic & social order of the original silicon revolution if the
kinks can be worked out.

note the current world record is (afaik)
a **7-qubit** QM computer successfully
used to factor the number 15 using shors algorithm by chuang et al. see
www.qubyte.com below for a tracking of a QM like moores law.

outside the basic "QM computers do not compute undecidable problems"
framework, the CS theoretical framework for QM computing is still
quite nontrivial & leads to many open questions, however, partly 
because QM computing natural seems to lead to the definition of 
new types of complexity classes. so all the CS theory that is
affected is mainly in complexity theory (but where it 
could also be revolutionary).

here I will just cut & paste from the theory-edge FAQ many 
1st rate & outstanding links on QM computing.  (some of these
are not in the previous version link I mentioned)

introduction to Quantum Computing and Communication, by black et al.
"intended to give general scientists (not computer scientists or physicists)
a feeling for how things work."

http://xsun.sdct.itl.nist.gov/~black/Papers/quantumCom.html

quantum information science, QIS, by michael nielsen, scientific american

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

scientific american on "spintronics" (QM computing electronics)

http://www.sciam.com/article.cfm?articleID=0007A735-759A-1CDD-B4A8809EC588EEDF

the quest for the spin transistor, IEEE online, dec 2001

http://www.spectrum.ieee.org/WEBONLY/publicfeature/dec01/spin.html

when will qm computing become a reality?

http://www.newsfactor.com/perl/story/19097.html

ibm scientists announce they have implemented shors
algorithm for qm factoring, to solve
15 = 3 * 5. chuang et al

http://www.nytimes.com/2001/12/20/science/20QUAN.html

http://www.wired.com/news/technology/0,1282,49268,00.html

up to 80 qubits by ertmer & birkl

http://www.economist.com/science/displayStory.cfm?story_id=1280667

june 1998 sci am article by gershenfield and chuang

http://www.media.mit.edu/physics/publications/papers/98.06.sciam/0698gershenfeld.html

previous record by knill/laflamme at los alamos

http://www.nytimes.com/2001/03/27/science/27QUAN.html

qm computers will be hard to build

http://physicsweb.org/article/world/15/8/2

QM computation, university of oxford

http://www.qubit.org/

NIST, US qm computing laboratory center

http://qubit.nist.gov/

will QM computation have its own moore's law?

http://www.qubyte.com/

from cbits to qbits: teaching computer scientsits quantum mechanics
by david mermin

http://www.arxiv.org/abs/quant-ph/0207118/

introduction to QM computing for nonphysicists, by rieffel and polak

http://www.arxiv.org/abs/quant-ph/9809016/

Quantum Physics and Computers By: Adriano Barenco

http://www.ennui.net/~quantum/papers/QuantumComputing.ps.gz

machines, logic & quantum physics, 1999

by david deutsch, artur ekert, rossella lupacchini

http://www.arxiv.org/abs/math.HO/9911150/

"one complexity theorists view of quantum computing, by fortnow (2000)

http://citeseer.nj.nec.com/289726.html

the square root of not, by brian hayes, 1995

http://www.americanscientist.org/issues/comsci95/compsci95-07.html

this is a new, sophisticated ~60 page survey article on QM computing.

from the page given by black below

Paul E. Black, D. Richard Kuhn, and Carl J. Williams,
Quantum Computing and Communications, Advances in
Computers, Academic Press, vol. 56, pages 189-244, 2002, to
be published. 

Abstract: 
           A quantum computer, if built, will be to an ordinary
       computer as a hydrogen bomb is to gunpowder, at least
       for some types of computations. Today no quantum
       computer exists, beyond laboratory prototypes capable
       of solving only tiny problems, and many practical
       problems remain to be solved. Yet the theory of
       quantum computing has advanced significantly in the
       past decade, and is becoming a significant discipline in
       itself. This article explains the concepts and basic
       mathematics behind quantum computers and some of
       the promising approaches for building them. We also
       discuss quantum communication, an essential
       component of future quantum information processing,
       and quantum cryptography, widely expected to be the
       first practical application for quantum information
       technology. 

From: Paul E. Black (p.black at acm.org)
Subject: Re: Quantum Computing 
Newsgroups: comp.theory
Date: 2002-10-15 10:23:42 PST 

Pannagadatta K Shivaswamy wrote:
> Looking at some of the mails regarding quantum computing, I was wondering
> how exactly it works.  Is there any modelling for the same?
> Is there any good source of information on the web which I can look into?

We wrote an introduction to Quantum Computing and Communication.  It 
intended to give general scientists (not computer scientists or physicists)
a feeling for how things work.  It has a some math so the reader can
get a feeling for it.  It is available at
        http://xsun.sdct.itl.nist.gov/~black/Papers/quantumCom.html

I also have a simulator written in C++ that I could send.  It is based on 
density matrices and has a very simple, command-line user interface.

-paul-
-- 
Paul E. Black (p.black at acm.org)