For some 40 years, computing has been driven by Moore's law which is the empirical observation that computing power doubles about every 18 months. This has made it possible for people to have computers in their homes as powerful as computers owned by corporations just 20 years ago. It has made the internet possible. Finally, powerful computers are indispensable to our national security. Computer chips and wires are getting so small that there is a consensus among technologists that Moore's law will end in 10 to 15 years using current silicon technology. Since it is critical for our country to maintain the Moore's law trajectory, new ways to compute are being considered. One of the most promising ideas is to use the principles of quantum mechanics to do quantum computing. The investigators and their colleagues are studying the following question: If physicists and chemists succeed in building quantum computers, for which problems are there the big payoffs? That is, what are the killer applications?
The goal of information-based complexity (IBC) is to create a theory of computational complexity and optimal algorithms for problems with partial, contaminated and priced information, and to apply the results to solving specific problems in varied disciplines. The theory is developed over abstract spaces while the applications are for multivariate problems. Since the information is partial and contaminated, only approximate solutions can be obtained. IBC studies computational complexity and optimal algorithms for computing approximations in various settings, such as the worst case, average, probabilistic and randomized settings. A new area of IBC research is quantum computing. The best known algorithms due to Shor and Grover are for discrete problems. But many problems occurring in science and engineering are continuous. Examples include high-dimensional and path integration, high-dimensional approximation, partial differential equations and integral equations. To understand the power of quantum computation for continuous problems one must know the computational complexity of these problems on a classical computer in various settings. This is exactly what has been studied in IBC. Questions to be answered include: For what problems is quantum computation exponentially or polynomially faster than classical computation? For what problems is there provably no speedup of quantum over classical computation? In addition, the investigators study randomization, breaking intractability by using additional domain knowledge, and a statistical model for a medical application.
INTELLECTUAL IMPACT The investigators have been working together on the core of IBC since 1973. Today there are many scores of researchers around the world working on IBC. The Journal of Complexity contains mainly IBC papers; in 2004 the Journal published 1000 pages in 6 issues. The investigators and their students participate in many international conferences and workshops. In addition to developing the core of IBC, the investigators apply it to a number of disciplines. The interdisciplinary research is published in journals of the application discipline. Examples are economics, physics, and mathematical finance.
BROADER IMPACT OF THE RESEARCH The investigators teach a graduate course, "Continuous Algorithms and Complexity" which teaches students the fundamentals of IBC. The course is also offered every year through the Columbia Video Network. Starting in Spring 2004, the investigators offered the first course on quantum computing at Columbia University. The investigators' graduate students attend professional meetings and present talks when they have done significant work. One of their graduate students, Krysta Svore, is working on quantum computing. She has presented a number of talks at international conferences.
