Tractability of High Dimensional Problems for Quantum and Classical Computers

点击翻译按钮获取中文摘要

The continuation of the study of algorithms and complexity for the solution of high dimensional continuous problems is proposed.  Examples of such problems occur in quantum chemistry, molecular dynamics, and condensed matter physics. Typical continuous mathematical formulations include partial differential equations, continuous optimization, high dimensional integration, and path integration. Dimension measures the size of a continuous problem. Just as in the rest of complexity studies the PIs are interested in solving large problems; that is, problems of high dimension. One cannot enter a function of real or complex variables into a digital computer. One has to discretize it to obtain the computer input. Thus the computer has only partial information about the continuous mathematical input. This permits adversary arguments at the information level pioneered by the PIs and their colleagues which lead to lower bounds on the problem complexity. This may be contrasted with discrete problems where the information is complete, there are often no adversary arguments at the information level, and one has to be content with conjectures that the complexity hierarchy does not collapse. Because of the importance of information-based arguments the study of the complexity of continuous problems is called information-based complexity (IBC).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, where E is the error threshold, but have unknown dependence on d. But to determine if a problem is tractable one needs to know the dependence on both 1/E and d. This requires new proof techniques.  This is the subject of the monograph "Tractability of Multivariate Problems" by E. Novak and H. Wozniakowski. Two volumes of the monograph have been published in 2008 and 2010. These two volumes include 91 open questions. Research will be devoted to trying to answer some of these open questions.