arXiv:1905.09084 · v6
Revisiting Shor's quantum algorithm for computing general discrete logarithms
重新审视Shor计算一般离散对数的量子算法
摘要
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 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 , the size of the search space in the post-processing, and the number of additional group operations evaluated quantumly. In the limit as , 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 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