CAREER: Efficient Computation in the Physical World

该奖项是根据2009年美国复苏和再投资法案(公法111-5)资助的。量子计算是一个结合了计算机科学和物理学中一些最深层次的学术问题的科学领域。归根结底，我们想知道：在物理宇宙中，什么是可行的，什么是不可行的？经过15年的努力，量子计算理论似乎已经达到了一个点，在这个点上，进一步的进步必然需要经典计算理论的进步。这项拟议的研究为推动这两个领域的发展提供了具体的想法，并将深化量子计算与经典复杂性理论中的前沿主题之间的联系。这项研究解决了一些关于经典计算机和量子计算机能力的最困难的“障碍问题”。这类问题的例子包括：允许使用高效量子算法的问题类别有多大？我们能不能找到证据证明这一类不属于经典计算的整个“多项式层次”-粗略地说，这意味着量子计算机解决某些问题的速度甚至比经典计算机检查答案的速度快得多？除了寻找周期函数的周期(Shor因式分解算法的核心)这样的“结构化”问题外，量子计算机是否还能以指数级的速度解决比经典计算机更快的“非结构化”问题？我们能否超越理想化的“黑箱模型”，获得利用量子电路结构的“非相对化结果”？黑箱模型涵盖了复杂性理论家目前对量子计算机能力的几乎所有了解。我们能更好地理解在P与NP及相关问题上取得进展的障碍吗？

This award is funded under the American Recovery and Reinvestment Act of 2009 (Public Law 111-5).Quantum computing is a scientific field that combines some of the deepest intellectual concerns of computer science and physics. Ultimately, we want to know: what is and is not feasibly computable in the physical universe? After fifteen years of effort, quantum computing theory seems to have reached a point where further progress will necessarily entail progress in classical computing theory. The proposed research embraces this with concrete ideas for advancing both fields and will deepen the connections between quantum computing and frontier topics in classical complexity theory.This research tackles some of the hardest "barrier problems" about the power of classical and quantum computers. Examples of such problems include: how large is the class of problems that admit efficient quantum algorithms? Can we obtain evidence that this class lies outside the entire "polynomial hierarchy" of classical computation---which, loosely speaking, would imply that quantum computers could solve certain problems much faster than classical computers could even check the answers? Are there "unstructured" problems that quantum computers can solve exponentially faster than classical computers, in addition to "structured" problems such as finding the period of a periodic function (the heart of Shor's factoring algorithm)? Can we go beyond the idealized "black-box model" that encompasses almost everything complexity theorists currently know about the power of quantum computers, to obtain "non-relativizing results" that exploit the structure of quantum circuits? Can we better understand the obstacles to progress on P versus NP and related questions?