量子计算百年风云史 “量子比特”何时统治世界？

会使得量子比特从叠加态坍缩，反之，量子比特中存储的信息将始终处于动态演化过程之中，并且，通过量子门就能读取其中的信息。

　　假设我们取数字15来作为要分解的对象，设它作N，随机选一个数字设作X，并且1《X《N-1，将X当做寄存器A中内容的指数然后对N进行模除，余数则置于寄存器B中，即：

　　我们将这个运算结果列表如下：

　　我们会发现上述取值的运算结果呈现出（1，2，4，8，1，2，4，8……）的重复数列，我们将重复的频次命为 f，那么这个运算中，f 的取值就是4。

　　通过寄存器B中一系列复杂的运算执行，上述的f可以在量子计算机中获得，得出的f值会带入下列公式计算出一个可能的因数。得出的结果不会一定就是正确的，但是生成f值的量子干涉会反复尝试对x进行代换从而筛选出正确的结果并排除错误的答案。

　　这就是休尔的量子算法的整体思路，它向科学界和大众真正展示了量子计算的强大威力。

　　计算机科学中一个最基本的问题就是非结构化搜索，1996年，贝尔实验室的拉夫·格罗夫（Lov Kumar Grover）在论文里提出了针对这一问题的量子算法。假设有 N 个黑箱，每个箱中包含确定的1或0，每次打开一个箱子记为一次搜索请求，那么如果我们想要寻找到包含1的箱子，那么最多讲需要进行N次请求，而格罗夫的算法则将其减少到了次。

　　量子计算机固然拥有众多优势，但是这些基于量子力学上的特性也使得它本身较之经典计算机更加不稳定。和经典计算机的设计、硬件并不一样，量子计算机的设计制造首先需要保证量子比特处于稳定的相干叠加态的之中。

　　量子计算机强大的能力是建立在量子相干态带来的量子平行上的，一旦相干态中的量子比特在和外部环境发生量子纠缠之后会陷入退相干状态，那么，此时的量子比特和传统比特一样只能表示一种状态，也就是说，不稳定状态下的量子计算机和经典计算机相比丧失了最大的优势——1995年，休尔和安德鲁·斯迪恩（Andrew Steane）分别独立发表了量子纠错的规划，试图以此来解决量子计算机在退相干上的隐患。

　　无论是休尔还是格罗夫的量子算法实际上都是建立在量子线路基础上的，而量子线路和经典计算机一样也包含导线——这里的导线在广义上还包括粒子、光子乃至地域传送、时间演化等——和逻辑门，前者用来传输信息，后者则负责操作。

　　机器纪元

　　如果量子计算仅仅是停留在模仿经典计算机算法的地步的话，那么量子计算本身在信息储存和操作具备的巨大优势就会仅仅被用来在计算复杂性理论（computational complexity theory）上留下一些成果，而现实的物理世界及问题则会被忽视。于是，在基于量子线路基础上的量子算法之外，还出现了其他的量子算法，而它们不仅确实能在一些应用场景中超过经典计算机，还能重新定义难解（intractability）和易解（tractability）问题的抽象概念。

　　绝热算法（adiabatic algorithm）

　　2000年，MIT和东北大学（Northeastern University）的物理学家团队提出了绝热算法（Adiabatic Algorithms），2004年，该算法被证明在多项式意义上等价于线路模型。

　　基于测量的量子算法（Measurement-Based Algorithms）

　　和量子线路模型以幺正演化（unitary evolution）作为基本机制来操作信息不同，该算法只使用非幺正测量手段作为可计算步骤，这套算法演变称两个主要门类，一是隐形传态下的量子计算（teleportation quantum computing），二是单向量子计算机（one way quantum computer）。在2003年，该算法被证明在计算复杂性理论问题上同样等价于线路模型。

　　拓扑量子场论（Topological-Quantum-Field-Theory Algorithms）

　　在2000年，有人已经证明，该模型可以在标准量子计算机上被高效模拟，但是该算法的最大优势在于高容错性，而这就意味着大规模量子计算机的可能性。

　　1996年，赛斯·罗伊德（Seth Lloyd）在论文里为费曼曾经提出的量子计算机的设想给予了肯定的答案，包括量子计算机在内的任何量子系统都能通过程序化来模仿任意量子系统的行为，而且他还给出了对量子计算机的未来展望：

　　"各式原子、分子以及半导体制成的量子设备的出现预示着量子模拟即将成为现实。"

　　1997年，第一个基于量子计算机的核磁共振模型提出，下一年，核磁共振技术就运用到了2量子比特位的寄存器中，而到了2000年，寄存器中的量子比特数量在美国洛斯阿拉莫斯国家实验室（Los Alamos National Laboratory）手中增加到了7个。

和经典计算机不一