By Gerald Gilbert

After the great chess master Gary Kasparov was defeated by IBM’s “Big Blue” computing machine in a famous match in May 1997, he displayed genuine amazement (and perfectly human anger) at the outcome. Amazing as this outcome was, it is even more amazing when considering the fact that Big Blue, and indeed all computing machines in use today—ranging from palm devices to supercomputers—are in a sense glorified abacuses!

How can this be? The information that is manipulated, stored, and transformed in both a massively parallel electronic computer and in a wooden abacus is classical information. Although a modern computer is mind-numbingly fast compared to an abacus, the underlying principles of information science that govern both machines are identical: the physical states that represent the information, the dynamic evolution of those states, and therefore the information itself, are all described by the equations of classical mechanics.

The paradigm for information science is, however, beginning to change. “All things must pass,” opined George Harrison in his pretty song of that title, and in a sense, this is just what is occurring today at the scientific frontier defined by the intersection of physics, engineering, and computer science. Worldwide research over the last few years has explored the possibilities for hardware and software development inherent in the explicit use of the physical properties of quantum mechanical systems, such as atoms and their components.

Emerging from the work is the nascent concept of a quantum computer. Although current computers incorporate semiconductors and thus rely upon quantum effects in their underlying technology, their design principles are purely classical. The memory of a computing machine is composed of some number of registers, which can be thought of as “boxes” that house bit values. A given classical bit can describe precisely one or the other of two exclusive information states, usually referred to as ‘0’ and ‘1’. At any particular time, an n-bit register in a classical computer can describe a maximum of n bit values. After all, how could a bit represent both a ‘0’ and a ‘1’ at the same time?

Actually, it can, if we consider the terrain of the very small, where the rules of quantum mechanics hold sway. If we imagine making use of elementary particles, such as electrons, or perhaps the nuclei of atoms, as the building blocks of computer memories, we find a new realm of possibilities. The analogue of an n-bit register in a quantum computer represents all of the 2ⁿ information states that are potentially associated with n distinct classical bits. This behavior of quantum information is so different from that of classical information that we distinguish it with a new concept, that of a quantum bit (or “qubit”, as it has come to be called), the generalization of a classical bit. At any instant, the quantum computer is in a linear superposition of all its possible bit patterns. If we can eventually build one, such a machine will be no abacus. It will not even be the “mother of all abacuses.” It will represent a new world of computing, a terra incognita the outlines of which we are only beginning to understand and explore today.

Quantum computers are being developed within the context of quantum information science, an emerging interdisciplinary field in which the basic, underlying principles and possibilities of the science and technology of information are being discovered and applied. The essence of the new field is captured in the statement “information is physical”—the data with which we work are encoded in the states of some physical objects. As such, the processes and paths that the data can participate in and follow are dictated by the laws of physics, which at their root are provided by quantum mechanics. Quantum mechanics underlies all current physical theory. The Standard Model (Weinberg-Salam model) of elementary particles, which correctly accounts for three out of the four fundamental forces of nature (the electromagnetic and strong and weak nuclear forces), is a quantum field theory, i.e., a mathematically consistent combination of quantum mechanics and special relativity. String Theory, a promising approach to describing the remaining fundamental force (gravity) unaccounted for in the Standard Model, along with the other three forces, is a quantum mechanical generalization of Einstein’s general theory of relativity. Although many have looked, there have been no experimental contradictions to the predictions of quantum mechanics discovered thus far, and we have had 75 years during which to discover them.

