Information-based complexity (IBC) studies optimal algorithms and computational complexity for the continuous problems which arise in physical science, economics, engineering, and mathematical finance. IBC has studied such continuous problems as path integration, partial differential equations, systems of ordinary differential equations, nonlinear equations, integral equations, fixed points, and integration. Usually these problems have to be solved numerically and therefore approximately to within error e. Often these problems involve a very large number of variables numbering in the hundreds or thousands. If a worst case assurance of an e-approximation is demanded, then the computational complexity depends exponentially on the number of variables; the problem suffers the "curse of dimensionality". The investigators and their colleagues attempt to vanquish the curse by settling for a stochastic assurance (average, probabilistic, randomized) or by using domain knowledge about the application. The investigators are also studying the power of quantum computation for continuous problems. 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. Recently the investigators introduced a new quantum setting in which randomized queries are permitted. They have shown that for path integration there is an exponential improvement for the qubit complexity compared to the standard quantum setting. This is important since the number of qubits is a critical resource for the foreseeable future. Among the questions the investigators and their colleagues stydying are: What are the query and qubit complexities for other continuous problems? Are there trade-offs between query and qubit complexities?
For some forty years, computing has been driven by Moore's Law which is the empirical observation that computing power doubles about every 18 months. Powerful computers have been crucial for our economic strength and our national security. They have made the internet possible. For a number of reasons the consensus among experts is that Moore's Law using current silicon technology will end in some 10 to 15 years. These reasons include the shrinkage of logic gates and wires to atomic size, the tre- mendous heat generated as chips get smaller and faster, and the cost of fabrication facilities. Since it is so important 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, which continuous problems arising in science and engineering can be solved much faster on a quantum computer than on a classical computer?
