Tractability of High Dimensional Problems for Quantum and Classical Computers

新的证明技术和新的最佳算法和复杂性的结果将获得的赠款。许多重要的科学和工程问题都有连续的数学公式。由于数字计算机只能处理数字，连续问题必须离散化后输入计算机。因此，关于连续数学问题的信息是部分的和污染的，并且只能得到E-近似。因为关于连续问题的信息是部分的和污染的，所以可以使用由研究人员和他们的同事开创的对抗性论点来获得重要问题的计算复杂性和最优算法.这可能与离散问题形成对比，例如整数分解，其中一个必须解决关于复杂性层次结构的问题。一个中心问题是确定一个问题在什么样的环境和空间下是可处理的;也就是说，它的复杂性不是指数的。关于d维问题的计算复杂性有大量的文献。这些论文和书籍中的大多数得到的结果是尖锐的1/E，但不幸的是，有未知的依赖于d。但要确定一个问题是否易处理，我们需要知道对1/E和d的依赖性。这需要新的证明技术。 许多重要的科学和工程问题涉及大量的变量。等价地说，它们是高维的，这类问题的例子出现在量子力学、分子生物学和经济学中。例如，p粒子的薛定谔方程的维数d = 3 p;具有大量粒子的系统在物理学和化学中具有很大的意义。这个问题只能用数值方法解决。在几十年的工作中，科学家们发现，随着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.