CAREER: Efficient Computation in the Physical World

该奖项是根据2009年美国复苏和再投资法案（公法111-5）资助的。量子计算是一个科学领域，它结合了计算机科学和物理学中一些最深奥的知识问题。最终，我们想知道：在物理宇宙中，什么是可计算的，什么是不可计算的？经过15年的努力，量子计算理论似乎已经达到了一个阶段，进一步的发展必然需要经典计算理论的进步。提出的研究包含了推进这两个领域的具体想法，并将深化量子计算与经典复杂性理论前沿主题之间的联系。这项研究解决了关于经典计算机和量子计算机的能力的一些最难的“障碍问题”。这类问题的例子包括：允许使用高效量子算法的问题有多大？我们能不能找到证据，证明这个类是在经典计算的整个“多项式层次”之外的？粗略地说，这意味着量子计算机可以比经典计算机更快地解决某些问题，甚至可以比经典计算机更快地检查答案？除了“结构化”问题，比如寻找周期函数的周期（肖尔分解算法的核心），量子计算机是否还能以指数级快的速度解决“非结构化”问题？我们能否超越理想化的“黑箱模型”，获得利用量子电路结构的“非相对论化结果”？这个模型几乎囊括了复杂性理论家目前所知道的关于量子计算机能力的一切。我们能否更好地理解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?