“E.g. work by Ewin Tang Quantum principal component analysis only achieves an exponential speedup because of its state preparation assumptions”
按年被提到
20182018 · 1 次2026
Quantum principal component analysis only achieves an exponential speedup because of its state preparation assumptions
量子主成分分析的指数加速仅源于其状态制备假设
Ewin Tang · 2018
给出经典去量子化算法,说明量子 PCA 的指数加速源于输入假设
被提及 · 3 人首次 2018-11-11 · 最近 2021-09-05
3不同的人
3活跃月份
3讨论串
157被引(OpenAlex)
作者引入一种经典输入模型,假设可以高效地对输入数据做 ℓ2 范数采样,它对应量子算法里高效制备经典数据量子态的假设。在此模型下,论文给出了 Lloyd、Mohseni 和 Rebentrost 的量子主成分分析与最近质心聚类算法的经典对应算法,只比量子版本慢多项式倍,说明那些指数加速只是状态制备假设带来的假象。
HN 为什么提它
评论者把 Ewin Tang 的工作作为例子,用来说明量子机器学习的指数加速往往取决于输入假设,并在论文正式发表后再次提到它。
方法难度 5 / 5约 120 分钟经得起时间
读之前最好知道
1量子算法基础
2线性代数与低秩近似
3主成分分析(PCA)
4随机采样与算法分析
5量子机器学习
学习路径
读这篇之前,按顺序读书架上的 4 篇 · 参考文献来自 OpenAlex,顺序和要点由 Claude Code 排出这条路径帮你建立量子线性代数加速的基础,以及量子机器学习算法的输入假设,再看经典去量子化如何拆穿加速来源。
- 1
HHL 是量子线性代数加速的原型,也是量子 PCA 类算法所依赖的框架。
读只读问题设定和结论:稀疏、条件数、状态制备与只估计解的期望值,这些假设后面都会被质疑。
- 2
给出量子 PCA 等量子机器学习算法,是目标论文要去量子化的对象。
读量子 PCA 与量子聚类的算法思路,以及它们对数据读入(qRAM)的假设。
- 3
- 4
Tang 的推荐系统去量子化算法,目标论文直接沿用其 l2 范数采样思路。
读l2-norm 采样输入模型,以及如何用它在经典计算中模拟低秩近似。
- 5Quantum principal component analysis only achieves an exponential speedup because of its state preparation assumptions
目标论文:把去量子化推广到 PCA,说明指数加速源于状态制备假设。
读采样查询输入模型、经典算法与量子算法的对比,以及哪些假设造成了加速。
HN 书评
推荐在前,同类按时间 · 每篇最多保留 20 条,统计用全部提及引用outlace · 2019-09
以 Ewin Tang 的工作为例,说明量子 PCA 的加速依赖状态制备假设
引用Strilanc · 2021-09
“the paper was finally published, like in a journal after peer-review, one month ago [1]”
补充说明这篇论文一个月前终于经同行评审发表
被提交为 story · 1 次
- Quantum-inspired classical algorithms for PCA and supervised clustering ↗apetresc · 2018-11-11 · 3 分