Traub and Wozniakowski The goal of information-based complexity 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. For brevity, information-based complexity will be called IBC. The theory is developed over abstract spaces, typically Hilbert and Banach spaces, while the applications are to multivariate problems. Because the information is partial and contaminated, only approximate solutions can be obtained. IBC studies computational complexity and optimal algorithms for computing e-approximations in various settings. Because the worst case setting often leads to negative results such as unsolvability and intractability, settings with a weaker assurance such as average, probabilistic, and randomized settings are also studied. A fairly new area of IBC research is quantum computing. The best known algorithms discovered to date, 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, and partial differential 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, polynomially) faster than classical computation? For what problems is there provably no speed-up of quantum over classical computation? 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. Because 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 big payoffs? That is, what are the killer applications?
