按年被提到
20222022 · 3 次2026
物理与量子›量子计算·arXiv:2209.06930 · quant-ph

How Much Structure Is Needed for Huge Quantum Speedups?

巨大的量子加速到底需要多少结构?
Scott Aaronson · 2022

面向大众的综述:哪类问题能获得量子计算的指数级加速

开始阅读 ↗PDFalphaXiv 讨论
被提及 · 4 人首次 2022-10-03 · 最近 2025-10-22
4不同的人
3活跃月份
4讨论串
19被引(OpenAlex)

Aaronson 面向一般科学读者,综述三十年来关于哪些问题可以通过量子计算机获得指数级加速的研究,从 Simon 和 Shor 算法的经典结果一直讲到 2022 年 4 月 Yamakawa 与 Zhandry 的突破。文章对比了量子电路模型与预言机(query complexity)模型,讨论转向采样任务的利弊,并对量子计算能为实际机器学习和优化问题带来指数加速的流行说法提出怀疑。他用“怪异性守恒定律”概括:任何有指数加速的问题都必须有某种不寻常的性质。

HN 为什么提它

评论者把它当作量子计算权威人物写的综述,用来佐证量子优势与可验证性的理论依据,以及纠偏“纠缠被高估”之类的说法。

综述难度 4 / 5约 90 分钟经得起时间
读之前最好知道
1量子计算基础(量子比特与量子门)
2Shor 算法
3计算复杂性(complexity theory)
4查询复杂性 / 预言机模型(oracle model)

HN 书评

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

“From a Quantum Computing perspective entanglement ist kind of overrated.”

引 Aaronson 的观点,从量子计算角度看纠缠被高估了
Nobel Prize in Physics Awarded to Alain Aspect, John Clauser and Anton Zeilinger原评论 ↗
引用civilized · 2022-11

“Here's a survey paper from quantum computing expert Scott Aaronson, posted to arXiv just a couple months ago:”

贴出量子计算专家 Aaronson 的综述,讲哪些问题有指数级量子加速
Quantum winter is coming原评论 ↗
引用pred_ · 2025-10

“cf. e.g. Mahadev ([OTHER_PAPER]), Aaronson, in a strong, theoretical, sense.”

引它作为量子可验证性与量子优势的理论来源
Willow quantum chip demonstrates verifiable quantum advantage on hardware原评论 ↗
被提交为 story · 1 次