[Lecture Notes by Prof Yuen and possibly others 2000-2001]

Quantum Computing
-----------------

There has been quite a bit of publicity about quantum computing as the next
big thing, and the fact that you keep getting different stories about what
quantum computing is, only adds to the mystery and excitement. To me it is
another illustration of how easy it is to overdo a good thing.

As semiconductor fabrication techniques improve, we will soon be constructing
digital devices using components consisting of just a small number of atoms,
perhaps one day, of individual atoms. Theoretically, there is no reason why
we cannot switch single atoms on and off as 1/0 storage, or to control a
path to be Open or Closed. But as components get smaller, the so called
quantum effects begin to arise, based on the Uncertainty Principle, that
you cannot measure both the position and momentum of an object accurately,
nor the energy level of an object together with the duration in which energy 
stays at that level; in fact dx.dp ~ dE.dt ~ h where h is Planck's Constant,
so that if you know one value say x or E exactly, dx or dE = 0, then the
other value p or t would have infinite error, i.e., complete uncertainty.

In Simulation, we said that if we know the position and velocity of a car
at time t plus steering direction and accelerator setting, then we can
predict its position/velocity at t+dt; the uncertainty principle says this
is wrong; but for a big object like a car, the uncertainty in its position
and velocity is negligible relative to the size of the car. When you are
dealing with objects like atoms however, the uncertainty is not at all
negligible, and indeed produces quite surprising consequences: e.g., no
system can remain at 0 energy or fixed position, because that would make
the uncertainty 0. This is why atoms must have a minimum quantum energy
level that is non-zero: no particle can stay in a fixed position without
kinetic energy. 

You cannot describe the behaviour of quantum systems using concepts and
mathematical formalisms originally designed for rigid bodies, including
idealized objects like point bodies of zero size, because uncertainty makes
such concepts meaningless. Instead, you have to use wave function equations
and quantum field operators to describe them; wave/operator equations have
solutions that are some combination of eigenfunctions (something like
standing waves or resonances), with each eigenfunction associated with
some kind of discrete values like energy levels, spin, etc, known as
quantization levels; an object/system can only jump between different
quantum levels rather than change its values continuously; hence, it
gains or loses energy or other values in some multiples of a finite
amount, which is physically interpreted as absorbing or losing a number
of "particles". Our universe is permeated by one total wave function that
includes all the objects and all the possible particles, making up a
"quantum field". Quantum physics predicts such phenomena as superfluidity
and superconductivity: the amount of energy available to produce the
quantum field particles is very low at temperatures near absolute 0,
and so the atoms in a crystal lattice do not interact with passing
electrons, nor atoms in a cold liquid with each other, by exchanging
particles, or to put it another way, they are unable jump to the next
quantum level with the limited field energy supply, so that particles
travel freely around without losing energy to atoms around them which
they pass by as they travel. 

So an atom or any other quantum object cannot be permanently fixed
at a particular energy level, because that violates the uncertainty
principle; we could, by making a measurement, determine that an atom is
at level x at time t, but it could immmediately afterwards make a jump
to a higher level by absorbing some particle from its evironment or to
a lower level by emitting one; the probability of jumping to a particular
level is determined by the wave/operator equations. Hence, it is not in
any particular state, but is in some unknown state that includes all the
possible solutions of the wave equation. This is called the principle of
superposition. An atom with a spin value in a magnetic field may have
an up spin or down spin, but the principle of superposition says it is
actually in some state containing both possibilities. If up spin is 1 and
down spin is 0, then the atom represents not 0 nor 1, but a superpositioned
state containing both; if we have N such atoms side by side, then the
binary number contained in the atoms represents all 2**N possible values
rather than one particular value. 

So here we have a quantum random number generator: if we take a measurement
of the N spins, the result would be one particular combination of 1's and
0's; afterwards, the atoms may jump to the other state, until we fix their
states with a new measurement which would return, unpredictably, some other
string of 1's and 0's. Now suppose we apply a function F on this string of
N bits x, what is F(x)? We could believe:

