论文标题
关于量子订单查找的成功概率
On the success probability of quantum order finding
论文作者
论文摘要
我们证明，Shor的订单找到算法的概率成功地恢复了单次运行中的订单$ r $。边界意味着，通过在该算法的经典后处理部分执行两个有限的搜索，可以保证任何$ r $的高成功概率，而无需重新运行量子零件或与Shor相比，指数长度或增加指数长度。从$ r $倾向于无穷大的范围内，成功恢复$ r $的可能性往往是一个。对于中等$ r $，超过的高成功概率已经超过了，例如$ 1-10^{ - 4} $可以保证。作为推论，我们证明了类似的结果，因为可能会在单一运行的订单调查算法中完全考虑任何整数$ n $。
We prove a lower bound on the probability of Shor's order-finding algorithm successfully recovering the order $r$ in a single run. The bound implies that by performing two limited searches in the classical post-processing part of the algorithm, a high success probability can be guaranteed, for any $r$, without re-running the quantum part or increasing the exponent length compared to Shor. Asymptotically, in the limit as $r$ tends to infinity, the probability of successfully recovering $r$ in a single run tends to one. Already for moderate $r$, a high success probability exceeding e.g. $1 - 10^{-4}$ can be guaranteed. As corollaries, we prove analogous results for the probability of completely factoring any integer $N$ in a single run of the order-finding algorithm.
