Extending Quantum topological data analysis to persistent homology

This is a Perspective on "Quantum algorithm for persistent Betti numbers and topological data analysis" by Ryu Hayakawa, published in Quantum 6, 873 (2022).

By Sam McArdle (AWS Center for Quantum Computing).

 

It is an open challenge to design quantum algorithms for machine learning that do not need access to large amounts of data – the efficient loading of which would require challenging-to-construct quantum-RAM [1]. In Ref. [2] a quantum algorithm for topological data analysis was introduced that circumvents the need for a large QRAM. However, it is not possible to apply that algorithm to compute persistent Betti numbers (the number of holes that survive from one length scale to another), which are the key quantity of interest in practical applications of topological data analysis. The work ‘Quantum algorithm for persistent Betti numbers and topological data analysis’ [3] by Hayakawa, recently published in Quantum, overcame this limitation, making it possible to compare classical and quantum algorithms for topological data analysis on an equal footing.

Topological data analysis

Topological data analysis computes the persistent homology (encapsulated by the persistent Betti numbers) of a dataset across multiple length scales. This technique, which extends algebraic topology of manifolds to datasets, is useful for the analysis of systems with multipartite interactions [4], studying time series [5], or in machine learning [6].

Algorithms for topological data analysis proceed by defining a length scale, and using it to construct a set of simplices from the data points. A $k$-simplex is a collection of $(k+1)$ points that are all within the length scale of each other. By treating the simplices as a scaffold approximating the underlying topological manifold of the dataset, we can calculate the number of holes in the scaffold. The number of $k$-dimensional holes at a single length scale is known as the $k$th Betti number, while the number of $k$-dimensional holes that persist between two length scales is known as the $k$th persistent Betti number. Most practical applications of topological data analysis require the calculation of persistent Betti numbers, rather than Betti numbers. This is because it is unclear a priori what the length scale should be. Moreover, even if the length scale were known, noise in the data can cause spurious, short-lived topological features to be present. Computing the persistent Betti numbers across multiple length scales enables one to identify the dominant topological features, which are typically those with the longest persistence.

Classical algorithms work by manipulating linear operators that act on the simplices, which relate simplices to their oriented boundaries. While classical algorithms scale polynomially with the number of $k$-simplices, which can be as large as ${N \choose k+1}$ for $N$ datapoints, they naturally calculate the persistent Betti numbers across multiple length scales [7].

In Ref [2], a quantum algorithm was proposed to compute Betti numbers. However, as noted in Ref. [8], it was unclear how to adapt this algorithm to compute persistent Betti numbers. In particular, as shown in Ref. [9], computing the Betti numbers at two different length scales is not sufficient to determine the persistent Betti numbers, as the number of holes at a given length scale does not uniquely identify when the holes are created or destroyed.

A quantum algorithm for persistent homology

The work by Hayakawa [3] provided the first quantum algorithm for computing persistent homology. It works by ‘quantizing’ a recent classical algorithm for constructing the persistent combinatorial Laplacian [10] and counting how many of its eigenvalues are zero – which yields the persistent Betti number. The classical algorithm for constructing the persistent combinatorial Laplacian is non-trivial, requiring taking the Schur complement of sub-matrices of the boundary operator (which maps simplices to their oriented boundaries). The work by Hayakawa adapts these approaches to the quantum setting by using quantum singular-value transformation (QSVT) [11] to implement operations, such as the Schur complement, coherently. QSVT is a technique to implement polynomial transformations on the singular values of block-encoded matrices. This work first provides a novel approach to block-encoding the boundary matrices that are the building blocks of the persistent combinatorial Laplacian. It then uses QSVT to coherently implement the required operations to block-encode the persistent combinatorial Laplacian. Hayakawa’s approach also uses QSVT for preparing initial states, and for measuring the number of zero eigenvalues of the persistent combinatorial Laplacian.

Outlook

The extent to which quantum algorithms for topological data analysis possess a practical advantage over their classical counterparts is still an open question. Quantum algorithms naturally return additive error estimates of the (persistent) Betti numbers normalized by the number of simplices, in polynomial time. This may provide an exponential speedup over classical algorithms for the normalized quantity (although recent improvements in classical approaches [12] make the speedup less clear-cut). In general, this normalized quantity will be very small, and converting the output to an additive error estimate of the actual (persistent) Betti number causes the quantum algorithm to scale polynomially with the number of $k$-simplices, just like classical algorithms.

