Quantum and Classical Complexity of Multivariate Problems

Traub和Wozniakowski基于信息的复杂性的目标是为具有部分、污染和定价信息的问题创建计算复杂性理论和优化算法，并将结果应用于解决不同学科中的特定问题。简而言之，基于信息的复杂性将被称为IBC。这一理论是在抽象空间上发展起来的，通常是希尔伯特和Banach空间，而应用则是多变量问题。由于信息是局部的和受污染的，只能得到近似解。IBM研究各种环境下计算e-近似的计算复杂性和最优算法。由于最坏情况的设置通常会导致不可解和难解等负面结果，因此还研究了具有弱保证的设置，如平均设置、概率设置和随机设置。IBC研究的一个相当新的领域是量子计算。到目前为止发现的最著名的算法Shor和Grover是针对离散问题的。但是，科学和工程中出现的许多问题是持续不断的。例如高维和路径积分、高维近似和偏微分方程组。要理解量子计算对于连续问题的能力，我们必须知道这些问题在不同环境下在经典计算机上的计算复杂性。这正是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?