推荐mathgenius · 2014-10
“This one is good too:”
补充推荐这篇,用应用拓扑做大数据拓扑分析的量子算法
计算持续同调 Betti 数的指数加速量子算法
拓扑方法能从大数据集中提取连通分量、空洞等拓扑特征,持续同调则追踪这些特征在不同尺度下的存续。论文给出了计算持续同调 Betti 数的量子算法,以及求组合拉普拉斯算子特征向量与特征值的量子算法。作者声称这些算法相对经典拓扑数据分析算法有指数级加速。
HN 上的人引用它作为量子算法能对持续同调这类有用方法带来指数加速的例子,用于讨论量子计算对大数据分析的潜力。
候选里与目标论文直接相关的是量子机器学习算法的先驱工作,读它能了解这类量子算法的整体风格,再读目标论文对拓扑数据分析的量子算法。
同样是针对大数据分析的指数加速量子算法,是目标论文方法思路的参照。
读量子算法如何以量子态编码数据、用相位估计等手段处理线性代数任务;留意其加速所依赖的前提条件。
目标论文:给出计算持续同调 Betti 数和组合拉普拉斯算子特征值的量子算法。
读持续同调问题的量子化方式、Betti 数的计算流程,以及声称的加速与适用条件。
“This one is good too:”
“Arxiv version here: Quantum algorithms for topological and geometric analysis of big data”
“For example, this[1] one provides an exponential speedup (over known classical algorithms) for calculating persistent homology, a useful method for identifying scale-independent patterns.”