Complexity-Theoretic Limitations on Quantum Algorithms for Topological Data Analysis
Alexander Schmidhuber, Seth Lloyd · PRX Quantum · 2023
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.