Tractability of High Dimensional Problems for Quantum and Classical Computers

对高维连续问题的求解算法和复杂度进行了进一步的研究。这类问题的例子出现在量子化学、分子动力学和凝聚态物理中。典型的连续数学公式包括偏微分方程、连续优化、高维积分和路径积分。维度度量连续问题的大小。就像在其他复杂性研究中一样，pi对解决大问题感兴趣；也就是高维问题。人们不能在数字计算机中输入实变量或复变量的函数。必须将其离散化以获得计算机输入。因此，计算机只有关于连续数学输入的部分信息。这允许由pi和他们的同事开创的信息层面的对立论点，从而导致问题复杂性的下限。这可能与离散问题形成对比，在离散问题中，信息是完整的，在信息层次上通常没有对立的论点，人们必须满足于复杂性层次不会崩溃的猜想。由于基于信息的论证的重要性，对连续问题复杂性的研究被称为基于信息的复杂性（IBC）。一个核心问题是确定问题在哪些环境和空间是可处理的；也就是说，它的复杂性不是指数级的。关于d维问题的计算复杂性有大量的文献。这些论文和书籍中的大多数都得到了关于1/E的尖锐结果，其中E是错误阈值，但对d有未知的依赖性。但是要确定问题是否可处理，需要知道对1/E和d的依赖性。这需要新的证明技术。这是E. Novak和H. Wozniakowski的专著“多变量问题的可追踪性”的主题。该专著已于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.