Quantum and Classical Complexity of Continuous Problems

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

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.