奇客 计算机科学家解决棘手的量子计算问题

量子计算机的功能越来越强大，可我们对其理解仍然很混乱。两位计算机科学家的工作让我们能深入了解这些未来机器可以计算什么。研究成果由芝加哥大学的 Bill Fefferman 和 Zachary Remscrim 于 2020 年 6 月发布，证明任何量子算法都可以重新编排，将在计算中执行的测量转移到过程结束，而不会改变最终结果或者大幅增加执行任务所需的内存量。此前计算机科学家认为这些测量的时机会影响内存需求，对量子算法的复杂性存在分歧。

Fefferman 表示：“这很烦人，我们不得不讨论两种复杂性类别——一种具有中间测量值，一种没有。”由于量子计算独特的工作方式，只有量子计算机才有这个问题。量子计算机和传统计算机之间基本的区别在于它们存储信息的方式。量子计算机并不用 0 和 1 的典型比特编码信息，而是将信息编码为更高维的比特组合，这些组合被称为量子比特。

这种方法可以实现更密集的信息存储，可加快计算速度。但它也带来了一个问题。在计算中的任何时候，你需要访问包含在一个量子比特中的信息并对其进行测量，那么该量子比特就会从同时可能的比特的组合坍缩成一个确定的比特，这可能会影响系统中的所有其他的量子比特。

这可能是一个问题，因为几乎所有算法都需要在计算过程中知道计算的值。例如一个算法中可能包含这样的语句：“如果变量x是一个数字，则将它乘以10；如果不是，别管它。”执行这些步骤似乎需要知道计算中那个时刻的x是什么——这对量子计算机来说是一个潜在的挑战，因为测量粒子的状态（以确定x是什么）就必然会改变它。

但是在 28 年前，计算机科学家证明有可能避免这种必输局面。他们确定，对于量子算法，你可以等到计算结束之后再进行中间测量，而不会改变最终结果。该结果的一个重要部分表明，你可以将中间测量推到计算的末尾，而不会显著增加总运行时间。量子算法的这些特征——测量可以延迟而不影响答案或运行时间——被称为延迟测量原则。

这一原则强化了量子算法，但要付出代价。延迟测量使用大量额外的内存空间，基本上每个延迟测量需要一个额外的量子比特。虽然在具有 4 万亿比特的经典计算机上，每次测量占据一个比特这点代价不算什么，但鉴于目前最大的量子计算机中的量子比特数量也很有限，这个代价就高昂得令人难以承受了。

Fefferman 和 Remscrim 的工作以一种令人惊讶的方式解决了这个问题。通过一个抽象的证明，他们表明，受制于一些注意事项，任何需要中间测量计算的东西都可以在没有它们的情况下被计算出来。他们的证明提供了一种节省内存的方法来推迟中间测量——避免了这种测量产生的内存问题。