Quantum algorithm for persistent Betti numbers and topological data analysis

Ryu Hayakawa

Yukawa Institute for Theoretical Physics, Kyoto University, Kitashirakawa Oiwakecho, Sakyoku, Kyoto 606-8502, Japan

Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.

Abstract

Topological data analysis (TDA) is an emergent field of data analysis. The critical step of TDA is computing the persistent Betti numbers. Existing classical algorithms for TDA are limited if we want to learn from high-dimensional topological features because the number of high-dimensional simplices grows exponentially in the size of the data. In the context of quantum computation, it has been previously shown that there exists an efficient quantum algorithm for estimating the Betti numbers even in high dimensions. However, the Betti numbers are less general than the persistent Betti numbers, and there have been no quantum algorithms that can estimate the persistent Betti numbers of arbitrary dimensions.
This paper shows the first quantum algorithm that can estimate the (normalized) persistent Betti numbers of arbitrary dimensions. Our algorithm is efficient for simplicial complexes such as the Vietoris-Rips complex and demonstrates exponential speedup over the known classical algorithms.

► BibTeX data

► References

[1] Mehmet E Aktas, Esra Akbas, and Ahmed El Fatmaoui. Persistence homology of networks: methods and applications. Applied Network Science, 4 (1): 1–28, 2019. 10.1007/​s41109-019-0179-3.
https:/​/​doi.org/​10.1007/​s41109-019-0179-3

[2] Jonathan Ariel Barmak and Elias Gabriel Minian. Strong homotopy types, nerves and collapses. Discrete & Computational Geometry, 47 (2): 301–328, 2012. 10.1007/​s00454-011-9357-5.
https:/​/​doi.org/​10.1007/​s00454-011-9357-5

[3] Andreas Bärtschi and Stephan Eidenbenz. Deterministic preparation of dicke states. In International Symposium on Fundamentals of Computation Theory, pages 126–139. Springer, 2019. 10.1007/​978-3-030-25027-0_9.
https:/​/​doi.org/​10.1007/​978-3-030-25027-0_9

[4] Gilles Brassard, Peter Hoyer, Michele Mosca, and Alain Tapp. Quantum amplitude amplification and estimation. Contemporary Mathematics, 305: 53–74, 2002. 10.1090/​conm/​305/​05215.
https:/​/​doi.org/​10.1090/​conm/​305/​05215

[5] Peter Bubenik et al. Statistical topological data analysis using persistence landscapes. J. Mach. Learn. Res., 16 (1): 77–102, 2015. 10.5555/​2789272.2789275.
https:/​/​doi.org/​10.5555/​2789272.2789275

[6] Frédéric Chazal and Bertrand Michel. An introduction to topological data analysis: fundamental and practical aspects for data scientists. Frontiers in artificial intelligence, 4, 2021. 10.3389/​frai.2021.667963.
https:/​/​doi.org/​10.3389/​frai.2021.667963

[7] Ho Yee Cheung, Tsz Chiu Kwok, and Lap Chi Lau. Fast matrix rank algorithms and applications. Journal of the ACM (JACM), 60 (5): 1–25, 2013. 10.1145/​2528404.
https:/​/​doi.org/​10.1145/​2528404

[8] David Cohen-Steiner, Herbert Edelsbrunner, and John Harer. Stability of persistence diagrams. Discrete & computational geometry, 37 (1): 103–120, 2007. 10.1007/​s00454-006-1276-5.
https:/​/​doi.org/​10.1007/​s00454-006-1276-5

[9] Alex Cole and Gary Shiu. Topological data analysis for the string landscape. Journal of High Energy Physics, 2019 (3): 1–31, 2019. 10.1007/​JHEP03(2019)054.
https:/​/​doi.org/​10.1007/​JHEP03(2019)054

[10] Steven A Cuccaro, Thomas G Draper, Samuel A Kutin, and David Petrie Moulton. A new quantum ripple-carry addition circuit. arXiv preprint quant-ph/​0410184, 2004. 10.48550/​arXiv.quant-ph/​0410184.
https:/​/​doi.org/​10.48550/​arXiv.quant-ph/​0410184
arXiv:quant-ph/0410184

[11] Edoardo Di Napoli, Eric Polizzi, and Yousef Saad. Efficient estimation of eigenvalue counts in an interval. Numerical Linear Algebra with Applications, 23 (4): 674–692, 2016. 10.1002/​nla.2048.
https:/​/​doi.org/​10.1002/​nla.2048

[12] Robert H Dicke. Coherence in spontaneous radiation processes. Physical review, 93 (1): 99, 1954. 10.1103/​PhysRev.93.99.
https:/​/​doi.org/​10.1103/​PhysRev.93.99

[13] Herbert Edelsbrunner and John Harer. Computational topology: an introduction. American Mathematical Soc., 2010. 10.1007/​978-3-540-33259-6_7.
https:/​/​doi.org/​10.1007/​978-3-540-33259-6_7

