  Even after decades of quantum computing development, examples of generally
useful quantum algorithms with exponential speedups over classical counterparts
are scarce. Recent progress in quantum algorithms for linear-algebra positioned
quantum machine learning (QML) as a potential source of such useful exponential
improvements. Yet, in an unexpected development, a recent series of
"dequantization" results has equally rapidly removed the promise of exponential
speedups for several QML algorithms. This raises the critical question whether
exponential speedups of other linear-algebraic QML algorithms persist. In this
paper, we study the quantum-algorithmic methods behind the algorithm for
topological data analysis of Lloyd, Garnerone and Zanardi through this lens. We
provide evidence that the problem solved by this algorithm is classically
intractable by showing that its natural generalization is as hard as simulating
the one clean qubit model -- which is widely believed to require
superpolynomial time on a classical computer -- and is thus very likely immune
to dequantizations. Based on this result, we provide a number of new quantum
algorithms for problems such as rank estimation and complex network analysis,
along with complexity-theoretic evidence for their classical intractability.
Furthermore, we analyze the suitability of the proposed quantum algorithms for
near-term implementations. Our results provide a number of useful applications
for full-blown, and restricted quantum computers with a guaranteed exponential
speedup over classical methods, recovering some of the potential for
linear-algebraic QML to become one of quantum computing's killer applications.
