quantum-computing

Comparing quantum and classical Monte Carlo algorithms for estimating Betti numbers of clique complexes

Ismail Yunus Akhalwaya, Ahmed Bhayat, Adam Connolly, Steven Herbert, Lior Horesh, Julien Sorci, and Shashanka Ubaru

10 min read

0 likes

⚡ Quantum Brief

Researchers led by Ismail Yunus Akhalwaya introduced a unified modular framework to compare quantum and classical Monte Carlo algorithms for estimating Betti numbers in clique complexes, addressing prior ambiguity in performance benchmarks. The team derived rigorous upper bounds for sample complexity, quantifying the number of samples required to achieve specified precision levels across different algorithms. By recombining existing modular components, they developed a novel quantum algorithm demonstrating exponential improvements in sample complexity compared to classical counterparts. Classical simulations validated theoretical bounds, confirming the predicted exponential separation between quantum and classical methods, though empirical convergence occurred faster than conservative estimates. This work advances topological data analysis by providing concrete performance metrics and a hybrid quantum-classical approach, potentially accelerating real-world applications in machine learning and complex network analysis.

AI Audio Summary

0:00 / 0:00

Click to play

Unsplash · Validated Fallback

Understand this faster with AI

Ask ChatGPT

Research with Perplexity

Explain with Claude

Discuss on Grok

