[FOM] QM computing links
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
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
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
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