Quantum and Classical Complexity of Multivariate Problems

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

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

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?

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