Quantum Algorithm for Estimating Betti Numbers Using Cohomology Approach

Nhat A. Nghiem; Xianfeng David Gu; Tzu-Chieh Wei

doi:10.22331/q-2025-12-23-1955

Quantum Algorithm for Estimating Betti Numbers Using Cohomology Approach

Nhat A. Nghiem^1,2,3, Xianfeng David Gu^4,5, and Tzu-Chieh Wei^2,3

¹QuEra Computing Inc., Boston, Massachusetts 02135, USA
²Department of Physics and Astronomy, State University of New York at Stony Brook, Stony Brook, NY 11794-3800, USA
³C. N. Yang Institute for Theoretical Physics, State University of New York at Stony Brook, Stony Brook, NY 11794-3840, USA
⁴Department of Computer Science, State University of New York at Stony Brook, Stony Brook, NY 11794, USA
⁵Department of Applied Mathematics & Statistics, State University of New York at Stony Brook, Stony Brook, NY 11794, USA

Published:	2025-12-23, volume 9, page 1955
Editor:	Aleksandrs Belovs
Eprint:	arXiv:2309.10800v4
Doi:	https://doi.org/10.22331/q-2025-12-23-1955
Citation:	Quantum 9, 1955 (2025).

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

Abstract

Topological data analysis has emerged as a powerful tool for analyzing large-scale data. An abstract simplicial complex, in principle, can be built from data points, and by using tools from homology, topological features could be identified. Given a simplex, an important feature is called the Betti numbers, which roughly count the number of `holes' in different dimensions. Calculating Betti numbers exactly can be $\#$P-hard, and approximating them can be NP-hard, which rules out the possibility of any generic efficient algorithms and unconditional exponential quantum speedup. Here, we explore the specific setting of a triangulated manifold. In contrast to most known methods to estimate Betti numbers, which rely on homology, we exploit the `dual' approach, namely, cohomology, combining the insight of the Hodge theory and de Rham cohomology. Our proposed algorithm can calculate its $r$-th normalized Betti number $\beta_r/|S_r|$ up to some additive error $\epsilon$ with running time $\mathcal{O}\Big(\frac{\log(|S_r^K| |S_{r+1}^K|)}{\epsilon^2} \log (\log |S_r^K|) \big( r\log |S_r^K| \big) \Big)$, where $|S_r|$ is the number of $r$-simplexes in the given complex. For the estimation of $r$-th Betti number $\beta_r$ to a chosen multiplicative accuracy $\epsilon'$, our algorithm has complexity $ \mathcal{O}\Big(\frac{\log(|S_r^K| |S_{r+1}^K|)}{\epsilon'^2} \big( \frac{ \Gamma}{\beta_r}\big)^2 (\log |S_r^K|) \log \big( r\log |S_r^K| \big) \Big)$, where $\Gamma \leq |S_r^K|$ can be chosen. A detailed analysis is provided, showing that our cohomology framework can even perform exponentially faster than previous homology methods in several regimes. In particular, our method is most effective when $\beta_r \ll |S_r^K|$, which can offer more flexibility and practicability than existing quantum algorithms that achieve the best performance in the regime $\beta_r \approx |S_r^K|$.

► BibTeX data

@article{Nghiem2025quantumalgorithm,
  doi = {10.22331/q-2025-12-23-1955},
  url = {https://doi.org/10.22331/q-2025-12-23-1955},
  title = {Quantum {A}lgorithm for {E}stimating {B}etti {N}umbers {U}sing {C}ohomology {A}pproach},
  author = {Nghiem, Nhat A. and Gu, Xianfeng David and Wei, Tzu-Chieh},
  journal = {{Quantum}},
  issn = {2521-327X},
  publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}},
  volume = {9},
  pages = {1955},
  month = dec,
  year = {2025}
}

► References

[1] Larry Wasserman. ``Topological data analysis'' (2016).

[2] Peter Bubenik et al. ``Statistical topological data analysis using persistence landscapes.''. J. Mach. Learn. Res. 16, 77–102 (2015).

[3] Xianfeng Gu, Yalin Wang, Tony F Chan, Paul M Thompson, and Shing-Tung Yau. ``Genus zero surface conformal mapping and its application to brain surface mapping''. IEEE Transaction on Medical Imaging (TMI) 23, 949–958 (2004).
https://doi.org/10.1109/tmi.2004.831226

[4] Xianfeng David Gu and Shing-Tung Yau. ``Computational conformal geometry''. Volume 1. International Press Somerville, MA. (2008).

[5] Xianfeng Gu, Feng Luo, and Shing Tung Yau. ``Computational conformal geometry behind modern technologies''. Notices of the American Mathematical Society 67, 1509–1525 (2020).
https://doi.org/10.1090/noti2164

[6] Yuri Manin. ``Computable and uncomputable''. Sovetskoye Radio, Moscow 128, 15 (1980).

[7] Paul Benioff. ``The computer as a physical system: A microscopic quantum mechanical hamiltonian model of computers as represented by turing machines''. Journal of statistical physics 22, 563–591 (1980).
https://doi.org/10.1007/bf01011339

[8] Richard P Feynman. ``Simulating physics with computers''. In Feynman and computation. Pages 133–153. CRC Press (2018).

[9] David Deutsch. ``Quantum theory, the church–turing principle and the universal quantum computer''. Proceedings of the Royal Society of London. A. Mathematical and Physical Sciences 400, 97–117 (1985).

[10] David Deutsch and Richard Jozsa. ``Rapid solution of problems by quantum computation''. Proceedings of the Royal Society of London. Series A: Mathematical and Physical Sciences 439, 553–558 (1992).

[11] Peter W Shor. ``Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer''. SIAM review 41, 303–332 (1999).
https://doi.org/10.1137/s0036144598347011

[12] Lov K Grover. ``A fast quantum mechanical algorithm for database search''. In Proceedings of the twenty-eighth annual ACM symposium on Theory of computing. Pages 212–219. (1996).
https://doi.org/10.1145/237814.237866

[13] Dorit Aharonov, Vaughan Jones, and Zeph Landau. ``A polynomial quantum algorithm for approximating the jones polynomial''. In Proceedings of the thirty-eighth annual ACM symposium on Theory of computing. Pages 427–436. (2006).
https://doi.org/10.1007/s00453-008-9168-0

[14] Dominic W Berry, Graeme Ahokas, Richard Cleve, and Barry C Sanders. ``Efficient quantum algorithms for simulating sparse hamiltonians''. Communications in Mathematical Physics 270, 359–371 (2007).
https://doi.org/10.1007/s00220-006-0150-x

[15] Dominic W Berry and Andrew M Childs. ``Black-box hamiltonian simulation and unitary implementation''. Quantum Information and Computation 12, 29–62 (2009).
https://doi.org/10.26421/qic12.1-2-4

[16] Dominic W Berry. ``High-order quantum algorithm for solving linear differential equations''. Journal of Physics A: Mathematical and Theoretical 47, 105301 (2014).
https://doi.org/10.1088/1751-8113/47/10/105301

[17] Dominic W Berry, Andrew M Childs, and Robin Kothari. ``Hamiltonian simulation with nearly optimal dependence on all parameters''. In 2015 IEEE 56th annual symposium on foundations of computer science. Pages 792–809. IEEE (2015).
https://doi.org/10.1109/focs.2015.54

[18] Dominic W Berry, Andrew M Childs, Richard Cleve, Robin Kothari, and Rolando D Somma. ``Simulating hamiltonian dynamics with a truncated taylor series''. Physical review letters 114, 090502 (2015).
https://doi.org/10.1103/physrevlett.114.090502

[19] Dominic W Berry, Andrew M Childs, Aaron Ostrander, and Guoming Wang. ``Quantum algorithm for linear differential equations with exponentially improved dependence on precision''. Communications in Mathematical Physics 356, 1057–1081 (2017).
https://doi.org/10.1007/s00220-017-3002-y

[20] Guang Hao Low and Isaac L Chuang. ``Optimal hamiltonian simulation by quantum signal processing''. Physical review letters 118, 010501 (2017).
https://doi.org/10.1103/physrevlett.118.010501

[21] Guang Hao Low and Isaac L Chuang. ``Hamiltonian simulation by qubitization''. Quantum 3, 163 (2019).
https://doi.org/10.22331/q-2019-07-12-163

[22] Andrew M Childs. ``On the relationship between continuous-and discrete-time quantum walk''. Communications in Mathematical Physics 294, 581–603 (2010).
https://doi.org/10.1007/s00220-009-0930-1

[23] Andrew M Childs, Dmitri Maslov, Yunseong Nam, Neil J Ross, and Yuan Su. ``Toward the first quantum simulation with quantum speedup''. Proceedings of the National Academy of Sciences 115, 9456–9461 (2018).
https://doi.org/10.1073/pnas.1801723115

[24] Andrew M Childs and Yuan Su. ``Nearly optimal lattice simulation by product formulas''. Physical review letters 123, 050503 (2019).
https://doi.org/10.1103/physrevlett.123.050503

[25] Kosuke Mitarai, Makoto Negoro, Masahiro Kitagawa, and Keisuke Fujii. ``Quantum circuit learning''. Physical Review A 98, 032309 (2018).
https://doi.org/10.1103/physreva.98.032309

[26] Maria Schuld, Ilya Sinayskiy, and Francesco Petruccione. ``The quest for a quantum neural network''. Quantum Information Processing 13, 2567–2586 (2014).
https://doi.org/10.1007/s11128-014-0809-8

[27] Maria Schuld and Francesco Petruccione. ``Supervised learning with quantum computers''. Volume 17. Springer. (2018).
https://doi.org/10.1007/978-3-319-96424-9

[28] Maria Schuld, Ville Bergholm, Christian Gogolin, Josh Izaac, and Nathan Killoran. ``Evaluating analytic gradients on quantum hardware''. Physical Review A 99, 032331 (2019).
https://doi.org/10.1103/physreva.99.032331

[29] Maria Schuld. ``Machine learning in quantum spaces'' (2019).
https://doi.org/10.1103/PhysRevLett.122.040504

[30] Maria Schuld and Nathan Killoran. ``Quantum machine learning in feature hilbert spaces''. Physical review letters 122, 040504 (2019).
https://doi.org/10.1103/physrevlett.122.040504

[31] Maria Schuld, Alex Bocharov, Krysta M Svore, and Nathan Wiebe. ``Circuit-centric quantum classifiers''. Physical Review A 101, 032308 (2020).
https://doi.org/10.1103/physreva.101.032308

[32] Maria Schuld, Ryan Sweke, and Johannes Jakob Meyer. ``The effect of data encoding on the expressive power of variational quantum machine learning models'' (2020).
https://doi.org/10.1103/PhysRevA.103.032430

[33] Edward Farhi and Hartmut Neven. ``Classification with quantum neural networks on near term processors'' (2018).

[34] Leo Zhou, Sheng-Tao Wang, Soonwon Choi, Hannes Pichler, and Mikhail D Lukin. ``Quantum approximate optimization algorithm: Performance, mechanism, and implementation on near-term devices''. Physical Review X 10, 021067 (2020).
https://doi.org/10.1103/physrevx.10.021067

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

[36] A Yu Kitaev. ``Quantum measurements and the abelian stabilizer problem'' (1995).

[37] Shashanka Ubaru, Ismail Yunus Akhalwaya, Mark S Squillante, Kenneth L Clarkson, and Lior Horesh. ``Quantum topological data analysis with linear depth and exponential speedup'' (2021).

[38] Sam McArdle, András Gilyén, and Mario Berta. ``A streamlined quantum algorithm for topological data analysis with exponentially fewer qubits'' (2022).

[39] Sam Gunn and Niels Kornerup. ``Review of a quantum algorithm for betti numbers'' (2019).

[40] Bernardo Ameneyro, Vasileios Maroulas, and George Siopsis. ``Quantum persistent homology'' (2022).

[41] Alexander Schmidhuber and Seth Lloyd. ``Complexity-theoretic limitations on quantum algorithms for topological data analysis'' (2022).
https://doi.org/10.1103/PRXQuantum.4.040349

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

[43] Seth Lloyd, Masoud Mohseni, and Patrick Rebentrost. ``Quantum principal component analysis''. Nature Physics 10, 631–633 (2014).
https://doi.org/10.1038/nphys3029

[44] Andrew M Childs, Robin Kothari, and Rolando D Somma. ``Quantum algorithm for systems of linear equations with exponentially improved dependence on precision''. SIAM Journal on Computing 46, 1920–1950 (2017).
https://doi.org/10.1137/16m1087072

[45] Nhat A Nghiem and Tzu-Chieh Wei. ``An improved method for quantum matrix multiplication''. Quantum Information Processing 22, 299 (2023).
https://doi.org/10.1007/s11128-023-04054-6

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

[47] Jeff Cheeger, Werner Müller, and Robert Schrader. ``On the curvature of piecewise flat spaces''. Communications in mathematical Physics 92, 405–454 (1984).
https://doi.org/10.1007/bf01210729

[48] Nicholas Sharp, Mark Gillespie, and Keenan Crane. ``Geometry processing with intrinsic triangulations''. SIGGRAPH'21: ACM SIGGRAPH 2021 Courses (2021).
https://doi.org/10.1145/3450508.3464592

[49] Oliver Attie. ``A surgery theory for manifolds of bounded geometry'' (2003).

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

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

[52] Marcos Crichigno and Tamara Kohler. ``Clique homology is qma 1-hard''. Nature Communications 15, 9846 (2024).
https://doi.org/10.1038/s41467-024-54118-z

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

[54] Shashanka Ubaru and Yousef Saad. ``Fast methods for estimating the numerical rank of large matrices''. In International Conference on Machine Learning. Pages 468–477. PMLR (2016).

[55] Shashanka Ubaru, Yousef Saad, and Abd-Krim Seghouane. ``Fast estimation of approximate matrix ranks using spectral densities''. Neural computation 29, 1317–1351 (2017).
https://doi.org/10.1162/neco_a_00951

[56] Bojan Mohar and Carsten Thomassen. ``Graphs on surfaces''. Johns Hopkins University Press. (2001).
https://doi.org/10.56021/9780801866890

[57] Jeff Erickson and Kim Whittlesey. ``Greedy optimal homotopy and homology generators''. In SODA. Volume 5, pages 1038–1046. (2005).

[58] Erin W Chambers, Jeff Erickson, and Amir Nayyeri. ``Homology flows, cohomology cuts''. In Proceedings of the forty-first annual ACM symposium on Theory of computing. Pages 273–282. (2009).
https://doi.org/10.1145/1536414.1536453

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

[60] Daan Camps and Roel Van Beeumen. ``Approximate quantum circuit synthesis using block encodings''. Physical Review A 102, 052411 (2020).
https://doi.org/10.1103/physreva.102.052411

[61] Nhat A Nghiem. ``Refined quantum algorithms for principal component analysis and solving linear system'' (2025).

[62] Xiao-Ming Zhang, Tongyang Li, and Xiao Yuan. ``Quantum state preparation with optimal circuit depth: Implementations and applications''. Physical Review Letters 129, 230504 (2022).
https://doi.org/10.1103/physrevlett.129.230504

[63] Sam McArdle, András Gilyén, and Mario Berta. ``Quantum state preparation without coherent arithmetic'' (2022).

[64] Gabriel Marin-Sanchez, Javier Gonzalez-Conde, and Mikel Sanz. ``Quantum algorithms for approximate function loading''. Physical Review Research 5, 033114 (2023).
https://doi.org/10.1103/physrevresearch.5.033114

[65] Kouhei Nakaji, Shumpei Uno, Yohichi Suzuki, Rudy Raymond, Tamiya Onodera, Tomoki Tanaka, Hiroyuki Tezuka, Naoki Mitsuda, and Naoki Yamamoto. ``Approximate amplitude encoding in shallow parameterized quantum circuits and its application to financial market indicators''. Physical Review Research 4, 023136 (2022).
https://doi.org/10.1103/physrevresearch.4.023136

[66] Shantanav Chakraborty, András Gilyén, and Stacey Jeffery. ``The power of block-encoded matrix powers: improved regression techniques via faster hamiltonian simulation'' (2018).
https://doi.org/10.4230/LIPIcs.ICALP.2019.33

[67] Mikio Nakahara. ``Geometry, topology and physics''. CRC press. (2018).
https://doi.org/10.1201/9781315275826

[68] Allen Hatcher. ``Algebraic topology''. Cambridge University Press. (2005).

[69] Raoul Bott, Loring W Tu, et al. ``Differential forms in algebraic topology''. Volume 82. Springer. (1982).
https://doi.org/10.1007/978-1-4757-3951-0

[70] David Xianfeng Gu and Emil Saucan. ``Classical and discrete differential geometry: theory, applications and algorithms''. CRC Press. (2023).

[71] Herbert Edelsbrunner and John Harer. ``Computational topology: an introduction''. American Mathematical Soc. (2010).

[72] James R Munkres. ``Elements of algebraic topology''. CRC press. (2018).
https://doi.org/10.1201/9780429493911

Cited by

[1] Kiran Siripuri, Shashank Thota, and Prasanna Mandala, 2026 6th International Conference on Inventive Computation and Information Technologies (ICICIT) 508 (2026) ISBN:979-8-3315-5011-0.

[2] Nhat A. Nghiem, Linh Nguyen, Tuan K. Do, Tzu-Chieh Wei, and Trung V. Phan, "Quantum algorithm for estimating Olivier-Ricci curvature", Physical Review Research 8 2, 023207 (2026).

[3] Casper Gyurik, Alexander Schmidhuber, Robbie King, Vedran Dunjko, and Ryu Hayakawa, "Provable Quantum Speedups for Computing Persistence in Topological Data Analysis", PRX Quantum 7 2, 020361 (2026).

[4] Nhat A. Nghiem and Tzu-Chieh Wei, "Hybrid quantum-classical framework for Betti number estimation with applications to topological data analysis", arXiv:2508.01516, (2025).

[5] Nhat A. Nghiem, "New Quantum Algorithm For Solving Linear System of Equations", arXiv:2502.13630, (2025).

[6] Stefano Scali, Chukwudubem Umeano, and Oleksandr Kyriienko, "The topology of data hides in quantum thermal states", arXiv:2402.15633, (2024).

[7] Nhat A. Nghiem, Tuan K. Do, Tzu-Chieh Wei, and Trung V. Phan, "Quantum Algorithm for Estimating Intrinsic Geometry", arXiv:2508.06355, (2025).

[8] Nhat A. Nghiem, "Towards quantum topological data analysis: torsion detection", arXiv:2508.19943, (2025).

[9] Nhat A. Nghiem, "Quantum topological data analysis algorithm for dynamical systems", arXiv:2509.22372, (2025).

[10] Nhat A. Nghiem, "New aspects of quantum topological data analysis: Betti number estimation, and testing and tracking of homology and cohomology classes", arXiv:2506.01432, (2025).

The above citations are from Crossref's cited-by service (last updated successfully 2026-08-09 04:47:17) and SAO/NASA ADS (last updated successfully 2026-08-08 15:55:17). The list may be incomplete as not all publishers provide suitable and complete citation data.

Could not fetch ADS cited-by data during last attempt 2026-08-09 04:47:17: Cannot retrieve data from ADS due to rate limitations.

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.