[14] Herbert Edelsbrunner, David Letscher, and Afra Zomorodian. Topological persistence and simplification. In Proceedings 41st annual symposium on foundations of computer science, pages 454–463. IEEE, 2000. 10.1007/​s00454-002-2885-2.
https:/​/​doi.org/​10.1007/​s00454-002-2885-2

[15] Herbert Edelsbrunner, John Harer, et al. Persistent homology-a survey. Contemporary mathematics, 453: 257–282, 2008. 10.1090/​conm/​453/​08802.
https:/​/​doi.org/​10.1090/​conm/​453/​08802

[16] Joel Friedman. Computing betti numbers via combinatorial laplacians. Algorithmica, 21 (4): 331–346, 1998. 10.1007/​PL00009218.
https:/​/​doi.org/​10.1007/​PL00009218

[17] Robert Ghrist. Barcodes: the persistent topology of data. Bulletin of the American Mathematical Society, 45 (1): 61–75, 2008. 10.1090/​S0273-0979-07-01191-3.
https:/​/​doi.org/​10.1090/​S0273-0979-07-01191-3

[18] 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. 10.1145/​3313276.3316366.
https:/​/​doi.org/​10.1145/​3313276.3316366

[19] Sam Gunn and Niels Kornerup. Review of a quantum algorithm for betti numbers. arXiv preprint arXiv:1906.07673, 2019. 10.48550/​arXiv.1906.07673.
https:/​/​doi.org/​10.48550/​arXiv.1906.07673
arXiv:1906.07673

[20] Aram W Harrow, Avinatan Hassidim, and Seth Lloyd. Quantum algorithm for linear systems of equations. Physical review letters, 103 (15): 150502, 2009. 10.1103/​PhysRevLett.103.150502.
https:/​/​doi.org/​10.1103/​PhysRevLett.103.150502

[21] Ryu Hayakawa. Quantum algorithm for persistent betti numbers and topological data analysis. arXiv preprint arXiv:2111.00433v1, 2021. 10.48550/​arXiv.2111.00433.
https:/​/​doi.org/​10.48550/​arXiv.2111.00433
arXiv:2111.00433v1

[22] Ryu Hayakawa, Tomoyuki Morimae, and Suguru Tamaki. Fine-grained quantum supremacy based on orthogonal vectors, 3-sum and all-pairs shortest paths. arXiv preprint arXiv:1902.08382, 2019. 10.48550/​arXiv.1902.08382.
https:/​/​doi.org/​10.48550/​arXiv.1902.08382
arXiv:1902.08382

[23] Yong He, Ming-Xing Luo, E Zhang, Hong-Ke Wang, and Xiao-Feng Wang. Decompositions of n-qubit toffoli gates with linear circuit complexity. International Journal of Theoretical Physics, 56 (7): 2350–2361, 2017. 10.1007/​s10773-017-3389-4.
https:/​/​doi.org/​10.1007/​s10773-017-3389-4

[24] He-Liang Huang, Xi-Lin Wang, Peter P Rohde, Yi-Han Luo, You-Wei Zhao, Chang Liu, Li Li, Nai-Le Liu, Chao-Yang Lu, and Jian-Wei Pan. Demonstration of topological data analysis on a quantum processor. Optica, 5 (2): 193–198, 2018. 10.1364/​OPTICA.5.000193.
https:/​/​doi.org/​10.1364/​OPTICA.5.000193

[25] Lek-Heng Lim. Hodge laplacians on graphs. SIAM Review, 62 (3): 685–715, 2020. 10.1137/​18M1223101.
https:/​/​doi.org/​10.1137/​18M1223101

[26] Lin Lin, Yousef Saad, and Chao Yang. Approximating spectral densities of large matrices. SIAM review, 58 (1): 34–65, 2016. 10.1137/​130934283.
https:/​/​doi.org/​10.1137/​130934283

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

[28] John M Martyn, Zane M Rossi, Andrew K Tan, and Isaac L Chuang. Grand unification of quantum algorithms. PRX Quantum, 2 (4): 040203, 2021. 10.1103/​PRXQuantum.2.040203.
https:/​/​doi.org/​10.1103/​PRXQuantum.2.040203

[29] RHAJ Meijer. Clustering using quantum persistent homology. Master's thesis, 2019.

[30] 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. 10.1137/​21M1435471.
https:/​/​doi.org/​10.1137/​21M1435471

[31] Niels Neumann and Sterre den Breeijen. Limitations of clustering using quantum persistent homology. arXiv preprint arXiv:1911.10781, 2019. 10.48550/​arXiv.1911.10781.
https:/​/​doi.org/​10.48550/​arXiv.1911.10781
arXiv:1911.10781

[32] Nina Otter, Mason A Porter, Ulrike Tillmann, Peter Grindrod, and Heather A Harrington. A roadmap for the computation of persistent homology. EPJ Data Science, 6: 1–38, 2017. 10.1140/​epjds/​s13688-017-0109-5.
https:/​/​doi.org/​10.1140/​epjds/​s13688-017-0109-5