Nevertheless, Hayakawa’s extension to computing persistent homology is a necessary prerequisite for practical quantum topological data analysis. Future work will assess the true viability of this work (and subsequent optimizations [13]), when all error-correction overheads are taken into account, for concrete problems of interest.

► BibTeX data

► References

[1] Scott Aaronson. Read the fine print. Nature Physics, 11 (4): 291–293, Apr 2015. URL https:/​/​doi.org/​10.1038/​nphys3272.
https:/​/​doi.org/​10.1038/​nphys3272

[2] Seth Lloyd, Silvano Garnerone, and Paolo Zanardi. Quantum algorithms for topological and geometric analysis of data. Nature communications, 7 (1): 1–7, 2016. URL https:/​/​doi.org/​10.1038/​ncomms10138.
https:/​/​doi.org/​10.1038/​ncomms10138

[3] Ryu Hayakawa. Quantum algorithm for persistent Betti numbers and topological data analysis. Quantum, 6: 873, 2022. URL https:/​/​doi.org/​10.22331/​q-2022-12-07-873.
https:/​/​doi.org/​10.22331/​q-2022-12-07-873

[4] Gunnar Carlsson. Topological methods for data modelling. Nature Reviews Physics, 2 (12): 697–708, 2020. URL https:/​/​doi.org/​10.1038/​s42254-020-00249-3.
https:/​/​doi.org/​10.1038/​s42254-020-00249-3

[5] Jose A Perea and John Harer. Sliding windows and persistence: An application of topological methods to signal analysis. Foundations of Computational Mathematics, 15 (3): 799–838, 2015. URL https:/​/​doi.org/​10.1007/​s10208-014-9206-z.
https:/​/​doi.org/​10.1007/​s10208-014-9206-z

[6] Felix Hensel, Michael Moor, and Bastian Rieck. A survey of topological machine learning methods. Frontiers in Artificial Intelligence, 4: 52, 2021. URL https:/​/​doi.org/​10.3389/​frai.2021.681108.
https:/​/​doi.org/​10.3389/​frai.2021.681108

[7] Edelsbrunner, Letscher, and Zomorodian. Topological persistence and simplification. Discrete & Computational Geometry, 28 (4): 511–533, 2002. URL https:/​/​doi.org/​10.1007/​s00454-002-2885-2.
https:/​/​doi.org/​10.1007/​s00454-002-2885-2

[8] Sam Gunn and Niels Kornerup. Review of a quantum algorithm for Betti numbers. arXiv preprint arXiv:1906.07673, 2019. URL https:/​/​arxiv.org/​abs/​1906.07673.
arXiv:1906.07673

[9] Niels Neumann and Sterre den Breeijen. Limitations of clustering using quantum persistent homology. arXiv preprint arXiv:1911.10781, 2019. URL https:/​/​arxiv.org/​abs/​1911.10781.
arXiv:1911.10781

[10] Facundo Mémoli, Zhengchao Wan, and Yusu Wang. Persistent laplacians: Properties, algorithms and implications. SIAM Journal on Mathematics of Data Science, 4 (2): 858–884, 2022. URL https:/​/​doi.org/​10.1137/​21M1435471.
https:/​/​doi.org/​10.1137/​21M1435471

[11] András Gilyén, Yuan Su, Guang Hao Low, and Nathan Wiebe. Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, pages 193–204, 2019. URL https:/​/​doi.org/​10.1145/​3313276.3316366.
https:/​/​doi.org/​10.1145/​3313276.3316366

[12] Simon Apers, Sayantan Sen, and Dániel Szabó. A (simple) classical algorithm for estimating Betti numbers. arXiv preprint arXiv:2211.09618, 2022. URL https:/​/​arxiv.org/​abs/​2211.09618.
arXiv:2211.09618

[13] Sam McArdle, András Gilyén, and Mario Berta. A streamlined quantum algorithm for topological data analysis with exponentially fewer qubits. arXiv preprint arXiv:2209.12887, 2022. URL https:/​/​arxiv.org/​abs/​2209.12887.
arXiv:2209.12887

Cited by

On Crossref's cited-by service no data on citing works was found (last attempt 2024-06-22 06:06:00). On SAO/NASA ADS no data on citing works was found (last attempt 2024-06-22 06:06:01).