{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,31]],"date-time":"2025-10-31T09:29:13Z","timestamp":1761902953339,"version":"build-2065373602"},"reference-count":30,"publisher":"Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften","license":[{"start":{"date-parts":[[2025,10,31]],"date-time":"2025-10-31T00:00:00Z","timestamp":1761868800000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["quantum-journal.org"],"crossmark-restriction":false},"short-container-title":["Quantum"],"abstract":"<jats:p>Several 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.<\/jats:p>","DOI":"10.22331\/q-2025-10-31-1901","type":"journal-article","created":{"date-parts":[[2025,10,31]],"date-time":"2025-10-31T09:25:57Z","timestamp":1761902757000},"page":"1901","update-policy":"https:\/\/doi.org\/10.22331\/q-crossmark-policy-page","source":"Crossref","is-referenced-by-count":0,"title":["Comparing quantum and classical Monte Carlo algorithms for estimating Betti numbers of clique complexes"],"prefix":"10.22331","volume":"9","author":[{"given":"Ismail Yunus","family":"Akhalwaya","sequence":"first","affiliation":[{"name":"Quantinuum, Terrington House, 13-15 Hills Road, Cambridge CB2 1NL, United Kingdom"}]},{"given":"Ahmed","family":"Bhayat","sequence":"additional","affiliation":[{"name":"Quantinuum, Terrington House, 13-15 Hills Road, Cambridge CB2 1NL, United Kingdom"}]},{"given":"Adam","family":"Connolly","sequence":"additional","affiliation":[{"name":"Quantinuum, Terrington House, 13-15 Hills Road, Cambridge CB2 1NL, United Kingdom"}]},{"given":"Steven","family":"Herbert","sequence":"additional","affiliation":[{"name":"Quantinuum, Terrington House, 13-15 Hills Road, Cambridge CB2 1NL, United Kingdom"}]},{"given":"Lior","family":"Horesh","sequence":"additional","affiliation":[{"name":"IBM Research, USA"}]},{"given":"Julien","family":"Sorci","sequence":"additional","affiliation":[{"name":"Quantinuum, 1300 N 17th Street, Arlington, VA 22209 USA"}]},{"given":"Shashanka","family":"Ubaru","sequence":"additional","affiliation":[{"name":"IBM Research, USA"}]}],"member":"9598","published-online":{"date-parts":[[2025,10,31]]},"reference":[{"key":"0","doi-asserted-by":"publisher","unstructured":"Ravindran Kannan and Achim Bachem. ``Polynomial algorithms for computing the smith and hermite normal forms of an integer matrix&apos;&apos;. SIAM Journal on Computing 8, 499\u2013507 (1979). arXiv:https:\/\/doi.org\/10.1137\/0208040.","DOI":"10.1137\/0208040"},{"key":"1","doi-asserted-by":"crossref","unstructured":"Gunnar E. Carlsson. ``Topology and data&apos;&apos;. Bulletin of the American Mathematical Society 46, 255\u2013308 (2009). url: https:\/\/api.semanticscholar.org\/CorpusID:1472609.","DOI":"10.1090\/S0273-0979-09-01249-X"},{"key":"2","doi-asserted-by":"publisher","unstructured":"Erik J. Am\u00e9zquita, 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&apos;&apos;. Developmental Dynamics 249, 816\u2013833 (2020). arXiv:https:\/\/anatomypubs.onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/dvdy.175.","DOI":"10.1002\/dvdy.175"},{"key":"3","doi-asserted-by":"publisher","unstructured":"Yara Skaf and Reinhard Laubenbacher. ``Topological data analysis in biomedicine: A review&apos;&apos;. Journal of Biomedical Informatics 130, 104082 (2022).","DOI":"10.1016\/j.jbi.2022.104082"},{"key":"4","doi-asserted-by":"publisher","unstructured":"Marcos Crichigno and Tamara Kohler. ``Clique homology is ${{\\mathsf{QMA} }}_{1}$-hard&apos;&apos;. Nature Communications 15 (2024).","DOI":"10.1038\/s41467-024-54118-z"},{"key":"5","doi-asserted-by":"publisher","unstructured":"G\u00e1bor Elek. ``Betti numbers are testable*&apos;&apos;. Pages 139\u2013149. Springer Berlin Heidelberg. Berlin, Heidelberg (2010).","DOI":"10.1007\/978-3-642-13580-4_6"},{"key":"6","doi-asserted-by":"publisher","unstructured":"Chris Cade and P. Marcos Crichigno. ``Complexity of supersymmetric systems and the cohomology problem&apos;&apos;. Quantum 8, 1325 (2024).","DOI":"10.22331\/q-2024-04-30-1325"},{"key":"7","doi-asserted-by":"publisher","unstructured":"Seth Lloyd, Silvano Garnerone, and Paolo Zanardi. ``Quantum algorithms for topological and geometric analysis of data&apos;&apos;. Nature Communications 7 (2016).","DOI":"10.1038\/ncomms10138"},{"key":"8","doi-asserted-by":"publisher","unstructured":"Ryu Hayakawa. ``Quantum algorithm for persistent Betti numbers and topological data analysis&apos;&apos;. Quantum 6, 873 (2022).","DOI":"10.22331\/q-2022-12-07-873"},{"key":"9","unstructured":"Sam McArdle, Andr\u00e1s Gily\u00e9n, and Mario Berta. ``A streamlined quantum algorithm for topological data analysis with exponentially fewer qubits&apos;&apos; (2022). arXiv:2209.12887."},{"key":"10","doi-asserted-by":"publisher","unstructured":"Casper Gyurik, Chris Cade, and Vedran Dunjko. ``Towards quantum advantage via topological data analysis&apos;&apos;. Quantum 6, 855 (2022).","DOI":"10.22331\/q-2022-11-10-855"},{"key":"11","unstructured":"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&apos;&apos; (2022)."},{"key":"12","doi-asserted-by":"publisher","unstructured":"Simon Apers, Sander Gribling, Sayantan Sen, and D\u00e1niel Szab\u00f3. ``A (simple) classical algorithm for estimating Betti numbers&apos;&apos;. Quantum 7, 1202 (2023).","DOI":"10.22331\/q-2023-12-06-1202"},{"key":"13","doi-asserted-by":"publisher","unstructured":"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&apos;&apos;. PRX Quantum 5, 010319 (2024).","DOI":"10.1103\/PRXQuantum.5.010319"},{"key":"14","unstructured":"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&apos;&apos;. In The Twelfth International Conference on Learning Representations. (2024). url: https:\/\/openreview.net\/forum?id=dLrhRIMVmB."},{"key":"15","unstructured":"Shashanka Ubaru, Ismail Yunus Akhalwaya, Mark S. Squillante, Kenneth L. Clarkson, and L. Horesh. ``Quantum topological data analysis with linear depth and exponential speedup&apos;&apos; (2021)."},{"key":"16","unstructured":"Allen Hatcher. ``Algebraic topology&apos;&apos;. Cambridge University Press. (2002). url: https:\/\/pi.math.cornell.edu\/ hatcher\/AT\/AT.pdf."},{"key":"17","doi-asserted-by":"publisher","unstructured":"Yan-Lin Yu. ``Combinatorial gauss-bonnet-chern formula&apos;&apos;. Topology 22, 153\u2013163 (1983).","DOI":"10.1016\/0040-9383(83)90026-5"},{"key":"18","doi-asserted-by":"publisher","unstructured":"Lek-Heng Lim. ``Hodge laplacians on graphs&apos;&apos;. SIAM Review 62, 685\u2013715 (2020). arXiv:https:\/\/doi.org\/10.1137\/18M1223101.","DOI":"10.1137\/18M1223101"},{"key":"19","unstructured":"T.E. Goldberg. ``Combinatorial laplacians of simplicial complexes&apos;&apos;. Bard College. (2002). url: https:\/\/books.google.com\/books?id=I-Gy0AEACAAJ."},{"key":"20","doi-asserted-by":"publisher","unstructured":"Haim Avron and Sivan Toledo. ``Randomized algorithms for estimating the trace of an implicit symmetric positive semi-definite matrix&apos;&apos;. J. ACM 58 (2011).","DOI":"10.1145\/1944345.1944349"},{"key":"21","doi-asserted-by":"publisher","unstructured":"Shashanka Ubaru and Yousef Saad. ``Applications of trace estimation techniques&apos;&apos;. In International Conference on High Performance Computing in Science and Engineering. Pages 19\u201333. Springer (2018).","DOI":"10.1007\/978-3-319-97136-0_2"},{"key":"22","doi-asserted-by":"publisher","unstructured":"Tyler Chen, Thomas Trogdon, and Shashanka Ubaru. ``Randomized matrix-free quadrature: Unified and uniform bounds for stochastic lanczos quadrature and the kernel polynomial method&apos;&apos;. SIAM Journal on Scientific Computing 47, A1733\u2013A1757 (2025). arXiv:https:\/\/doi.org\/10.1137\/23M1600414.","DOI":"10.1137\/23M1600414"},{"key":"23","doi-asserted-by":"publisher","unstructured":"Wassily Hoeffding. ``Probability inequalities for sums of bounded random variables&apos;&apos;. Journal of the American Statistical Association 58, 13\u201330 (1963). arXiv:https:\/\/www.tandfonline.com\/doi\/pdf\/10.1080\/01621459.1963.10500830.","DOI":"10.1080\/01621459.1963.10500830"},{"key":"24","doi-asserted-by":"publisher","unstructured":"Dorit Aharonov, Vaughan Jones, and Zeph Landau. ``A polynomial quantum algorithm for approximating the jones polynomial&apos;&apos;. Algorithmica 55, 395\u2013421 (2009).","DOI":"10.1007\/s00453-008-9168-0"},{"key":"25","doi-asserted-by":"publisher","unstructured":"Ismail Yunus Akhalwaya, Yang-Hui He, Lior Horesh, Vishnu Jejjala, William Kirby, Kugendran Naidoo, and Shashanka Ubaru. ``Representation of the fermionic boundary operator&apos;&apos;. Phys. Rev. A 106, 022407 (2022).","DOI":"10.1103\/PhysRevA.106.02240"},{"key":"26","doi-asserted-by":"crossref","unstructured":"Beno Eckmann. ``Harmonische funktionen und randwertaufgaben in einem komplex.&apos;&apos;. Commentarii mathematici Helvetici 17, 240\u2013255 (1944\/45). url: http:\/\/eudml.org\/doc\/138857.","DOI":"10.1007\/BF02566245"},{"key":"27","doi-asserted-by":"publisher","unstructured":"J. Friedman. ``Computing betti numbers via combinatorial laplacians&apos;&apos;. Algorithmica 21, 331\u2013346 (1998).","DOI":"10.1007\/PL00009218"},{"key":"28","unstructured":"Sushant Sachdeva and Nisheeth Vishnoi. ``Approximation theory and the design of fast algorithms&apos;&apos; (2013). arXiv:1309.4882."},{"key":"29","doi-asserted-by":"crossref","unstructured":"Paul Erd\u00f6s. ``Some remarks on polynomials&apos;&apos;. Bulletin of the American Mathematical Society 53, 1169\u20131176 (1947). url: https:\/\/api.semanticscholar.org\/CorpusID:120848504.","DOI":"10.1090\/S0002-9904-1947-08938-2"}],"container-title":["Quantum"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/quantum-journal.org\/papers\/q-2025-10-31-1901\/pdf\/","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2025,10,31]],"date-time":"2025-10-31T09:26:00Z","timestamp":1761902760000},"score":1,"resource":{"primary":{"URL":"https:\/\/quantum-journal.org\/papers\/q-2025-10-31-1901\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,10,31]]},"references-count":30,"URL":"https:\/\/doi.org\/10.22331\/q-2025-10-31-1901","archive":["CLOCKSS"],"relation":{},"ISSN":["2521-327X"],"issn-type":[{"value":"2521-327X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,10,31]]},"article-number":"1901"}}