Quantum algorithms achieve polylogarithmic complexity for Betti number estimation and homology testing via block-encoded Laplacians and cohomological projections, claiming exponential speedups under sparsity assumptions.
A streamlined quantum algorithm for topological data analysis with exponentially fewer qubits
3 Pith papers cite this work. Polarity classification is still indexing.
3
Pith papers citing it
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.
fields
quant-ph 3verdicts
UNVERDICTED 3representative citing papers
Quantum algorithms achieve polynomial advantage for synchronization estimation and super-polynomial advantage for no-phase-locking certification in higher-order simplicial Kuramoto models under stated assumptions.
Hybrid quantum-classical method for Betti number estimation that combines classical simplex enumeration with quantum processing and claims polynomial-to-exponential speedups over existing quantum algorithms at the cost of extra ancilla qubits.
citing papers explorer
-
New aspects of quantum topological data analysis: Betti number estimation, and testing and tracking of homology and cohomology classes
Quantum algorithms achieve polylogarithmic complexity for Betti number estimation and homology testing via block-encoded Laplacians and cohomological projections, claiming exponential speedups under sparsity assumptions.
-
Efficient Quantum Algorithms for Higher-Order Coupled Oscillators
Quantum algorithms achieve polynomial advantage for synchronization estimation and super-polynomial advantage for no-phase-locking certification in higher-order simplicial Kuramoto models under stated assumptions.
-
Hybrid quantum-classical framework for Betti number estimation with applications to topological data analysis
Hybrid quantum-classical method for Betti number estimation that combines classical simplex enumeration with quantum processing and claims polynomial-to-exponential speedups over existing quantum algorithms at the cost of extra ancilla qubits.