按年被提到
20172018 · 2 次2026
物理与量子›量子计算·arXiv:1704.00690 · quant-ph

Quantum advantage with shallow circuits

Sergey Bravyi, David Gosset, Robert Koenig · 2017
开始阅读 ↗PDFalphaXiv 讨论
被提及 · 3 人首次 2017-12-31 · 最近 2018-10-19
3不同的人
2活跃月份
3讨论串
406被引(OpenAlex)
arXiv 摘要(候选层不写导读)

We prove that constant-depth quantum circuits are more powerful than their classical counterparts. To this end we introduce a non-oracular version of the Bernstein-Vazirani problem which we call the 2D Hidden Linear Function problem. An instance of the problem is specified by a quadratic form q that maps n-bit strings to integers modulo four. The goal is to identify a linear boolean function which describes the action of q on a certain subset of n-bit strings. We prove that any classical probabilistic circuit composed of bounded fan-in gates that solves the 2D Hidden Linear Function problem with high probability must have depth logarithmic in n. In contrast, we show that this problem can be solved with certainty by a constant-depth quantum circuit composed of one- and two-qubit gates acting locally on a two-dimensional grid.

候选层:至少 2 个不同的人、在 2 个不同月份提到过,还没到主书架的 3 人 3 个月。没有做立场标注,所以只写“被提及”。

HN 书评

推荐在前,同类按时间 · 每篇最多保留 20 条,统计用全部提及
评论da-bacon · 2017-12

“"Quantum advantage with shallow circuits" by Bravyi, Gosset, and Koenig https://arxiv.org/abs/1704.00690 What's beautiful about this paper is that it shows a provable separation in the power of quantum circuits over classical circuits. That is in contrast to many cases where quantum advantage is only suspected (the most notorious being Shor's algorithm: …”

Ask HN: What was the best CS paper you read in 2017?原评论 ↗
被提交为 story · 2 次