In October 1998 I described the DNA computer, which uses the techniques of molecular biology to manipulate strands of specially prepared DNA and solve difficult mathematical problems. "The DNA computer provides enormous parallelism... in one fiftieth of a teaspoon of solution approximately 10 to the power 14 DNA 'flight numbers' were simultaneously concatenated in about one second".
There is another line of research that also has the potential for enormous parallelism (possibly conducting billions of calculations simultaneously) and that is the Quantum-Mechanical Computer. The field of research is known as Quantum Computing. Whereas DNA computers operate with molecules quantum-mechanical computers operate with fundamental atomic particles such as atoms, electrons and photons.
Quantum mechanics describes the interactions between such
particles and these interactions are very strange. One of the
founders of quantum mechanics, Neil Bohrs said "Anyone who can
contemplate quantum mechanics without getting dizzy hasn't
properly understood it.". Thankfully, for the purpose of
understanding the basic operation of a quantum computer, we do
not need to "understand" quantum mechanics - just two key
points:
Conventional computers work with logic gates. For example, the AND gate takes two inputs and the output is 1 if both inputs are 1, otherwise the output is 0. Any arithmetic task can be achieved using a combination of these logic gates. It turns out that quantum particles can be manipulated in ways that achieve the same logic and this is how scientists are building the first quantum-mechanical computers. The task of making a useful device is going to be very difficult but some simple demonstration devices have already been made.
Why bother working with such tiny objects? It is the second property of quantum particles that is so alluring. Provided that we don't try to take a peek during the computations, the nature of a quantum-mechanical computer is such that it will calculate the results for all possible combinations of input - remember this is done in parallel using just one sequence of interactions between particles. Thus the uncertainty about the state of individual particles is the strength of the quantum-mechanical computer. Since the state of a particle represents a "bit" of information, the uncertainty about its state also applies to the unit of information, which is called a "qubit" in quantum computing. A qubit is a bit of information that is in a twilight world of (generally) two states.
We can think of qubits working their way through the quantum-mechanical computer and at the end of the calculation all possible "answers" are available. The last step is to convert qubits back to bits so they make sense - this might involve observing photons emitted by atoms to determine the state of these atoms. Note that if this was attempted part-way through the calculation the qubits would be destroyed and the calculation disrupted.
Seth Lloyd has likened the quantum-mechanical computer to a symphony orchestra. Energy states of atoms can be thought of as waves, much like the sound waves. An atom in a single state is like a single note (tone) from a single instrument. A superposition of states of one atom is like a musical chord. The quantum computation is like the sound from a whole orchestra. Taking this analogy further, if you wanted to know what note a particular instrument was playing you would need to isolate it in a sound-proof room in order to take an accurate measurement - in doing so you would ruin the symphony. In the same way measuring the state of a particle during a quantum computation will ruin the computation.
Several classes of "intractable" computing problems could be
addressed by quantum computing. One is the task of finding the
factors of a large number - important for computer security
because factors are used for encryption systems. In brief, a
binary number consisting of 50 digits has 250
combinations (2 to the power of 50, or about
10,000,000,000,000,000,000,000,000 !) and a conventional
computer would need to work through all of the possible
combinations - the most powerful conventional computer
available (perhaps physically possible!) would take over a
million years to do this. In theory, a quantum computer could
achieve the same result with just a few hundred qubits
(hydrogen atoms!). A similar efficiency could apply to finding
an item in a randomly sorted database. And how about debugging
software - every possible pathway tested in one go!
Page created in 1999 when URLs were limited to 8 digit
filenames!