FUTURE HISTORY:
QUANTUM AND DNA COMPUTING
Lecture Notes
Prof. Cassidy
chmdcc@hofstra.edu Websites
CCenter for Quantum Computation,
Oxford University: http://www.qubit.com CHow Stuff Works (Will Work) web
sites: www.howstuffworks.com/quantum-computer.htm www.howstuffworks.com/dna-computer.htm Introduction Computers are information processing devices. Today the information is encoded digitally, in the digits 0,
1 Processing is done by a “processor” consisting of logic
circuits or “gates” that take the input, perform a series of tasks in linear
sequence, then give the result in a series of 0s and 1s. 0,1 digits may be on/off states of transistors that allow
flow of charge. Flow = 1, no flow=0. But this technology is reaching its limit in size and
processing ability. Transistors, 1947, >50 years ago; silicon microprocessors,
1971, >30 years ago. Moore’s law–doubling of transistors on microchip every 18
months. Already at nanoscale, as discussed previously. (1 billionth of meter) ca 2010-2020, will reach limit at the level of individual
atoms and molecules. QM will come into play, voiding the “classical” computer
just described. Thus, new technologies will be needed. Possibilities include: 1. Quantum computers.
Take advantage of the strange, “nonclassical” world of objects at the
atomic level, which obey quantum mechanics. 2. Use enormous
information storage and processing power in the tiny natural supercomputers
that exist w/in each cell of every living organism–DNA Both would be capable of storing billions of times more
information than any computer today. Both would also be much faster than today’s computers,
because able to perform many operations simultaneously–parallel computing. –classical single-processor computer
can perform only 1 operation at a time–linear. BUT–both of these new possibilities are still in the
theoretical stage. The ideas are less than a decade old, and technology is not
yet advanced enough to produce a practical computer in either case. In fact,
they may not be practical at all. But rapid progress is being made so far. In theory at least,
they will be ideally suited for certain types of computational tasks. Quantum Computers QM–founded in 1920s and behavior explored in >=1930s. Ca
only 70 years ago. Qubits QM has a lot of strange features not seen in our everyday,
classical world. Seen only in submicroscopic atomic world. One of these already noted in discussion of transistor–electrons
orbiting in atoms can take orbit only in certain energy states–quantized. If send in a photon, electron jumps to next state, if carries
enough energy. Can assign 0, 1 bits to
ground, excited states. But what happens when send in only fraction of energy
needed? In QM, It has a probability to jump to next state
anyway. So electron is probably in 0 state, but also has probability of being
in 1, or even somewhere in between. [coins example] Another example: nucleus of spin ˝. If put it in Mag field (like MRI), QM
requires that it is in up or down position. Up can be 1, down 0. But where is it if there is no mag field? QM allows it to be up or down, or anywhere in
any of the Infinite states in between.
This is called a “superposition.” Until we “look” at it by turning on the mag field. Then it
must be up or down. If the spinning nucleus represents a bit, then when we are
not interfering with it by turning on fields, it can have not just 2 values but
an infinite number of values. Such a bit is called a “quantum bit” or a “qubit.” It can store infinite amount of classical information,
depending upon its orientation. But unfortunately we cannot recover this information
directly, because if we try to measure the angle we have to disturb the system
from the outside, by turning on a mag field or sending in a photon. When that happens, the qubit is jolted into our classical
world and becomes a classical bit, up/down, 1,0. To encompass this situation, we can think of a qubit as one
unit of quantum information, containing an infinite amount of hidden classical
information. This one unit then becomes the basis for a quantum computer. Entangled states Strangest property of QM is that 2 or more quantum particles
can become entangled with each other in such a way that the individual members
do not have individual states. The group as a whole acts as a single state, and
the individual particles correlate their behavior according to quantum rules. Particles can be entangled when they collide, or when put
into same energy system, e.g. nuclei in
a molecule, photons colliding, or ions in EM trap. One quantum rule is that no 2 particles in the same energy
state can have the exact same quantum properties. Eg, if one nucleus is spin
up, the other must be spin down. Another weird thing about this is that distance and time have
no effect. Can be miles away from each other. If 2 nuclei are entangled, and we
measure one to be spin up, then the other instantly becomes spin down. As if the entanglement exists outside our
normal space and time in some other “dimension.” Use–transmitting information over large distances without
possibility of eavesdropping, eg. In communications or cryptography (transmit a
key). More below. Computer use of entanglement Consider 2 entangled qubits.
Can represent 4 numbers: 0--00, 1--01, 2--10, 3--11 and all numbers in
between. Classical bits–only one number can be present at any given
instant. Quantum bits–all 4 numbers are present all the time. Can then perform different operations on these particles,
then measure the state of one of them. Once you know the state of one of them, it immediately
provides information about the other, without measuring it. The amount of information increases rapidly with the number
of entangled particles, 3 gives 8 numbers, 4 gives 16 etc Advantage: a processor can perform different calculations on
each of the particles or groups of particles simultaneously and obtain all of
the results together. Quantum parallelism, unlike classical, sequential computers. History 1981–Richard Feynman at Caltech suggested that parallelism
could be used to make a quantum supercomputer. And that only a quantum would be
able to calculate quantum properties. 1985–David Deutsch, Oxford–published a paper on quantum
parallelism showing that Q computer can perform 2 different operations
exploring 2 different routes to solve one problem simultaneously. So twice as
fast, but it would be right only ˝ the time. –not clear then that any advantage to Q computer. Certainly
not for word processing, email etc. 1994–breakthrough. Peter Shor, computer scientist at
Bell Labs, proved that a Q computer, if one could be built, could easily solve
a math problem beyond the reach of normal computers. Problem had to do with cryptography. Cryptography today based on factoring large numbers by large
prime numbers. The 2 factors are the “keys” that allow access. EG, the number 24,288 has easily found factors of 2, 3, 11,
23–all prime. But 24,287 is factored only by the prime numbers 149 x
163. Hard to find Today, 250 and 500 digit numbers are used. Normal computers
would take thousands of years to factor them into primes. Shor–presented an algorithm (steps) by which a quantum
computer could exploit quantum parallelism and factor a 500-digit number in
seconds. Implications were stunning–all current cryptography would be
rendered obsolete. But new quantum crypt would be uncrackable. This would have major consequences for military codes,
e-commerce, telecommunications, etc Shor’s work became the driving motivation for building Q
computer ever since. The result was massive infusion of defense funds in US and
elsewhere. Main obstacle to Q Computer Coherence of entangled particles is essential. But easily destroyed by interaction
with outside environment. This is why we don’t see these effects in the
everyday world. Particle must be isolated at very low temperature. Attempts
to combat this (quantum error correction etc) have had only little success so
far. But progress is continuing, mainly in the theoretical area,
but also in the experimental phase. Progress so far (less than a decade of work, but large amounts of funding) 1998–Los Alamos and MIT researchers Spread a single qubit over 3 nuclear spins in a molecule,
instead of just 1. The spread made it harder to corrupt the entanglement and
easier to extract the quantum information. March 2000–Los Alamos researchers created a 7-qubit computer
in a single drop of supercooled liquid. Used NMR to encode classical
information (0, 1) onto the bits, then were able to manipulate them in various
processes. August 2000–IBM labs. Researchers entangled 5 flourine nuclei
into a 5-qubit entanglement. They then encoded them with classical information using RF
pulses, performed math operation on them, and read the result using NMR. They solved in 1 step a simple math problem related to
factoring in cryptography which would take a normal computer many steps. DNA COMPUTING Probably more practical in short term. DNA is more stable and predictable in
chemical reactions. That’s why it works
so well in genetics. Also has potential to perform certain types of calculations
many times faster because of parallel computing. Also promises much smaller and cheaper computers. Amazingly there are about 6 feet of DNA wrapped up into the
tiny nucleus of every cell of every living organism. Put another way, 1 ml (1 cm3) of DNA contains 10 trillion DNA
molecules each holding 10 terabytes of data. Theoretically they could perform
10 trillion simultaneous calculations. Again, work on DNA computing less than a decade old. 1994–Leonard Adleman, a computer scientists at USC, read
about the Watson-Crick double-helix model of DNA from Watson’s textbook. He
then showed in article in Science how
DNA computer could work. DNA is basis of the genetic code of every living thing. DNA
molecules make up the genes. So enormous amount of information in each cell. Adleman realized that DNA stores this infomation similarly to
info on a computer hard drive. DNA uses just 4 bits: A, T, C, G bases (Fig 1) Every A goes only with T, G only with C. No other pairings possible. So eg, if bases are AGGTTAC the match must be TCCAATG Like Shor, Adleman showed how this scheme could be used to
create an algorithm to easily solve a complicated problem that would take a
normal computer many steps. The problem was “traveling salesman problem” or “directed
Hamilton path problem” (see Website) Eg: 7 cities. Get from
start to end cities while touching each city once and only once. 1. Represent each city by ATCG combinations 2. Mix open strips of DNA pieces containing the city
combinations in a test tube. 3. Chains of DNA represent possible answers. 4. Pick only those that have the right start and end cities
and only 7 components. 5. Eliminate all wrong ones by chemical reactions. 6. The remaining strands will be the solutions. Thus, can solve the problem essentially in 1 step, step 3,
during mixing process. But, requires human assistance to prepare and analyze the
mixture; and several days to extract the correct results through chemical
reactions. Research today is to find a faster method independently of
human assistance. Meanwhile– 1997–U. Rochester researchers developed the first DNA logic
gates for performing various processes. The DNA gate detects fragments of genetic material as input,
then splices them together in such a way to get the desired output. Example: Creating
an AND gate One variation of an AND gate made of DNA would be the
following: [A A] represents a strip of DNA with two A
bases A bases
combine only with T bases G bases
combine only with C bases Use the DNA strip [T
C] to serve as selector for the AND
gate Since T and C will combine with A and G, then [A A] will represent 1 at the A input [G G] will represent 1 at the B input [T T] and [C
C] will represent 0 at the inputs, since they don’t combine with T or C Truth Table A B X [T
T] = 0 [C
C] = 0 0 [T
T] = 0 [G
G] = 1 0 [A
A] = 1 [C
C] = 0 0 [A
A] = 1 [G
G] = 1 [T C] =
1 [A
A][G G] Gates like the AND gate might be combined together into a
type of DNA microchip–a “biochip” Such a chip might be used to speed up a conventional
computer. Advantages of a biochip 1. Beats Moore’s law-- More processing power in same or even
smaller space. 2. There is obviously a large supply of cheap DNA. (Potential disadvantage in ethical question about using
genetic material, but does not seem to be a problem at this point)
CSC 5
