Q#入门理论：量子逻辑门

量子门我们前面提到过一句。

 

量子计算机之所以能成为量子计算机，更在于其对于量子比特的特殊计算操作。那么这里就需要引入量子逻辑门（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} 个系数都会改变。

 

这个就是哈德玛门，我们第一个Q#程序用的就是这个操作。

 

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