《量子算法及应用》美空军AFRL32页技术报告

最近量子优势的展示使我们完全进入了含噪、中尺度量子（NISQ）设备的时代。尽管如此，目前仍不清楚哪些问题最适合于量子加速。在这份报告中，我们描述了博思艾伦-汉密尔顿公司量子研究团队在区分量子计算机在哪些方面可以比经典计算更有优势方面取得的进展。我们通过三个基本问题探索量子算法在哪些方面可以加速重要的经典方法：

(1) 哪些重要算法的常见子程序可以通过量子计算变得更有效率？

(2) 什么时候可以完全避免这些常见的子程序？

(3) 什么时候我们对经典算法的了解太有限而存在更好的经典子程序？

我们通过探索以下三个研究课题来研究这些问题：

(a) 首先，我们研究在局部查询模型中寻找标记状态的量子行走算法。

(b) 其次，我们利用蒙特卡洛技术模拟各种量子哈密尔顿，研究已知的对经典计算机的阻碍。

(c) 最后，我们探索量子线性系统问题（QLSP）的近期可实施的量子算法。

我们对(a)和(b)项的研究是以纯理论研究的方式进行的，而对(c)项则是以理论和计算的方式进行。对于(a)项，我们已经找到了可以推进量子步行算法的方法，以利用纯粹的局部查询来探索任意的、未知的空间，同时也采用了非常新的技术来加速解决布尔可满足性（和优化）问题。对于(b)项，我们引入了一种新的经典的准分子时间算法来处理由于特定量子态的𝐿1和𝐿2规范之间的指数分离而产生的障碍。对于(c)，我们目前正在开发代码以在Qiskit中实现QLSP，同时也在研究改进Lin和Tong最近的进展的渐近扩展的可能性。

我们将分别介绍这些研究工作，并指定章节介绍其方法和结果。这三项工作的结论以及它们的总体主题将一起提出。此外，通过履行该合同，博思艾伦公司为AFRL的实验小组提供了广泛的支持，包括LaHaye超导qubit实验室和Soderberg-Tabakov Ytterbium（Yb）离子诱捕工作。