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

An Efficient Quantum Factoring Algorithm

Oded Regev · 2023
开始阅读 ↗PDFalphaXiv 讨论
被提及 · 3 人首次 2023-09-24 · 最近 2023-10-23
3不同的人
2活跃月份
3讨论串
67被引(OpenAlex)
arXiv 摘要(候选层不写导读)

We show that $n$-bit integers can be factorized by independently running a quantum circuit with $\tilde{O}(n^{3/2})$ gates for $\sqrt{n}+4$ times, and then using polynomial-time classical post-processing. The correctness of the algorithm relies on a number-theoretic heuristic assumption reminiscent of those used in subexponential classical factorization algorithms. It is currently not clear if the algorithm can lead to improved physical implementations in practice.

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

HN 书评

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

“You are wrong, but close. They show that you can split up the factoring problem so you may solve sqrt(n) smaller problems, all requiring n^1.5 quantum operations, instead of a single run taking n^2 operations. This reduction can be implemented on a classical computer in polynomial time. They also require more qubits per run, n^1.5 instead of n but it is …”

Thirty Years Later, a Speed Boost for Quantum Factoring原评论 ↗
评论japanuspus · 2023-10

“Quantum factoring may not be quite as far distant as you might think Most importantly, Shor is not the algorithm of choice for first-gen hardware where the central challenge is likely to be circuit depth due to error correction overhead. The current front-runner is a probably proposal by Regev [0] with a space-optimization by Ragavan et al. [1], which fa…”

Java implementation of a quantum computing resistant cryptographic algorithm原评论 ↗
被提交为 story · 1 次