[33] Pratyush Pranav, Herbert Edelsbrunner, Rien Van de Weygaert, Gert Vegter, Michael Kerber, Bernard JT Jones, and Mathijs Wintraecken. The topology of the cosmic web in terms of persistent betti numbers. Monthly Notices of the Royal Astronomical Society, 465 (4): 4281–4310, 2017. 10.1093/​mnras/​stw2862.
https:/​/​doi.org/​10.1093/​mnras/​stw2862

[34] Chi Seng Pun, Si Xian Lee, and Kelin Xia. Persistent-homology-based machine learning: a survey and a comparative study. Artificial Intelligence Review, pages 1–45, 2022. 10.1007/​s10462-022-10146-z.
https:/​/​doi.org/​10.1007/​s10462-022-10146-z

[35] Patrick Rall. Faster coherent quantum algorithms for phase, energy, and amplitude estimation. Quantum, 5: 566, 2021. 10.22331/​q-2021-10-19-566.
https:/​/​doi.org/​10.22331/​q-2021-10-19-566

[36] Abu Bakar Siddique, Saadia Farid, and Muhammad Tahir. Proof of bijection for combinatorial number system. arXiv preprint arXiv:1601.05794, 2016. 10.48550/​arXiv.1601.05794.
https:/​/​doi.org/​10.48550/​arXiv.1601.05794
arXiv:1601.05794

[37] Daniel Spitz, Jürgen Berges, Markus Oberthaler, and Anna Wienhard. Finding self-similar behavior in quantum many-body dynamics via persistent homology. SciPost Phys., 11: 060, 2021. 10.21468/​SciPostPhys.11.3.060. URL https:/​/​scipost.org/​10.21468/​SciPostPhys.11.3.060.
https:/​/​doi.org/​10.21468/​SciPostPhys.11.3.060

[38] Shashanka Ubaru, Ismail Yunus Akhalwaya, Mark S Squillante, Kenneth L Clarkson, and Lior Horesh. Quantum topological data analysis with linear depth and exponential speedup. arXiv preprint arXiv:2108.02811, 2021. 10.48550/​arXiv.2108.02811.
https:/​/​doi.org/​10.48550/​arXiv.2108.02811
arXiv:2108.02811

[39] Rui Wang, Duc Duy Nguyen, and Guo-Wei Wei. Persistent spectral graph. International journal for numerical methods in biomedical engineering, 36 (9): e3376, 2020. 10.1002/​cnm.3376.
https:/​/​doi.org/​10.1002/​cnm.3376

[40] Larry Wasserman. Topological data analysis. Annual Review of Statistics and Its Application, 5: 501–532, 2018. 10.1146/​annurev-statistics-031017-100045.
https:/​/​doi.org/​10.1146/​annurev-statistics-031017-100045

[41] Kelin Xia and Guo-Wei Wei. Persistent homology analysis of protein structure, flexibility, and folding. International journal for numerical methods in biomedical engineering, 30 (8): 814–844, 2014. 10.1002/​cnm.2655.
https:/​/​doi.org/​10.1002/​cnm.2655

[42] Afra Zomorodian and Gunnar Carlsson. Computing persistent homology. Discrete & Computational Geometry, 33 (2): 249–274, 2005. 10.1007/​s00454-004-1146-y.
https:/​/​doi.org/​10.1007/​s00454-004-1146-y

Cited by

[1] Sam McArdle, "Extending Quantum topological data analysis to persistent homology", Quantum Views 7, 70 (2023).

[2] Alexander Schmidhuber and Seth Lloyd, "Complexity-Theoretic Limitations on Quantum Algorithms for Topological Data Analysis", arXiv:2209.14286, (2022).

[3] Bernardo Ameneyro, Vasileios Maroulas, and George Siopsis, "Quantum Persistent Homology", arXiv:2202.12965, (2022).

[4] Dominic W. Berry, Yuan Su, Casper Gyurik, Robbie King, Joao Basso, Alexander Del Toro Barba, Abhishek Rajput, Nathan Wiebe, Vedran Dunjko, and Ryan Babbush, "Quantifying Quantum Advantage in Topological Data Analysis", arXiv:2209.13581, (2022).

[5] Iordanis Kerenidis and Anupam Prakash, "Quantum machine learning with subspace states", arXiv:2202.00054, (2022).

[6] Sam McArdle, András Gilyén, and Mario Berta, "A streamlined quantum algorithm for topological data analysis with exponentially fewer qubits", arXiv:2209.12887, (2022).

[7] Simon Apers, Sayantan Sen, and Dániel Szabó, "A (simple) classical algorithm for estimating Betti numbers", arXiv:2211.09618, (2022).

[8] Bernardo Ameneyro, George Siopsis, and Vasileios Maroulas, "Quantum Persistent Homology for Time Series", arXiv:2211.04465, (2022).

[9] Andrew Vlasic and Anh Pham, "Understanding the Mapping of Encode Data Through An Implementation of Quantum Topological Analysis", arXiv:2209.10596, (2022).

The above citations are from Crossref's cited-by service (last updated successfully 2023-02-07 13:41:06) and SAO/NASA ADS (last updated successfully 2023-02-07 13:41:08). The list may be incomplete as not all publishers provide suitable and complete citation data.