A VERY thoughtful set of thoughts on the article. 'A Shortcut Through Time': Quantum Weirdness

[Dave Farber <dave () farber net>]

------ Forwarded Message
From: Rod Van Meter <rdv () adsl-63-199-185-122 dsl snfc21 pacbell net>
Reply-To: rdv () halfmoonbaylabs org
Date: Sun, 06 Apr 2003 16:17:26 -0700
To: dave () farber net
Subject: Re: [IP] 'A Shortcut Through Time': Quantum Weirdness

Hi Dave,

As you know, I'm about to give up my current career and go be an
ascetic, er, grad student, studying quantum computing (at Keio
University in Japan).  So, some thoughts for IP, if you wish, on the
article by Jim Holt you recently sent out.  Keep in mind that I'm
still a neophyte in this area.

Mr. Holt implies that quantum computing (QC) is a "one trick pony" --
Shor's algorithm for factoring large primes.  One thing that has
become clear over the last decade is how extraordinary an intellectual
achievement that algorithm is, as evidenced by the still-slim number
of equally useful results.  However, there are a handful of
interesting algorithms, some interesting recent implementation
results, and some other, surprising areas in which QC is making
contributions.

Personally, I think that within twenty years, we will be teaching our
students QC as an adjunct to classical computer science, much like
relativity extends Newtonian mechanics.

Most of your readers are probably at least passingly familiar with the
"P = NP?" question and notions of computational complexity.  Shor's
algorithm reduces the resources (not just time; Shor actually trades a
large number of gates for execution time) for factoring a large number
from exponential in the number of bits to polynomial (from O(e^L) to
O(L^3) for an L-bit number), for an exponential speedup.

Shor's algorithm uses the quantum Fourier transform in order-finding,
period-finding, and hidden subgroup problems, via a technique known as
phase estimation; factoring is a specific instance of order-finding.

Mr. Holt says that NP-complete problems such as the travelling
salesman problem cannot be usefully attacked using quantum computing.
This is not true.  Grover's algorithm can reduce an NP-complete search
space with N possible total paths to sqrt(N) iterations.

Shor's algorithm apparently ignited much of the current interest in
QC, but the Deutsch-Jozsa algorithm predates it.  It allows you to
determine if a function f(x) is constant for all x, or balanced (0
half the time, 1 half the time).  This can be used to determine, for
example, if all of the values in a superposition are members of the
same set.

All of these algorithms give you a probabilistic answer; the quality
of that answer can be made arbitrarily good via repeated application
of the algorithm or other techniques.

QC is likely to tell us something about computational complexity in
general.  It may even open up new avenues for attack on the "P = NP?"
problem itself.  We don't actually even know yet if a quantum computer
is strictly more powerful than a classical one!

Almost all of the research on QC algorithms to date has involved
circuits for calculating specific results.  More general machines are
clearly needed.  Research into Quantum Turing Machines is really just
beginning.

QC, in layman's terms, also includes quantum information theory and
quantum communications.

Quantum information theory provides us with quantum error correcting
codes and the remarkable result of superdense coding, which allows us
to send two classical bits for each qubit.

Quantum communications includes quantum key distribution (QKD), which
is generating a lot of excitement.  There is at least one startup
company attempting to sell equipment to do exactly this.  Personally,
I'm a little skeptical; it seems to me that our biggest problem is not
actually key distribution but the transitive trust model necessary for
authentication, and QKD doesn't help there.

In a recent issue (21mar2003) of _Science_, a qubit (quantum bit)
constructed of three mesoscopic Josephson junctions was described by
Chiorescu.  This gives a lot of hope for solid-state quantum computing
devices.

Finally, studying QC is bringing some unexpected results in physics.
Quantum teleportation may be the most famous one; with a
previously-shared entangled pair of qubits, and a classical
communication channel, you can teleport a quantum state from here to
there.  It's not clear to me yet what this useful for, but it's very
cool.

QC also offers an interesting solution to Maxwell's demon's violation
of the second law of thermodynamics (answer: if you account for the
entropy in the measurements and information about the system state,
looks like things balance -- no violation), and is contributing to, of
all things, black hole research!  Physicists now routinely consider
issues around the loss of "information" when things disappear into
black holes.

So, my personal bet is on mobile/ubiquitous computing as the topic
that will have the largest societal impact in this decade, and
robotics the next.  But, the most exciting intellectual challenge in
computer science today seems to me to be quantum computing.  It will
revolutionize both the science and the art of computing within the
next twenty years or so.  I also don't believe it's too early for
computer scientists to be involved; in my twenty years in this
business, hardware capabilities have always outstripped our ability to
fully utilize them.  We shouldn't wait for the hardware to be
practical, we should be driving it!

I haven't yet read _A Shortcut Through Time_, but some references:

"Rules for a Complex Quantum World," by Michael A. Nielsen,
_Scientific American_ special edition, _The Edge of Physics_,
Jan. 2003.  Good, quick introduction.

_Quantum Computation and Quantum Information_, Michael A. Nielsen and
Isaac L. Chuang, Cambridge University Press, 2000.  This is my
constant companion.  Almost 700 pages, suitable for a grad-level
course.  Includes introductory/review material (_almost_ enough,
though you'll probably want those old college texts on hand) on the
notation, quantum mechanics, linear algebra (which you'll need LOTS
of), reversible computing, and computational complexity, as well as
the material on QC.  Mentions almost nothing about quantum Turing
machines; I'll have to get that elsewhere.  Endorsed by other QC
professionals, too.

I would avoid _The Feynman Processor_ (which I essentially read
standing in Powell's bookstore), and almost any explanation which
invokes optical polarization to explain quantum mechanics, which I
find misleading.  Hirvensalo and Pittenger I both found too dense
initially.

        --Rod


------ End of Forwarded Message

-------------------------------------
You are subscribed as interesting-people () lists elistx com
To manage your subscription, go to
  http://v2.listbox.com/member/?listname=ip

Archives at: http://www.interesting-people.org/archives/interesting-people/