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

Space-Efficient and Noise-Robust Quantum Factoring

Seyoon Ragavan, Vinod Vaikuntanathan · 2023
开始阅读 ↗PDFalphaXiv 讨论
被提及 · 2 人首次 2023-10-23 · 最近 2024-04-28
2不同的人
2活跃月份
2讨论串
6被引(OpenAlex)
arXiv 摘要(候选层不写导读)

We provide two improvements to Regev's recent quantum factoring algorithm (Journal of the ACM 2025), addressing its space efficiency and its noise-tolerance. Our first contribution is to improve the quantum space efficiency of Regev's algorithm while keeping the circuit size the same. Our main result constructs a quantum factoring circuit using $O(n \log n)$ qubits and $O(n^{3/2} \log n)$ gates. We achieve the best of Shor and Regev (upto a logarithmic factor in the space complexity): on the one hand, Regev's circuit requires $O(n^{3/2})$ qubits and $O(n^{3/2} \log n)$ gates, while Shor's circuit requires $O(n^2 \log n)$ gates but only $O(n \log n)$ qubits. As with Regev, to factor an $n$-bit integer $N$, we run our circuit independently $O(\sqrt{n})$ times and apply Regev's classical postprocessing procedure. Our optimization is achieved by implementing efficient and reversible exponentiation with Fibonacci numbers in the exponent, rather than the usual powers of 2, adapting work by Kaliski (arXiv:1711.02491) from the classical reversible setting to the quantum setting. This technique also allows us to perform quantum modular exponentiation that is efficient in both space and size without requiring significant precomputation, a result that may be useful for other quantum algorithms. A key ingredient of our exponentiation implementation is an efficient circuit for a function resembling in-place quantum-quantum modular multiplication. Our second contribution is to show that Regev's classical postprocessing procedure can be modified to tolerate a constant fraction of the quantum circuit runs being corrupted by errors. In contrast, Regev's analysis of his classical postprocessing procedure requires all $\approx \sqrt{n}$ runs to be successful. In a nutshell, we achieve this using lattice reduction techniques to detect and filter out corrupt samples.

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

HN 书评

推荐在前,同类按时间 · 每篇最多保留 20 条,统计用全部提及
评论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原评论 ↗
评论sgt101 · 2024-04

“I've been going down this rabbit hole for a few weeks. Here is what I now think. Cai 2023 (https://pages.cs.wisc.edu/~jyc/Shor-Algorithm-with-Noise.pdf) showed that there is a definite noise floor for Shor's and gave a way to determine this. New algorithms are better than Shor's the in that they are smaller in space and time and more resilient to noise.…”

Google Quantum AI原评论 ↗