Quantum Computers:
What are They and What Do They Mean to Us?
Ever since 1980 when quantum theory was applied to the classical Turing machine, the development of a quantum computer was pondered. Not only can these kinds of computers run 1,000,000,000 times faster than current silicon based computers, but they can theoretically run with no energy consumption. These computers will obsolete the silicon chip much as the transistor did the vacuum tube. Consequently, silicon chip and computer manufacturers, the U.S. government, and Japan are allocating huge funds for quantum computer research. An overview of the NMR-type quantum computer prototype produced at MIT last summer (1998) is discussed at the end of this paper.
The paper discusses an overview of the quantum computing world, and what it means to the computing industry. It discusses the inevitability of quantum computers, how they originated, and what is different about them from classical computers, using the principles of superposition, entanglement, and quantum teleportation as examples. This paper is intended to be accessible to the general reader, so it will explain the basics of a few quantum computer features at the risk of over-simplification, and the paradoxical effects quantum theory produces in a practical world.
This author has not built nor operated a quantum computer, so he relies heavily on the scientific literature, and the only book so far published on the topic, "Explorations in Quantum Computing", by Colin Williams and Scott Clearwater (see bibliography at bottom).
As our technology rushes forward, several factors work together to push us toward the quantum computing world, and push out the classical silicon-based chips. These factors are: scaling in size, energy consumption, economics of building leading edge computers, and new applications that are available with quantum computers that cannot be executed with classical computers. At the current rate of chip miniaturization, energy efficiency, and economics, the classical computer of the year 2020 (if it could happen at all), would contain a CPU running at 40 GHz (or 40,000 MHz), with 160 Gb (160,000 MB) RAM, and run on 40 watts of power.
Our computing world is surrounded by breath-taking innovations, and many of them involve more powerful and smaller chips. Chip capacity has doubled every 18 months, according to Moore’s Law, but the chip size remains constant. The number of transistors on a single chip is rising exponentially also. Keyes extrapolates that if miniaturization continues at the current rate, a bit will be represented by a single atom by the year 2020. This trend inevitably leads us into the micoworld of quantum effects, where classical rules no longer apply.
The speed of chips is also rising exponentially. Faster, more densely-packed, and closer transistors cause thermodynamic problems. Advances in energy efficiency are required to keep the chips from melting during use. Fortunately, energy efficiencies are increasing, and the thermodynamic problems are being resolved. These energy advances are also pushing the physics of chips into the quantum realm.
Quantum computers are reversible, therefore there is theoretically no net energy consumption. Quantum reversibility means that quantum computers drive themselves forward in infinitesimal (reversible) steps, much the same way that molecules of perfume would diffuse from a perfume bottle. Quantum computer programs are not "run", but are said to "evolve," as they process the program’s inputs to outputs. Incidentally, reversibility also means that the inputs of a quantum computer can be implied from the outputs; the program can be run backwards to get the inputs.)
The argument for energy inevitability is a "carrot-and-stick" argument: the energy inefficiencies drive us away from classical computers, and the appeal for energy-free (or at least, much reduced energy consumption) computing drives us toward quantum computers.
Besides the energy factors at the micro level of computing, there are large-scale economic factors pushing us to a more energy-efficient means of computing: 5% of the entire national power production is consumed by computing machinery. With "fossil fuels continuing to dwindle, fission power in disfavor with the public, and fusion power still many decades away, the drain computers impose on our power supply could become significant."
The cost to build a semiconductor plant doubles every three years. By extrapolating that trend to the year 2020, a semiconductor plant will cost $1 trillion to build, which is 5% of the U.S. GNP. Based on Motorola’s sales figures, a similar company would need $10 trillion in annual sales to support that kind of construction.
Japan, in its bid for software and hardware global dominance, has allocated huge funds for quantum computer research. ***, VP of Hewlett-Packard, reported that 70% of all quantum computer research is being done by the Japanese. They have included quantum computers as an integrated step of their global acquisition strategy.
The speed of quantum computers also jeopardizes the encryption schemes that rely on impracticably-long times to decrypt by brute force methods. Encryption schemes that may take millions of years to guess and check are now vulnerable to quantum computers that may reach a solution within one year. Many governments, included ours, use such encryption schemes for national security. They are very interested in any technology that puts that at risk. As a result, the Office of Naval Research, the CIA, and DARPA, are sinking huge funds into quantum computer research. DARPA is funding $5 million for a Quantum Information and Computing Institute, and the CIA is funding an unknown amount for factoring of large integers, a fundamental part of encryption technology.
It is possible to transmit information without a signal path by using a newly-discovered quantum principles, quantum teleportation. There is no way to intercept the path and extract information. Ultra-secure communication is also possible by super-dense information coding, which is a new technology in its own right. Quantum bits can be used to allow more information to be communicated per bit than the same number of classical bits.
Through similar processes that support ultra-secure and super-dense communications, the existing bit streams can be made more robust and secure by improvements in error correction and detection. Recovering informational from a noisy transmission path will also be a lucrative and useful practice.
Richard Feynman showed in 1982 that classical computers cannot simulate quantum effects without slowing down exponentially; a quantum computer can simulate physical processes of quantum effects in real time. Molecular simulations of chemical interactions will allow chemists and pharmacists to learn more about how their products interaction with each other, and with biological processes such as how a drug may interact with a person’s metabolism or disease. Pharmaceutical research offers a big market to such applications.
Classical computers do not have the ability to generate true random numbers. The random number generators on today’s computers are pseudo-random generators—there is always a cycle or a trend, however subtle. Pseudo-random generators cannot simulate natural random processes accurately for some applications, and can not reproduce certain random effects. Quantum computers can generate true randomness, thus give more veracity to programs that need true randomness in their processing. Randomness plays a significant part of applications with a heavy reliance on statistical approaches, for simulations, for code making, randomized algorithms for problems solving, and for stock market predictions, to name a few.
With the global forces of computer competition, encryption technology for national security, new applications, and the thermodynamics of computer systems changing as they are, there is a rush toward the new quantum technology to produce the first viable quantum computer. The world is moving toward a place that no classical computer has gone before, nor can go.
Quantum theory is not new. It started with Max Planck’s discovery of the energy quantum (Nobel prize in 1918), and Einstein’s discovery of the photon (Nobel prize in 1921). We might trace the invention of the modern computer back to 1956, when Bardeen, Brattain, and Shockley won the Nobel prize for the invention of the transistor. The idea of a quantum computer originated in 1980 when P. Benioff thought about the now-classic Turing machine (developed in 1935 by Alan Turing) in terms of quantum states. Whereas the convention Turing machine computes by punching holes in a linear strip of paper, the Benioff’s Quantum Turing Machine (QTM) has strips of paper with multiple paths, each one with a probability of traversal. The QTM has exponentially many paths, not all equally probably, but all possible.
Two years later, Richard Feynman showed that because of these diverse paths a classical computer would slow down exponentially in attempting to traverse an exponentially-growing number of paths; that is, a classical computer would not be able to simulate quantum processes. Berthiaume & Brassard proved in 1994 that QTM’s are theoretically faster than Turing machines, part due to the parallelism of quantum computing; Shor was able to demonstrate that fact that same year by factoring large integers in polynomial time. Shor’s algorithm was the first significant problem solved by a quantum approach to excel classical computers.
Grover showed in 1996 a quantum algorithm to search unsorted databases in the square root of the time it would take a classical computer to find an entry. *** has said that to search for your name in the entire text of the Library of Congress would take classical computers about 100 years, but a quantum computer could find your name in a little under half a second. Grover’s algorithm and the law of super-positioning makes this possible. (Super-positioning is discussed later in this paper.),
The Turing machine, designed around a machine traversing a strip of paper, is hard to use as a focus to manipulate new ideas in programming and electronics. In 1993, Yao showed that the same effect could be accomplished by using quantum circuits. These circuits are an equivalent to digital logic circuits, but they use quantum principles. Classical circuits use Boolean logic, either state 0 or 1, for inputs and outputs. Quantum circuits use these states simultaneously: the inputs of a quantum circuit are both 0 and 1.
These algorithms are constructed and proved in theory, but last summer (June, 1998), Gershenfeld and Chuang built the first quantum computer at MIT. It was based on the principles of Nuclear Magnetic Resonance (NMR). There are other types of quantum computers that may be built, but it is characteristic in that it uses molecules in a liquid CPU of chloroform for logic gates . Their prototype is discussed later in this paper.
In December of last year, Anton Zeilinger made a fantastic accomplishment. He was able to quantum teleport a beam of light about three feet across his laboratory. This feat was achieved using a principle called quantum entanglement, both of which are explained later in this paper.,,
There is much that is different between quantum computers and classical computers. This paper will address only two: superpositioning to support the explanation of quantum circuits, and entanglement to support the explanation of quantum teleportation..
Superpositioning is a big word for an old concept: that two things can overlap each other without interfering with each other. In classical computers, electrons cannot occupy the same space at the same time, but as waves, they can.
Figure 1 is an illustration of two super-imposed waves A and B. If I were to add these waves together numerically, S = A + B, the result would be a wave that looks like neither of its components. However, one could retrieve either wave be subtracting out the other, as shown. (The wave form S, is shown as dotted to indicate that it is only the apparent wave form; the actual wave form is the combination of two different waves. In the quantum world, the combined wave form is a set of amplitude probabilities.)
For an example germane to computer programming, one may look at a data structure called a linked list. Each date node in the list contains a reference, or pointer, to the next data node. The program traverses the list by jumping to the next data node indicated by the pointer. In a doubly-linked list, the data node contains two pointers, one for traversing to the top of the list, and another for traversing to the bottom of the list.
Another way of implementing a doubly-linked list is to use a single pointer space that contains the exclusive-or (XOR) or the two adjacent pointers. Figure 2 shows a link list node with pointer S that is the XOR of reference A (before) and reference B( after). To traverse the link list upward, the program XORs the current pointer (S) with the one it just left (B), and the result is the pointer of the next node (A). The same process works when traversing down the list. This superpositioning of node pointers is analogous to the water wave superposition example above, and is how the quantum states are maintained simultaneously in a quantum bit.
A state vector is a mathematical name for the superpositioning of all the probabilities that a quantum bit may find itself in. These probabilities are not all equal. One may think of this as a vector of the probabilities drawn in a two-dimensional coordinate system of the Complex plane, that is, coordinates of the form x+iy, where x is a coordinate on the Real number line, and y is a coordinate on the Imaginary number line.
Classical bits are either vectors of 0 or 1 and have no Imaginary component. Quantum bits, or "qubits", have both components. If the probabilities were equal, the vector could be represented as 45 degrees from vertical; if the probability of 1 were twice that of 0, the vector could be represented as 30 degrees from vertical. This vector represents the superposition of the probability of 1 and the probability of 0 simultaneously. In this way, the state vectors of classical bits are "collapsed" qubit state vectors.
It is an important side note that any physical quantity that is expressed by an Imaginary number cannot be measured directly, and any physical quantity that is expressed by a Complex number can be measured only on its Real number component. Because of this, qubits cannot be measured directly. Any measurement of a qubit will break superposition and collapse its state vector to a classical bit, just as subtracting a component wave or XOR’ing a pointer, will produce a different result. In performing computation with qubits, it is important not to measure the qubits until the final answer is computed, or information can be lost or changed.
Williams and Clearwater give an excellent example of a quantum circuit that cannot be explained in terms of classical physics. It also illustrates the principle of quantum circuits and superpositioning. They have termed the gate the Square-Root-NOT gate, in contrast to the classical NOT gate. The classical NOT gate takes either a 0 or 1 input and converts it to a 1 or 0 output respectively. It is a reversible gate in that the input may be deduced from the input. The quantum circuit symbol for the NOT gate is shown in Figure 3 (top).
Now imagine another logic circuit that is also reversible, but it contains two gates in series such that the input of either a 0 or 1 is converted to a 1 or 0 output respectively. Because the two-gate circuit is reversible like the NOT gate, and inverts the input exactly like the NOT gate, each gate is called a Square-Root-NOT gate (see Figure 3, bottom). There is no way classical gates can perform this logic. It can be done as a quantum circuit though.
A quantum circuit has two important differences. First, the input is a qubit, and contains the superposition of both 1 and 0, and the output is also the superposition of both 1 and 0, but with the probabilities reversed. Second, the output of the first gate, halfway through the circuit, is in an unknown state; it has a calculable state vector, but one that cannot be measured directly.
A universal gate is a gate that can be used to produce all circuits. Quantum computers have a universal gate: the XOR gate. Any quantum circuit can be made with only this one gate (and a complement of 1-bit gates). Of course, the circuit will probably be awkward and it may not be pretty, but it will work. Let it suffice for now that quantum circuits can be built, at least on paper, with similar tools available for classical circuits, and one may construct a logic circuit to do what one wants. The XOR gate has a naturally occurring counterpart that comes into play when building quantum computers, which will be discussed in the section below on the NMR prototype.
The quantum property of entanglement has an interesting history. Einstein, who claimed that "God does not play dice with the universe" used the property of entanglement in 1935 in an attempt to prove that quantum theory was incomplete.
Albert Einstein, Boris Podolski, and Nathan Rosen knew that the state vectors of certain quantum systems were correlated, or "entangled" with each other. If one changes the state vector of one system, the corresponding state vector of the other system is also changed, instantaneously, and independently of the medium through which some communicating signal must travel. Since nothing could travel faster than the speed of light, how could one system arbitrarily far apart affect the other? Einstein called this "spooky action at a distance" and it required a philosophy of reality contrary to science as then known. He preferred the idea that some unknown or "hidden variables" were contributing to the effect, and since they weren’t known, then quantum theory must be incomplete.
In 1964, John Bell proved that there could not possibly be any hidden variables, which meant that spooky action at a distance was a fact. Alan Aspect later (1982) performed an experiment in which he showed that Bells’ Theorem, as it was called, had experimental validity. Either some faster-than-light speed communication was happening, or some other mechanism was at work. This basic concept has made all the difference between classical ideas of reality and quantum ideas of reality.
Throughout all of history previously, all physical phenomenon was dependent on some force, and some particle to carry that force, and therefore the speed of light restriction applied. For example, electrostatic forces are carried by the electron, gravitational forces are carried by the graviton, etc. However, with entanglement, quantum systems are correlated in some way that does not involve a force, and the speed of light restriction does not apply. The actual mechanism of how one system affects the other is still unknown.
When two quantum systems are created while conserving some property, their state vectors are correlated, or entangled. For example, when two photons are created, and their spin conserved, as it must, one photon has a spin of 1 and a spin of -1. By measuring one of the state vectors of the photon, the state vector collapses into a knowable state. Instantaneously and automatically, the state vector of the other photon collapses into the other knowable state. When one photon’s spin is measured and found to be 1, the other photon’s spin of -1 immediately becomes known too. There are no forces involved and no explanation of the mechanism.
The principle of entanglement enables a phenomenon called quantum teleportation. This kind of teleportation does not involve moving an entity from one physical location to another, as may be found in many popular science fiction stories, but a destruction of the original and recreation of an identical duplicate at another location.
Gilles Brassard, in 1996, conceived of a quantum circuit that could create and entangle two pairs of qubits, where one is entangled with two others. Figure 4 shows Brassard’s quantum circuit. In general, Alice’s circuit entangles three bits (M, A, and B), and transmits M to Bob. Bob’s circuit, using knowledge from M, produces a replica of bit B. The instantaneous result on B, by measuring M, is effectively a teleportation of qubit B.
For purposes of discussion and at the risk of over-simplification, the gates marked L, R, S, and T, are referred to as left-rotation, right-rotation, forward-phase shift, and backward-phase shift gates, respectively. The XOR gate is shown as a circumscribed cross. These gates can cause entanglement when qubits are put through them.
The conceptual circuit works like this:
The original qubit B was not magically transferred through space, but was recreated from a different bit M; only the state vector information was transferred through space, when Alice told Bob the states of the qubits A and B that she measured.
Figure 5 shows a diagram of how Zeilinger setup his teleportation device at the University of Austria at Innsbruck. This diagram shows the physcial counterpart to Brassard’s theoretical circuit described above.
Although quantum computers were predicted some years ago, the engineering obstacles were considered prohibitive, and quantum computers were not expected to be produced, even in prototype, until sometime in the year 2025. Despite predictions, the first prototype was built by Gershenfeld and Chuang in the summer of 1998 at MIT. Although there are several different designs for quantum computers, Gershenfeld and Chuang chose to use one based on nuclear magnetic resonance (NMR) principles.
In an NMR-type quantum computer, the atoms themselves are used as qubits for the system, and Gershenfeld and Chuang chose a liquid CPU containing two ounces of chloroform. The carbon-hydrogen atoms of chloroform each act as XOR gates, or in the jargon of quantum computers, controlled-NOT gates. The atoms are programmed through a sequence of radio pulses, and the answer is read through standard NMR detection techniques. The CPU is a two-bit "circuit" with about 1023 molecules. Each atom has a two-spin state, a "chemical spin" and an "atomic spin". The two kinds of spin used together provides 2-bits, and when used in conjunction with the other atom of the molecule, the molecule provides an effective XOR gate.
Each atom acts like a bar magnetic when in an external magnetic field, the atoms aligning parallel (spin 1) or antiparallel (spin 0) to the field. By using a radio pulse, the atoms can be made to flip between states. This is the atom’s so-called chemical spin.
The "atomic spin" of an atom causes it to precess in the magnetic field. Depending on its chemical spin alignment, it will rotate either clockwise or counter-clockwise, much like a gyroscope.
The Controlled-NOT gate is a better description of the XOR gate because it is a 2-bit gate where one input controls the inversion property of the other input. Call one input line the Control, and the other input line the NOT input. The NOT function will only work if the Control line is set, but any input to the NOT line will be ignored if the Control is not set. The table below shows the truth table for the Controlled-NOT gate. Recall that the XOR gate, or the Controlled-NOT gate,. Is a universal gate, and therefore any circuit can be made from just this one kind of gate.
|
LINE 1 (Control) |
LINE 2 (NOT) |
OUTPUT |
|
0 |
0 |
0 |
|
0 |
1 |
1 |
|
1 |
0 |
1 |
|
1 |
1 |
0 |
Figure 6 shows a diagram of how a controlled-NOT gate works at the atomic level. The nature of the molecule works for the quantum computer because the chemical spin has slightly more energy in one alignment than the other. The hydrogen atom works like the control input, and the carbon acts like the NOT input. If the carbon is parallel aligned (spin 1) with the magnetic field, then a properly tuned radio signal can cause it to flip to be aligned antiparallel (spin 0) if the hydrogen is in the aligned position (state 1). If the hydrogen atom is in state spin 0, then the carbon will not flip states even with the radio pulse. (Similarly, the carbon atom can be flipped from state 0 to state 1 when hydrogen is in state 1.)
It actually takes two radio pulses to affect a carbon state transition, one for precessing and one for alignment. In this way, the quantum computer can send a programmed series of radio pulses at the molecules to set and reset the various bits of the "molecular registers". In contrast to the classical computer, which sends bits through gates to perform computation, the quantum computer sends the gates at the qubits to perform computation.
By throwing a programmed set of radio pulses at the molecules, and the numerous quantum gates within, Gershenfeld and Chuang implemented Grover’s search algorithm to select a marked item in an unsorted list of items. Their quantum computer performed the equivalent of opening a two-number combination padlock and in few number of average tries than a classical computer would need.
This paper skimmed the marvelous ideas of quantum computing, its concepts, and how quantum theory allows technological jumps in the computer industry that will revolutionize the practical computing world. Quantum computes are coming, and they will require a new way of looking at computing. Applications that can not be done now are easily possible with quantum computers. The spin-off concepts, like quantum teleportation, open vistas only imagined before. Computer science is still immature for its barely 80 years, and this radical divergence from the traditional development path is one indicator that. Who knows what the next 870 years will bring?
Figure 1. Superposition in water waves
Figure 2. Superposition in Link Lists
Figure 3. NOT Gate and Square-Root-NOT Gates
Figure 4. Brassard’s Teleportation Circuit
(after Wilson & Clearwater, 1998)
Figure 5. Zeilinger’s Experimental Teleportation Circuit
Figure 6. Controlled-NOT Molecular Gates of
NMR-type Quantum Computer
(after Gershenfeld & Chuang)