论文标题
用于拓扑数据分析的量子算法的复杂性理论限制
Complexity-Theoretic Limitations on Quantum Algorithms for Topological Data Analysis
论文作者
论文摘要
拓扑数据分析（TDA）的量子算法似乎比最佳的经典方法具有指数优势，同时又不受去量化程序和数据加载问题的影响。在本文中，我们提供了复杂性理论的证据，即TDA的核心任务（估计Betti数字）即使对于量子计算机也很棘手。具体而言，我们证明，计算Betti数字的问题完全是＃p-hard，而将betti数字近似为乘法错误的问题是NP-HARD。此外，如果仅限于TDA的量子算法，这两个问题都会保留其硬度。由于预计量子计算机不会在次指数时间内解决＃p-hard或NP - 硬问题问题，因此我们的结果表明，TDA的量子算法在最坏情况下仅提供多项式优势。我们通过表明劳埃德（Lloyd），加纳龙（Garnerone）和扎纳迪（Zanardi）开发的TDA的开创性量子算法来支持我们的主张，这在几乎所有情况下都超过了最著名的经典方法，而不是最著名的经典方法。最后，我们认为，如果给出输入数据作为简单的规范，而不是作为顶点和边缘列表，则可以恢复指数量子优势。
Quantum algorithms for topological data analysis (TDA) seem to provide an exponential advantage over the best classical approach while remaining immune to dequantization procedures and the data-loading problem. In this paper, we give complexity-theoretic evidence that the central task of TDA -- estimating Betti numbers -- is intractable even for quantum computers. Specifically, we prove that the problem of computing Betti numbers exactly is #P-hard, while the problem of approximating Betti numbers up to multiplicative error is NP-hard. Moreover, both problems retain their hardness if restricted to the regime where quantum algorithms for TDA perform best. Because quantum computers are not expected to solve #P-hard or NP-hard problems in subexponential time, our results imply that quantum algorithms for TDA offer only a polynomial advantage in the worst case. We support our claim by showing that the seminal quantum algorithm for TDA developed by Lloyd, Garnerone and Zanardi achieves a quadratic speedup over the best known classical approach in asymptotically almost all cases. Finally, we argue that an exponential quantum advantage can be recovered if the input data is given as a specification of simplices rather than as a list of vertices and edges.
