Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2609.28058

Quantum Advantage in Topological Data Analysis via Mayer Homology

Nhat A. Nghiem, Ryan Babbush, Adam Zalcman, Dominic W. Berry, Trung V. Phan, Guo-Wei Wei, Ryu Hayakawa

quant-phSubmitted Sep 23, 2026• Announced Sep 24, 2026• 0 citations
arXivHTMLPDF

Abstract

Prior work has explored quantum algorithms for topological data analysis (TDA), revealing the possibility of exponential quantum speedups in estimating the ratios of Betti numbers to the dimension of the combinatorial Laplacian. However, this quantity is only non-vanishing and efficient-to-quantumly-estimate when Betti numbers are exponentially large, a case for which concrete examples are rarely known. Furthermore, certain randomized classical algorithms are sometimes efficient in this regime. Thus, the prospect of achieving quantum advantage in conventional TDA appears fairly narrow. Here, we address these challenges to the quantum advantage in TDA by developing quantum algorithms for Mayer homology, which generalize simplicial homology to $N$-nilpotent boundary operators ($\partial^N =0$) and have recently been successfully applied to real-world TDA contexts. We introduce an efficient quantum algorithm for estimating Mayer Betti numbers and their persistent counterparts. We then prove that for high-order simplices, Mayer Betti numbers are often exponentially large in the dense regime, which ameliorates the normalization bottleneck of conventional quantum TDA. In the same regime, we argue that existing dequantization algorithms developed for conventional TDA, when applied to Mayer homology, generally lose theoretical guaranties, facing certain structural barriers that prevent their practical utilities. We also provide logical resource estimates revealing that a quantum computer with roughly a few hundred qubits and sixty million Toffoli gates could solve Mayer homology problems beyond the capabilities of known classical approaches. Finally, we discuss real-world applications of Mayer homology in genomics, supersymmetry, drug discovery, and neuroscience, revealing the potential of our quantum algorithm to deliver real-world impacts via Mayer homology.

AI Summary

Quantum algorithms for topological data analysis estimate normalized Betti numbers, which can be exponentially small. This paper asks whether Mayer homology, based on $\partial^N=0$ rather than $\partial^2=0$, offers larger signals while retaining efficient quantum estimation. It constructs boundary block-encodings and combines QSVT kernel filtering with amplitude estimation to estimate normalized Mayer Betti numbers; persistent ranks are handled through Schur-complement block-encodings. Runtime is polynomial for fixed $N$, inverse-polynomial spectral gaps, sufficiently dense simplex sets, and inverse-polynomial normalized ranks. A rank–nullity argument establishes $\beta_{d,p}\geq f_d-f_{d-p}-f_{d+N-p}$, where $f_k$ counts $k$-simplices. An explicit cone family on $n=3m$ vertices has $f_{m-1}=\binom{3m}{m}=\exp(\Theta(n))$ and $\beta_{m-1,p}/f_{m-1}=\Omega(1)$. For $p=N-1$ and $m\equiv1\pmod N$, its positive spectral gap is at least $(n+1)^{-(2N-2)}$, with polynomial-cost membership access. These results establish speedups over explicit simplex enumeration, not over all classical estimators. Extensions of randomized classical trace-estimation methods are examined, but their variance and mixing guarantees remain unresolved in the quantum-efficient regimes. The cone family is not established to be classically hard. Mayer ranks depend on vertex ordering and triangulation; useful high-degree application features remain unverified. Large endpoint ranks do not guarantee large persistent ranks, and barcode reconstruction requires additional error control. An optimistic resource estimate gives roughly hundreds of logical qubits and $63$ million Toffoli gates, conditional on favorable gaps, signals, and precision rather than an end-to-end benchmark.

Some signs of AI-generated textOverclaimsMissing comparisonStrong assumptionsPossible error

