量子算法实现拓扑数据分析中洞的持续性计算，理论证明比经典方法快得多。
Provable quantum speedups for computing persistence in topological data analysis
- 用调制稀疏哈密顿量编码洞的持续性，构造谐波代表态作为引导态
- 证明该问题为BQP₁-难，标准假设下存在指数级量子加速
- 首次严格证明量子优势，适合关注量子计算理论的学者
拓扑数据分析（TDA）通过考察数据集拓扑中洞的数量与持续性，提取抗噪声特征。本文提出一种高效量子算法，解决与核心任务密切相关的问题：判断给定洞是否在不同尺度下持续存在。进一步证明该问题本身属于BQP₁-难，这意味着经典计算极难求解；这与以往所有量子TDA方法不同，此前的方法要么对量子计算机也难以处理，要么尚未有严格的经典难解性证明。在标准复杂度理论假设下，本结果意味着该问题存在指数级量子加速。方法核心是将洞的持久性编码为一种变体的引导稀疏哈密顿量问题，其中引导态由洞的调和代表态构造而成。
原文摘要 · Abstract (English)
Topological data analysis (TDA) aims to extract noise-robust features from a data set by examining the number and persistence of holes in its topology. We provide an efficient quantum algorithm for a computational problem closely related to a core task in TDA -- determining whether a given hole persists across different length scales. Further, we prove the problem itself is $\mathsf{BQP}_1$-hard, implying that a classical solution is extremely unlikely; this stands in contrast to all previous quantum approaches to TDA, where the problems were also intractable for quantum computers, or where a rigorous proof of classical hardness still remains open. This result implies an {exponential} quantum speedup for this problem under standard complexity-theoretic assumptions. Our approach relies on encoding the persistence of a hole in a variant of the guided sparse Hamiltonian problem, where the guiding state is constructed from a harmonic representative of the hole.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。