Quantum and Classical Complexity of Multivariate Problems

基于信息的复杂性(IBC)研究物理科学、经济、工程和数学金融中出现的连续问题的最优算法和计算复杂性。IBC研究了路径积分、偏微分方程组、常微分方程组、非线性方程、积分方程组、不动点和积分等连续问题。这些问题通常需要数值求解，因此误差几乎在e以内。这些问题通常涉及大量的变量，数量在数百或数千之间。如果要求e近似的最坏情况保证，那么计算的复杂性以指数形式依赖于变量的数量；问题遭受“维度诅咒”。研究人员和他们的同事试图通过满足于随机保证(平均、概率、随机)或使用关于应用的领域知识来克服诅咒。研究人员还在研究量子计算对连续问题的能力。要理解连续问题的量子计算的能力，就必须知道这些问题在各种环境下在经典计算机上的计算复杂性。这正是IBC所研究的。最近，研究人员引入了一种新的量子设置，其中允许随机提问。他们已经证明，对于路径积分，与标准量子设置相比，量子比特的复杂性有指数级的提高。这一点很重要，因为在可预见的未来，量子比特的数量是一个关键的资源。研究人员和他们的同事提出的问题包括：对于其他连续的问题，查询和量子比特的复杂性是什么？查询和量子比特的复杂性之间是否存在权衡？大约40年来，计算一直由摩尔定律驱动，摩尔定律是一种经验观察，即计算能力大约每18个月翻一番。强大的计算机对我们的经济实力和国家安全至关重要。他们让互联网成为可能。由于许多原因，专家们一致认为，使用当前硅技术的摩尔定律将在大约10到15年内结束。这些原因包括逻辑门和导线缩小到原子尺寸，芯片变得更小和更快而产生的巨大热量，以及制造设施的成本。由于保持摩尔定律的轨迹是如此重要，人们正在考虑新的计算方法。最有希望的想法之一是利用量子力学的原理来进行量子计算。研究人员和他们的同事正在研究以下问题：如果物理学家和化学家成功地建造了量子计算机，那么在量子计算机上解决科学和工程中的哪些连续问题可以比在经典计算机上快得多？

Information-based complexity (IBC) studies optimal algorithms andcomputational complexity for the continuous problems which arise inphysical science, economics, engineering, and mathematical finance.IBC has studied such continuous problems as path integration, partialdifferential equations, systems of ordinary differential equations,nonlinear equations, integral equations, fixed points, and integration.Usually these problems have to be solved numerically and thereforeapproximately to within error e. Often these problems involve a verylarge number of variables numbering in the hundreds or thousands. If aworst case assurance of an e-approximation is demanded, then thecomputational complexity depends exponentially on the number of variables;the problem suffers the "curse of dimensionality". The investigators andtheir colleagues attempt to vanquish the curse by settling for astochastic assurance (average, probabilistic, randomized) or by usingdomain knowledge about the application. The investigators are alsostudying the power of quantum computation for continuous problems. Tounderstand the power of quantum computation for continuous problems onemust know the computational complexity of these problems on a classicalcomputer in various settings. This is exactly what has been studied inIBC. Recently the investigators introduced a new quantum setting in whichrandomized queries are permitted. They have shown that for pathintegration there is an exponential improvement for the qubit complexitycompared to the standard quantum setting. This is important since thenumber of qubits is a critical resource for the foreseeable future. Amongthe questions the investigators and their colleagues stydying are:What are the query and qubit complexities for other continuous problems?Are there trade-offs between query and qubit complexities?For some forty years, computing has been driven by Moore's Law which isthe empirical observation that computing power doubles about every 18months. Powerful computers have been crucial for our economic strengthand our national security. They have made the internet possible. For anumber of reasons the consensus among experts is that Moore's Law usingcurrent silicon technology will end in some 10 to 15 years. These reasonsinclude the shrinkage of logic gates and wires to atomic size, the tre-mendous heat generated as chips get smaller and faster, and the cost offabrication facilities. Since it is so important to maintain theMoore's Law trajectory, new ways to compute are being considered. Oneof the most promising ideas is to use the principles of quantum mechanicsto do quantum computing. The investigators and their colleagues arestudying the following question: If physicists and chemists succeed inbuilding quantum computers, which continuous problems arising in scienceand engineering can be solved much faster on a quantum computer than on aclassical computer?