图灵汇官网

量子计算：突破经典计算的界限

零和一，阴与阳，开关，有时开启有时关闭——这些都是计算机科学中的基础元素。然而，随着技术的不断进步，传统的计算方式已经面临新的挑战。英特尔、AMD、ARM和英伟达等公司在每年推出下一代顶级芯片的同时，也推动了计算能力的极限。尽管如此，更快的处理器并不总是意味着更强的计算能力。

在过去几十年中，计算速度确实实现了指数级的增长，但与此同时，我们能够处理的数据量也在迅速增加。如今，我们可以利用互联网上的艾字节（Exabyte）数据训练深度学习模型，比如OpenAI的GPT-3，以及在复杂的游戏中击败顶尖选手所需的计算能力。

这些技术的进步是否已经从根本上改变了我们使用计算机的方式，超出了最初的预期？换句话说，我们是否已经改变了经典的计算模式？

现代计算机遵循冯·诺依曼结构（von Neumann architecture）的原理运作（Ogban等人，2007年）。这种结构利用输入和输出处理器的逻辑函数，根据一组指令处理输入。虽然冯·诺依曼结构在实际问题解决中有其价值，但它们无法全面描述计算过程本身。为了更好地理解计算过程，我们需要借助图灵机（De Mol等人，2018年）。图灵机提供了一个抽象模型，描述了当今计算机的工作原理。图灵机通过一组规则操作磁带上符号，进而决定下一步的操作。

经典计算机能够完成的所有计算任务，理论上都可以在图灵机上实现。这与丘奇-图灵论题（Church-Turing thesis）密切相关，该理论指出，任何实际存在的计算都可以通过λ演算（λ-calculus）完成（Rabin，2012年）。然而，在实际应用中，图灵机对于大多数实际问题来说过于缓慢。

尽管如此，图灵机所展示的计算能力仍然是一个不可逾越的障碍。虽然我们的计算设备基于图灵机模型，开启了计算的可能性，但这种模型本身也存在固有的缺陷。不过，这并不意味着一切都结束了。正如马丁·路德·金所说：“我们必须接受有限的失望，但永远不要失去无限的希望。”（We must accept finite disappointment, but never lose infinite hope.）要突破这一障碍，需要从根本上重新思考计算机的设计，从最基本的单元——比特开始。

进入量子领域

过去120年里，物理学领域取得了许多伟大成就。爱因斯坦的广义相对论和量子力学彻底改变了我们对宇宙的理解。量子力学不仅在微观世界中提供了全新的视角，还为寻找强大的新计算模型提供了直接的联系。早在20世纪80年代初，理查德·费曼就设想量子计算机可以提供一种解决经典计算机难以处理的问题的方法（费曼，1986年）。量子计算机的核心在于一种全新的比特概念，即量子比特（qubit）。

与经典计算机不同，经典计算机的比特只能存在于0或1的状态，而量子比特可以存在于多种状态的叠加中。它可以是0或1，也可以是两者的叠加。这是量子比特的一个固有属性，赋予了它概率分布的特性。

本文的目的不是解释量子计算机背后的物理原理，但有必要回顾量子力学的两个基本概念：波粒二象性和纠缠。波粒二象性指的是粒子既可以表现出波动性，也可以表现出粒子性，而纠缠则是指粒子之间的一种特殊关联，即使相隔很远也能瞬间影响彼此的状态。

量子力学插曲

量子比特的状态可以用列向量表示。不同的状态由不同的列向量表示，这些向量彼此正交。量子比特的状态可以通过一组复数加权的基态的线性组合来描述。这相当于说，在任何时刻，量子比特处于这些基态的叠加，或者说处于概率波中。测量量子比特会引发概率波的坍缩，从而揭示出单一状态。

波粒二象性表明，一个粒子既表现出波动性，又表现出粒子性。在我们明确观测到粒子之前，我们无法确定它处于哪种状态。哥本哈根解释正是基于这一现象提出的。

量子纠缠是指当两个粒子处于纠缠状态时，测量其中一个粒子的状态会立即影响另一个粒子的状态。这种现象被爱因斯坦称为“幽灵般的超距作用”。

完全不同的计算模型

在经典计算机中，晶体管代表1比特的信息，而在量子计算机中，核自旋等微观粒子可以代表一个量子比特的信息。这些粒子通过电场和磁场进行操控和读取（Vogel，N.D.，Physics World期刊，2019年）。

