By Stephen Page, author of “The Quantum Killer’

Introduction

World scientists have been committing millions and now billions of dollars in 2004 for the research and construction of a quantum computer capable of performing calculations a billion times faster than a classical computer. In 1985, the U.S. Government began funding research on quantum computers when physicists brought it to their attention that a quantum computer could potentially cripple national security; hence, a national security nightmare. Corporations such as IBM, Boeing, Hewlett-Packard, or Microsoft and science-based educational institutions such as MIT, Caltech, or Stanford joined the bandwagon and committed funds and full-time resources to studying quantum computers. And remarkably, in April 2004, the founders of the University of Waterloo (UW) at Ontario, Canada, donated $33.3 million to UW’s Institute for Quantum Computing bringing their research funding total to $100 million. A little known fact and quite alarming is the fact that foreign governments are spending twice as much as the rest of the world on quantum computer research.

The Furor Starts

Physicists and computer scientists first explored the idea of a computational device based on quantum mechanics in the 1970’s and early 1980’s. The real furor began in 1981 when brainy physicist Richard Feynman suggested that quantum phenomena could perform calculations. He also explained how a machine would be able to act as a simulator for quantum physics. In other words, a physicist would have the ability to carry out experiments in quantum physics inside a quantum mechanical computer. At about the same time, other theorists such as Charles H. Bennett, IBM, and Paul A. Benioff, Argonne National Laboratory, began to toy with the idea that quantum particles might function as computer bits. In 1985, physicist David Deutsch, University of Oxford, realized that Feynman’s assertion could eventually lead to a general purpose quantum computer. He published a crucial theoretical paper showing that any physical process, in principle, could be modeled perfectly by a quantum computer. Thus, a quantum computer would have capabilities far beyond those of any traditional classical computer. The real icebreaker came in 1994 when Peter Shor, AT&T Labs, outlined how a quantum computer could factor a huge number exponentially faster than a classical computer. This factoring algorithm became a killer app because any application based on encryption (e.g., national security, banking transactions, stock trades, secure web sites, or vital governmental installations) could be compromised in seconds or minutes. With this breakthrough, quantum computing transformed from a mere academic curiosity directly into a national and world interest.

Slow Progress

With the billions of dollars and thousands of resources being thrown at quantum computer research, one has to wonder why the quantum computer has barely left the drawing board in 29 years!

We are spoiled, end of story.

We are used to fast computer progress so we naturally think the same holds for “just” another computer. Each year there is something faster and more powerful. With each blink of the eye, there is a new, faster processor or a more data-storage intensive hard drive. But for all their computational might, computers as we know them will eventually bump up against the laws of physics. Technology marches forward and components get smaller. If the current rate of miniaturization continues, computer experts predict that within a decade or two, transistors will dwindle to the size of an atom. And at those dimensions, well-behaved, predictable classical behavior goes out the window, and the slippery, untenable nature of quantum mechanics takes over. In the quantum world, rather than being entities with sharply defined positions and motions, particles are described by spread out wave-functions, seemingly existing in many places at once. It might seem that the power of computers is destined to reach a limit. This is not so with a computer that is based on the laws of physics, or a quantum computer. This computer is made of quantum particles with built-in parallelism because quantum calculations can be performed on particles’ (or quantum bits, or qubits), which co-exist in multiple states simultaneously.

Obstacles to Building a Quantum Computer

Quantum computers are still more science fiction than fact…even the most optimistic of experts predict a decade or more before anyone builds one that actually computes anything. The field of quantum information processing has made numerous promising advancements since its conception, including the building of two-, three-, and seven-qubit quantum computers capable of some simple arithmetic and data sorting. Scientists believe that a fully featured quantum computer must use at least two hundred qubits. “What is the problem?” you ask. Progress is slow because there are a few potentially large obstacles that must be resolved before a breakthrough of single digit qubit computers can lead to double and triple-digit qubit quantum computers.

The formidable obstacles include error correction, decoherence, and hardware architecture. Error correction is rather self-explanatory, but what errors need correction? The answer is primarily those errors that arise as a direct result of decoherence, or the tendency of a quantum computer to decay from a given quantum state into an incoherent state as it interacts, or entangles, with the state of the environment. These interactions between the environment and qubits are unavoidable, and induce the breakdown of information stored in the quantum computer, and thus errors in computation. A “Catch 22” scenario.

Before any quantum computer will be capable of solving hard problems, research must devise a way to maintain decoherence and other potential sources of error at an acceptable level. Thanks to the theory (and now reality) of quantum error correction, first proposed in 1995 by Peter Shor and continually developed since, small-scale quantum computers have been built and the prospects of large quantum computers are looking up.

Future Research

Currently, research is underway to discover methods for battling the destructive effects of decoherence, to develop optimal hardware architecture for designing and building a quantum computer, and to further uncover quantum algorithms to utilize the immense computing power available in these devices. The future of quantum computer hardware architecture is likely to be very different from what we know today, however, the current research has helped to provide insight as to what obstacles the future will hold for these devices. Research suggests it is only a matter of time before we have devices large enough to test Shor’s and other quantum algorithms. Quantum computation has its origins in highly specialized fields of theoretical physics, but its future undoubtedly lies in the profound effect it will have on the lives of all mankind. To answer the question of why progress is slow, it is because quantum computers lie with a pioneering stage and face numerous difficulties inherent within quantum physics. When research breaks through the obstacles, the building of a quantum computer will be a free for all.

Quantum Computer Benefits

In theory, a quantum computer can:

1.                  Factor large integers in a time that is exponentially faster than any known classical algorithm

2.                  Solve a discrete log problem

3.                  Run simulations of quantum mechanics

4.                  Crack encrypted secret messages in seconds that classical computers cannot crack in a million years.

5.                  Create unbreakable encryption systems to protect national security systems, financial transactions, secure Internet transactions, and other systems based on current encryption schemes

6.                  Advance cryptography to a point where messages can be sent and retrieved without encryption and without eavesdropping

7.                  Search impossibly large and unsorted databases that had previously been impossible by classical computers.

8.                  Improve pharmaceutical research because a quantum computer can sift through all chemical substances and interactions in seconds

9.                  Create fraud-proof digital signatures

10.              Predict weather patterns and identify causes of global warming

11.              Improve the precision of atomic clocks and precisely pinpoint the location of the seven thousand plus satellites floating above Earth each day

12.              Make teleportation a reality

13.              Optimize spacecraft design

14.              Enhance space network communication scheduling

15.              Develop highly efficient algorithms for several related application domains such as scheduling, planning, pattern recognition, and data compression