93、量子算法（1 / 2）

随着计算机硬件沿着摩尔定律的轨迹不断发展，集成电路中的晶体管尺寸也越来越小。当晶体管缩小到量子效应不能忽略的程度时，传统的经典计算机也就迎来了它的瓶颈，难以进一步通过提高芯片集成度提升硬件的性能。而费曼曾经指出，既然某些传统问题会伴随着系统尺度的增大计算量呈指数增长，为什么不用量子系统本身对体系进行模拟呢？这样，基于量子规律的量子计算机也就名正言顺的走上历史舞台。

量子计算在某些特殊问题中，一般会拥有指数级别的加速能力，可以将一些传统方法中需要指数时间的问题降低为多项式时间，从而降低问题的复杂度，显现出量子计算的潜力。

构成量子计算机的主要构件被称为量子逻辑门，类似于经典逻辑门，它可以对输入的信息进行相应的运算，从而输出相应的结果。所不同的是，经典计算机的输入输出信号是经典的比特，也就是0和1，而量子计算机的输入与输出则是量子比特，它可以是0和1这两种状态的叠加态。因此量子计算机是对量子态进行运算的机器。

经典计算机的核心部分一般是用通用逻辑门，比如与非门构造而成的，其运行过程可以理解为一台通用图灵机。而量子计算机的通用逻辑门可以是控制非门加上任意的单比特门。每一个量子逻辑门对应的是对某个量子态的一种可逆操作，由于可以用酉矩阵来表述对量子态的演化过程，因此量子逻辑门可以通过酉矩阵表达。如果一个矩阵的共轭转置矩阵是它的逆矩阵，那么它就是一个酉矩阵。

量子计算一般是通过一种与图灵机等价的量子线路完成的，理论上，量子线路可以实现图灵机能够实现的所有运算。一个量子计算机可以同时对多少量子比特进行运算，就有多少条量子线路，而量子线路上的每一个节点都可以通过编程编辑相应的量子逻辑门，这些具体的编程规则构成了相应的量子算法。

通过一系列的量子门对初始量子态进行可逆运算，会得到我们通过编程希望得到的最终量子态，对最终的量子态进行测量，就可以获得量子态中包含的信息。值得一提的是，测量过程也是波函数的坍缩过程，我们只能得到量子态的振幅对应的信息，而无法获得相位信息。

量子计算最大的优势就是可以进行并行计算和指数加速，有了n量子比特的计算机，我们可以同时对2的n次方个数据进行计算，然后通过巧妙的设计使我们希望获得的结果以很大的概率出现在结果中，而且每增加一个量子比特，其相应的计算能力翻倍。