Will there be a useful quantum advantage for topological data analysis?

 

We don't know yet. 

Prominent applications of topological data analysis (TDA) including Mapper-based visualisation are based on fast and interpretable heuristics. While quantum TDA may speed up the calculation of high-dimensional Betti numbers, it doesn't help with understanding when and why high-dimensional topological features might be important, and whether they need to be computed to high precision or classical Monte Carlo methods can give a sufficient accuracy in practice. What high-dimensional Betti numbers might be good for needs to be determined empirically using machine learning benchmark datasets and the best classical algorithms.

Beyond the Betti number problem, for which quantum algorithms have already been proposed, it will be interesting to explore what other TDA methods could be sped up using quantum subroutines. For example, the nonzero eigenvalues of the persistent Laplacian also seem to be useful as features for machine learning algorithms, in contrast to traditional persistent homology methods that focus only on the zero or near-zero eigenvalues of the persistent Laplacian. The speedup for quantum persistent homology comes from being able to construct the persistent Laplacian exponentially faster the best-known classical methods. If there is useful information that can be extracted from the persistent Laplacian without requiring the quantum singular value transformation or rejection sampling, the resource requirements for a quantum advantage would be reduced enormously.

Thanks to the the team at QCWare for inviting me to give a seminar on this topic and the thought-provoking discussions afterwards!