Central claim may not hold: The abstract suggests quantum advantage beyond known classical approaches, while the established exponential improvement is over explicit enumeration and the body leaves comparison with the best classical estimators unresolved. The abstract claims structural barriers prevent practical dequantization, but the analysis establishes neither classical inefficiency nor the necessary adverse variance or mixing behavior. The approximately 63-million-Toffoli crossover is unsupported because the resource section converts one measured classical runtime into a lower bound for different instances and uses unmatched simplex and edge counts to declare classical infeasibility. The resource example incorrectly states binomial(18,6)=31824 and 18+153=153; the correct values are 18564 and 171, while 31824 counts degree-6 simplices through binomial(18,7). The efficiency and hardware claims remain conditional on signal and spectral promises, and the hardware example does not satisfy the sector restrictions of the paper's explicit cone-family gap theorem.

Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.

Related papers

Analyzing Prospects for Quantum Advantage in Topological Data Analysis

Dominic William Berry, Yuan Su, Casper Gyurik +7 more

Lloyd [Nat. Commun. , 10138 (2016)] were first to demonstrate the promise of quantum algorithms for computing Betti numbers, a way to characterize topological features of data sets. Here, we propose, analyze, and optimize an improved quantum algorithm for topological data analysis (TDA) with reduced scaling, including a method for preparing Dicke states based on inequality testing, a more efficient amplitude estimation algorithm using Kaiser windows, and an optimal implementation of eigenvalue projectors based on Chebyshev polynomials. We compile our approach to a fault-tolerant gate set and estimate constant factors in the Toffoli complexity. Our analysis reveals that superquadratic quantum speedups are only possible for this problem when targeting a multiplicative error approximation and the Betti number grows asymptotically. Further, we propose a dequantization of the quantum TDA algorithm that shows that having exponentially large dimension and Betti number are necessary, but insufficient conditions, for superpolynomial advantage. We then introduce and analyze specific problem examples which have parameters in the regime where superpolynomial advantages may be achieved, and argue that quantum circuits with tens of billions of Toffoli gates can solve seemingly classically intractable instances. Published by the American Physical Society 2024

arXiv:2209.13581•PRX Quantum•Feb 6, 2024•78 citations

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.00433•Quantum•Dec 7, 2022•53 citations

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

Anonymous, 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.01516•Physical Review A•Sep 21, 2026•6 citations

Quantum Topological Data Analysis Beyond Betti Numbers: Complexity Hardness $\&$ An Algorithm for Torsion Witness

Nhat A. Nghiem, Dominic W. Berry, Trung V. Phan

Recent advances have revealed an interplay between quantum computing and topological data analysis (TDA). Most quantum TDA has focused on Betti numbers, which characterize the connectivity and ``holes'' of a dataset. Homology, however, contains additional information in the form of torsion: a nontrivial cycle can become trivial after being repeated finitely, revealing global constraints on how cycles combine and wrap around one another. Beyond applications in biomolecular studies, torsion appears in physical settings including homological quantum rotor codes, discrete charges, and gauge sectors. We study torsion from both classical and quantum perspectives. Given a graph $G$ and its clique complex $K = \mathrm{Cl}(G)$, we first prove that, for fixed $r$ and prime $p$, deciding whether $H_r(K,\mathbb{Z})$ contains $p$-torsion is NP-hard. As a corollary, when a homological rotor code is specified by $G$, deciding whether the code has a finite-dimensional logical sector of a given order is NP-hard. We discuss related problems, including the Bockstein homomorphism, Smith normal form, lattice saturation, and cohomology. Second, for a finite set of primes $P$, we develop a quantum algorithm that serves as a one-sided torsion witness. For fixed $r$, it outputs WITNESS or INCONCLUSIVE, i.e. WITNESS certifies that either $H_r(K,\mathbb{Z})$ or $H_{r-1}(K,\mathbb{Z})$ contains $p$-torsion for some $p\in P$ while INCONCLUSIVE makes no claim about its presence or absence. We identify a regime in which the algorithm achieves a near-quadratic quantum speedup over the corresponding classical algorithm under the same input model. Our NP-hardness result complements recent hardness results for estimating Betti numbers, adding a complexity-theoretic perspective to quantum TDA. Together, these results demonstrate that integral homology, beyond its Betti numbers, can be computationally challenging.

quant-pharXiv:2609.28112•Sep 24, 2026•1 citation

Practical Quantum Topological Data Analysis with Applications to High-Dimensional Feature Extraction and Time Series Analysis

Jason Iaconis, Sayonee Ray, Samwel Sekwao +2 more

