Tractability of High Dimensional Problems for Quantum and Classical Computers

提出了高维连续问题求解的算法和复杂性研究的继续。 这类问题的例子出现在量子化学、分子动力学和凝聚态物理学中。典型的连续数学公式包括偏微分方程、连续优化、高维积分和路径积分。维度度量连续问题的大小。正如在其他复杂性研究中一样，PI感兴趣的是解决大问题，也就是高维问题。人们不能把一个真实的或复变的函数输入数字计算机。必须将其离散化以获得计算机输入。因此，计算机只有关于连续数学输入的部分信息。这使得对手的论点在信息水平上率先由PI和他们的同事，导致问题的复杂性下限。这可能与离散问题形成对比，在离散问题中，信息是完整的，在信息水平上通常没有对手的论点，并且人们必须满足于复杂性层次结构不会崩溃的假设。由于信息论的重要性，对连续问题复杂性的研究被称为基于信息的复杂性（information-based complex，IBC）。一个核心问题是确定问题在什么样的环境和空间下是可处理的，也就是说，它的复杂性不是指数的。 关于d维问题的计算复杂性有大量的文献。 大多数这些论文和书籍获得的结果是尖锐的1/E，其中E是错误的阈值，但有未知的依赖于d。但要确定一个问题是否易处理，需要知道对1/E和d的依赖性。这需要新的证明技术。 这是E. Novak和H.沃兹尼亚科夫斯基2008年和2010年出版了两卷专著。这两卷包括91个开放式问题。研究将致力于试图回答其中一些开放的问题。

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.