量子比特是量子计算机的基本单元。由于量子比特可以存在于多种状态，而不是仅仅0和1，因此可以编码更多信息。事实上，量子比特可以用来编码经典比特，但反之则不行。量子比特的信息无法在经典晶体管中编码。

经典比特的n个晶体管可以用来编码n个分量系统，而量子比特则需要2^n个复数来编码。例如，8个量子比特需要256个复数来编码，而模拟64个量子比特则需要2^64个复数。

因此，相对于经典计算机，量子计算机提供了更大的状态空间。尽管量子比特是更大的计算对象，但它们可以用较少的量子比特来表示复杂的计算问题。显然，经典计算机很难模拟这样的表示。

量子门是量子计算机的基本操作单元，包括Hadamard门和CNOT门。Hadamard门可以创建叠加态，而CNOT门可以创建纠缠态。

量子计算机通过叠加和纠缠的原理，可以同时计算多个量子比特的结果。例如，对于一组输入，可以同时处理多个输入，而经典计算机则需要依次处理。这种并行性使得量子计算机在某些问题上具有指数级的加速能力。

量子计算的里程碑

2019年，谷歌的Sycamore量子计算机展示了量子霸权，用200秒完成了经典计算机需要1万年才能完成的任务。这一成就表明量子计算范式比经典计算范式更为强大。

然而，量子计算机的实现和发展并非一帆风顺。为了维持稳定性，量子计算机需要在接近绝对零度的低温环境下运行。此外，量子比特容易受到噪声的影响，导致退相干现象。这些问题使得量子计算机的应用主要局限于研究领域。

尽管如此，量子计算机在某些特定问题上的表现依然出色。例如，在量子机器学习和优化问题上，量子计算机展现了显著的优势。量子计算机在化学反应模拟、优化问题、金融分析等领域具有巨大的潜力。

量子机器学习

近年来的研究表明，量子计算的真正潜力在于构建由经典段和量子段共同组成的管道。对于科学研究，需要计算粒子的基态。传统方法需要计算哈密顿量的最小本征值，但对于大规模系统，这一任务会迅速耗尽计算资源。而使用混合量子机器学习算法，可以更高效地解决这一问题。例如，变分量子本征求解器（VQE）结合了经典算法和量子算法，可以有效估计哈密顿量的最小本征值。

量子计算机在机器学习领域的应用也取得了进展。例如，量子神经网络在某些情况下表现出了更快的训练速度和更好的性能。这些结果表明，量子计算机在处理特定问题时具有显著优势。

NP难题、搜索和蒙特卡洛模拟

量子计算机在优化问题和搜索问题上也有显著优势。例如，量子算法可以比经典算法更快地解决旅行商问题。Grovers算法可以在O(√N)的时间内搜索未排序的数据库，而经典算法需要O(N)的时间。

金融行业也在积极探索量子计算机的应用，特别是在优化问题和蒙特卡洛模拟方面。量子计算机在这些领域的应用有望带来显著的效率提升。

量子计算的未来

量子计算机揭示了一种新的计算和解决问题的方法。指数加速和多项式时间解都是量子比特的量子力学性质的自然结果。这使得计算模型更接近于量子图灵机的抽象模型。

量子图灵机是经典图灵机的量子化版本，其中磁头和磁带是叠加的。这种方式下，机器的形状是希尔伯特空间中的量子态。量子图灵机的磁带是一个有限长的单边磁带，代表叠加的比特。这种计算是一种幺正变换，由量子测量决定结果。

量子计算机在化学、金融和优化问题中的具体应用，为其实用化提供了可能。量子神经网络的训练速度和维度也为量子计算机在机器学习和深度学习领域的应用提供了新的可能性。

IBM、英特尔、Zapata、亚马逊和霍尼韦尔等科技公司正在加大对量子计算机的投入。高级编程语言、框架和库如Q#、Qiskit、TensorFlow Quantum和Cirq等也在不断发展。

尽管取得了显著进展，我们仍需批判性地思考量子计算机的现状。量子比特对退相关的敏感性和高昂的低温要求限制了其实际应用。因此，量子计算机能否在实践中占据主导地位，仍是未知数。更为紧迫的问题是，我们能否克服NISQ时代的限制。

总的来说，量子计算机的发展是一场激动人心的旅程，未来充满无限可能。