New proof techniques and new optimal algorithms and complexity results will be obtained under the grant. Many important scientific and engineering problems have continuous mathematical formulations. Since digital computers can only deal with numbers, continuous problem have to be discretized for input into the computer. Hence the information about the continuous mathematical problem is partial and contaminated and only an E-approximation can be obtained. Because the information about the continuous problem is partial and contaminated one can use adversary arguments pioneered by the investigators and their colleagues to obtain computational complexity and optimal algorithms for important problems. This may be contrasted with discrete problems such as integer factorization, where one has to settle for conjectures about the complexity hierarchy. A central issue is to determine for which settings and spaces a problem is tractable; that is, its complexity is not exponential. There is a huge literature on the computational complexity of d-dimensional problems. Most of these papers and books obtain results which are sharp with respect to 1/E but have, unfortunately, unknown dependence on d. But to determine if a problem is tractable, we need to know the dependence on both 1/E and d. This requires new proof techniques.
Many important scientific and engineering problems involve a large number of variables. Equivalently they are said to be high dimensional. Examples of such problems occur in quantum mechanics, molecular biology, and economics. For example, the Schrodinger equation for p particles has dimension d = 3p; systems with a large number of particles are of great interest in physics and chemistry. This problem can only be solved numerically. In decades of work scientists have found that the problems get increasingly hard as p increases. The investigators believe this does not stem from a failure to create good numerical methods--the difficulty is intrinsic. The investigators believe solving the Schrodinger equation suffers the curse of dimensionality on a classical computer. That is, the time to solve this problem must grow exponentially with p. (A classical computer is any machine not based on the principles of quantum mechanics--all machines in use today are classical computers.) The investigators hope to show this problem is tractable on a quantum computer. Success in this research would mark the first instance of a PROVEN exponential quantum speedup for an important non-artificial problem.
Many important scientific and engineering problems have continuous mathematical formulations. Examples of such problems occur in quantum mechanics, molecular biology, financial mathematics, and general relativity. Typical continuous mathematical formulations include partial differential equations (e.g. Schroedinger's equation), molecular dynamics, integral equations, high dimensional integration and path integration. Many of these problems have high dimension, d. For example, the Schroedinger equation for p particles has dimension d = 3p; systems with p large are of great interest in physics and chemistry. Since digital computers can only deal with numbers, continuous problems have to be discretized for input into the computer. Hence the information about the continuous mathematical problem is partial and contaminated and only an E-approximation can be obtained. Because the information about the continuous problem is partial and contaminated one can use adversary arguments pioneered by the PIs and their colleagues to obtain computational complexity and optimal algorithms for important problems. This may be contrasted with discrete problems such as integer factorization where one has to settle for conjuctures about the complexity hierarchy. Because of this information based adversary arguments the field is called information-based complexity (IBC). The goal of IBC is to create a theory of computational complexity and optimal algorithms for important continuous problems. In particular, we are interested in important problems which are intractable on classical computers but which can be solved fast on quantum computers. An example of such a problem is approximating the ground state of the Schroedinger equation for p particles. We have shown that the computational complexity of this problem is exponential in p on a classical computer. That is, the problem suffers the curse of dimensionality. We have shown that the curse can be vanquished on a quantum computer. Indeed, the cost is linear in p on a quantum computer.
