Tractability of High Dimensional Problems for Quantum and Classical Computers

量子和经典计算机高维问题的可处理性

• 批准号: 0914345
• 负责人: Joseph Traub
• 金额: $ 47.34万
• 依托单位: Columbia University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2009
• 资助国家: 美国
• 起止时间: 2009-09-01 至 2012-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0914345&HistoricalAwards=false
• 关键词: Tractability; Dimensional; Problems; Quantum; Classical

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.

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