Complexity-Theoretic Limitations on Quantum Algorithms for Topological Data Analysis

Abstract

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.

19 pages, 4 figures

References in corpus (3)

• Quantum algorithm for solving linear systems of equations
• An introduction to quantum machine learning
• Focus beyond quadratic speedups for error-corrected quantum advantage

Cited by in corpus (6)

• Clique Homology is QMA1-hard
• The topology of data hides in quantum thermal states
• Quantum topological data analysis via the estimation of the density of states
• Quantum Algorithm for Estimating Betti Numbers Using Cohomology Approach
• Provable quantum speedups for computing persistence in topological data analysis
• Topological Signal Processing on Quantum Computers for Higher-Order Network Analysis