Monthly Archives: March 2016

量子计算

量子计算（一）

Leave a comment

进入公司之后第一次听到“量子计算”这个概念，一直觉得十分神秘。从维基百科或者知乎上看来说什么量子计算机利用量子来提升效率，有极强的并行能力，可以加速很多算法等。但是个人还是对这个方向了解甚少。直到前几天听完组里面大神的讲座，并用《Quantum Computing: From Linear Algebra to Physical Realizations》一书的作为量子计算的入门读物。读后豁然开朗，虽然也对这个方向了解也不够深入，不过还是略做笔记作为分享。作为一个量子计算的初学者，还是有很多理解不够到位之处，希望大家指正。

普通计算机一个比特（bit）可以表示 0 或者 1。而量子具有不确定性，这使得一个量子比特（qubit）需要描述成 α0|0⟩+α1|1⟩（量子比特的 0 状态记作 |0⟩，1 状态记作 |1⟩），其中 |α0|^2+|α1|^2=1。也就是表示了这个量子比特有 |α0|^2 的概率是 |0⟩，有 |α1|^2 的概率是 |1⟩。这里面的 α0 和 α1 都是复数，所以要先取模再平方才是其概率。可以记作 p(0)=|α0|^2, p(1)=|α1|^2, p(0)+p(1)=1。举例说明：

如果某个量子的状态是 \phi\rangle=\sqrt{1/3}|0 \rangle + \sqrt{2/3}|1 \rangle, 那么 p(0)=1/3，p(1)=2/3。如果测量的结果是0，那么这个 qubit 的状态就是0，换言之，|\phi \rangle=|0\rangle；如果测量的结果是1，那么这个 qubit 的状态也就变成了1，换言之， |\phi \rangle=|1\rangle。

总之，量子状态有很多的可能性，因为复数 α0 和 α1 只有一个限制条件，那就是它们模的平方和是1。测量一个 qubit 只会给出 0 或者 1 的结果，这一点和传统的 bit 是一样的。同时，如果再次测量的话，只会给出和前一次一样的结果，结果并不会再次改变。除此之外，我们还可以把单个量子比特推广到两个量子比特为： α0|00⟩+α1|01⟩+α2|10⟩+α3|11⟩。同样的，系数的模的平方和为 1。换言之，α0，α1，α2，α3 这几个复数的模的平方和是1。

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

如果仅仅是有表达向量的能力，传统的计算机就可以搞定。量子计算机之所以能成为量子计算机，更在于其对于量子比特的特殊计算操作。那么这里就需要引入量子逻辑门（Quantum Logic Gates）的概念。每一个 Quantum Logic Gate 都对应了一个数学上面的一个酉矩阵（Unitary Matrix）。如果 n*n 的矩阵 U 满足 UU^{T}=U^{T}U=I，这里的 I 指的是 n*n 的单位矩阵，U^{T} 指的是矩阵 U 的转置，那么 U 就被成为酉矩阵。

（1）量子非门（Quantum NOT Gate）是把 α0|0⟩+α1|1⟩ 映射成 α1|0⟩+α0|1⟩，也就是把 α0 和 α1 交换顺序。

（2）Quantum Controlled NOT Gate 是把 α0|00⟩+α1|01⟩+α2|10⟩+α3|11⟩ 映射成 α0|00⟩+α1|01⟩+α3|10⟩+α2|11⟩，也就是把 α2 和 α3 交换顺序。

（3）一个很著名的计算单元是 Hadamard Gate，输入 α0|0⟩+α1|1⟩，输出 2^{-1/2}(α0+α1)|0⟩+2^{-1/2}(α0-α1)|1⟩ 。Hadamard Gate 就是把经典的状态 |0⟩ 和 |1⟩ 转换成 |0⟩ 和 |1⟩ 的“halfway” 状态。不要小看这个操作，即使仅仅对 n 个量子比特中的第一位进行了 Hadamard gate 运算，所有的 2^{n} 个系数都会改变，证明如下：

