arXiv:2209.12887 · Quantum

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

Sam McArdle, András Gilyén, Mario Berta

Published Apr 10, 2026• 16 citations

Abstract

Topological 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.

DOI: 10.22331/q-2026-04-10-2058

Related papers

Quantum algorithm for persistent Betti numbers and topological data analysis

Ryu Hayakawa

Topological data analysis (TDA) is an emergent field of data analysis. The critical step of TDA is computing the persistent Betti numbers. Existing classical algorithms for TDA are limited if we want to learn from high-dimensional topological features because the number of high-dimensional simplices grows exponentially in the size of the data. In the context of quantum computation, it has been previously shown that there exists an efficient quantum algorithm for estimating the Betti numbers even in high dimensions. However, the Betti numbers are less general than the persistent Betti numbers, and there have been no quantum algorithms that can estimate the persistent Betti numbers of arbitrary dimensions. This paper shows the first quantum algorithm that can estimate the (normalized) persistent Betti numbers of arbitrary dimensions. Our algorithm is efficient for simplicial complexes such as the Vietoris-Rips complex and demonstrates exponential speedup over the known classical algorithms.

arXiv:2111.00433QuantumDec 7, 202240 citations

Provable Quantum Speedups for Computing Persistence in Topological Data Analysis

Casper Gyurik, Alexander Schmidhuber, Robbie King +2 more

Topological data analysis (TDA) aims to extract noise-robust features from a dataset by examining the number and persistence of holes in its topology. We provide an efficient quantum algorithm for a computational problem closely related to a core task in TDA—determining whether a given hole persists across different length scales. Further, we prove the problem itself is B Q P 1 -hard, implying that a classical solution is extremely unlikely; this stands in contrast to all previous quantum approaches to TDA, where the problems were also intractable for quantum computers, or where a rigorous proof of classical hardness still remains open. This result implies an exponential quantum speedup for this problem under standard complexity-theoretic assumptions. Our approach relies on encoding the persistence of a hole in a variant of the guided sparse Hamiltonian problem, where the guiding state is constructed from a harmonic representative of the hole.

arXiv:2410.21258PRX QuantumMay 5, 20262 citations

Complexity-Theoretic Limitations on Quantum Algorithms for Topological Data Analysis

Alexander Schmidhuber, Seth Lloyd

Quantum algorithms for topological data analysis (TDA) seem to provide an exponential advantage over the best classical approach while remaining immune to dequantization procedures and the data-loading problem.In this paper, we give complexity-theoretic evidence that the central task of TDA-estimating Betti numbers-is intractable even for quantum computers.Specifically, we prove that the problem of computing Betti numbers exactly is #P-hard, while the problem of approximating Betti numbers up to multiplicative error is NP-hard.Moreover, both problems retain their hardness if restricted to the regime where quantum algorithms for TDA perform best.Because quantum computers are not expected to solve #P-hard or NP-hard problems in subexponential time, our results imply that quantum algorithms for TDA offer only a polynomial advantage in the worst case.We support our claim by showing that the seminal quantum algorithm for TDA developed by Lloyd, Garnerone, and Zanardi achieves a quadratic speedup over the best-known classical approach in asymptotically almost all cases.Finally, we argue that an exponential quantum advantage can be recovered if the input data is given as a specification of simplices rather than as a list of vertices and edges.

PRX QuantumDec 28, 202317 citations

From Betti Numbers to Persistence Diagrams: A Hybrid Quantum Algorithm for Topological Data Analysis

Dong Liu

Persistence diagrams serve as a core tool in topological data analysis, playing a crucial role in pathological monitoring, drug discovery, and materials design. However, existing quantum topological algorithms, such as the LGZ algorithm, can only efficiently compute summary statistics like Betti numbers, failing to provide persistence diagram information that tracks the lifecycle of individual topological features, severely limiting their practical value. This paper proposes a novel quantum-classical hybrid algorithm that achieves, for the first time, the leap from "quantum computation of Betti numbers" to "quantum acquisition of practical persistence diagrams." The algorithm leverages the LGZ quantum algorithm as an efficient feature extractor, mining the harmonic form eigenvectors of the combinatorial Laplacian as well as Betti numbers, constructing specialized topological kernel functions to train a quantum support vector machine (QSVM), and learning the mapping from quantum topological features to persistence diagrams. The core contributions of this algorithm are: (1) elevating quantum topological computation from statistical summaries to pattern recognition, greatly expanding its application value; (2) obtaining more practical topological information in the form of persistence diagrams for real-world applications while maintaining the exponential speedup advantage of quantum computation; (3) proposing a novel hybrid paradigm of "classical precision guiding quantum efficiency." This method provides a feasible pathway for the practical implementation of quantum topological data analysis.

quant-pharXiv:2512.02081Dec 2, 20250 citations

Complexity-Theoretic Limitations on Quantum Algorithms for Topological Data Analysis

Alexander Schmidhuber, Seth Lloyd

Quantum algorithms for topological data analysis (TDA) seem to provide an exponential advantage over the best classical approach while remaining immune to dequantization procedures and the data-loading problem. In this paper, we give complexity-theoretic evidence that the central task of TDA -- estimating Betti numbers -- is intractable even for quantum computers. Specifically, we prove that the problem of computing Betti numbers exactly is #P-hard, while the problem of approximating Betti numbers up to multiplicative error is NP-hard. Moreover, both problems retain their hardness if restricted to the regime where quantum algorithms for TDA perform best. Because quantum computers are not expected to solve #P-hard or NP-hard problems in subexponential time, our results imply that quantum algorithms for TDA offer only a polynomial advantage in the worst case. We support our claim by showing that the seminal quantum algorithm for TDA developed by Lloyd, Garnerone and Zanardi achieves a quadratic speedup over the best known classical approach in asymptotically almost all cases. Finally, we argue that an exponential quantum advantage can be recovered if the input data is given as a specification of simplices rather than as a list of vertices and edges.

arXiv:2209.14286Sep 28, 20223 citations

Hybrid quantum-classical framework for Betti number estimation with applications to topological data analysis

Nhat A. Nghiem, Tzu-Chieh Wei

Topological data analysis (TDA) is a rapidly growing area that applies techniques from algebraic topology to extract robust features from large-scale data. A key task in TDA is the estimation of (normalized) Betti numbers, which capture essential topological invariants. While recent work has led to quantum algorithms for this problem, we explore an alternative direction: combining classical and quantum resources to estimate the Betti numbers of a simplicial complex more efficiently. Assuming the classical description of a simplicial complex, that is, its set of vertices and edges, we propose a hybrid quantum-classical algorithm. The classical component enumerates all simplices, and this combinatorial structure is subsequently processed by a quantum algorithm to estimate the Betti numbers. We analyze the performance of our approach and identify regimes where it potentially achieves polynomial to exponential speedups over existing quantum methods, at the trade-off of using more ancilla qubits. We further demonstrate the utility of normalized Betti numbers in concrete applications, highlighting the broader potential of hybrid quantum algorithms in topological data analysis.

arXiv:2508.01516Aug 2, 20250 citations