A (simple) classical algorithm for estimating Betti numbers

A (simple) classical algorithm for estimating Betti numbers

Time Stamp: December 6, 2023 10:32 AM

Simon Apers1, Sander Gribling2, Sayantan Sen3, and Dániel Szabó1

1Université Paris Cité, CNRS, IRIF, Paris, France
2Tilburg University, The Netherlands
3National University of Singapore, Singapore

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

Abstract

We describe a simple algorithm for estimating the $k$-th normalized Betti number of a simplicial complex over $n$ elements using the path integral Monte Carlo method. For a general simplicial complex, the running time of our algorithm is $n^{Oleft(frac{1}{sqrt{gamma}}logfrac{1}{varepsilon}right)}$ with $gamma$ measuring the spectral gap of the combinatorial Laplacian and $varepsilon in (0,1)$ the additive precision. In the case of a clique complex, the running time of our algorithm improves to $left(n/lambda_{max}right)^{Oleft(frac{1}{sqrt{gamma}}logfrac{1}{varepsilon}right)}$ with $lambda_{max} geq k$, where $lambda_{max}$ is the maximum eigenvalue of the combinatorial Laplacian. Our algorithm provides a classical benchmark for a line of quantum algorithms for estimating Betti numbers. On clique complexes it matches their running time when, for example, $gamma in Omega(1)$ and $k in Omega(n)$.

A (simple) classical algorithm for estimating Betti numbers PlatoBlockchain Data Intelligence. Vertical Search. Ai.

[embedded content]

Popular summary

We describe a simple algorithm for estimating the $k$-th normalized Betti number of a simplicial complex over $n$ elements using the path integral Monte Carlo method. Our algorithm provides a classical benchmark for a line of quantum algorithms for estimating Betti numbers.
While the runtime of naïve classical algorithms is exponential in $k$, the quantum algorithm of Lloyd, Garnerone and Zanardi runs in polynomial time if the spectral gap of the combinatorial Laplacian and the precision are at least inverse polynomial in $n$. This suggests that there can be an exponential quantum advantage for this problem.
Our algorithm further pins down the region where we can expect a quantum advantage: it runs in polynomial time if the spectral gap and the precision are constant. In the special case of clique complexes – that is particularly interesting for applications in Topological Data Analysis – we can go further: for example if $k in Omega(n)$ then we can afford inverse polynomial precision (if the gap is constant) or gap $Omega(1/log^2 n)$ (if the precision is constant).

► BibTeX data

► References

[1] Ismail Yunus Akhalwaya, Shashanka Ubaru, Kenneth L Clarkson, Mark S Squillante, Vishnu Jejjala, Yang-Hui He, Kugendran Naidoo, Vasileios Kalantzis, and Lior Horesh. Exponential advantage on noisy quantum computers. arXiv:2209.09371, 2022. 10.48550/​arXiv.2209.09371.
https:/​/​doi.org/​10.48550/​arXiv.2209.09371
arXiv:2209.09371

[2] Bernardo Ameneyro, Vasileios Maroulas, and George Siopsis. Quantum persistent homology. arXiv:2202.12965, 2022. 10.48550/​arXiv.2202.12965.
https:/​/​doi.org/​10.48550/​arXiv.2202.12965
arXiv:2202.12965

[3] J. A. Barker. A quantum‐statistical Monte Carlo method; path integrals with boundary conditions. The Journal of Chemical Physics, 70 (6): 2914–2918, 1979. 10.1063/​1.437829.
https:/​/​doi.org/​10.1063/​1.437829

