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:2404.15407 · Quantum

Quantum Walks on Simplicial Complexes and Harmonic Homology: Application to Topological Data Analysis with Superpolynomial Speedups

Ryu Hayakawa, Kuo-Chin Chen, Min-Hsiu Hsieh

Published Jun 15, 2026• 0 citations
arXivHTMLPDF

Abstract

This work investigates whether quantum walks on simplicial complexes exhibit quantum advantages. We introduce a novel quantum walk that encodes the combinatorial Laplacian, a key object reflecting the topology of the simplicial complex. We construct a unitary encoding projecting onto the kernel of the Laplacian, representing the harmonic cycles in the complex's homology. Our efficient construction of quantum walk unitaries for clique complexes paves the way for exploring higher-order interactions within topological structures. Our construction requires O ( n 3 log ⁡ ( 1 / ϵ ) / λ k ) gates, where n is the number of vertices, λ k is the smallest non-zero eigenvalue of the Laplacian, and ϵ is the projection error. Our results indicate apparent superpolynomial quantum speedup with quantum walks, without quantum oracles, provided the spectral gap of the Laplacian is inverse-polynomially bounded and efficient simplex sampling is available.Crucially, the walk operates on a state space encompassing both positively and negatively oriented simplices, effectively doubling its size compared to unoriented approaches. Through coherent interference of these paired simplices, we are able to successfully encode the combinatorial Laplacian, which would otherwise be impossible. This is our major technical contribution. We also extend the framework by constructing variant quantum walks that enable us to: (1) estimate normalized persistent Betti numbers throughout a deformation process, (2) verify a specific QMA 1 -hard problem related to clique complex homology, showcasing potential applications in computational complexity theory, and (3) solve the high-dimensional discrete Dirichlet problem (HDDP), generalizing the classical discrete Dirichlet problem on graphs to simplicial complexes, with an apparent superpolynomial speedup over the best known classical algorithm.

DOI
10.22331/q-2026-06-15-2138

Related papers

Quantum Advantage in Topological Data Analysis via Mayer Homology

Nhat A. Nghiem, Ryan Babbush, Adam Zalcman +4 more

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.

quant-pharXiv:2609.28058•Sep 24, 2026•0 citations

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•0 citations

Gapped Clique Homology on Weighted Graphs Is \({\text{QMA}_1}\)-Hard and Contained in QMA

Robbie King, Tamara Kohler

Abstract. We study the complexity of a classic problem in computational topology, the homology problem: given a description of some space [Formula: see text] and an integer [Formula: see text], decide if [Formula: see text] contains a [Formula: see text]-dimensional hole. The setting and statement of the homology problem are completely classical, yet we find that the complexity is characterized by quantum complexity classes. Our result can be seen as an aspect of a connection between homology and supersymmetric quantum mechanics established by Witten (1982). We consider clique complexes, motivated by the practical application of topological data analysis (TDA). The clique complex of a graph is the simplicial complex formed by declaring every [Formula: see text]-clique in the graph to be a [Formula: see text]-simplex. Our main result is that deciding whether the clique complex of a weighted graph has a hole or not, given a suitable promise on the gap, is [Formula: see text]-hard and contained in QMA. Our main innovation is a technique to lower bound the eigenvalues of the combinatorial Laplacian operator. For this, we invoke a tool from algebraic topology known as spectral sequences. In particular, we exploit a connection between spectral sequences and Hodge theory outlined by Forman (1994). Spectral sequences will play a role analogous to perturbation theory for combinatorial Laplacians. In addition, we develop the simplicial surgery technique used in prior work by Crichigno and Kohler (2022). Our result provides some suggestion that the quantum TDA algorithm due to Lloyd, Garnerone, and Zanardi (2016) cannot be dequantized, although proving this would require studying the complexity of a different problem related to the combinatorial Laplacian of clique complexes.

SIAM Journal on Computing•Jan 2, 2026•1 citation

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.01516•Aug 2, 2025•0 citations

An Incremental Span-Program-Based Algorithm and the Fine Print of Quantum Topological Data Analysis

M. J. Black, William Maxwell, Amir Nayyeri

