Tractability of High Dimensional Problems for Quantum and Classical Computers

新的证明技术、新的优化算法和复杂的结果将在授予下获得。许多重要的科学和工程问题都有连续的数学公式。由于数字计算机只能处理数字，所以连续问题必须离散化才能输入计算机。因此，关于连续数学问题的信息是局部的和被污染的，只能得到E-近似。由于关于连续问题的信息是部分的和受污染的，人们可以利用研究人员和他们的同事开创的敌对论点来获得重要问题的计算复杂性和最优算法。这可能与整数分解这样的离散问题形成对比，在这些问题中，人们不得不满足关于复杂层次的猜测。一个中心问题是确定问题对于哪些设置和空间是容易处理的；也就是说，它的复杂性不是指数级的。关于三维问题的计算复杂性，有大量的文献。这些论文和书籍中的大多数都得到了关于1/E的精确结果，但不幸的是，它们对d具有未知的依赖性。但要确定一个问题是否可处理，我们需要知道对1/E和d的依赖性。这就需要新的证明技术。许多重要的科学和工程问题涉及大量变量。同样，它们被认为是高维的。这类问题的例子包括量子力学、分子生物学和经济学。例如，p粒子的薛定谔方程的维为d=3p；具有大量粒子的系统在物理和化学上都有很大的兴趣。这个问题只能用数值方法来解决。在几十年的工作中，科学家们发现，随着p的增加，这个问题变得越来越难。研究人员认为，这并不是因为没有创造出好的数值方法--困难是内在的。研究人员认为，在经典计算机上求解薛定谔方程会受到维度诅咒的影响。也就是说，解决这个问题的时间必须随着p的增加而呈指数增长。(经典计算机是任何不基于量子力学原理的机器--今天使用的所有机器都是经典计算机。)研究人员希望证明这个问题在量子计算机上是可以处理的。这项研究的成功将标志着一个重要的非人工问题得到证实的指数量子加速的第一个实例。

New proof techniques and new optimal algorithms and complexityresults will be obtained under the grant. Many important scientific andengineering problems have continuous mathematical formulations. Sincedigital computers can only deal with numbers, continuous problem have tobe discretized for input into the computer. Hence the information aboutthe continuous mathematical problem is partial and contaminated and onlyan E-approximation can be obtained. Because the information about thecontinuous problem is partial and contaminatedone can use adversary arguments pioneered by the investigators and theircolleagues to obtain computational complexity and optimal algorithms forimportant problems. This may be contrasted with discrete problems such asinteger factorization, where one has to settle for conjectures about thecomplexity hierarchy. A central issue is to determine for which settingsand spaces a problem is tractable; that is, its complexity is notexponential. There is a huge literature on the computational complexity ofd-dimensional problems. Most of these papers and books obtain resultswhich are sharp with respect to 1/E but have, unfortunately, unknowndependence on d. But to determine if a problem is tractable, we need toknow the dependence on both 1/E and d. This requires new proof techniques. Many important scientific and engineering problems involve a largenumber 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 hasdimension d = 3p; systems with a large number of particles are of greatinterest in physics and chemistry. This problem can only be solvednumerically. In decades of work scientists have found that the problemsget increasingly hard as p increases. The investigators believe this doesnot stem from a failure to create good numerical methods--the difficultyis intrinsic. The investigators believe solving the Schrodinger equationsuffers the curse of dimensionality on a classical computer. That is, thetime to solve this problem must grow exponentially with p. (A classicalcomputer is any machine not based on the principles of quantummechanics--all machines in use today are classical computers.) Theinvestigators hope to show this problem is tractable on a quantumcomputer. Success in this research would mark the first instance of aPROVEN exponential quantum speedup for an important non-artificialproblem.