跳到正文
研踪PaperTrail
← 研踪 PaperTrail

arXiv:1905.09084 · v6

Revisiting Shor's quantum algorithm for computing general discrete logarithms

重新审视Shor计算一般离散对数的量子算法

首次提交 2019-05-22 19:47
版本更新 2026-11-17 02:18
雷达观测 2026-11-17 16:10
arXiv ↗PDF ↗

摘要

We heuristically show that Shor's quantum algorithm for the DLP achieves an expected success probability of approximately 60-82% in a single run when modified to enable efficient implementation with the semi-classical QFT. By slightly increasing the number of group operations that are evaluated quantumly and performing a single limited search in the post-processing, or by performing two limited searches in the post-processing, we rigorously prove that the modified algorithm can be made to achieve a success probability that, e.g., exceeds 1−10−41 - 10^{-4} in a single run. Specifically, we give an exact analysis of the probability distribution induced by the algorithm and use it to prove a lower bound on the success probability, as a function of the group order rr, the size of the search space in the post-processing, and the number of additional group operations evaluated quantumly. In the limit as r→∞r \rightarrow \infty, we show that the lower bound can be made to tend to one. In analogy with our earlier work, we explain how the limited searches in the post-processing can be performed efficiently using meet-in-the-middle or random-walk techniques, and we show how slightly better tradeoffs can be achieved, compared to our earlier work, when rr is known. We generalize our exact analysis to cover several quantum algorithms analyzed in our earlier works, including for parameter regimes not covered by our earlier analyses, yielding a unified lens on all of these algorithms. Furthermore, we generalize our exact analysis to the setting where information on multiple discrete logarithms is computed in each run of the algorithm so as to amortize costs. Last but not least, we give a novel exact simulator, which is based on our generalized exact analysis, and which hence works for all quantum algorithms covered by said analysis.

作者备注:Added an exact analysis of the probability distribution induced by the quantum algorithm, and used it to rigorously prove the lower bound on the success probability (which was previously heuristically derived). Also generalized the exact analysis, and added a novel exact simulator and other material; see the updated abstract and the paper for further details

AI 论文解读

基于摘要 · 非全文审阅

作者对采用半经典QFT的Shor离散对数算法做精确概率分析,证明通过少量额外量子群运算与后处理有限搜索可将单次成功率提升至接近1。

正在读取账号与研究记录…

版本差异

本站首次收录为 v6,暂无更早版本可对照。

观测到的版本

相邻记录可能跳过中间版本;首次发现 v2 及以上也会标为版本更新。

v6 · 2026-11-17 02:18 · 最新观测版本

Revisiting Shor's quantum algorithm for computing general discrete logarithms

We heuristically show that Shor's quantum algorithm for the DLP achieves an expected success probability of approximately 60-82% in a single run when modified to enable efficient implementation with the semi-classical QFT. By slightly increasing the number of group operations that are evaluated quantumly and performing a single limited search in the post-processing, or by performing two limited searches in the post-processing, we rigorously prove that the modified algorithm can be made to achieve a success probability that, e.g., exceeds 1−10−41 - 10^{-4} in a single run. Specifically, we give an exact analysis of the probability distribution induced by the algorithm and use it to prove a lower bound on the success probability, as a function of the group order rr, the size of the search space in the post-processing, and the number of additional group operations evaluated quantumly. In the limit as r→∞r \rightarrow \infty, we show that the lower bound can be made to tend to one. In analogy with our earlier work, we explain how the limited searches in the post-processing can be performed efficiently using meet-in-the-middle or random-walk techniques, and we show how slightly better tradeoffs can be achieved, compared to our earlier work, when rr is known. We generalize our exact analysis to cover several quantum algorithms analyzed in our earlier works, including for parameter regimes not covered by our earlier analyses, yielding a unified lens on all of these algorithms. Furthermore, we generalize our exact analysis to the setting where information on multiple discrete logarithms is computed in each run of the algorithm so as to amortize costs. Last but not least, we give a novel exact simulator, which is based on our generalized exact analysis, and which hence works for all quantum algorithms covered by said analysis.

查看此版本解读 →查看此版本原文 ↗