量子计算机优势的第一个证明

多年来，量子计算机并不仅仅是一个想法。今天，公司，政府和情报机构正在投资开发量子技术。TUM复杂量子系统理论教授RobertKönig与滑铁卢大学量子计算研究所的David Gosset和IBM的Sergey Bravyi合作，现在已经在这个充满希望的领域奠定了基石。

传统的计算机遵守经典物理学的规律。它们依赖于零和一的二进制数。这些数字被存储并用于数学运算。在传统的存储器单元中，每个比特 - 最小的信息单元 - 由确定该比特是设置为1还是0的电荷表示。

然而，在量子计算机中，一个位可以同时为0和1。这是因为量子物理定律允许电子一次占据多个状态。因此，量子比特或量子比特存在于多个重叠状态中。这种所谓的叠加允许量子计算机一次性对许多值执行操作，而单个传统计算机必须顺序执行这些操作。量子计算的前景在于能够更快地解决某些问题。

从猜想到证明

König和他的同事现在已经最终证明了量子计算机的优势。为此，他们开发了一种能够解决特定困难代数问题的量子电路。新电路结构简单 - 它只对每个量子位执行固定数量的操作。这种电路被称为具有恒定的深度。在他们的工作中，研究人员证明使用经典的恒定深度电路无法解决手头的问题。他们进一步回答了为什么量子算法胜过任何可比较的经典电路的问题：量子算法利用了量子物理学的非局域性。

在这项工作之前，量子计算机的优势既没有得到证实也没有经过实验证明 - 尽管有证据指向了这个方向。一个例子是Shor的量子算法，它有效地解决了素因子分解的问题。然而，如果没有量子计算机，这个问题就不能有效地解决，这只是一个复杂性理论的猜想。也可以想象，对于经典计算机来说，还没有找到正确的方法。

RobertKönig认为新结果主要是对复杂性理论的贡献。“我们的结果表明量子信息处理确实提供了好处 - 而不必依赖未经证实的复杂性理论猜想，”他说。除此之外，这项工作为量子计算机之路提供了新的里程碑。由于其结构简单，新的量子电路是量子算法的近期实验实现的候选者。