AbstractSeveral quantum and classical Monte Carlo algorithms for Betti Number Estimation (BNE) on clique complexes have recently been proposed, though it is unclear how their performances compare. We review these algorithms, emphasising their common Monte Carlo structure within a new modular framework. We derive upper bounds for the number of samples needed to reach a given level of precision, and use them to compare these algorithms. By recombining the different modules, we create a new quantum algorithm with an exponentially-improved dependence in the sample complexity. We run classical simulations to verify convergence within the theoretical bounds and observe the predicted exponential separation, even though empirical convergence occurs substantially earlier than the conservative theoretical bounds.► BibTeX data@article{Akhalwaya2025comparingquantum, doi = {10.22331/q-2025-10-31-1901}, url = {https://doi.org/10.22331/q-2025-10-31-1901}, title = {Comparing quantum and classical {M}onte {C}arlo algorithms for estimating {B}etti numbers of clique complexes}, author = {Akhalwaya, Ismail Yunus and Bhayat, Ahmed and Connolly, Adam and Herbert, Steven and Horesh, Lior and Sorci, Julien and Ubaru, Shashanka}, journal = {{Quantum}}, issn = {2521-327X}, publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, volume = {9}, pages = {1901}, month = oct, year = {2025} }► References [1] Ravindran Kannan and Achim Bachem. ``Polynomial algorithms for computing the smith and hermite normal forms of an integer matrix''. SIAM Journal on Computing 8, 499–507 (1979). arXiv:https://doi.org/10.1137/0208040. https://doi.org/10.1137/0208040 arXiv:https://doi.org/10.1137/0208040 [2] Gunnar E. Carlsson. ``Topology and data''. Bulletin of the American Mathematical Society 46, 255–308 (2009). url: https://api.semanticscholar.org/CorpusID:1472609. https://api.semanticscholar.org/CorpusID:1472609 [3] Erik J. Amézquita, Michelle Y. Quigley, Tim Ophelders, Elizabeth Munch, and Daniel H. Chitwood. ``The shape of things to come: Topological data analysis and biology, from molecules to organisms''. Developmental Dynamics 249, 816–833 (2020). arXiv:https://anatomypubs.onlinelibrary.wiley.com/doi/pdf/10.1002/dvdy.175. https://doi.org/10.1002/dvdy.175 arXiv:https://anatomypubs.onlinelibrary.wiley.com/doi/pdf/10.1002/dvdy.175 [4] Yara Skaf and Reinhard Laubenbacher. ``Topological data analysis in biomedicine: A review''. Journal of Biomedical Informatics 130, 104082 (2022). https://doi.org/10.1016/j.jbi.2022.104082 [5] Marcos Crichigno and Tamara Kohler. ``Clique homology is ${{\mathsf{QMA} }}_{1}$-hard''. Nature Communications 15 (2024). https://doi.org/10.1038/s41467-024-54118-z [6] Gábor Elek. ``Betti numbers are testable*''. Pages 139–149.

Springer Berlin Heidelberg. Berlin, Heidelberg (2010). https://doi.org/10.1007/978-3-642-13580-4_6 [7] Chris Cade and P. Marcos Crichigno. ``Complexity of supersymmetric systems and the cohomology problem''. Quantum 8, 1325 (2024). https://doi.org/10.22331/q-2024-04-30-1325 [8] Seth Lloyd, Silvano Garnerone, and Paolo Zanardi. ``Quantum algorithms for topological and geometric analysis of data''. Nature Communications 7 (2016). https://doi.org/10.1038/ncomms10138 [9] Ryu Hayakawa. ``Quantum algorithm for persistent Betti numbers and topological data analysis''. Quantum 6, 873 (2022). https://doi.org/10.22331/q-2022-12-07-873 [10] Sam McArdle, András Gilyén, and Mario Berta. ``A streamlined quantum algorithm for topological data analysis with exponentially fewer qubits'' (2022). arXiv:2209.12887. arXiv:2209.12887 [11] Casper Gyurik, Chris Cade, and Vedran Dunjko. ``Towards quantum advantage via topological data analysis''. Quantum 6, 855 (2022). https://doi.org/10.22331/q-2022-11-10-855 [12] Ismail Yunus Akhalwaya, Shashanka Ubaru, Kenneth L Clarkson, Mark S Squillante, Vishnu Jejjala, Yang-Hui He, Kugendran Naidoo, Vasileios Kalantzis, and Lior Horesh. ``Towards quantum advantage on noisy quantum computers'' (2022). [13] Simon Apers, Sander Gribling, Sayantan Sen, and Dániel Szabó. ``A (simple) classical algorithm for estimating Betti numbers''. Quantum 7, 1202 (2023). https://doi.org/10.22331/q-2023-12-06-1202 [14] 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''. PRX Quantum 5, 010319 (2024). https://doi.org/10.1103/PRXQuantum.5.010319 [15] Ismail Yunus Akhalwaya, Shashanka Ubaru, Kenneth L. Clarkson, Mark S. Squillante, Vishnu Jejjala, Yang-Hui He, Kugendran Naidoo, Vasileios Kalantzis, and Lior Horesh. ``Topological data analysis on noisy quantum computers''.

In The Twelfth International Conference on Learning Representations. (2024). url: https://openreview.net/forum?id=dLrhRIMVmB. https://openreview.net/forum?id=dLrhRIMVmB [16] Shashanka Ubaru, Ismail Yunus Akhalwaya, Mark S. Squillante, Kenneth L. Clarkson, and L. Horesh. ``Quantum topological data analysis with linear depth and exponential speedup'' (2021). [17] Allen Hatcher. ``Algebraic topology''.

Cambridge University Press. (2002). url: https://pi.math.cornell.edu/ hatcher/AT/AT.pdf. https://pi.math.cornell.edu/~hatcher/AT/AT.pdf [18] Yan-Lin Yu. ``Combinatorial gauss-bonnet-chern formula''. Topology 22, 153–163 (1983). https://doi.org/10.1016/0040-9383(83)90026-5 [19] Lek-Heng Lim. ``Hodge laplacians on graphs''. SIAM Review 62, 685–715 (2020). arXiv:https://doi.org/10.1137/18M1223101. https://doi.org/10.1137/18M1223101 arXiv:https://doi.org/10.1137/18M1223101 [20] T.E. Goldberg. ``Combinatorial laplacians of simplicial complexes''. Bard College. (2002). url: https://books.google.com/books?id=I-Gy0AEACAAJ. https://books.google.com/books?id=I-Gy0AEACAAJ [21] Haim Avron and Sivan Toledo. ``Randomized algorithms for estimating the trace of an implicit symmetric positive semi-definite matrix''. J. ACM 58 (2011). https://doi.org/10.1145/1944345.1944349 [22] Shashanka Ubaru and Yousef Saad. ``Applications of trace estimation techniques''.

In International Conference on High Performance Computing in Science and Engineering. Pages 19–33. Springer (2018). https://doi.org/10.1007/978-3-319-97136-0_2 [23] Tyler Chen, Thomas Trogdon, and Shashanka Ubaru. ``Randomized matrix-free quadrature: Unified and uniform bounds for stochastic lanczos quadrature and the kernel polynomial method''. SIAM Journal on Scientific Computing 47, A1733–A1757 (2025). arXiv:https://doi.org/10.1137/23M1600414. https://doi.org/10.1137/23M1600414 arXiv:https://doi.org/10.1137/23M1600414 [24] Wassily Hoeffding. ``Probability inequalities for sums of bounded random variables''. Journal of the American Statistical Association 58, 13–30 (1963). arXiv:https://www.tandfonline.com/doi/pdf/10.1080/01621459.1963.10500830. https://doi.org/10.1080/01621459.1963.10500830 arXiv:https://www.tandfonline.com/doi/pdf/10.1080/01621459.1963.10500830 [25] Dorit Aharonov, Vaughan Jones, and Zeph Landau. ``A polynomial quantum algorithm for approximating the jones polynomial''. Algorithmica 55, 395–421 (2009). https://doi.org/10.1007/s00453-008-9168-0 [26] Ismail Yunus Akhalwaya, Yang-Hui He, Lior Horesh, Vishnu Jejjala, William Kirby, Kugendran Naidoo, and Shashanka Ubaru. ``Representation of the fermionic boundary operator''. Phys. Rev. A 106, 022407 (2022). https://doi.org/10.1103/PhysRevA.106.02240 [27] Beno Eckmann. ``Harmonische funktionen und randwertaufgaben in einem komplex.''. Commentarii mathematici Helvetici 17, 240–255 (1944/45). url: http://eudml.org/doc/138857. http://eudml.org/doc/138857 [28] J. Friedman. ``Computing betti numbers via combinatorial laplacians''. Algorithmica 21, 331–346 (1998). https://doi.org/10.1007/PL00009218 [29] Sushant Sachdeva and Nisheeth Vishnoi. ``Approximation theory and the design of fast algorithms'' (2013). arXiv:1309.4882. arXiv:1309.4882 [30] Paul Erdös. ``Some remarks on polynomials''. Bulletin of the American Mathematical Society 53, 1169–1176 (1947). url: https://api.semanticscholar.org/CorpusID:120848504. https://api.semanticscholar.org/CorpusID:120848504Cited byCould not fetch Crossref cited-by data during last attempt 2025-10-31 09:23:09: Could not fetch cited-by data for 10.22331/q-2025-10-31-1901 from Crossref. This is normal if the DOI was registered recently. Could not fetch ADS cited-by data during last attempt 2025-10-31 09:23:09: No response from ADS or unable to decode the received json data when getting the list of citing works.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. AbstractSeveral quantum and classical Monte Carlo algorithms for Betti Number Estimation (BNE) on clique complexes have recently been proposed, though it is unclear how their performances compare. We review these algorithms, emphasising their common Monte Carlo structure within a new modular framework. We derive upper bounds for the number of samples needed to reach a given level of precision, and use them to compare these algorithms. By recombining the different modules, we create a new quantum algorithm with an exponentially-improved dependence in the sample complexity. We run classical simulations to verify convergence within the theoretical bounds and observe the predicted exponential separation, even though empirical convergence occurs substantially earlier than the conservative theoretical bounds.► BibTeX data@article{Akhalwaya2025comparingquantum, doi = {10.22331/q-2025-10-31-1901}, url = {https://doi.org/10.22331/q-2025-10-31-1901}, title = {Comparing quantum and classical {M}onte {C}arlo algorithms for estimating {B}etti numbers of clique complexes}, author = {Akhalwaya, Ismail Yunus and Bhayat, Ahmed and Connolly, Adam and Herbert, Steven and Horesh, Lior and Sorci, Julien and Ubaru, Shashanka}, journal = {{Quantum}}, issn = {2521-327X}, publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, volume = {9}, pages = {1901}, month = oct, year = {2025} }► References [1] Ravindran Kannan and Achim Bachem. ``Polynomial algorithms for computing the smith and hermite normal forms of an integer matrix''. SIAM Journal on Computing 8, 499–507 (1979). arXiv:https://doi.org/10.1137/0208040. https://doi.org/10.1137/0208040 arXiv:https://doi.org/10.1137/0208040 [2] Gunnar E. Carlsson. ``Topology and data''. Bulletin of the American Mathematical Society 46, 255–308 (2009). url: https://api.semanticscholar.org/CorpusID:1472609. https://api.semanticscholar.org/CorpusID:1472609 [3] Erik J. Amézquita, Michelle Y. Quigley, Tim Ophelders, Elizabeth Munch, and Daniel H. Chitwood. ``The shape of things to come: Topological data analysis and biology, from molecules to organisms''. Developmental Dynamics 249, 816–833 (2020). arXiv:https://anatomypubs.onlinelibrary.wiley.com/doi/pdf/10.1002/dvdy.175. https://doi.org/10.1002/dvdy.175 arXiv:https://anatomypubs.onlinelibrary.wiley.com/doi/pdf/10.1002/dvdy.175 [4] Yara Skaf and Reinhard Laubenbacher. ``Topological data analysis in biomedicine: A review''. Journal of Biomedical Informatics 130, 104082 (2022). https://doi.org/10.1016/j.jbi.2022.104082 [5] Marcos Crichigno and Tamara Kohler. ``Clique homology is ${{\mathsf{QMA} }}_{1}$-hard''. Nature Communications 15 (2024). https://doi.org/10.1038/s41467-024-54118-z [6] Gábor Elek. ``Betti numbers are testable*''. Pages 139–149.

Read Original

Source Information

Source: Quantum Journal

Website: https://quantum-journal.org/feed/

Discussion

0 professional contributions

Be the first to add a constructive contribution.

Comparing quantum and classical Monte Carlo algorithms for estimating Betti numbers of clique complexes

Tags

Source Information