QIP 2023：亚马逊量子计算三篇论文突破

量子技术

某机构在QIP 2023发表的量子计算论文

针对“超级Grover”优化、拓扑数据分析的量子算法以及物理系统模拟的研究，展示了某机构在量子计算领域的广泛兴趣。

作者： Fernando Brandão

日期： 2023年2月2日

阅读时间： 7分钟

在今年的量子信息处理大会（QIP）上，某机构量子技术小组的研究人员共同发表了三篇论文，展示了该小组研究兴趣的广度。

在《弥合鸿沟：通过跳转至终点实现超越Grover的量子加速》一文中，研究科学家Alexander Dalzell、量子研究科学家Nicola Pancotti，与谢菲尔德大学和Riverlane的Earl Campbell共同提出了一种量子算法，该算法提高了Grover算法的效率。Grover算法是少数几个被证明相对于经典算法具有加速效果的量子算法之一。尽管对Grover算法的改进很小，但它打破了一个此前未被突破的性能瓶颈，并指出了一种可能带来更大改进的方法论。

在《一种用于拓扑数据分析的简化量子算法，量子比特需求呈指数级减少》一文中，研究科学家Sam McArdle、亚琛工业大学的Mario Berta和布达佩斯阿尔弗雷德·雷尼数学研究所的András Gilyén研究了拓扑数据分析，这是一种用于分析大数据的技术。他们提出了一种新的拓扑数据分析量子算法，与现有量子算法相比，该算法实现了二次加速，并且量子内存的使用效率呈指数级提高。

加州理工学院研究生、论文完成时在某机构实习的Chi-Fang (Anthony) Chen凭借《稀疏随机哈密顿量的量子易解性》一文荣获会议最佳学生论文奖。该论文的合作者包括Alex Dalzell、Mario Berta、加州理工学院的Joel Tropp。该论文研究了使用量子计算机模拟量子系统的物理性质。他们证明了，对于特定类型的物理系统模型（即稀疏随机哈密顿量），在量子计算机上以高概率进行高效模拟是可行的。

超越Grover的量子加速

Grover算法是已知的少数几个相比经典计算能提供加速的量子算法之一。例如，对于3-SAT问题（涉及寻找满足形式逻辑表达式约束的N个变量的值），暴力经典算法的运行时间与2^N成正比；而Grover算法的运行时间与2^(N/2)成正比。

绝热量子计算是一种量子计算方法，其中，量子系统被制备成其最低能量状态（“基态”）编码了一个相对简单问题的解。然后，系统的某个参数（例如磁场强度）逐渐改变，使系统编码一个更复杂的问题。如果系统在这些变化中始终保持基态，它最终将编码复杂问题的解。

然而，随着参数的改变，系统的基态与第一激发态之间的间隙会发生变化，有时会变得极小。如果参数变化过快，系统可能会跃迁到某个激发态，从而破坏计算。

在《弥合鸿沟：通过跳转至终点实现超越Grover的量子加速》中，我们证明，对于一类重要的优化问题，可以进行参数设置的初始跳转，该跳转不会导致系统进入更高能量状态的风险。然后，第二次跳转将参数直接设置为其最大值。大多数情况下这会失败，但偶尔会成功：系统保持在基态，从而解决问题。初始跳转越大，成功率的提升也越大。

我们的论文证明了该算法相对于Grover算法具有微小但可量化的优势，并报告了一系列数值实验以确定该方法的实用性。这些实验表明，该方法实际带来的效率提升比数学上能证明的还要多，尽管其规模仍不足以带来巨大的实际效益。我们期望这种方法能带来进一步的改进，从而对未来量子计算机的实际应用产生影响。

拓扑数据分析

拓扑学是数学的一个分支，它在高度抽象的层面上处理几何问题：根据拓扑描述，任何具有相同孔洞数量的两个物体（例如，一个咖啡杯和一个甜甜圈）是相同的。

将大数据映射到一个拓扑对象（或流形）上，可以实现较低抽象层次上难以进行的分析。例如，由于拓扑描述在形状变换下保持不变，它们对数据中的噪声具有鲁棒性。

拓扑数据分析通常涉及计算持久贝蒂数，它表征流形中孔洞的数量，这一属性可能对底层数据具有重要含义。在《一种用于拓扑数据分析的简化量子算法，量子比特需求呈指数级减少》中，作者提出了一种用于计算持久贝蒂数的新量子算法。与经典算法相比，它提供了二次加速，并且相比现有量子算法，其量子内存的使用效率呈指数级提高。

数据可以表示为多维空间中的点，拓扑映射可以看作是在点之间绘制线段以生成表面，类似于动画师创建3D对象的网格轮廓。线段的最大长度定义了映射的长度尺度。

在足够短的长度尺度下，数据将被映射到大量的三角形、四面体及其高维类比物（统称为单纯形）。随着长度尺度的增加，单纯形连接起来形成更大的复合体，结果流形中的孔洞逐渐消失。持久贝蒂数是在一系列较长长度尺度范围内持续存在的孔洞数量。

研究人员的主要见解是，尽管表示空间的维度可能很高，但在大多数实际情况下，孔洞的维度要低得多。研究人员定义了一组边界算子，用于在表示空间中寻找复合体（单纯形的组合）的边界（例如3D形状的表面）。反过来，边界算子（更准确地说，它们的特征向量）提供了空间的新几何描述，其中空间区域被分类为孔洞或非孔洞。

由于孔洞通常是低维的，因此空间也是低维的，这使得研究人员能够引入一种指数级更紧凑的单纯形到量子比特的映射，从而大幅减少了算法所需的空间资源。

稀疏随机哈密顿量

量子计算可能实现相比经典计算有用加速的问题范围仍不清楚。但量子计算可能具有优势的一个领域是模拟量子系统，如分子。这类模拟可以在生物化学和材料科学等领域带来深刻见解。

在量子模拟中，我们通常关注量子系统的低能量属性。但一般来说，证明给定量子算法能够将量子系统制备到低能量状态是困难的。量子系统的能量由其哈密顿量定义，哈密顿量可以表示为一个矩阵。在《稀疏随机哈密顿量的量子易解性》中，我们证明，对于几乎所有稀疏（即非零元素很少）且随机（即非零元素的位置随机分配）的哈密顿矩阵，制备低能量状态是可行的。

此外，我们证明了制备这种状态的方法就是简单地将存储模型的量子内存初始化为一个随机状态（称为制备最大混合态）。

我们证明的关键是将一个关于稠密矩阵的著名结果——高斯酉系综（GUE）的维格纳半圆分布——推广到稀疏矩阵。从哈密顿量计算量子系统的能级涉及计算哈密顿量矩阵的特征值，这是线性代数中的标准操作。维格纳证明了随机稠密矩阵的特征值形成一个半圆分布。这意味着，随机矩阵的可能特征值不会以一个长尾的形式无限延伸；相反，它们有明确的界点。在某些清晰定义的阈值之上和之下没有可能的取值。

然而，稠密哈密顿量在自然界中很少见。描述物理学家和化学家关心的多数物理系统的哈密顿量都是稀疏的。通过证明稀疏哈密顿量符合与稠密哈密顿量相同的半圆分布，我们证明了测量量子模拟的低能量状态所需的实验次数不会呈指数级增长。

在论文中，我们还证明任何低能量状态都必须具有不可忽略的量子电路复杂性，这表明经典计算机无法高效计算它——这论证了使用量子计算机模拟量子系统的必要性。

关于作者

Fernando Brandão

Fernando Brandão是某机构的应用科学总监，也是加州理工学院的布伦理论物理学教授。FINISHED