Joseph F. Traub

Two computer scientists at Columbia University and a third collaborator at the Massachusetts Institute of Technology have received $1.8 million in funding from the U.S. Defense Advanced Research Projects Agency for research on quantum computing.

The principal investigators are Joseph F. Traub, the Edwin Howard Armstrong Professor of Computer Science, Henryk Wozniakowski, professor of computer science, both at Columbia, and Seth Lloyd of MIT.

Their challenge is whether quantum mechanics -- which, in concert with general relatively, provide fundamental laws of the universe -- can be used to create an entirely different type of computer.

A second question is whether certain problems that appear intractable on current computers can be solved on quantum computers, for example, factoring large integers. This challenge is essential to modern cryptography, the security of encrypted messages.

The third driving force for the research is Moore's Law, which has held for some forty years, but is now believed to be nearing its end. The law is based on the empirical observation that computer power doubles about every 18 months. This is why millions of people own computers more powerful than those that only very large corporations could afford a few decades ago. For Moore's Law to continue to hold, computer components must get smaller and smaller, but the expectation is that this will become impossible in some fifteen years. If we are to continue to have increasingly powerful computers, an entirely new technology will have to be found. Quantum computing is a prime candidate.

Fundamental laws of physics, such as decoherence, make quantum computers difficult to construct. Today they exist only as laboratory prototypes. A quantum computer's size is measured by the number of qubits (quantum bits), and to date, only computers with a very few number of qubits have been constructed. A goal of the Columbia-MIT project is to answer the following question: If quantum computers become feasible outside the laboratory, what problems can be solved significantly faster than on the common computers in use today?

The goal is to find "killer" computer applications. Since most applications in science and engineering have continuous mathematical models, a focus of the Columbia-MIT project is to solve such problems very fast. Examples include path integrals (which occur in the foundations of physics, chemistry, and mathematical finance), partial differential equations, and operator equations. Algorithms for solving these problems will be developed and implemented, initially on laboratory prototypes.

Also of interest is the identification of problems for which quantum computation can never offer significant speed-ups over classical computation.