Topological data analysis (TDA) provides a powerful framework for extracting information about the shape of complex, unstructured data, but the classical cost of computing high dimensional topological features limits its application. Quantum algorithms for TDA offer a route around this bottleneck, yet existing approaches typically focus on exact or high precision Betti number estimation, making the regime for practical quantum advantage appear narrow. Here, we instead frame quantum TDA as a feature-extraction method for downstream data analysis by extracting low-order spectral information from the combinatorial Laplacian as a proxy for high-dimensional topology. We support this perspective from both the application and algorithmic sides. First, we show that higher-order TDA features improve predictive performance in two time-series applications: functional MRI analysis for neurodegenerative disease classification and financial time-series analysis for identifying market instability. Second, we develop a moment-based quantum algorithm and show that low-order moments, including the relative trace, are strongly correlated with high-dimensional Betti information, even when the relative Betti number is small. Finally, we present circuit constructions, resource estimates, quantum-classical crossover projections, and experimental results from a Barium development system similar to the forthcoming IonQ Tempo line, extracting Laplacian-derived observables from graph instances and quantitatively comparing them with exact Betti information. Together, these results establish quantum TDA as a practical approach for extracting topological features from classically challenging data

quant-pharXiv:2607.27206•Jul 30, 2026•1 citation

New aspects of quantum topological data analysis: Betti number estimation, and testing and tracking of homology and cohomology classes

Nhat A. Nghiem

We introduce several new quantum algorithms for estimating homological invariants, specifically Betti numbers and persistent Betti numbers, of a simplicial complex given via a structured classical input. At the core of our algorithm lies the ability to efficiently construct the block-encoding of Laplacians (and persistent Laplacians) based on the classical description of the given complex. From such block-encodings, Betti numbers (and persistent Betti numbers) can be estimated. The complexity of our method is polylogarithmic in the number of simplices in both simplex-sparse and simplex-dense regimes, thus offering an advantage over existing works. Moreover, prior quantum algorithms based on spectral methods incur significant overhead due to their reliance on estimating the kernel of combinatorial Laplacians, particularly when the Betti number is small. We introduce a new approach for estimating Betti numbers based on homology tracking and homology property testing, which enables exponential quantum speedups over both classical and prior quantum approaches under sparsity and structure assumptions. We further initiate the study of homology triviality and equivalence testing as natural property testing problems in topological data analysis, and provide efficient quantum algorithms with time complexity nearly linear in the number of simplices when the rank of the boundary operator is large. In addition, we develop a cohomological approach based on block-encoded projections onto cocycle spaces, enabling rank-independent testing of homology equivalence. This yields the first quantum algorithms for constructing and manipulating r-cocycles in time polylogarithmic in the size of the complex. Together, these results establish a new direction in quantum topological data analysis and demonstrate that computing topological invariants can serve as a fertile ground for provable quantum advantage.

