Complexity-Theoretic Limitations on Quantum Algorithms for Topological Data Analysis
Quantum algorithms for topological data analysis (TDA) seem to provide an exponential advantage over the best classical approach while remaining immune to dequantization procedures and the data-loading problem. In this paper, we give complexity-theoretic evidence that the central task of TDA—estimat...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
American Physical Society
2023-12-01
|
| Series: | PRX Quantum |
| Online Access: | http://doi.org/10.1103/PRXQuantum.4.040349 |