AF: Small: Quantum Algorithms Arising from Ideas in Physics

AF：小：源自物理学思想的量子算法

• 批准号: 1525130
• 负责人: Peter Shor
• 金额: $ 32.74万
• 依托单位: Massachusetts Institute of Technology
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2015
• 资助国家: 美国
• 起止时间: 2015-08-01 至 2019-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1525130&HistoricalAwards=false
• 关键词: AF; Small; Quantum; Algorithms; Arising

Currently, quantum computers are able to manipulate no more than a few handfuls of qubits. However, it is widely expected that in the next few decades, quantum computers that are large enough to do interesting things will be built. Currently, the most lucrative application of these appear to be in the areas of cryptography and the areas of simulation of quantum mechanics, which it is hoped will have great impact in the areas of physics, chemistry, and pharmaceutical research. However, a toolbox of techniques for designing algorithms could give quantum computers a much greater impact, if algorithms could be developed for them that speed up other classes of problems, especially ones that speed up finding either the optimal or approximation solutions for combinatorial search problems.The PIs intend to investigate several algorithms in quantum computing, approaching them by using ideas from physics, computer science, and mathematics. The PIs view quantum information science as a branch of all of these disciplines, and believe that techniques from each area can open insights into the others. The questions the PIs intend to address are related to algorithms and protocols: (1) exploration instances of adiabatic quantum algorithms where they outperform classical algorithms, (2) an in-depth study of knot-based quantum money schemes, (3) an attempt to solve quantum versions of the satisfiability problem, and (4) investigate quantum approximate optimization algorithms.

目前，量子计算机只能操纵几个量子比特。然而，人们普遍预计，在未来几十年内，将建造足够大的量子计算机来做有趣的事情。目前，这些技术最有利可图的应用似乎是在密码学和量子力学模拟领域，希望这将对物理，化学和制药研究领域产生重大影响。然而，如果能为量子计算机开发出加速其他类型问题的算法，特别是那些加速寻找组合搜索问题的最优或近似解的算法，那么设计算法的技术工具箱可能会给量子计算机带来更大的影响。PI打算研究量子计算中的几种算法，通过使用物理学，计算机科学和数学的思想来接近它们。PI将量子信息科学视为所有这些学科的一个分支，并相信每个领域的技术都可以为其他领域提供见解。 PI打算解决的问题与算法和协议有关：（1）绝热量子算法的探索实例，它们优于经典算法，（2）对基于结的量子货币方案的深入研究，（3）尝试解决量子版本的可满足性问题，以及（4）研究量子近似优化算法。