.png){kind=icon}
返回
Complexity-Theoretic Limitations on Quantum Algorithms for Topological Data Analysis
.png){kind=icon}
OA
AI
DOI：10.1103/PRXQuantum.4.040349.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
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-estimating Betti numbers-is intractable even for quantum computers. Specifically, we prove that the problem of computing Betti numbers exactly is #P-hard, while the problem of approximating Betti numbers up to multiplicative error is NP-hard. Moreover, both problems retain their hardness if restricted to the regime where quantum algorithms for TDA perform best. Because quantum computers are not expected to solve #P-hard or NP-hard problems in subexponential time, our results imply that quantum algorithms for TDA offer only a polynomial advantage in the worst case. We support our claim by showing that the seminal quantum algorithm for TDA developed by Lloyd, Garnerone, and Zanardi achieves a quadratic speedup over the best-known classical approach in asymptotically almost all cases. Finally, we argue that an expo-nential quantum advantage can be recovered if the input data is given as a specification of simplices rather than as a list of vertices and edges.
Keyword:
INDEPENDENCE COMPLEXES
ALEXANDER DUALITY
COMPLETENESS
期刊
P
IF:
11
论文数:
919
被引数:
9.0K
机构
引用论文
.png){kind=icon}
分享收藏
查看更多内容