(a) The function application works like a measurement which fixes x to one
    of the 2**N possible values; hence, F(x) is, unpredictably, one of the
    possible output values of function F;

(b) The output is a superposition of all 2**N possible values of F(x);

(c) Over time, all 2**N possible values of F(x) would be produced and we
    have an array of length 2**N.

If either (b) or (c) is true, then quantum computing opens up the possibility
of using one function application to produce 2**N results, maybe separately
usable (b), or used together as a single data structure (c). It is however
not at all clear that (b) and (c) could be done in practice, or even in theory
since they could very well violate some other laws of quantum physics. 

A particular version of this says that even if we cannot get all 2**N values,
we could use some function that produces a combination of all 2**N values to
produce a single result that would otherwise take much longer to compute,
since it depends on 2**N separate values, but this too remains to be 
demonstrated. The issue ties into an early study of "reversible" computing:
a function that preserves all the information from the input in the output
would produce a superpositioned output from a superpositioned input, and
permit the input to be reconstructed from the output. While theoretically
reversible digital circuits can be constructed, and indeed are supposed to
provide zero energy consumption, their practical construction is not assured.
Basically, you use XOR/Equal gates rather than AND/OR gates as the basic
switching circuit unit, but such a substitution, always keeping the reversible
property, would make circuits more complex. Various hardware techniques to
store superpositioned numbers and apply functions to them have also been
suggested, but with nothing that come close to the capability of current
non-quantum hardware.

High speed codebreaking has been suggested: a coding system that depended
on the difficulty of factorizing a large integer was shown to be vulnerable
to a quantum computing idea of quickly finding the periodicities of number
sets and using these to guess what the factors a given number might be.
The method requires reversible circuits to compute Fourier transforms
(which is an information preserving operation, basically multiplication
by a matrix of complex numbers which are all roots of -1.) In the mean time,
however, mathematicians have improved their factorization techniques to
break the prime-factor based coding system, though they require large 
parallel machines to carry out.

A reverse application of quantum ideas is to achieve secure communication:
if particles with certain quantum values are sent over a transmission line,
and a evesdropper tries to read these values, the measurement disturbs the
quantum levels and could be detected on the receive side. This however assumes
that your enemy wants to read your messages, but perhaps he just wants to
disturb your communication deliberately by his reading it. Yet another is to
use some laws of conservation that impose mathematical relations between
quantum values at one point with those at another point: measurements here
tell us what measurements can be expected over there.

Instead of being a defect that makes the state of digital devices uncertain,
quantum effects could very well produce new benefits, but at this moment it
is hard to know whether the benefits would actually occur and what the cost
of producing such quantum effects would be. Predicting wonderful new devices
based on the ideas is at present premature and overoptimistic.
   
----------------------------------------------------------------------------
from NY Times   August 27, 2001

