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

Cited by

This View is published in Quantum Views under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions.