Quantum computing and persistence in topological data analysis
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866929563549827072 |
|---|---|
| author | Gyurik, Casper Schmidhuber, Alexander King, Robbie Dunjko, Vedran Hayakawa, Ryu |
| author_facet | Gyurik, Casper Schmidhuber, Alexander King, Robbie Dunjko, Vedran Hayakawa, Ryu |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_21258 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Quantum computing and persistence in topological data analysis Gyurik, Casper Schmidhuber, Alexander King, Robbie Dunjko, Vedran Hayakawa, Ryu Quantum Physics Computational Complexity Machine Learning 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. |
| title | Quantum computing and persistence in topological data analysis |
| topic | Quantum Physics Computational Complexity Machine Learning |
| url | https://arxiv.org/abs/2410.21258 |