Quantum and Classical Complexity of Multivariate Problems

基于信息的复杂性的目标是为部分、污染和定价信息的问题创建计算复杂性的理论和最佳算法，并将结果应用于解决不同学科的具体问题。为简洁起见，将基于信息的复杂性称为IBC。该理论是在抽象空间上发展起来的，典型的是希尔伯特和巴拿赫空间，而应用于多变量问题。由于信息是局部的和受污染的，所以只能得到近似解。ibc研究在各种设置下计算e逼近的计算复杂性和最优算法。由于最坏的情况通常会导致诸如不可解性和难解性等负面结果，因此我们也研究了具有较弱保证的情况，如平均、概率和随机设置。IBC研究的一个相当新的领域是量子计算。迄今为止发现的最著名的算法，肖尔和格罗弗，是针对离散问题的。但是，科学和工程领域出现的许多问题是连续不断的。例子包括高维和路径积分、高维近似和偏微分方程。为了理解量子计算对连续问题的能力，我们必须了解这些问题在不同设置下经典计算机上的计算复杂性。这正是IBC研究的结果。要回答的问题包括：对于什么问题，量子计算（指数、多项式）比经典计算快？对于哪些问题，量子计算可以证明比经典计算没有加速？大约40年来，计算一直由摩尔定律驱动，摩尔定律是一种经验观察，即计算能力大约每18个月翻一番。这使得人们在家里拥有电脑成为可能，就像20年前公司拥有的电脑一样强大。它使互联网成为可能。最后，强大的计算机对我们的国家安全是不可或缺的。计算机芯片和电线变得如此之小，以至于技术专家们一致认为，使用目前的硅技术，摩尔定律将在10到15年内终结。由于保持摩尔定律轨迹对我国至关重要，因此正在考虑新的计算方法。最有希望的想法之一是利用量子力学原理进行量子计算。研究人员和他们的同事正在研究以下问题：如果物理学家和化学家成功地建造了量子计算机，那么哪些问题会有很大的回报？也就是说，杀手级应用程序是什么？

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?