Quantum Computers

John K Clark (johnkc@well.com)
Thu, 30 Jan 1997 09:52:47 -0800 (PST)


I sent my post on Quantum Computers to comp.ai.philosophy, this is what
Hans Moravec (Mind Children,) has to say on the subject. Moravec by the
way is a fan of Uploading.

John K Clark johnkc@well.com
Date: Thu, 30 Jan 1997 04:54:51 -0500
From: Hans Moravec <hpm@cmu.edu>
Organization: Carnegie Mellon Robotics
Newsgroups: comp.ai.philosophy
Cc: hpm@cs.cmu.edu, johnkc@well.com, David@longley.demon.co.uk
Subject: Re: Quantum Computers

John K Clark writes:
> For me It's still hard for me for it to sink in that an
> otherworldly object like a Quantum computer could actually
> exist in our worldly universe, but it's beginning to look
> like one can really be built. If so the world will
> never be the same.

David Longley asks:
> Why? Wouldn't this "just" suggest that computers and
> storage devices could be made smaller (and thus faster)
> and even more cost effectively? Is there any reason to
> expect anything other than that?

No, this is not quantum-scale integrated circuitry, but
something exponentially wilder:

Quantum mechanics describes unobserved systems as existing
in a "superposition" of all possible states, each weighted
by an amplitude and a phase. A particle whose position
is known has unknown momentum. Its future path is then described
by a wavefront of all possible directions it could go.
This wavefront is very real, as can be demonstrated by
putting a barrier with two slits in its path. After doing
the experiment repeatedly, a banded pattern of hits builds
up on a screen beyond the barrier, that can be explained as
the interference between the two possible paths each particle
could have taken to its hit on the screen. Each path has
a phase and an amplitude, and for some screen positions the
phases are opposite, causing the two possibilities to
partially or completely cancel. Other places, in phase, they
mutually reinforce.

Quantum computing creates n "qbits", each in an independent
unobserved state of superposition of 1 and 0. Together,
they constitute a machine with all 2^n possible combinations
of states superimposed. By manipulating things like external
fields, this giant superposition is then stepped through a
sequence of computations, without being observed, producing
a superposition of 2^n answers. When the superposition is
finally observed to get an answer, the 2^n possibilities
interfere, cancelling some outcomes, making others more
probable. By cleverly designing the computation, the
interference can be tailored to filter a desired result.

Quantum computing became really exciting about two years
ago when Peter Shor showed how a quantum computer with a
few times n qbits could be used to factor n bit numbers in
little more than linear time. On a classical computer,
which can be in only one state at a time, factoring seems
to take time exponential in the size of the number.

In some limited circumstances, quantum computing gives
the effect of a parallel computer with 2^n processors, in
a single machine with n quantum bits. If it were possible
to push n to hundreds of qbits, a quantum computer could
complete computations beyond a classical atomic-scale
computer filling the universe.

The catch may be that things like the noise-to-signal ratio
of the final measurement, or the difficulty of maintaining
the coherence of the qbits (i.e. of isolating them from any
possible observation via interaction with the outside world)
goes up exponentially with the number of qbits.
But these limitations may be just properties of
particular implementations. As the Science article
showed, the fun has just begun, and dramatically better
approaches are still being created and developed. One of
the first approaches, using the spin states of individual
laser-trapped atoms to represent qbits, lost its coherence
on the time scale of milliseconds. The magnetic-resonance
approach described in Science, which uses the spin of atomic
nuclei, shielded from the world by their fuzzy balls of
orbiting electrons, can maintain coherence for an hour!

-- Hans Moravec CMU Robotics

Version: 2.6.i