按年被提到
20182018 · 1 次2026
物理与量子›量子计算·arXiv:1811.00414 · cs.DS

Quantum principal component analysis only achieves an exponential speedup because of its state preparation assumptions

量子主成分分析的指数加速仅源于其状态制备假设
Ewin Tang · 2018

给出经典去量子化算法,说明量子 PCA 的指数加速源于输入假设

开始阅读 ↗PDFalphaXiv 讨论
被提及 · 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. 1
    Quantum algorithm for solving linear systems of equations求解线性方程组的量子算法 · 2008

    HHL 是量子线性代数加速的原型,也是量子 PCA 类算法所依赖的框架。

    读只读问题设定和结论:稀疏、条件数、状态制备与只估计解的期望值,这些假设后面都会被质疑。

  2. 2

    给出量子 PCA 等量子机器学习算法,是目标论文要去量子化的对象。

    读量子 PCA 与量子聚类的算法思路,以及它们对数据读入(qRAM)的假设。

  3. 3

    量子机器学习综述,把各类算法及其输入输出假设放进同一张图里。

    读各算法的加速来源和输入输出假设,特别是数据如何以量子态读入。

  4. 4

    Tang 的推荐系统去量子化算法,目标论文直接沿用其 l2 范数采样思路。

    读l2-norm 采样输入模型,以及如何用它在经典计算中模拟低秩近似。

  5. 5
    Quantum principal component analysis only achieves an exponential speedup because of its state preparation assumptions量子主成分分析的指数加速仅源于其状态制备假设 · 2018 · 就是这篇

    目标论文:把去量子化推广到 PCA,说明指数加速源于状态制备假设。

    读采样查询输入模型、经典算法与量子算法的对比,以及哪些假设造成了加速。

HN 书评

推荐在前,同类按时间 · 每篇最多保留 20 条,统计用全部提及
引用outlace · 2019-09

“E.g. work by Ewin Tang Quantum principal component analysis only achieves an exponential speedup because of its state preparation assumptions”

以 Ewin Tang 的工作为例,说明量子 PCA 的加速依赖状态制备假设
Quantum Supremacy Using a Programmable Superconducting Processor原评论 ↗
引用Strilanc · 2021-09

“the paper was finally published, like in a journal after peer-review, one month ago [1]”

补充说明这篇论文一个月前终于经同行评审发表
Major Quantum Computing Advance Made Obsolete by Teenager (2018)原评论 ↗
被提交为 story · 1 次