论文标题
简化的量子算法用于拓扑数据分析，量子较少的量子
A streamlined quantum algorithm for topological data analysis with exponentially fewer qubits
论文作者
论文摘要
数据集的拓扑不变性，例如从一个长度尺度到另一个长度（持续的betti数字）生存的孔数，可用于在机器学习应用程序中分析和分类数据。我们提出了一种改进的量子算法，用于计算持续的betti数字，并提供端到端的复杂性分析。我们的方法可在现有的量子算法上进行大量的多项式时间改进，并节省指数空间。在受差距依赖性的前提下，我们的算法在数据标记数量的数量中获得了几乎Quintic的加速，而不是先前已知的严格经典算法，用于计算持续的betti编号到常数加法错误 - 应用程序的显着任务。但是，我们还引入了一种量子启发的经典功率方法，其可证明的缩放仅比量子算法更差。这提供了一种可证明的经典算法，并具有与现有的经典启发式方法相当的缩放。我们讨论量子算法是否可以实现实践利益任务的指数加速。我们得出的结论是，目前没有证据表明情况。
Topological invariants of a dataset, such as the number of holes that survive from one length scale to another (persistent Betti numbers) can be used to analyze and classify data in machine learning applications. We present an improved quantum algorithm for computing persistent Betti numbers, and provide an end-to-end complexity analysis. Our approach provides large polynomial time improvements, and an exponential space saving, over existing quantum algorithms. Subject to gap dependencies, our algorithm obtains an almost quintic speedup in the number of datapoints over previously known rigorous classical algorithms for computing the persistent Betti numbers to constant additive error - the salient task for applications. However, we also introduce a quantum-inspired classical power method with provable scaling only quadratically worse than the quantum algorithm. This gives a provable classical algorithm with scaling comparable to existing classical heuristics. We discuss whether quantum algorithms can achieve an exponential speedup for tasks of practical interest, as claimed previously. We conclude that there is currently no evidence for this being the case.
