CAREER: Efficient Computation in the Physical World

职业：物理世界的高效计算

• 批准号: 0844626
• 负责人: Scott Aaronson
• 金额: $ 57.87万
• 依托单位: Massachusetts Institute of Technology
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2009
• 资助国家: 美国
• 起止时间: 2009-06-01 至 2014-05-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0844626&HistoricalAwards=false
• 关键词: CAREER; Efficient; Computation; Physical; World

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?

该奖项是根据2009年美国复苏和再投资法案（公法111-5）资助的。量子计算是一个科学领域，结合了计算机科学和物理学的一些最深层次的智力问题。最终，我们想知道：在物理宇宙中，什么是可计算的，什么是不可计算的？ 经过15年的努力，量子计算理论似乎已经达到了一个点，进一步的进展必然会带来经典计算理论的进步。该研究计划包含了推进这两个领域的具体想法，并将深化量子计算与经典复杂性理论前沿课题之间的联系。这项研究解决了一些关于经典和量子计算机能力的最困难的“障碍问题”。这样的问题的例子包括：有多大的类的问题，承认有效的量子算法？我们能否获得证据，证明这个类位于经典计算的整个“多项式层次”之外--除了找到周期函数的周期（Shor因子分解算法的核心）等“结构化”问题之外，量子计算机是否可以以指数级的速度解决“非结构化”问题？我们能否超越理想化的“黑箱模型”，获得利用量子电路结构的“非相对化结果”？我们能否更好地理解在P与NP及相关问题上取得进展的障碍？