quantum-computing

A streamlined quantum algorithm for topological data analysis with exponentially fewer qubits

Quantum Journal

25 min read

0 likes

⚡ Quantum Brief

Researchers Sam McArdle, András Gilyén, and Mario Berta developed a quantum algorithm for topological data analysis that computes persistent Betti numbers with exponentially fewer qubits than prior methods. The algorithm achieves a near-quintic speedup over classical approaches for datasets with constant additive error, significantly reducing runtime for machine learning applications. A new quantum-inspired classical power method was introduced, scaling only quadratically worse than the quantum version, matching heuristic classical performance. The study challenges claims of exponential quantum advantage for practical tasks, finding no current evidence supporting such speedups in topological data analysis. Complexity analysis reveals polynomial time improvements and exponential space savings over existing quantum algorithms, advancing resource-efficient quantum computation.

A streamlined quantum algorithm for topological data analysis with exponentially fewer qubits

Summarize this article with:

AbstractTopological invariants of a dataset, such as the number of holes that survive from one length scale to another (persistent Betti numbers) can be used to analyze and classify data in machine learning applications. We present an improved quantum algorithm for computing persistent Betti numbers, and provide an end-to-end complexity analysis. Our approach provides large polynomial time improvements, and an exponential space saving, over existing quantum algorithms. Subject to gap dependencies, our algorithm obtains an almost quintic speedup in the number of datapoints over previously known rigorous classical algorithms for computing the persistent Betti numbers to constant additive error – the salient task for applications. However, we also introduce a quantum-inspired classical power method with provable scaling only quadratically worse than the quantum algorithm. This gives a provable classical algorithm with scaling comparable to existing classical heuristics. We discuss whether quantum algorithms can achieve an exponential speedup for tasks of practical interest, as claimed previously. We conclude that there is currently no evidence for this being the case.► BibTeX data@article{McArdle2026streamlinedquantum, doi = {10.22331/q-2026-04-10-2058}, url = {https://doi.org/10.22331/q-2026-04-10-2058}, title = {A streamlined quantum algorithm for topological data analysis with exponentially fewer qubits}, author = {McArdle, Sam and Gily{\'{e}}n,, Andr{\'{a}}s and Berta, Mario}, journal = {{Quantum}}, issn = {2521-327X}, publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, volume = {10}, pages = {2058}, month = apr, year = {2026} }► References [1] Gunnar Carlsson. Topological methods for data modelling.

Nature Reviews Physics, 2 (12): 697–708, 2020. 10.1038/s42254-020-00249-3. https://doi.org/10.1038/s42254-020-00249-3 [2] Vin De Silva and Robert Ghrist. Coverage in sensor networks via persistent homology. Algebraic & Geometric Topology, 7 (1): 339–358, 2007. 10.2140/agt.2007.7.339. https://doi.org/10.2140/agt.2007.7.339 [3] Michelle Feng and Mason A Porter. Persistent homology of geospatial data: A case study with voting. SIAM Review, 63 (1): 67–99, 2021. 10.1137/19m1241519. https://doi.org/10.1137/19m1241519 [4] 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 [5] Bastian Rieck, Tristan Yates, Christian Bock, Karsten Borgwardt, Guy Wolf, Nicholas Turk-Browne, and Smita Krishnaswamy. Uncovering the topology of time-varying fmri data using cubical persistence. Advances in neural information processing systems, 33: 6900–6912, 2020. 10.5555/3495724.3496303. URL https://dl.acm.org/doi/abs/10.5555/3495724.3496303. https://doi.org/10.5555/3495724.3496303 [6] Jose A Perea and John Harer. Sliding windows and persistence: An application of topological methods to signal analysis. Foundations of Computational Mathematics, 15 (3): 799–838, 2015. 10.1007/s10208-014-9206-z. https://doi.org/10.1007/s10208-014-9206-z [7] Marian Gidea and Yuri Katz. Topological data analysis of financial time series: Landscapes of crashes. Physica A: Statistical Mechanics and its Applications, 491: 820–834, 2018. 10.1016/j.physa.2017.09.028. https://doi.org/10.1016/j.physa.2017.09.028 [8] Daniel Leykam and Dimitris G. Angelakis. Topological data analysis and machine learning. Advances in Physics: X, 8 (1): 2202331, 2023. 10.1080/23746149.2023.2202331. https://doi.org/10.1080/23746149.2023.2202331 [9] Nicholas Sale, Jeffrey Giansiracusa, and Biagio Lucini. Quantitative analysis of phase transitions in two-dimensional $xy$ models using persistent homology. Phys. Rev. E, 105: 024121, Feb 2022. 10.1103/PhysRevE.105.024121. URL https://doi.org/10.1103/PhysRevE.105.024121. https://doi.org/10.1103/PhysRevE.105.024121 [10] Andrea Tirelli and Natanael C. Costa. Learning quantum phase transitions through topological data analysis. Phys. Rev. B, 104: 235146, Dec 2021. 10.1103/PhysRevB.104.235146. URL https://doi.org/10.1103/PhysRevB.104.235146. https://doi.org/10.1103/PhysRevB.104.235146 [11] Felix Hensel, Michael Moor, and Bastian Rieck. A survey of topological machine learning methods. Frontiers in Artificial Intelligence, 4: 681108, 2021. 10.3389/frai.2021.681108. https://doi.org/10.3389/frai.2021.681108 [12] Niels Neumann and Sterre den Breeijen. Limitations of clustering using quantum persistent homology. arXiv preprint arXiv:1911.10781, 2019. arXiv:1911.10781 [13] 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 [14] Seth Lloyd. Quantum algorithms for topological and geometric analysis of data, 2021. URL https://youtu.be/G4t7Pdn9R6c?t=3853. Timecode: 1:04:13. https://youtu.be/G4t7Pdn9R6c?t=3853 [15] Sam Gunn and Niels Kornerup. Review of a quantum algorithm for betti numbers. arXiv preprint arXiv:1906.07673, 2019. arXiv:1906.07673 [16] 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. arXiv:2108.02811 [17] Ryu Hayakawa. Quantum algorithm for persistent Betti numbers and topological data analysis. Quantum, 6: 873, December 2022. ISSN 2521-327X. 10.22331/q-2022-12-07-873. URL https://doi.org/10.22331/q-2022-12-07-873. https://doi.org/10.22331/q-2022-12-07-873 [18] Bernardo Ameneyro, Vasileios Maroulas, and George Siopsis. Quantum persistent homology. Journal of Applied and Computational Topology, 8: 1929–1963, 2024. 10.1007/s41468-023-00160-7. https://doi.org/10.1007/s41468-023-00160-7 [19] 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 (1): 010319, 2024. 10.1103/prxquantum.5.010319. https://doi.org/10.1103/prxquantum.5.010319 [20] Edelsbrunner, Letscher, and Zomorodian. Topological persistence and simplification. Discrete & Computational Geometry, 28 (4): 511–533, Nov 2002. ISSN 1432-0444. 10.1007/s00454-002-2885-2. URL https://doi.org/10.1007/s00454-002-2885-2. https://doi.org/10.1007/s00454-002-2885-2 [21] Nikola Milosavljević, Dmitriy Morozov, and Primoz Skraba. Zigzag persistent homology in matrix multiplication time. In Proceedings of the twenty-seventh Annual Symposium on Computational Geometry, pages 216–225, 2011. 10.1145/1998196.1998229. https://doi.org/10.1145/1998196.1998229 [22] Nikola Milosavljevic, Dmitriy Morozov, and Primoz Skraba.

Zigzag Persistent Homology in Matrix Multiplication Time. Research Report RR-7393, INRIA, September 2010. URL https://hal.inria.fr/inria-00520171. https://hal.inria.fr/inria-00520171 [23] Konstantin Mischaikow and Vidit Nanda. Morse theory for filtrations and efficient computation of persistent homology. Discrete & Computational Geometry, 50 (2): 330–353, 2013. 10.1007/s00454-013-9529-6. https://doi.org/10.1007/s00454-013-9529-6 [24] Joel Friedman. Computing betti numbers via combinatorial laplacians. Algorithmica, 21 (4): 331–346, 1998. 10.1007/pl00009218. https://doi.org/10.1007/pl00009218 [25] 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 [26] 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. 2022a. URL https://arxiv.org/abs/2209.09371. arXiv:2209.09371 [27] 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 [28] Chris Cade and P Marcos Crichigno. Complexity of supersymmetric systems and the cohomology problem. Quantum, 8: 1325, 2024. 10.22331/q-2024-04-30-1325. https://doi.org/10.22331/q-2024-04-30-1325 [29] Dorit Aharonov, Vaughan Jones, and Zeph Landau. A polynomial quantum algorithm for approximating the Jones polynomial. Algorithmica, 55 (3): 395–421, 2009. 10.1007/s00453-008-9168-0. https://doi.org/10.1007/s00453-008-9168-0 [30] Peter W Shor and Stephen P Jordan. Estimating Jones polynomials is a complete problem for one clean qubit. Quantum Information and Computation, 8 (8–9): 681–714, 2008. 10.26421/qic8.8-9-1. https://doi.org/10.26421/qic8.8-9-1 [31] Magnus Bordewich, Michael Freedman, László Lovász, and D Welsh. Approximate counting and quantum computation. Combinatorics, Probability and Computing, 14 (5–6): 737–754, 2005. 10.1017/s0963548305007005. https://doi.org/10.1017/s0963548305007005 [32] 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 [33] Marcos Crichigno and Tamara Kohler. Clique homology is QMA$_1$-hard. Nature Communications, 15: 9846, 2024. 10.1038/s41467-024-54118-z. https://doi.org/10.1038/s41467-024-54118-z [34] Alexander Schmidhuber and Seth Lloyd. Complexity-theoretic limitations on quantum algorithms for topological data analysis. PRX Quantum, 4 (4): 040349, 2023. 10.1103/prxquantum.4.040349. https://doi.org/10.1103/prxquantum.4.040349 [35] Robbie King and Tamara Kohler. Gapped clique homology on weighted graphs is QMA$_1$-hard and contained in QMA. SIAM Journal on Computing, 55 (1): S198–S231, 2026. 10.1137/24m1710243. https://doi.org/10.1137/24m1710243 [36] Simon Apers, Sayantan Sen, and Dániel Szabó. A (simple) classical algorithm for estimating betti numbers. Quantum, 7: 1202, 2023. 10.22331/q-2023-12-06-1202. https://doi.org/10.22331/q-2023-12-06-1202 [37] 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 [38] Allen Hatcher. Algebraic topology.

Cambridge University Press, 2005. [39] András Gilyén, Yuan Su, Guang Hao Low, and Nathan Wiebe. Quantum singular value transformation and beyond: Exponential improvements for quantum matrix arithmetics [full version], 2018. arXiv: 1806.01838. https://doi.org/10.1145/3313276.3316366 [40] Sara Ayman Metwalli, François Le Gall, and Rodney Van Meter. Finding small and large $k$-clique instances on a quantum computer. IEEE Transactions on Quantum Engineering, 1: 1–11, 2020. 10.1109/TQE.2020.3045692. https://doi.org/10.1109/TQE.2020.3045692 [41] Connor T. Hann, Gideon Lee, S.M. Girvin, and Liang Jiang. Resilience of quantum random access memory to generic noise. PRX Quantum, 2: 020311, Apr 2021. 10.1103/PRXQuantum.2.020311. URL https://doi.org/10.1103/PRXQuantum.2.020311. https://doi.org/10.1103/PRXQuantum.2.020311 [42] Ismail Yunus Akhalwaya, Yang-Hui He, Lior Horesh, Vishnu Jejjala, William Kirby, Kugendran Naidoo, and Shashanka Ubaru. Representation of the fermionic boundary operator. Physical Review A, 106 (2): 022407, 2022b. 10.1103/physreva.106.022407. https://doi.org/10.1103/physreva.106.022407 [43] Iordanis Kerenidis and Anupam Prakash. Quantum machine learning with subspace states. arXiv preprint arXiv:2202.00054, 2022. arXiv:2202.00054 [44] Kianna Wan. Exponentially faster implementations of select (h) for fermionic hamiltonians. Quantum, 5: 380, 2021. 10.22331/q-2021-01-12-380. https://doi.org/10.22331/q-2021-01-12-380 [45] Lin Lin and Yu Tong. Near-optimal ground state preparation. Quantum, 4: 372, 2020a. 10.22331/q-2020-12-14-372. https://doi.org/10.22331/q-2020-12-14-372 [46] Andreas Bärtschi and Stephan Eidenbenz. Deterministic preparation of dicke states. In Fundamentals of Computation Theory, pages 126–139.

Springer International Publishing, 2019. 10.1007/978-3-030-25027-0_9. URL https://doi.org/10.1007%2F978-3-030-25027-0_9. https://doi.org/10.1007/978-3-030-25027-0_9 [47] Andreas Bärtschi and Stephan Eidenbenz. Short-depth circuits for dicke state preparation. In 2022 IEEE International Conference on Quantum Computing and Engineering (QCE), pages 87–96. IEEE, 2022. 10.1109/qce53715.2022.00027. https://doi.org/10.1109/qce53715.2022.00027 [48] András Gilyén. Quantum walk based search methods and algorithmic applications. Master's thesis, Eötvös Loránd University, 2014. URL http://web.cs.elte.hu/blobs/diplomamunkak/msc_mat/2014/gilyen_andras_pal.pdf. http://web.cs.elte.hu/blobs/diplomamunkak/msc_mat/2014/gilyen_andras_pal.pdf [49] Dmitriy Morozov. Persistence algorithm takes cubic time in worst case. BioGeometry News, Dept. Comput. Sci., Duke Univ, 2, 2005. [50] Chao Chen and Michael Kerber. Persistent homology computation with a twist. In Proceedings 27th European workshop on computational geometry, volume 11, pages 197–200, 2011. [51] Vin De Silva, Dmitriy Morozov, and Mikael Vejdemo-Johansson. Dualities in persistent (co) homology. Inverse Problems, 27 (12): 124003, 2011. 10.1088/0266-5611/27/12/124003. https://doi.org/10.1088/0266-5611/27/12/124003 [52] Michael Joswig and Marc E Pfetsch. Computing optimal morse matchings. SIAM Journal on Discrete Mathematics, 20 (1): 11–25, 2006. 10.1137/s0895480104445885. https://doi.org/10.1137/s0895480104445885 [53] Marian Mrozek, Paweł Pilarczyk, and Natalia Żelazna. Homology algorithm based on acyclic subspace. Computers & Mathematics with Applications, 55 (11): 2395–2412, 2008. 10.1016/j.camwa.2007.08.044. https://doi.org/10.1016/j.camwa.2007.08.044 [54] Afra Zomorodian. The tidy set: a minimal simplicial set for computing homology of clique complexes. In Proceedings of the twenty-sixth annual symposium on Computational geometry, pages 257–266, 2010. 10.1145/1810959.1811004. https://doi.org/10.1145/1810959.1811004 [55] 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 [56] Paweł Dłotko and Hubert Wagner. Simplification of complexes for persistent homology computations. Homology, Homotopy and Applications, 16 (1): 49–63, 2014. 10.4310/hha.2014.v16.n1.a3. https://doi.org/10.4310/hha.2014.v16.n1.a3 [57] Jean-Daniel Boissonnat, Siddharth Pritam, and Divyansh Pareek. Strong collapse and persistent homology. Journal of Topology and Analysis, 15 (1): 185–213, 2023. 10.1142/s1793525321500291. https://doi.org/10.1142/s1793525321500291 [58] 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 [59] 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 [60] Rui Wang, Rundong Zhao, Emily Ribando-Gros, Jiahui Chen, Yiying Tong, and Guo-Wei Wei. Hermes: Persistent spectral graph software. Foundations of data science (Springfield, Mo.), 3 (1): 67, 2021. 10.3934/fods.2021006. https://doi.org/10.3934/fods.2021006 [61] Jared L. Aurentz, Anthony P. Austin, Michele Benzi, and Vassilis Kalantzis. Stable computation of generalized matrix functions via polynomial interpolation. SIAM Journal on Matrix Analysis and Applications, 40 (1): 210–234, 2019. 10.1137/18M1191786. URL https://doi.org/10.1137/18M1191786. https://doi.org/10.1137/18M1191786 [62] Michael Goff. Extremal Betti numbers of Vietoris-Rips complexes. Discrete & Computational Geometry, 46 (1): 132–155, 2011. 10.1007/s00454-010-9274-z. https://doi.org/10.1007/s00454-010-9274-z [63] Matthew Kahle. Random geometric complexes. Discrete & Computational Geometry, 45 (3): 553–573, jan 2011. 10.1007/s00454-010-9319-3. URL https://doi.org/10.1007%2Fs00454-010-9319-3. https://doi.org/10.1007/s00454-010-9319-3 [64] Omer Bobrowski and Matthew Kahle. Topology of random geometric complexes: a survey. Journal of Applied and Computational Topology, 1 (3–4): 331–364, 2018. 10.1007/s41468-017-0010-0. https://doi.org/10.1007/s41468-017-0010-0 [65] Gunnar Carlsson and Mikael Vejdemo-Johansson.

Topological Data Analysis with Applications.

Cambridge University Press, 2021. 10.1017/9781108975704. https://doi.org/10.1017/9781108975704 [66] Chad Topaz. Chad's self-help homology tutorial for the simple(x) minded, 2016. URL https://drive.google.com/file/d/0B3Www1z6Tm8xV3ozTmN5RE94bDg/view?resourcekey=0-tE7y-zXFtV3OWSGmjUebYA. Last accessed 7 April 2022. https://drive.google.com/file/d/0B3Www1z6Tm8xV3ozTmN5RE94bDg/view?resourcekey=0-tE7y-zXFtV3OWSGmjUebYA [67] Michelle Feng, Abigail Hickok, Yacoub Kureh, Mason Porter, and Chad Topaz. Connecting the dots: Discovering the `shape' of data. Front. Young Minds, 9 (551557), 2021. 10.3389/frym.2021.551557. URL https://kids.frontiersin.org/articles/10.3389/frym.2021.551557. https://doi.org/10.3389/frym.2021.551557 [68] Bastian Rieck. Topological data analysis for machine learning i: Algebraic topology, September 2020. URL https://www.youtube.com/watch?v=gVq_xXnwV-4. Last accessed 7 April 2022. https://www.youtube.com/watch?v=gVq_xXnwV-4 [69] Michelle Feng. Michelle feng: Topological techniques, February 2021. URL https://www.youtube.com/watch?v=M3TU4NmHDkM. Last accessed 7 April 2022. https://www.youtube.com/watch?v=M3TU4NmHDkM [70] Lek-Heng Lim. Hodge laplacians on graphs. SIAM Review, 62 (3): 685–715, 2020. 10.1137/18m1223101. https://doi.org/10.1137/18m1223101 [71] Timothy E Goldberg. Combinatorial laplacians of simplicial complexes. Senior Thesis, Bard College, 2002. [72] Guang Hao Low and Isaac L. Chuang. Hamiltonian simulation by uniform spectral amplification. arXiv: 1707.05391, 2017. arXiv:1707.05391 [73] Gilles Brassard, Peter Høyer, Michele Mosca, and Alain Tapp. Quantum amplitude amplification and estimation.

In Quantum Computation and Quantum Information: A Millennium Volume, volume 305 of Contemporary Mathematics Series, pages 53–74. AMS, 2002. 10.1090/conm/305/05215. arXiv: quant-ph/0005055. https://doi.org/10.1090/conm/305/05215 arXiv:quant-ph/0005055 [74] Patrick Rall and Bryce Fuller. Amplitude Estimation from Quantum Signal Processing. Quantum, 7: 937, March 2023. ISSN 2521-327X. 10.22331/q-2023-03-02-937. URL https://doi.org/10.22331/q-2023-03-02-937. https://doi.org/10.22331/q-2023-03-02-937 [75] Ryan Babbush, Craig Gidney, Dominic W Berry, Nathan Wiebe, Jarrod McClean, Alexandru Paler, Austin Fowler, and Hartmut Neven. Encoding electronic spectra in quantum circuits with linear t complexity. Physical Review X, 8 (4): 041015, 2018. 10.1103/physrevx.8.041015. https://doi.org/10.1103/physrevx.8.041015 [76] Vittorio Giovannetti, Seth Lloyd, and Lorenzo Maccone. Quantum random access memory.

Physical Review Letters, 100 (16): 160501, 2008. 10.1103/PhysRevLett.100.160501. arXiv: 0708.1879. https://doi.org/10.1103/PhysRevLett.100.160501 arXiv:0708.1879 [77] Thomas G Draper, Samuel A Kutin, Eric M Rains, and Krysta M Svore. A logarithmic-depth quantum carry-lookahead adder. Quantum Information and Computation, 6 (4–5): 351–369, 2006. 10.26421/qic6.4-5-4. https://doi.org/10.26421/qic6.4-5-4 [78] Shouvanik Chakrabarti, Rajiv Krishnakumar, Guglielmo Mazzola, Nikitas Stamatopoulos, Stefan Woerner, and William J. Zeng. A Threshold for Quantum Advantage in Derivative Pricing. Quantum, 5: 463, June 2021. ISSN 2521-327X. 10.22331/q-2021-06-01-463. URL https://doi.org/10.22331/q-2021-06-01-463. https://doi.org/10.22331/q-2021-06-01-463 [79] Guang Hao Low, Vadym Kliuchnikov, and Luke Schaeffer. Trading T gates for dirty qubits in state preparation and unitary synthesis. Quantum, 8: 1375, 2024. 10.22331/q-2024-06-17-1375. https://doi.org/10.22331/q-2024-06-17-1375 [80] Lin Lin and Yu Tong. Optimal polynomial based quantum eigenstate filtering with application to solving quantum linear systems. Quantum, 4: 361, 2020b. 10.22331/q-2020-11-11-361. arXiv: 1910.14596. https://doi.org/10.22331/q-2020-11-11-361 arXiv:1910.14596 [81] John M. Martyn, Zane M. Rossi, Andrew K. Tan, and Isaac L. Chuang. Grand unification of quantum algorithms. PRX Quantum, 2: 040203, Dec 2021. 10.1103/PRXQuantum.2.040203. URL https://doi.org/10.1103/PRXQuantum.2.040203. https://doi.org/10.1103/PRXQuantum.2.040203 [82] András Pál Gilyén. Quantum walk based search methods and algorithmic applications. PhD thesis, MSc Thesis, Eötvös Loránd University, 2014. [83] C Gidney. Quantum computing stack exchange, 2020. URL https://quantumcomputing.stackexchange.com/questions/11734/what-is-the-complexity-of-splitting-a-state-into-a-superposition-of-n-computat. https://quantumcomputing.stackexchange.com/questions/11734/what-is-the-complexity-of-splitting-a-state-into-a-superposition-of-n-computat [84] S Pallister. Quantum computing stack exchange, 2022. URL https://quantumcomputing.stackexchange.com/questions/27864/creating-a-uniform-superposition-of-a-subset-of-basis-states. https://quantumcomputing.stackexchange.com/questions/27864/creating-a-uniform-superposition-of-a-subset-of-basis-statesCited byCould not fetch Crossref cited-by data during last attempt 2026-04-10 06:47:38: Could not fetch cited-by data for 10.22331/q-2026-04-10-2058 from Crossref. This is normal if the DOI was registered recently. Could not fetch ADS cited-by data during last attempt 2026-04-10 06:47:38: 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. AbstractTopological invariants of a dataset, such as the number of holes that survive from one length scale to another (persistent Betti numbers) can be used to analyze and classify data in machine learning applications. We present an improved quantum algorithm for computing persistent Betti numbers, and provide an end-to-end complexity analysis. Our approach provides large polynomial time improvements, and an exponential space saving, over existing quantum algorithms. Subject to gap dependencies, our algorithm obtains an almost quintic speedup in the number of datapoints over previously known rigorous classical algorithms for computing the persistent Betti numbers to constant additive error – the salient task for applications. However, we also introduce a quantum-inspired classical power method with provable scaling only quadratically worse than the quantum algorithm. This gives a provable classical algorithm with scaling comparable to existing classical heuristics. We discuss whether quantum algorithms can achieve an exponential speedup for tasks of practical interest, as claimed previously. We conclude that there is currently no evidence for this being the case.► BibTeX data@article{McArdle2026streamlinedquantum, doi = {10.22331/q-2026-04-10-2058}, url = {https://doi.org/10.22331/q-2026-04-10-2058}, title = {A streamlined quantum algorithm for topological data analysis with exponentially fewer qubits}, author = {McArdle, Sam and Gily{\'{e}}n,, Andr{\'{a}}s and Berta, Mario}, journal = {{Quantum}}, issn = {2521-327X}, publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, volume = {10}, pages = {2058}, month = apr, year = {2026} }► References [1] Gunnar Carlsson. Topological methods for data modelling.

Topological Data Analysis with Applications.

Read Original

Source Information

Source: Quantum Journal

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

A streamlined quantum algorithm for topological data analysis with exponentially fewer qubits

Tags

Source Information