Quantum and Classical Complexity of Multivariate Problems

多元问题的量子和经典复杂性

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

Traub and Wozniakowski The goal of information-based complexity is to create atheory of computational complexity and optimal algorithms forproblems with partial, contaminated, and priced information, andto apply the results to solving specific problems in varieddisciplines. For brevity, information-based complexity will becalled IBC. The theory is developed over abstract spaces,typically Hilbert and Banach spaces, while the applications areto multivariate problems. Because the information is partial andcontaminated, only approximate solutions can be obtained. IBCstudies computational complexity and optimal algorithms forcomputing e-approximations in various settings. Because theworst case setting often leads to negative results such asunsolvability and intractability, settings with a weakerassurance such as average, probabilistic, and randomized settingsare also studied. A fairly new area of IBC research is quantumcomputing. The best known algorithms discovered to date, Shor andGrover, are for discrete problems. But many problems occurringin science and engineering are continuous. Examples includehigh-dimensional and path integration, high-dimensionalapproximation, and partial differential equations. To understandthe power of quantum computation for continuous problems one mustknow the computational complexity of these problems on aclassical computer in various settings. This is exactly what hasbeen studied in IBC. Questions to be answered include: For whatproblems is quantum computation (exponentially, polynomially)faster than classical computation? For what problems is thereprovably no speed-up of quantum over classical computation? For some 40 years, computing has been driven by Moore's law,which is the empirical observation that computing power doublesabout every 18 months. This has made it possible for people tohave computers in their homes as powerful as computers owned bycorporations just 20 years ago. It has made the internetpossible. Finally, powerful computers are indispensable to ournational security. Computer chips and wires are getting so smallthat there is a consensus among technologists that Moore's lawwill end in 10 to 15 years using current silicon technology.Because it is critical for our country to maintain the Moore'slaw trajectory, new ways to compute are being considered. One ofthe most promising ideas is to use the principles of quantummechanics to do quantum computing. The investigators and theircolleagues are studying the following question: If physicistsand chemists succeed in building quantum computers, for whichproblems are there big payoffs? That is, what are the killerapplications?

特劳布和沃兹尼亚科夫斯基 基于信息的复杂性的目标是建立一个计算复杂性的理论和最优算法的问题与部分，污染，和定价的信息，并将其结果应用于解决特定的问题在varieddisciplines。 为简洁起见，基于信息的复杂性将被称为IBC。 该理论是在抽象空间上发展起来的，典型的是Hilbert和Banach空间，而应用则是多变量问题。 由于信息的不完整和污染，只能得到近似解。 IBC研究计算复杂性和最佳算法forcomputing e-近似在各种设置。 由于最坏情况下的设置往往会导致负面的结果，如unsolvability和棘手的，设置与一个较弱的保证，如平均，概率和随机设置也进行了研究。 IBC研究的一个相当新的领域是量子计算。 迄今为止发现的最著名的算法Shor和Grover是针对离散问题的。 但是科学和工程中出现的许多问题是连续的。 例子包括高维和路径积分，高维近似和偏微分方程。 为了理解量子计算对连续问题的威力，我们必须知道这些问题在各种设置下在经典计算机上的计算复杂性。 这正是IBC所研究的。 要回答的问题包括：对于什么问题，量子计算（指数，多项式）比经典计算快？ 对于什么问题，量子计算的速度没有超过经典计算是可以证明的？ 大约40年来，计算一直受到摩尔定律的驱动，这是一个经验性的观察，计算能力大约每18个月就会增加一次。 这使得人们有可能在家里拥有像20年前公司拥有的计算机一样强大的计算机。 它使互联网成为可能。 最后，强大的计算机对我们的国家安全是不可或缺的。 计算机芯片和线路变得如此之小，以至于技术专家们一致认为，使用当前的硅技术，摩尔定律将在10到15年内结束。因为对我们国家来说，保持摩尔定律的轨迹至关重要，所以正在考虑新的计算方法。 最有前途的想法之一是利用量子力学原理进行量子计算。 研究人员和他们的同事正在研究以下问题：如果物理学家和化学家成功地建造了量子计算机，那么哪些问题会有巨大的回报？ 也就是说，这些应用程序是什么？