在2019年，谷歌声称它是第一个展示量子计算机来执行超越当今最强大的超级计算机能力的计算。普渡大学的科学家们说，但是大多数时候，创造一种可以击败传统计算机的量子算法是一个偶然的过程。为了给该过程带来更多指导并减少其随意性，这些科学家开发了一种新理论，该理论可能最终导致对量子算法进行更系统的设计。

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

　　物理学家将这种具有正确门数以控制每个状态的门称为“复杂性”。由于量子算法的复杂性与算法中涉及的量子态的复杂性密切相关，因此该理论可以通过表征哪些量子态满足该复杂性标准，从而为寻找量子算法打下基础。

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

　　在普通计算机中，电路具有将位切换到0或1状态的门。相反，量子计算机依赖于称为“量子位”的计算单元，该计算单元可以同时叠加存储0和1状态，从而可以处理更多信息。

　　使量子计算机比普通计算机快的是更简单的信息处理，其特征在于与普通电路相比，量子电路中量子门的数量大大减少。

　　在普通计算机中，电路中门的数量相对于所关注问题的大小呈指数增长。这个指数模型增长得如此之快，以至于即使是中等大小的关注问题，它在物理上也无法处理。

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

　　对于量子计算机，有一种方法可以使量子门按问题的大小（如上一个示例中的电子数）“多项式地”按比例放大，而不仅仅是像普通计算机那样按指数比例放大。“多项式”意味着处理相同数量的信息所需的步骤（门）将大大减少，从而使量子算法优于普通算法。

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

　　“有一个寻找状态和顺序非常大的搜索空间门匹配，在复杂创建能够执行计算比普通算法快的一个有用的量子算法，”凯斯他的研究小组正在开发的量子算法和量子说机器学习方法。

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

　　考虑到任何量子态，我们现在能够设计一种有效的系数采样程序来确定它是否属于该类。