一直觉得量子计算很神秘。从各种消息看来说什么量子计算机利用平行宇宙来计算，有超强的并行能力，穷举解决一切问题等等。真是越听越玄乎。维基百科和知乎上的一些解答还是看得让人茫然。

　　几天前上古神犇JYY推荐《Algorithms》一书的第十章作为量子计算的通俗入门读物。阅后豁然开朗，不敢独享，略做笔记。

　　普通计算机一个比特（bit）可以表示 0 或者 1。而量子具有不确定性，这使得一个量子比特（qubit）需要描述成 $ \alpha_0 \left|0\right\rangle + \alpha_1 \left|1\right\rangle $（量子比特的 0 状态记作 $\left|0\right\rangle$，1 状态记作 $\left|1\right\rangle$），其中 $ \left|\alpha_0\right|^2 + \left|\alpha_1\right|^2 = 1 $。也就是表示了这个量子比特有 $\left|\alpha_0\right|^2$ 的概率是 $\left|0\right\rangle$，有 $\left|\alpha_1\right|^2$ 的概率是 $\left|1\right\rangle$。这里面的 $\alpha_0$ 和 $\alpha_1$ 都是复数，所以要先取模再平方才是其概率（感谢 @shuyechengying 的指出）。
　　推广到两个量子比特为： $ \alpha_0 \left|00\right\rangle + \alpha_1 \left|01\right\rangle + \alpha_2 \left|10\right\rangle + \alpha_3 \left|11\right\rangle $。同样系数的模的平方和为 1。

　　这里就能看出量子计算的 NB 之处了，普通计算机 $n$ 比特可以描述 $2^n$ 个整数之一，而 $n$ 个量子比特可以同时描述 $2^n$ 个复数（一个 $2^n$ 维的复数向量）。

　　如果仅仅是有表达向量的能力，传统的向量机就可以搞定。量子计算机之所以能成为量子计算机，更在于其对于量子比特的特殊计算操作。一个很著名的计算单元是 Hadamard gate，输入 $ \alpha_0 \left|0\right\rangle + \alpha_1 \left|1\right\rangle $，输出 $ \frac{\alpha_0 + \alpha_1}{\sqrt{2}} \left|0\right\rangle + \frac{\alpha_0 – \alpha_1}{\sqrt{2}} \left|1\right\rangle $。不要小看这个操作，即使仅仅对 $n$ 个量子比特中的第一位进行了 Hadamard gate 运算，所有的 $2^n$ 个系数都会改变（书上有简单的证明）。这里有个量子纠缠的概念，没去深究了，大意就是量子的特性会让这些运算比向量机的逐元素运算要强大很多。

　　最后，薛定谔的猫要出场了。怎么把计算结果从混沌的量子态变成我们可理解的结果呢？这就需要“观测”。每次观测，量子就会塌缩到 $\left|0\right\rangle$ 或者 $\left|1\right\rangle$，按照 $\left|\alpha_0\right|^2$、$\left|\alpha_1\right|^2$ 的概率。反复测几次就知道结果了。但可惜的是，量子存在一个 No-cloning theorem，这就导致了我们不能简单地“反复观测”量子计算的结果了，而需要反复计算+观测。

　　借助量子计算机，FFT 的复杂度可以降低到 $O(\log ^2 (n))$，甚至连读一遍数据的 $O(n)$ 时间都不用，因为只要 $log(n)$ 个量子比特就可以描述 n 维向量了。利用高性能的 FFT，因子分解的复杂度可以达到 sub-exponential time [Shor’s algorithm]，RSA 加密就失效了。

　　但是传说中量子计算机目前还是不能有效地解 NPC 问题，可以参考维基百科 BQP 的介绍。

　　总结一下，从我目前理解来看，量子计算的优势主要在因子分解上（借助更快的 FFT）。对于传统的 NPC 问题，量子计算机目前还是束手无策的。当然这种强大的表达能力和计算能力还是非常有潜力的。

　　我也就看懂了这些，至少不觉得量子计算这么无敌了。最后，还是建议看原书，写的非常清楚。