We introduce a new quantum algorithm for computing the Betti numbers of a simplicial complex. In contrast to previous quantum algorithms that work by estimating the eigenvalues of the combinatorial Laplacian, our algorithm is an instance of the generic Incremental Algorithm for computing Betti numbers that incrementally adds simplices to the simplicial complex and tests whether or not they create a cycle. In contrast to existing quantum algorithms for computing Betti numbers that work best when the complex has close to the maximal number of simplices, our algorithm works best for sparse complexes. To test whether a simplex creates a cycle, we introduce a quantum span-program algorithm. We show that the query complexity of our span program is parameterized by quantities called the effective resistance and effective capacitance of the boundary of the simplex. Unfortunately, we also prove upper and lower bounds on the effective resistance and capacitance, showing both quantities can be exponentially large with respect to the size of the complex, implying that our algorithm would have to run for exponential time to exactly compute Betti numbers. However, as a corollary to these bounds, we show that the spectral gap of the combinatorial Laplacian can be exponentially small. As the runtime of all previous quantum algorithms for computing Betti numbers are parameterized by the inverse of the spectral gap, our bounds show that all quantum algorithms for computing Betti numbers must run for exponentially long to exactly compute Betti numbers. Finally, we prove some novel formulas for effective resistance and effective capacitance to give intuition for these quantities.

arXiv:2307.07073•Jul 13, 2023•0 citations

Quantum topological data analysis via the estimation of the density of states

Stefano Scali, Chukwudubem Umeano, Oleksandr Kyriienko

We develop a quantum topological data analysis (QTDA) protocol based on the estimation of the density of states (DOS) of the combinatorial Laplacian. Computing topological features of graphs and simplicial complexes is crucial for analyzing data sets and building explainable artificial intelligence solutions. This task becomes computationally hard for simplicial complexes with over 60 vertices and high-degree topological features due to a combinatorial scaling. We propose to approach the task by embedding underlying hypergraphs as effective quantum Hamiltonians and evaluating their density of states from the time evolution. Specifically, we compose propagators as quantum circuits using the Cartan decomposition of effective Hamiltonians and sample overlaps of time-evolved states using multifidelity protocols. Next we develop various postprocessing routines and implement a Fourier-like transform to recover the rank (and kernel) of Hamiltonians. This enables us to estimate the Betti numbers, revealing the topological features of simplicial complexes. We test our protocol on noiseless and noisy quantum simulators and run examples on IBM quantum processors. We observe the resilience of the proposed QTDA approach to real-hardware noise even in the absence of error mitigation, showing the promise for near-term device implementations and highlighting the utility of global DOS-based estimators. Published by the American Physical Society 2024