arXiv:2506.01432•Jun 2, 2025•12 citations
Prior work has explored quantum algorithms for topological data analysis (TDA), revealing the possibility of exponential quantum speedups in estimating the ratios of Betti numbers to the dimension of the combinatorial Laplacian. However, this quantity is only non-vanishing and efficient-to-quantumly-estimate when Betti numbers are exponentially large, a case for which concrete examples are rarely known. Furthermore, certain randomized classical algorithms are sometimes efficient in this regime. Thus, the prospect of achieving quantum advantage in conventional TDA appears fairly narrow. Here, we address these challenges to the quantum advantage in TDA by developing quantum algorithms for Mayer homology, which generalize simplicial homology to NNN-nilpotent boundary operators (∂N=0\partial^N =0∂N=0) and have recently been successfully applied to real-world TDA contexts. We introduce an efficient quantum algorithm for estimating Mayer Betti numbers and their persistent counterparts. We then prove that for high-order simplices, Mayer Betti numbers are often exponentially large in the dense regime, which ameliorates the normalization bottleneck of conventional quantum TDA. In the same regime, we argue that existing dequantization algorithms developed for conventional TDA, when applied to Mayer homology, generally lose theoretical guaranties, facing certain structural barriers that prevent their practical utilities. We also provide logical resource estimates revealing that a quantum computer with roughly a few hundred qubits and sixty million Toffoli gates could solve Mayer homology problems beyond the capabilities of known classical approaches. Finally, we discuss real-world applications of Mayer homology in genomics, supersymmetry, drug discovery, and neuroscience, revealing the potential of our quantum algorithm to deliver real-world impacts via Mayer homology.
Quantum algorithms for topological data analysis estimate normalized Betti numbers, which can be exponentially small. This paper asks whether Mayer homology, based on ∂N=0\partial^N=0∂N=0 rather than ∂2=0\partial^2=0∂2=0, offers larger signals while retaining efficient quantum estimation.
It constructs boundary block-encodings and combines QSVT kernel filtering with amplitude estimation to estimate normalized Mayer Betti numbers; persistent ranks are handled through Schur-complement block-encodings. Runtime is polynomial for fixed NNN, inverse-polynomial spectral gaps, sufficiently dense simplex sets, and inverse-polynomial normalized ranks. A rank–nullity argument establishes βd,p≥fd−fd−p−fd+N−p\beta_{d,p}\geq f_d-f_{d-p}-f_{d+N-p}βd,p​≥fd​−fd−p​−fd+N−p​, where fkf_kfk​ counts kkk-simplices. An explicit cone family on n=3mn=3mn=3m vertices has fm−1=(3mm)=exp⁡(Θ(n))f_{m-1}=\binom{3m}{m}=\exp(\Theta(n))fm−1​=(m3m​)=exp(Θ(n)) and βm−1,p/fm−1=Ω(1)\beta_{m-1,p}/f_{m-1}=\Omega(1)βm−1,p​/fm−1​=Ω(1). For p=N−1p=N-1p=N−1 and m≡1(modN)m\equiv1\pmod Nm≡1(modN), its positive spectral gap is at least (n+1)−(2N−2)(n+1)^{-(2N-2)}(n+1)−(2N−2), with polynomial-cost membership access.
These results establish speedups over explicit simplex enumeration, not over all classical estimators. Extensions of randomized classical trace-estimation methods are examined, but their variance and mixing guarantees remain unresolved in the quantum-efficient regimes. The cone family is not established to be classically hard. Mayer ranks depend on vertex ordering and triangulation; useful high-degree application features remain unverified. Large endpoint ranks do not guarantee large persistent ranks, and barcode reconstruction requires additional error control. An optimistic resource estimate gives roughly hundreds of logical qubits and 636363 million Toffoli gates, conditional on favorable gaps, signals, and precision rather than an end-to-end benchmark.
Lloyd [Nat. Commun. , 10138 (2016)] were first to demonstrate the promise of quantum algorithms for computing Betti numbers, a way to characterize topological features of data sets. Here, we propose, analyze, and optimize an improved quantum algorithm for topological data analysis (TDA) with reduced scaling, including a method for preparing Dicke states based on inequality testing, a more efficient amplitude estimation algorithm using Kaiser windows, and an optimal implementation of eigenvalue projectors based on Chebyshev polynomials. We compile our approach to a fault-tolerant gate set and estimate constant factors in the Toffoli complexity. Our analysis reveals that superquadratic quantum speedups are only possible for this problem when targeting a multiplicative error approximation and the Betti number grows asymptotically. Further, we propose a dequantization of the quantum TDA algorithm that shows that having exponentially large dimension and Betti number are necessary, but insufficient conditions, for superpolynomial advantage. We then introduce and analyze specific problem examples which have parameters in the regime where superpolynomial advantages may be achieved, and argue that quantum circuits with tens of billions of Toffoli gates can solve seemingly classically intractable instances. Published by the American Physical Society 2024
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.
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.
Quantum Topological Data Analysis Beyond Betti Numbers: Complexity Hardness &\&& An Algorithm for Torsion Witness
Recent advances have revealed an interplay between quantum computing and topological data analysis (TDA). Most quantum TDA has focused on Betti numbers, which characterize the connectivity and ``holes'' of a dataset. Homology, however, contains additional information in the form of torsion: a nontrivial cycle can become trivial after being repeated finitely, revealing global constraints on how cycles combine and wrap around one another. Beyond applications in biomolecular studies, torsion appears in physical settings including homological quantum rotor codes, discrete charges, and gauge sectors. We study torsion from both classical and quantum perspectives. Given a graph GGG and its clique complex K=Cl(G)K = \mathrm{Cl}(G)K=Cl(G), we first prove that, for fixed rrr and prime ppp, deciding whether Hr(K,Z)H_r(K,\mathbb{Z})Hr​(K,Z) contains ppp-torsion is NP-hard. As a corollary, when a homological rotor code is specified by GGG, deciding whether the code has a finite-dimensional logical sector of a given order is NP-hard. We discuss related problems, including the Bockstein homomorphism, Smith normal form, lattice saturation, and cohomology. Second, for a finite set of primes PPP, we develop a quantum algorithm that serves as a one-sided torsion witness. For fixed rrr, it outputs WITNESS or INCONCLUSIVE, i.e. WITNESS certifies that either Hr(K,Z)H_r(K,\mathbb{Z})Hr​(K,Z) or Hr−1(K,Z)H_{r-1}(K,\mathbb{Z})Hr−1​(K,Z) contains ppp-torsion for some p∈Pp\in Pp∈P while INCONCLUSIVE makes no claim about its presence or absence. We identify a regime in which the algorithm achieves a near-quadratic quantum speedup over the corresponding classical algorithm under the same input model. Our NP-hardness result complements recent hardness results for estimating Betti numbers, adding a complexity-theoretic perspective to quantum TDA. Together, these results demonstrate that integral homology, beyond its Betti numbers, can be computationally challenging.
Topological data analysis (TDA) provides a powerful framework for extracting information about the shape of complex, unstructured data, but the classical cost of computing high dimensional topological features limits its application. Quantum algorithms for TDA offer a route around this bottleneck, yet existing approaches typically focus on exact or high precision Betti number estimation, making the regime for practical quantum advantage appear narrow. Here, we instead frame quantum TDA as a feature-extraction method for downstream data analysis by extracting low-order spectral information from the combinatorial Laplacian as a proxy for high-dimensional topology. We support this perspective from both the application and algorithmic sides. First, we show that higher-order TDA features improve predictive performance in two time-series applications: functional MRI analysis for neurodegenerative disease classification and financial time-series analysis for identifying market instability. Second, we develop a moment-based quantum algorithm and show that low-order moments, including the relative trace, are strongly correlated with high-dimensional Betti information, even when the relative Betti number is small. Finally, we present circuit constructions, resource estimates, quantum-classical crossover projections, and experimental results from a Barium development system similar to the forthcoming IonQ Tempo line, extracting Laplacian-derived observables from graph instances and quantitatively comparing them with exact Betti information. Together, these results establish quantum TDA as a practical approach for extracting topological features from classically challenging data
We introduce several new quantum algorithms for estimating homological invariants, specifically Betti numbers and persistent Betti numbers, of a simplicial complex given via a structured classical input. At the core of our algorithm lies the ability to efficiently construct the block-encoding of Laplacians (and persistent Laplacians) based on the classical description of the given complex. From such block-encodings, Betti numbers (and persistent Betti numbers) can be estimated. The complexity of our method is polylogarithmic in the number of simplices in both simplex-sparse and simplex-dense regimes, thus offering an advantage over existing works. Moreover, prior quantum algorithms based on spectral methods incur significant overhead due to their reliance on estimating the kernel of combinatorial Laplacians, particularly when the Betti number is small. We introduce a new approach for estimating Betti numbers based on homology tracking and homology property testing, which enables exponential quantum speedups over both classical and prior quantum approaches under sparsity and structure assumptions. We further initiate the study of homology triviality and equivalence testing as natural property testing problems in topological data analysis, and provide efficient quantum algorithms with time complexity nearly linear in the number of simplices when the rank of the boundary operator is large. In addition, we develop a cohomological approach based on block-encoded projections onto cocycle spaces, enabling rank-independent testing of homology equivalence. This yields the first quantum algorithms for constructing and manipulating r-cocycles in time polylogarithmic in the size of the complex. Together, these results establish a new direction in quantum topological data analysis and demonstrate that computing topological invariants can serve as a fertile ground for provable quantum advantage.