By Christopher Rogala, managing editor

HPCwire: Why do research on quantum computing?

TRAUB: Moore’s law has held for some 35 years. As you know, this is the empirical observation that chip densities, and therefore computer power, double roughly every eighteen months. Current projections estimate that this exponential improvement will end in one or two decades for a number of reasons:

— There are physical limits to the smallness of what can be put on a chip.

— There are financial limits because the cost of building a chip manufacturing facility doubles with each chip generation.

What might come after silicon computers? DNA computation will probably be special purpose. Nanotube circuits are being studied. There is much interest in quantum computers with the hope that they can solve problems which are intractable on classical machines.

There is huge current interest in quantum computing. A recent search on Google yielded 232,000 hits.

HPCwire: How confident are you that quantum computing will eventually become truly practical?

TRAUB: As you know, although quantum computers with a few qubits have been built in the laboratory, it is not clear whether quantum computers will prove to be an answer to the end of Moore’s law for silicon-based classical computers. A difficulty is whether the superposition of states can be maintained or, to use the interpretation of the Copenhagen school, whether we can avoid the collapse of the wave function by measurement or interaction of the computer with its environment.

HPCwire: What sort of time line do you foresee for the development of usable quantum computers?

TRAUB: At present we have quantum computers only in the laboratory. I cannot predict a time-line.

HPCwire: What role is the federal government playing in funding quantum computing research?

TRAUB: There are major federal government investments in quantum computing research. One of the main efforts is the Quantum Information Science and Technology (QuIST) by the Defense Advanced Research Projects Agency (DARPA). The kickoff conference for QuIST was to have been in Dallas, starting September 22. Due to the events of September 11, this meeting was deferred to a later date. For information on QuIST, see http://www.darpa.mail/ito/research/quist/index.html

HPCwire: Please describe your approach to quantum computing.

TRAUB: The research is being conducted jointly by the continuous algorithm and complexity group at Columbia and the quantum computation groups at MIT. The thrust of our research is if quantum computers can be built, what are the killer applications?

To date there have been only two major algorithms for quantum computers which are significantly better than for classical computers: Shor’s factorization and Grover’s data search. These algorithms are for discrete problems. But many applications in science and engineering have continuous mathematical models. Examples of such models are high dimensional integration, path integration, partial differential equations, and continuous optimization. Such problems are usually solved numerically; they can only be solved to with an uncertainty e. These problems are typically intractable on classical computers if one wants a worst-case deterministic assurance. For some continuous problems, intractability can be vanquished by weakening the worst-case deterministic assurance to a stochastic assurance such as the randomized setting of which Monte Carlo is the prime example.

We will seek new algorithms for quantum computers for important continuous applications. We believe that there are a number of killer applications which will enjoy exponential speed-ups over classical computation while requiring only a small or modest number of qubits. Preliminary investigations suggest that path integrals and high-dimensional finite integrals can be big winners on quantum computers.

Initially the algorithms will be implemented on quantum computer simulators. Then they will be implmented on NMR quantum computers in D. Cory’s laboratory at MIT.

For more on this research, see http://quantum.cs.columbia.edu

HPCwire: How will a functioning quantum computer actually work?

TRAUB: A variety of physical realizations are being studied in the laboratory. These include:

— Nuclear magnetic resonance (NMR) — Ion trap — Optical photon — Optical cavity — Quantum dot

HPCwire: How widepsread will the use of quantum computers become? For what uses is quantum computing best suited?

TRAUB: These are questions which I hope research will illuminate.

HPCwire: Other than advances in processing speed, what is to be gained from the research and development of this technology?

TRAUB: Quantum theory continues to amaze physicists because it is so counter to experience. As Niels Bohr put it, “Anyone who is not shocked by quantum theory has not understood it.” There is hope that quantum computing and quantum theory will lead to better understanding of both.

============================================================