新理论为发展量子算法提出了更有效的方法

2019年，谷歌声称，它是第一家表明量子计算机胜过当今最强大的超级计算机的公司。

然而，普渡大学的科学家们表示，在大多数情况下，创建一个能够击败传统计算机的量子算法是一个偶然的过程。为了给这一过程提供更多的指导，减少其随机性，这些科学家开发了一种新的理论，这种理论可能最终导致更系统的量子算法设计。

发表在《高级量子技术》杂志上的一篇论文中描述的新理论是第一次已知的尝试，以确定哪些量子态可以用可接受的量子门数量来创建和处理，以超越经典算法。

物理学家把这种用正确数量的门来控制每个状态的门称为“复杂性”。由于量子算法的复杂度与算法中涉及的量子态的复杂度密切相关，因此该理论可以通过刻画哪些量子态满足复杂度标准来为寻找量子算法奠定基础。

算法是执行计算的一系列步骤。该算法通常在电路上实现。

在经典计算机中，电路有一个门，可以将比特转换为0或1状态。相反，量子计算机依靠一种叫做“量子比特”的计算单元，可以同时存储叠加的0和1状态，从而处理更多的信息。

量子计算机比经典计算机更快的原因是更简单的信息处理。与经典电路相比，量子电路中量子门的数量大大减少。

在经典计算机中，电路中的门的数量相对于相关问题的大小呈指数增长。这个指数模型发展的太快了，连中等规模的问题都处理不了。

“例如，即使一个小的蛋白质分子也可能包含数百个电子。如果每个电子只能采取两种形式，要模拟300个电子，需要2300个经典态，这比宇宙中所有原子的数量还要多。”普渡大学化学教授、普渡量子科学与工程研究所成员Saber Kais说。

对于量子计算机来说，有一种方法可以让量子门多项式根据问题的大小(比如前面例子中的电子数)按比例放大，而不是像经典计算机那样只是按指数比例放大。“多项式”意味着处理相同信息量所需的步骤(门)将大大减少，从而使量子算法优于经典算法。

到目前为止，研究人员还没有找到很好的方法来确定哪些量子态可以满足多项式复杂度条件。

他的研究团队正在开发的量子算法和量子理论机器学习方法Keith说：“有一个搜索空间门，它匹配非常大的状态和序列，可以在复杂性上创建一个有用的量子算法，它可以比经典算法更快地执行计算。

普渡大学的博士后研究人员Kais和Hu使用新理论识别了大量具有多项式复杂性的量子态。他们还表明，这些状态可能共享一个系数特征，这可以在设计量子算法时更好地识别它们。

废话：“考虑任何量子态，我们现在都可以设计一个有效的系数采样程序来确定它是否属于这个范畴。”