按年被提到
19972010 · 1 次2026
物理与量子›量子计算·arXiv:quant-ph/9701001 · quant-ph

Strengths and Weaknesses of Quantum Computing

Charles H. Bennett, Ethan Bernstein, Gilles Brassard, Umesh Vazirani · 1997
开始阅读 ↗PDFalphaXiv 讨论
被提及 · 2 人首次 2010-06-04 · 最近 2026-04-21
2不同的人
2活跃月份
2讨论串
1,465被引(OpenAlex)
arXiv 摘要(候选层不写导读)

Recently a great deal of attention has focused on quantum computation following a sequence of results suggesting that quantum computers are more powerful than classical probabilistic computers. Following Shor's result that factoring and the extraction of discrete logarithms are both solvable in quantum polynomial time, it is natural to ask whether all of NP can be efficiently solved in quantum polynomial time. In this paper, we address this question by proving that relative to an oracle chosen uniformly at random, with probability 1, the class NP cannot be solved on a quantum Turing machine in time $o(2^{n/2})$. We also show that relative to a permutation oracle chosen uniformly at random, with probability 1, the class $NP \cap coNP$ cannot be solved on a quantum Turing machine in time $o(2^{n/3})$. The former bound is tight since recent work of Grover shows how to accept the class NP relative to any oracle on a quantum computer in time $O(2^{n/2})$.

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

HN 书评

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

“Hard to say. My first instinct is probably not a whole lot. It's more or less conventional wisdom in the field that quantum computers are unlikely to be able to solve NP-complete problems in polynomial time. The argument for this conventional wisdom is heuristic (and certainly open to doubt, maybe most people are wrong), and it's in this paper: http://arx…”

Quantum computers no better than classical ones for NP-complete problems.原评论 ↗
评论amluto · 2026-04

“Yes and no. Grover's algorithm is provably optimal [0]. No quantum algorithm will every find an n-bit key by queries to any reasonable sort of oracle faster than Grover's algorithm, and Grover's algorithm is way too slow to be a serious problem. But symmetric cipher's are not black boxes. They're mostly build on some variant of a Feistel network, which …”

Quantum Computers Are Not a Threat to 128-Bit Symmetric Keys原评论 ↗