Tractability of High Dimensional Problems for Quantum and Classical Computers

Columbia University, New York NY

Investigators

Abstract

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.