假设我们有一个在 n 个 qubits 的量子状态 |\alpha\rangle=\sum_{x\in\{0,1\}^{n}}\alpha_{x}|x\rangle，如果我们对第一个 qubit 使用 Hadamard Gate，那么状态就会变成|\beta\rangle=\sum_{x\in\{0,1\}^{n}}\beta_{x}|x\rangle，其中\beta_{0y}=(\alpha_{0y}+\alpha_{1y})/\sqrt{2}, \beta_{1y}=(\alpha_{0y}-\alpha_{1y})/\sqrt{2}。也就是说每一对 \alpha_{0y} 和 \alpha_{1y} 都会被映射成 (\alpha_{0y}+\alpha_{1y})/\sqrt{2} 和 (\alpha_{0y}-\alpha_{1y})/\sqrt{2}。因此就证明了，仅仅对 n 个量子比特中的第一位进行了 Hadamard gate 运算，所有的 2^n 个系数都会改变。这个就是在 quantum fourier transform 算法中达到指数级别加速的基础。

最后，薛定谔的猫要出场了。怎么把计算结果从混沌的量子态变成我们可理解的结果呢？这就需要“观测”。每次观测，量子就会按照 |α0|^2、|α1|^2 的概率塌缩到 |0⟩ 或者 |1⟩。量子存在一个 No-Cloning Theorem，这就导致了我们不能简单地“反复观测”量子计算的结果了，而需要反复计算+观测。通过 No-Cloning Theorem，我们可以得出一个观点：We can not copy a genderal quantum state. 为了能够加深读者对定理的理解，No-Cloning Theorem 的证明采取了数学上经典的反证法，先假设存在一个系统能够完全的拷贝任意量子比特，从而推导出矛盾。细节如下：

Theorem. (No-Cloning Theorem, Wootters and Zurek, Dieks) An unknown quantum system cannot be cloned by unitary transformations.

Proof. By contradiction, there exists a unitary transformation U that makes a clone of a quantum system. That means for any state |\varphi\rangle,

U: |\varphi 0\rangle \rightarrow |\varphi\varphi\rangle.

Consider two linear independent states |\varphi\rangle and |\phi\rangle. Then we have U|\varphi 0\rangle=|\varphi\varphi\rangle, U|\phi 0\rangle=|\phi\phi\rangle from the assumption of U. Let |\psi\rangle=\frac{1}{\sqrt{2}}(|\varphi\rangle +|\phi\rangle), we get

U|\psi 0\rangle=\frac{1}{\sqrt{2}}(U|\varphi 0\rangle+U|\phi 0\rangle).

However,

U|\psi 0\rangle=|\psi\psi\rangle=\frac{1}{2}(|\varphi\varphi\rangle+|\varphi\phi\rangle+|\phi\varphi\rangle+|\phi\phi\rangle)

which contradicts the previous result. Therefore, there does not exist a unitary cloning transformation.

借助量子计算机，FFT 的复杂度可以降低到 O((log(n))^2)，甚至连读一遍数据的 O(n) 时间都不用，因为只要 log(n) 个量子比特就可以描述 n 维向量了。利用高性能的 FFT，因子分解的复杂度可以达到 sub-exponential time [Shor’s Algorithm]，RSA 加密就失效了。而且目前量子计算机已经第一次以可扩展的方式，使用 Shor’s Algorithm 完成了对15的素数分解。有人表示：用 Shor 算法实现素数分解这一件事情，可以与经典计算机中的 “Hello World!” 相提并论。

总结一下，从我目前理解来看，借助更快的 FFT 算法，量子计算的优势主要在素数分解上，可以把原来指数复杂度的算法减少至多项式复杂度的算法。对于传统的一些问题，量子计算机和传统计算机相比目前还是不具备绝对的优势。当然量子计算机这种强大的表达能力和计算能力还是非常有潜力和令人期待的。