Quantum computing and persistence in topological data analysis
Topological data analysis (TDA) aims to extract noise-robust features from a data set by examining the number and persistence of holes in its topology. We show that a computational problem closely related to a core task in TDA -- determining whether a given hole persists across different length scales -- is $\mathsf{BQP}_1$-hard and contained in $\mathsf{BQP}$. 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.
Code (0)
등록된 구현이 없습니다.
Tasks
Topological Data AnalysisMethods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
From Betti Numbers to Persistence Diagrams: A Hybrid Quantum Algorithm for Topological Data Analysis
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 t…
Drug DiscoveryQuantum Distance Approximation for Persistence Diagrams
Topological Data Analysis methods can be useful for classification and clustering tasks in many different fields as they can provide two dimensional persistence diagrams that summarize important information about the sha…
Topological Data AnalysisPersistent Patterns in Eye Movements: A Topological Approach to Emotion Recognition
We present a topological pipeline for automated multiclass emotion recognition from eye-tracking data. Delay embeddings of gaze trajectories are analyzed using persistent homology. From the resulting persistence diagrams…
Emotion RecognitionComplexity of Normalized Persistence Problems for Topological Data Analysis and Local Hamiltonians
Topological data analysis (TDA) is a machine learning technique that uses topology to extract patterns from data and has shown the potential to exhibit quantum advantage. A key concept in TDA is persistent homology, whic…
Demonstration of Topological Data Analysis on a Quantum Processor
Topological data analysis offers a robust way to extract useful information from noisy, unstructured data by identifying its underlying structure. Recently, an efficient quantum algorithm was proposed [Lloyd, Garnerone, …
Topological Data Analysis