Quantum and Classical Complexity of Continuous Problems

连续问题的量子和经典复杂性

• 批准号: 0429211
• 负责人: Joseph Traub
• 金额: $ 36.06万
• 依托单位: Columbia University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2005
• 资助国家: 美国
• 起止时间: 2005-03-15 至 2008-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0429211&HistoricalAwards=false
• 关键词: Quantum; Classical; Complexity; Continuous; Problems

For some 40 years, computing has been driven by Moore's law which is the empirical observation that computing power doubles about every 18 months. This has made it possible for people to have computers in their homes as powerful as computers owned by corporations just 20 years ago. It has made the internet possible. Finally, powerful computers are indispensable to our national security. Computer chips and wires are getting so small that there is a consensus among technologists that Moore's law will end in 10 to 15 years using current silicon technology. Since it is critical for our country to maintain the Moore's law trajectory, new ways to compute are being considered. One of the most promising ideas is to use the principles of quantum mechanics to do quantum computing. The investigators and their colleagues are studying the following question: If physicists and chemists succeed in building quantum computers, for which problems are there the big payoffs? That is, what are the killer applications?The goal of information-based complexity (IBC) is to create a theory of computational complexity and optimal algorithms for problems with partial, contaminated and priced information, and to apply the results to solving specific problems in varied disciplines. The theory is developed over abstract spaces while the applications are for multivariate problems. Since the information is partial and contaminated, only approximate solutions can be obtained. IBC studies computational complexity and optimal algorithms for computing approximations in various settings, such as the worst case, average, probabilistic and randomized settings. A new area of IBC research is quantum computing. The best known algorithms due to Shor and Grover are for discrete problems. But many problems occurring in science and engineering are continuous. Examples include high-dimensional and path integration, high-dimensional approximation, partial differential equations and integral equations. To understand the power of quantum computation for continuous problems one must know the computational complexity of these problems on a classical computer in various settings. This is exactly what has been studied in IBC. Questions to be answered include: For what problems is quantum computation exponentially or polynomially faster than classical computation? For what problems is there provably no speedup of quantum over classical computation? In addition, the investigators study randomization, breaking intractability by using additional domain knowledge, and a statistical model for a medical application.INTELLECTUAL IMPACTThe investigators have been working together on the core of IBC since 1973. Today there are many scores of researchers around the world working on IBC. The Journal of Complexity contains mainly IBC papers; in 2004 the Journal published 1000 pages in 6 issues. The investigators and their students participate in many international conferences and workshops. In addition to developing the core of IBC, the investigators apply it to a number of disciplines. The interdisciplinary research is published in journals of the application discipline. Examples are economics, physics, and mathematical finance.BROADER IMPACT OF THE RESEARCHThe investigators teach a graduate course, "Continuous Algorithms and Complexity" which teaches students the fundamentals of IBC. The course is also offered every year through the Columbia Video Network. Starting in Spring 2004, the investigators offered the first course on quantum computing at Columbia University. The investigators' graduate students attend professional meetings and present talks when they have done significant work. One of their graduate students, Krysta Svore, is working on quantum computing. She has presented a number of talks at international conferences.

大约40年来，计算一直受到摩尔定律的驱动，摩尔定律是一种经验观察，即计算能力大约每18个月翻一番。 这使得人们有可能在家里拥有与20年前公司拥有的计算机一样强大的计算机。它使互联网成为可能。 最后，强大的计算机对我们的国家安全是不可或缺的。 计算机芯片和导线变得如此之小，以至于技术专家们一致认为，使用目前的硅技术，摩尔定律将在10到15年内结束。由于对我国来说，保持摩尔定律的轨迹至关重要，因此正在考虑新的计算方法。 最有前途的想法之一是利用量子力学原理进行量子计算。 研究人员和他们的同事正在研究以下问题：如果物理学家和化学家成功地建造了量子计算机，那么哪些问题会有巨大的回报？ 也就是说，杀手级应用程序是什么？基于信息的复杂性（IBC）的目标是建立一个计算复杂性的理论和最优算法的问题与部分，污染和定价的信息，并将其结果应用于解决特定的问题在不同的学科。 该理论是在抽象空间上发展的，而应用程序是多变量问题。由于信息是部分的和污染的，只能得到近似解。 IBC研究计算复杂性和在各种设置中计算近似的最佳算法，例如最坏情况，平均值，概率和随机设置。IBC研究的一个新领域是量子计算。 由于Shor和Grover最著名的算法是离散问题。 但是，科学和工程中出现的许多问题是连续的。 例子包括高维和路径积分，高维近似，偏微分方程和积分方程。 为了理解量子计算对连续问题的能力，我们必须知道这些问题在各种设置下在经典计算机上的计算复杂性。 这正是IBC所研究的。 需要回答的问题包括：对于什么问题，量子计算比经典计算快指数或多项式？ 对于哪些问题，量子计算相对于经典计算的加速是不可证明的？ 此外，研究人员还研究随机化，通过使用额外的领域知识来打破棘手问题，以及用于医学应用的统计模型。智力影响研究人员自1973年以来一直在IBC的核心上合作。今天，世界各地有许多研究人员在研究IBC。 《复杂性杂志》主要收录了IBC的论文; 2004年，该杂志共出版了6期，共1000页。 研究人员和他们的学生参加了许多国际会议和研讨会。 除了开发IBC的核心，研究人员还将其应用于许多学科。 跨学科研究发表在应用学科的期刊上。 例如经济学、物理学和数理金融学。研究的更广泛影响研究人员教授研究生课程“连续算法和复杂性”，向学生教授IBC的基础知识。 该课程每年还通过哥伦比亚视频网络提供。从2004年春天开始，研究人员在哥伦比亚大学开设了第一门量子计算课程。 研究人员的研究生参加专业会议，并在完成重要工作时发表演讲。 他们的一名研究生Kavia Svore正在研究量子计算。 她在国际会议上发表了许多演讲。