DNA Computers and Quantum Computers
A poll of computer scientists showed that the vast majority believe that no
polynomial-time algorithm will be found—but the majority of experts
has been wrong many times in the past. Even if they are right, there are
some viable alternatives that are being explored.
All the algorithms that we have investigated in this section have been im-
plemented sequentially—for instance, when exploring all the possible routes
in the traveling salesman problem, we envision a computer that examines
the N! routes one at a time. Another way of handling the problem is to break
up the problem into smaller, more manageable chunks, and hand each
chunk to a different computer. This is known as parallel computing, and it
holds the possibility of greatly speeding up computation. There are several
ways to accomplish this outside the realm of using standard computers.
The first of these is DNA computing, which was first achieved by Leon-
ard Adleman of the University of Southern California in 1994 (it’s not just
a football factory). The idea is to use the ability of strands of DNA to select
from a multitude of possible strands the one strand that complements it.
Since a quart of liquid contains in the neighborhood of 10^24 molecules,
there is the possibility of greatly speeding up computation—although it’s
not a viable possibility for very large problems.
A potentially more powerful technique is quantum computing, which
uses the uniquely quantum phenomenon of superposition to perform
massively parallel operations. In a classical computer, which uses 1s and
0s, a 3-bit register always records a definite 3-digit binary integer, such as
110 ( 4 2 6 as a decimal integer). However, a 3-qubit (a qubit is a quan-
tum bit) register exists in a superposition of all eight 3-digit binary inte-
gers, from 000 (decimal integer 0) to 111 (decimal integer 7). Consequently,
an N-qubit register exists in a superposition of 2N states; under the right
circumstances, the wave collapse can realize any one of these 2N possibili-
ties. Since qubits can be very small indeed (possibly even subatomic), a
1 00-qubit register can encompass 2^100 different states (approximately 10^30 ),
and 100 subatomic particles do not take up a whole lot of space.
While the possibilities for quantum computers are extremely exciting,
there are major problems to overcome. One of these is the decoherence
problem—the environment tends to react with quantum computers and
initiate wave collapse. One would want wave collapse to reveal the answer,
rather than having wave collapse occur as the result of random environ-
mental interactions, and so the computer must be kept isolated from the
environment for significantly longer periods of time than have presently
been achieved.
Murphy’s Law 167