I.B.M. Creates a Tiny Circuit Out of Carbon
By KENNETH CHANG
   In another step toward post-silicon computers, I.B.M. (news/quote)
   scientists have built a computer circuit out of a single strand of
   carbon.
   
   The I.B.M. circuit performs only a single, simple operation --
   flipping a "true" to "false" and vice versa -- but it marks the first
   time that a device made of carbon strands known as nanotubes has been
   able to carry out any sort of logic. It is also the first logic
   circuit made of a single molecule.
   
   At least another year or two of research is needed before I.B.M. can
   even evaluate whether a practical computer chip can be manufactured
   from nanotubes, said Dr. Phaedon Avouris, manager of nanoscale science
   at IBM Research and the lead scientist on the project.
   
   But the fact that the researchers were able to build the circuit
   raises hopes that nanotubes could eventually be used for computer
   processors that pack up to 10,000 times more transistors in the same
   amount of space.
   
   Dr. Avouris declined to speculate when a chip with nanotube circuitry
   might appear commercially, but he described nanotubes as "the best
   candidate from what we've seen" in the emerging field of molecular
   electronics.
   
   "This is yet another test that nanotubes have passed," Dr. Avouris
   said. "The physics works."
   
   The processing power of computer chips has consistently doubled every
   year or two as the size of transistors continues to shrink. But
   current chip-making technology, which etches circuits into silicon, is
   expected to run up against fundamental physics limits in 10 to 15
   years.
   
   A nanotube, which resembles a rolled-up tube of chicken wire, is about
   one hundred- thousandth the thickness of a human hair. Its thinness,
   only about 10 atoms wide, makes it a promising candidate for circuits
   in future faster and smaller computer chips. It takes its name from
   nanometer, a unit of measurement one-billionth of a meter long, which
   is a convenient length for specifying molecular dimensions.
   
   Dr. Charles M. Lieber, a professor of chemistry at Harvard and an
   expert in the field of nanotechnology, called the I.B.M. achievement
   "quite significant." The effort to incorporate nanotubes in computer
   chips is a "great strategy and one that could be implemented
   relatively quickly," he said.
   
   The I.B.M. researchers presented their findings yesterday at a meeting
   of the American Chemical Society in Chicago. An article describing the
   results will appear in the September issue of the journal Nano
   Letters.
   
   Nanotubes are not the only approach to building ultratiny circuits.
   Other researchers, like those at Hewlett-Packard (news/quote), have
   designed custom molecules that act as on- off switches. However,
   unlike transistors, the switches do not amplify electric signals, and
   a computer made of molecular switches would have to employ a different
   method for performing calculations, one that scientists are still
   working to devise.
   
   "They don't even have a transistor," Dr. Avouris said. "In that sense,
   we're way ahead in the game. You don't have to worry about finding a
   different architecture. You use what exists now."
   
   In April, the same researchers at I.B.M.'s T. J. Watson Research
   Center in Yorktown Heights, N.Y., reported that they had constructed
   vast arrays of transistors made out of carbon nanotubes, but the
   arrays were not wired up to perform any calculations.
   
   In the latest research, the scientists succeeded in hooking up two of
   these transistors to perform the true-false flipping operation. Even
   more remarkably, the two transistors exist along sections of the same
   nanotube.
   
   This function -- a "not" operator -- is one of three fundamental logic
   operations that underlie all computer calculations. (The other two
   operations are "and" and "or"; the "and" operator compares whether two
   statements are both true; the "or" operator determines if at least one
   statement is true.)
   
   In the binary language of 1's and 0's used by computers, a "not"
   operator converts a "0" (the equivalent of "false") into a "1"
   ("true"). It also works the other way, changing a "1" into a "0."
   Computer calculations are all reduced to combinations of "and," "or"
   and "not" operators.
   
   To build the circuit, the researchers draped a single nanotube on a
   silicon wafer over three parallel gold electrodes, added a layer of
   polymer between two of the electrodes and then sprinkled some
   potassium atoms on top.
   
   All of the carbon nanotube transistors built previously were
   positive-type transistors, meaning that they carried current via empty
   spaces, or "holes," in the sea of electrons that act like positive
   charges. The sprinkled potassium atoms added enough electrons to the
   nanotube that its behavior changed to that of a negative-type
   transistor, where current is carried by electrons.
   
   The piece of nanotube sprinkled with potassium atoms acted like a
   negative-type transistor; the section protected under the polymer
   layer remained a positive-type transistor. The combination of the two
   transistors formed a "not" operator, flipping an incoming voltage
   signal to an opposite output signal.
   
   The ability to change positive-type transistors to negative-type is "a
   very neat trick" said Dr. Uzi Landman, a professor of physics at the
   Georgia Institute of Technology. "As a demonstration, it is an
   important step."
   
   The logic circuit is about one-15,000th an inch wide -- larger than
   the equivalent silicon structure -- but Dr. Avouris said that it could
   eventually be shrunk so that 10,000 nanotube transistors fit in the
   space taken up by one current-day silicon transistor. "In principle,
   it can be small," he said. "It's a matter of just making the
   connections."
   
   The I.B.M. researchers are now trying to build the more complicated
   "and" and "or" operators and tie them together into more complex
   circuits.