[FOM] QM computing links

vznuri@earthlink.net vznuri at earthlink.net
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."


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


scientific american on "spintronics" (QM computing electronics)


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


when will qm computing become a reality?


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



up to 80 qubits by ertmer & birkl


june 1998 sci am article by gershenfield and chuang


previous record by knill/laflamme at los alamos


qm computers will be hard to build


QM computation, university of oxford


NIST, US qm computing laboratory center


will QM computation have its own moore's law?


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


introduction to QM computing for nonphysicists, by rieffel and polak


Quantum Physics and Computers By: Adriano Barenco


machines, logic & quantum physics, 1999

by david deutsch, artur ekert, rossella lupacchini


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


the square root of not, by brian hayes, 1995


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. 

           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

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

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 E. Black (p.black at acm.org)

More information about the FOM mailing list