引用archgoon · 2017-12
“According to this paper:”
引用论文说明 Shor 算法只需 2n+3 个量子比特
把 Shor 分解算法所需量子比特数压到 2n+3 的线路
试图最小化用 Shor 算法分解 n 位整数所需的量子比特数,给出一个使用 2n+3 个量子比特、O(n^3 lg(n)) 个基本量子门、深度为 O(n^3) 的线路。该线路可在经典计算机上于多项式时间内构造,并且完全通用,不依赖待分解整数的任何性质。
评论者用它说明分解 n 位整数的 Shor 算法只需约 2n 个量子比特,并据此推算出 1024 位 RSA 约需 2051 个逻辑量子比特。
先读 Shor 算法原文,明白需要多少量子比特和哪些步骤,再看如何把它压缩到 2n+3 个比特。
目标线路实现的就是 Shor 的分解算法,模幂运算是资源消耗的主要来源。
读分解化归为求阶的思路、量子傅里叶变换与模幂运算两部分。
目标论文:2n+3 量子比特的 Shor 线路。
读如何用模加法、模乘法构造模幂运算,并复用比特以节省寄存器。
“According to this paper:”
“According to this paper, one can use 2n+3 qubits to factor an integer with n bits:”
“It has been shown that, to factor an integer with n bits, Shor's algorithm requires ~2n logical qubits: Circuit for Shor's algorithm using 2n+3 qubits”
“You can crack 1024-bit RSA with 2051 logical qubits according to:”