So there is a deep and fundamental reason to carry out research in quantum information science: the experimental evidence tells us that nature is not really classical, but is instead quantum mechanical. This fact alone impels one to think about the possibility of computing, and communicating, with quantum mechanics, and brings to mind other questions that we will address below. However, there are purely practical motivations as well. It is already known that there are certain classes of computational problems for which one can obtain solutions much more efficiently with quantum computers than with classical computers. In some cases one obtains a moderate speedup (Lov Grover’s quantum algorithm for searching a database), and in other cases one obtains an exponential speedup (Peter Shor's algorithm for period-finding and factoring). These allow for solving problems that are basically impossible to solve with classical computers. Considering the application of quantum information more generally to communications tasks, we already know that under certain circumstances it is possible to increase the capacity of a communications channel beyond that which is allowed for by classical information theory; this is called quantum superdense coding. In other circumstances it is possible to carry out a task that has no classical counterpart and is otherwise physically impossible. Such a task is quantum cryptography, which allows unconditionally secret communications between remotely located parties (see “Pushing the Frontier of Science”).

Among the possible uses to which quantum computers might be applied, special attention (not to mention substantial—and growing—funding) has been directed to the subject of cryptanalysis, the science and art of “breaking codes.” Immediately upon Peter Shor’s discovery of an algorithm for period-finding and factoring, it became apparent that quantum computers represent both an opportunity and a specter: much of current cryptography will be rendered useless if and when powerful quantum computers are built. The development of powerful quantum computers would pose a distinct threat to all communications and other information processing systems that rely in an important way for their cryptographic security on public key cryptography methods.

It is important to note here that all of the known methods of public key cryptography are vulnerable to quantum computers—this includes those methods based on the difficulty of factoring very large numbers, exemplified by Rivest-Shamir-Adelman (RSA) encryption, and those methods based on the use of elliptical curves. The impact of this vulnerability would extend across the military, economic, and diplomatic domains precisely to the extent that public key cryptography is embedded in various systems employed in these domains. It is now an official, announced policy of the Department of Defense (DOD) to embed and implement public key cryptography very widely throughout many important DOD information and communication systems.

Adversaries equipped with powerful quantum computers who are also able to intercept the relevant information should be able to exploit this. Any currently intercepted ciphertext communications that are stored by an adversary for future analysis if and when powerful quantum computers become available will also become transparent if they have been protected by public key cryptography today. Current doctrine, concept-of-operations, order-of-battle information, etc., for future military operations, to the extent that they are protected today using public key encryption, should be considered just as vulnerable to decryption by an adversary with quantum computers as future transmissions intercepted after the eventual appearance of quantum computers.

Quite apart from these and other possible practical applications of quantum computing, we must confront quantum information science in any event.

The developmental trend in classical computer design and manufacture discerned by Gordon Moore, universally referred to as “Moore’s Law,” consists in the observation that the memory capacity of integrated circuit chips appears to be doubling every 18 months for a given size of chip. The implication of this observation is that every 18 months only half as many atoms are needed as were before to store a bit of information.

As a consequence of Moore’s Law, classical computing will inevitably come into direct conflict with the basic physical laws of nature. If current trends in miniaturization and energy efficiency continue as they have during the period that provided the basis for Moore’s Law, we will find that computer technology must reach the quantum level at some time between 2010 and 2020. At that point individual transistors will have shrunk to the mesoscopic scale (about 10 angstrom or 1 nanometer). Owing to the onset of large-scale quantum fluctuations in the operation of transistors, circuits, and switching units, which results in the replacement of deterministic values with quantum probabilistically distributed ones, this occurrence will mean that all aspects of computer operation will be dominated by quantum mechanical effects, and it will be necessary to modify computer design accordingly. Our knowledge of the physics of quantum mechanical systems leads us to the conclusion that the design principles of classical computers must then be replaced with the new design principles of quantum mechanical computing machines.

For an illustration of the magnitude of the radical departure in design that is entailed in moving from classical computers to quantum computers, consider the following, so-called “quantum corollary” to Moore’s Law. Roughly speaking, the corollary consists in the assertion that, in comparing the resources required to increase the computing power of quantum versus classical computers, for every power doubling period of a classical computer it suffices to add a single quantum bit to the memory of the quantum computer in order to maintain a comparable improvement.

There is no doubt that the quickly developing field of quantum computing is of fundamental importance to the future of information technology, but what about to science in general? We have been intrigued and confused for many years about the wonderment of nature that is revealed by the physics of quantum mechanics. This is exemplified by the phenomenon of entanglement, a purely quantum mechanical phenomenon that reveals itself in strange non-local correlations between separated physical objects. Entanglement cannot be explained in terms of classical physics, even in principle, and the human mind appears to be inadequate in providing a satisfying intuitive understanding. Einstein was himself puzzled about some of the deepest questions that are raised by the surprising features of quantum mechanics, and invoked the expression “spukhafte Fernwirkungen” (spooky actions at a distance) to register his alarm. The implications of quantum computing and quantum information science in general force one to think deeply about these questions within the context of careful scientific activity. We may hope that the questions raised by the study of quantum information will lead to our ultimate goal: increased understanding.

---

For more information, please contact Gerald Gilbert using the employee directory.

---