arXiv:2312.07115•Physical Review A•Oct 15, 2024•5 citations
This work investigates whether quantum walks on simplicial complexes exhibit quantum advantages. We introduce a novel quantum walk that encodes the combinatorial Laplacian, a key object reflecting the topology of the simplicial complex. We construct a unitary encoding projecting onto the kernel of the Laplacian, representing the harmonic cycles in the complex's homology. Our efficient construction of quantum walk unitaries for clique complexes paves the way for exploring higher-order interactions within topological structures. Our construction requires O ( n 3 log ⁡ ( 1 / ϵ ) / λ k ) gates, where n is the number of vertices, λ k is the smallest non-zero eigenvalue of the Laplacian, and ϵ is the projection error. Our results indicate apparent superpolynomial quantum speedup with quantum walks, without quantum oracles, provided the spectral gap of the Laplacian is inverse-polynomially bounded and efficient simplex sampling is available.Crucially, the walk operates on a state space encompassing both positively and negatively oriented simplices, effectively doubling its size compared to unoriented approaches. Through coherent interference of these paired simplices, we are able to successfully encode the combinatorial Laplacian, which would otherwise be impossible. This is our major technical contribution. We also extend the framework by constructing variant quantum walks that enable us to: (1) estimate normalized persistent Betti numbers throughout a deformation process, (2) verify a specific QMA 1 -hard problem related to clique complex homology, showcasing potential applications in computational complexity theory, and (3) solve the high-dimensional discrete Dirichlet problem (HDDP), generalizing the classical discrete Dirichlet problem on graphs to simplicial complexes, with an apparent superpolynomial speedup over the best known classical algorithm.
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.
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.
Gapped Clique Homology on Weighted Graphs Is QMA1{\text{QMA}_1}QMA1​-Hard and Contained in QMA
Abstract. We study the complexity of a classic problem in computational topology, the homology problem: given a description of some space [Formula: see text] and an integer [Formula: see text], decide if [Formula: see text] contains a [Formula: see text]-dimensional hole. The setting and statement of the homology problem are completely classical, yet we find that the complexity is characterized by quantum complexity classes. Our result can be seen as an aspect of a connection between homology and supersymmetric quantum mechanics established by Witten (1982). We consider clique complexes, motivated by the practical application of topological data analysis (TDA). The clique complex of a graph is the simplicial complex formed by declaring every [Formula: see text]-clique in the graph to be a [Formula: see text]-simplex. Our main result is that deciding whether the clique complex of a weighted graph has a hole or not, given a suitable promise on the gap, is [Formula: see text]-hard and contained in QMA. Our main innovation is a technique to lower bound the eigenvalues of the combinatorial Laplacian operator. For this, we invoke a tool from algebraic topology known as spectral sequences. In particular, we exploit a connection between spectral sequences and Hodge theory outlined by Forman (1994). Spectral sequences will play a role analogous to perturbation theory for combinatorial Laplacians. In addition, we develop the simplicial surgery technique used in prior work by Crichigno and Kohler (2022). Our result provides some suggestion that the quantum TDA algorithm due to Lloyd, Garnerone, and Zanardi (2016) cannot be dequantized, although proving this would require studying the complexity of a different problem related to the combinatorial Laplacian of clique complexes.
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.
We introduce a new quantum algorithm for computing the Betti numbers of a simplicial complex. In contrast to previous quantum algorithms that work by estimating the eigenvalues of the combinatorial Laplacian, our algorithm is an instance of the generic Incremental Algorithm for computing Betti numbers that incrementally adds simplices to the simplicial complex and tests whether or not they create a cycle. In contrast to existing quantum algorithms for computing Betti numbers that work best when the complex has close to the maximal number of simplices, our algorithm works best for sparse complexes. To test whether a simplex creates a cycle, we introduce a quantum span-program algorithm. We show that the query complexity of our span program is parameterized by quantities called the effective resistance and effective capacitance of the boundary of the simplex. Unfortunately, we also prove upper and lower bounds on the effective resistance and capacitance, showing both quantities can be exponentially large with respect to the size of the complex, implying that our algorithm would have to run for exponential time to exactly compute Betti numbers. However, as a corollary to these bounds, we show that the spectral gap of the combinatorial Laplacian can be exponentially small. As the runtime of all previous quantum algorithms for computing Betti numbers are parameterized by the inverse of the spectral gap, our bounds show that all quantum algorithms for computing Betti numbers must run for exponentially long to exactly compute Betti numbers. Finally, we prove some novel formulas for effective resistance and effective capacitance to give intuition for these quantities.
We develop a quantum topological data analysis (QTDA) protocol based on the estimation of the density of states (DOS) of the combinatorial Laplacian. Computing topological features of graphs and simplicial complexes is crucial for analyzing data sets and building explainable artificial intelligence solutions. This task becomes computationally hard for simplicial complexes with over 60 vertices and high-degree topological features due to a combinatorial scaling. We propose to approach the task by embedding underlying hypergraphs as effective quantum Hamiltonians and evaluating their density of states from the time evolution. Specifically, we compose propagators as quantum circuits using the Cartan decomposition of effective Hamiltonians and sample overlaps of time-evolved states using multifidelity protocols. Next we develop various postprocessing routines and implement a Fourier-like transform to recover the rank (and kernel) of Hamiltonians. This enables us to estimate the Betti numbers, revealing the topological features of simplicial complexes. We test our protocol on noiseless and noisy quantum simulators and run examples on IBM quantum processors. We observe the resilience of the proposed QTDA approach to real-hardware noise even in the absence of error mitigation, showing the promise for near-term device implementations and highlighting the utility of global DOS-based estimators. Published by the American Physical Society 2024