Quantum Algorithm For Persistent Betti Numbers And Topological Data Analysis

Republished By Plato

Followers: 0

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

@article{Hayakawa2022quantumalgorithm, doi = {10.22331/q-2022-12-07-873}, url = {https://doi.org/10.22331/q-2022-12-07-873}, title = {Quantum algorithm for persistent {B}etti numbers and topological data analysis}, author = {Hayakawa, Ryu}, journal = {{Quantum}}, issn = {2521-327X}, publisher = {{Verein zur F{“{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, volume = {6}, pages = {873}, month = dec, year = {2022} }

► 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] Alexander Schmidhuber and Seth Lloyd, “Complexity-Theoretic Limitations on Quantum Algorithms for Topological Data Analysis”, arXiv:2209.14286.

[2] Bernardo Ameneyro, Vasileios Maroulas, and George Siopsis, “Quantum Persistent Homology”, arXiv:2202.12965.

[3] 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.

[4] Iordanis Kerenidis and Anupam Prakash, “Quantum machine learning with subspace states”, arXiv:2202.00054.

[5] Bernardo Ameneyro, George Siopsis, and Vasileios Maroulas, “Quantum Persistent Homology for Time Series”, arXiv:2211.04465.

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

[7] Sam McArdle, András Gilyén, and Mario Berta, “A streamlined quantum algorithm for topological data analysis with exponentially fewer qubits”, arXiv:2209.12887.

[8] Andrew Vlasic and Anh Pham, “Understanding the Mapping of Encode Data Through An Implementation of Quantum Topological Analysis”, arXiv:2209.10596.

The above citations are from SAO/NASA ADS (last updated successfully 2022-12-07 16:42:14). The list may be incomplete as not all publishers provide suitable and complete citation data.

Could not fetch Crossref cited-by data during last attempt 2022-12-07 16:42:12: Could not fetch cited-by data for 10.22331/q-2022-12-07-873 from Crossref. This is normal if the DOI was registered recently.

This Paper is published in Quantum 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.

Time Stamp: December 7, 2022December 7, 2022

Time Stamp: Dec 13, 2022

Quantum algorithm for persistent Betti numbers and topological data analysis

Republished By Plato

Abstract

► BibTeX data

► References

Cited by

More from Quantum Journal

Quantum Goemans-Williamson Algorithm with the Hadamard Test and Approximate Amplitude Constraints

Bounding entanglement dimensionality from the covariance matrix

Correlations in typicality and an affirmative solution to the exact catalytic entropy conjecture

Quantum Local Search with the Quantum Alternating Operator Ansatz

Two-Unitary Decomposition Algorithm and Open Quantum System Simulation

Pipelined correlated minimum weight perfect matching of the surface code

A monogamy-of-entanglement game for subspace coset states

On contraction coefficients, partial orders and approximation of capacities for quantum channels

Testing identity of collections of quantum states: sample complexity analysis

Variational Quantum Simulation of Valence-Bond Solids

About Us

Vertical Search & Ai

Platform

Stay Connected

Account