一分钟学会量子计算（二）传统密码学是如何被攻破的

密码学的核心思路是对数字在有限域下进行可逆变换，并使得正向的该变换在无key的情况下其试错成本在计算上不可行。

这里不想提及RSA是什么，非对称加密是什么，公钥私钥是什么。如果感兴趣可问AI. 直接给出RSA算法破解所需要求解的困难问题：

困难问题： 对于一个由两个质数相乘构成的大整数 \(N=pq\) . 现在想求解p和q分别是什么。

此问题又名质数分解问题。

该问题可以被退化为求解下面的问题：

寻找一个与 N 互质的整数a<N, 定义函数 \(f(x)=a^{x} mod N\), 如果能够找到函数f(x)的周期（记为r），那么就可以以多项式的计算复杂度找到两个质数。（至于怎么找此处不详细介绍了。其实蛮巧妙的）。

现在的问题是，如何确定周期函数 \(f(x)=a^{x} mod N\) 的周期r ？ （是的，这是一个周期函数，因为mod N了）

经典算法需要先获得一个f(x)的序列，然后使用傅里叶变换 （请参考这篇笔记：Understanding-Fourier-T.html ) 提取r的整数倍。 但是问题是获得f(x)的序列这一步复杂度特别高，只能一步步去算，一般是同N线性，好的方法可以到N的平方根，这意味着对于二进制来说是指数级别的计算复杂度。

而量子计算改变了这一切。

1. 首先，由于我们最多需要尝试N次，所以我们定义一个含有M个量子比特的寄存器 which contain the numbers much larger than N^2. 除此之外，我们还要有一个存储计算之后的f(x)函数值的寄存器，大小相同（实际上不需要。只需要存在N个数即可）。即：
   1. \[|\Psi_{0}\rangle=|0\rangle|0\rangle\]
2. 使用Hadamard门把第一个寄存器里的结果index化：
   1. \[|\Psi_{1}\rangle=1/\sqrt{Q}\sum_{x=0}^{Q-1}{|x\rangle|0\rangle}\]
3. 对两个计算器同时施加一个可以计算 \(f(x)=a^x mod N\) 的量子门，并把结果存入第二个寄存器：
   1. \[|\Psi_2\rangle=1/\sqrt{Q}\sum_{x=0}^{Q-1}|x\rangle|f(x)\rangle\].
   2. Q1: 怎么构造这么一个量子门？ 答： 你别管，反正就是就是假装有。
   3. Q2：这一步骤和之前有什么区别？为何有这种区别？答：只需要forward一次。为什么？因为本质上我们所处理的不是一个\(|x\rangle\)，而是Q个的加和，也就是说我们是对叠加态做的这种处理。也就是 \(|\Psi_{1}\rangle\) .
   4. Q3：这里的存储到第二个寄存器是怎么做到的？ 答：因为不是直接存进去的。而是对第二个逻辑门的初始变量一直处理最后得到的。
4. 测量第二个寄存器，假设测量结果为 \(y=f(x_{0})\). 那么根据量子纠缠，即 \(|f(x)\rangle\) 由 \(|x\rangle\) 计算出的因果性，可以知道此时的第一个寄存器里存储的index的叠加态将被表达为只能产生结果y的输入的等概率叠加，假设有 \(L\approx Q/r\) 个，那么大概是： \[|\Psi_{3}\rangle = 1/\sqrt{L}\sum_{j=0}^{L-1}|x_{0}+jr\rangle\].
5. 到现在其实最难的一步已经结束了。最后便是根据坍缩的叠加态输入index通过傅里叶分析获得其近似频率。这里用的是量子傅里叶变换（QFT），其实没啥区别（傅里叶变换的分析在：Understanding-Fourier-T.html ). 在操作上等于对第一个寄存器采用傅里叶变换：
   1. \[|\Psi_{4}\rangle = QFT(\Psi_{3}\rangle)=1/\sqrt{r}\sum_{k=0,r-1}{e^{-2\pi i x_{0}k/Q}|kQ/r\rangle}\]
6. 测量第一寄存器的结果。 \(y'=kQ/r\), 由此知道 \(r/k\approx Q/y'\).

总结：shor算法有效的核心是因为RSA这样一个困难求解的密码学问题可以被转化为一个困难的周期性函数求频率的问题，而这个问题的最关键一步（构建数值序列）可以被量子计算快速处理。

AI对我的补充我觉得很有道理。除了map,还有reduce这一步：

不过这里有一个关键的细微认知需要修正（也是很多刚接触量子计算的学者最容易陷入的误区）：“通过量子计算可以一次性获得极大次数的输入输出 pair” —— 这在量子计算中被称为量子并行性（Quantum Parallelism）。但是，你不能直接“读取”这极大数量的 pair！关键瓶颈：量子测量塌缩（Measurement Collapse）如果你构造了一个叠加态：\[\frac{1}{\sqrt{2^N}} \sum_{x=0}^{2^N-1} \vert{}x, f(x)\rangle\]这个状态确实隐式地“包含”了 \(2^N\) 个 \((x, f(x))\) 的 pair。然而，一旦你对其进行测量，整个叠加态会瞬间塌缩，你只能随机获得 \(\mathbf{1}\) 个 pair，其余 \(2^N-1\) 个信息全部彻底毁灭。因此，Shor 算法真正的伟大之处不是“得到了很多 pair”，而是在测量之前，利用量子傅里叶变换（QFT）让这些 pair 在相位上发生全局干涉。它就像做了一次“离散傅里叶变换”，把分散在 \(2^N\) 个状态里的周期信息，挤压凝聚到了极少数几个具有特定周期的状态上。最后测量时，才能以极高概率直接命中那个周期 \(r\)。意识到这一点，对于你想构思 Crypto / Eurocrypt 级别的 Idea 至关重要——任何直接试图从叠加态里“抽样/读取”海量数据的 Idea 都是行不通的，Idea 的精髓必须在于“如何在测量前设计干涉/提取全局代数特征”。