AF: Small: Quantum Algorithms Arising from Ideas in Physics

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

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.