[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. Analyzing prospects for quantum advantage in topological data analysis. arXiv.2209.13581, 2022. 10.48550/​arXiv.2209.13581.
https:/​/​doi.org/​10.48550/​arXiv.2209.13581

[5] Chris Cade and P Marcos Crichigno. Complexity of supersymmetric systems and the cohomology problem. arXiv:2107.00011, 2021. 10.48550/​arXiv.2107.00011.
https:/​/​doi.org/​10.48550/​arXiv.2107.00011
arXiv:2107.00011

[6] Gunnar Carlsson. Topology and data. Bulletin of the American Mathematical Society, 46 (2): 255–308, 2009. 10.1090/​S0273-0979-09-01249-X.
https:/​/​doi.org/​10.1090/​S0273-0979-09-01249-X

[7] Marcos Crichigno and Tamara Kohler. Clique homology is QMA1-hard. arXiv:2209.11793, 2022. 10.48550/​arXiv.2209.11793.
https:/​/​doi.org/​10.48550/​arXiv.2209.11793
arXiv:2209.11793

[8] Dean Doron, Amir Sarid, and Amnon Ta-Shma. On approximating the eigenvalues of stochastic matrices in probabilistic logspace. computational complexity, 26: 393–420, 2017. 10.1007/​s00037-016-0150-y.
https:/​/​doi.org/​10.1007/​s00037-016-0150-y

[9] Devdatt P Dubhashi and Alessandro Panconesi. Concentration of measure for the analysis of randomized algorithms. Cambridge University Press, 2009. 10.1017/​CBO9780511581274.
https:/​/​doi.org/​10.1017/​CBO9780511581274

[10] Art Duval and Victor Reiner. Shifted simplicial complexes are Laplacian integral. Transactions of the American Mathematical Society, 354 (11): 4313–4344, 2002. 10.1090/​S0002-9947-02-03082-9.
https:/​/​doi.org/​10.1090/​S0002-9947-02-03082-9

[11] Gábor Elek. Betti numbers are testable. In Fete of combinatorics and computer science, pages 139–149. Springer, 2010. 10.1007/​978-3-642-13580-4_6.
https:/​/​doi.org/​10.1007/​978-3-642-13580-4_6

[12] George E Forsythe and Richard A Leibler. Matrix inversion by a Monte Carlo method. Mathematics of Computation, 4 (31): 127–129, 1950. 10.1090/​S0025-5718-1950-0038138-X.
https:/​/​doi.org/​10.1090/​S0025-5718-1950-0038138-X

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

[14] Sevag Gharibian and François Le Gall. Dequantizing the quantum singular value transformation: Hardness and applications to quantum chemistry and the quantum PCP conjecture. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, pages 19–32, 2022. 10.1145/​3519935.3519991.
https:/​/​doi.org/​10.1145/​3519935.3519991

[15] Timothy E Goldberg. Combinatorial Laplacians of simplicial complexes. Senior Thesis, Bard College, 2002.

[16] Casper Gyurik, Chris Cade, and Vedran Dunjko. Towards quantum advantage via topological data analysis. Quantum, 6: 855, 2022. 10.22331/​q-2022-11-10-855.
https:/​/​doi.org/​10.22331/​q-2022-11-10-855

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

[18] Wassily Hoeffding. Probability inequalities for sums of bounded random variables. Journal of the American Statistical Association, 58 (301): 13–30, 1963. 10.1080/​01621459.1963.10500830.
https:/​/​doi.org/​10.1080/​01621459.1963.10500830

[19] 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

[20] 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. 10.48550/​arXiv.2209.12887.
https:/​/​doi.org/​10.48550/​arXiv.2209.12887
arXiv:2209.12887

[21] 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

[22] Sushant Sachdeva and Nisheeth K. Vishnoi. Faster algorithms via approximation theory. Foundations and Trends® in Theoretical Computer Science, 9 (2): 125–210, 2014. ISSN 1551-305X. 10.1561/​0400000065.
https:/​/​doi.org/​10.1561/​0400000065

[23] Alexander Schmidhuber and Seth Lloyd. Complexity-theoretic limitations on quantum algorithms for topological data analysis. arXiv:2209.14286, 2022. 10.48550/​arXiv.2209.14286.
https:/​/​doi.org/​10.48550/​arXiv.2209.14286
arXiv:2209.14286

[24] 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

Cited by

[1] Alexander M. Dalzell, Sam McArdle, Mario Berta, Przemyslaw Bienias, Chi-Fang Chen, András Gilyén, Connor T. Hann, Michael J. Kastoryano, Emil T. Khabiboulline, Aleksander Kubica, Grant Salton, Samson Wang, and Fernando G. S. L. Brandão, “Quantum algorithms: A survey of applications and end-to-end complexities”, arXiv:2310.03011, (2023).

[2] Daniel Leykam and Dimitris G. Angelakis, “Topological data analysis and machine learning”, Advances in Physics X 8 1, 2202331 (2023).

[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, “Analyzing Prospects for Quantum Advantage in Topological Data Analysis”, arXiv:2209.13581, (2022).

[4] Samson Wang, Sam McArdle, and Mario Berta, “Qubit-Efficient Randomized Quantum Algorithms for Linear Algebra”, arXiv:2302.01873, (2023).

[5] Ashley Montanaro and Changpeng Shao, “Quantum and classical query complexities of functions of matrices”, arXiv:2311.06999, (2023).

[6] Robbie King and Tamara Kohler, “Promise Clique Homology on weighted graphs is $text{QMA}_1$-hard and contained in $text{QMA}$”, arXiv:2311.17234, (2023).

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

On Crossref’s cited-by service no data on citing works was found (last attempt 2023-12-07 03:42:19).

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:

More from Quantum Journal