量子算法复杂度是什么？

（图片来源：网络）

编者按：量子计算机究竟有多大神奇的魔力？它有多大的能力？能否带来计算的革命，是否能取代我们现在的经典计算机？探寻量子优势是量子计算领域的核心问题之一，而量子优势的发挥有赖于量子算法。同时，要搞清楚量子计算与经典计算的边界，需要从算法复杂度的角度进行深入研究。因此量子算法复杂度也是量子计算理论的核心内容之一。

算法复杂度的定义

无论是量子计算机还是经典计算机，具有共同的本质，就是需要去解决数学问题或逻辑问题。这就需要去判断哪些问题是可计算的，哪些是不可计算的。对于可计算的问题，计算机需要投入多少时间资源和内存资源去求解，不同类型的计算机的效率如何比较，这些都涉及到可计算理论。

早在20世纪50年代，现代的电子计算机都还没有很成型的时候，可计算性理论就已经开始发展起来。可计算性理论旨在探索不同计算机器理论上的能力界限，判断解决具体问题所设计的实际算法是否具备可行性，也就是在有限（内存）空间和时间范围内，能够在输入后获得最终的处理结果。

算法复杂度就是可计算理论的核心，它在数学上将算法与解决问题的“规模”挂钩，让问题“规模”与算法形成函数类的映射关系。以排序算法为例，对1万个数进行排序所需时间肯定比对10个数排序的时间长得多。但是这个时间长得多，能否有一个相对的比对关系作为衡量？复杂度理论就给出了这个比较关系，它包含两方面的复杂度：

时间复杂度：用于评估执行程序所消耗的时间，可以估算出程序对处理器的使用程度。

空间复杂度：用于评估执行程序所占用的内存空间，可以估算出程序对计算机内存的使用程度。

根据复杂度理论的研究成果，时间复杂度与空间复杂度之间是相互关系的。其结论是当在时间复杂度上获得利益的同时，必须在空间复杂度上做出妥协，时间与空间的开销就像分别坐在跷跷板两边，一方面抬起，另一方面必然下沉，我们无法在两个方面同时获益。

算法复杂度的衡量

由于内存空间的开销好满足，而时间上的开销更加具有“刚性”，所以一般在算法复杂度中，主要讨论的是时间复杂度的问题。时间复杂度并不是表示一个算法解决某个具体问题需要花多少时间，而是要衡量当算法所处理的问题规模扩大后，求解需要的时间长度对应增长得有多快。

也就是说，对于某一个算法其处理某一系列特定数据的效率不能衡量该程序的好坏，而应该看当这个数据的规模变大到数百倍后，程序运行时间是否还是一样，或者也跟着慢了数百倍，或者变慢了数万倍。时间复杂度一般用O(大写字母O)表示。

如果不管数据的规模如何增长，算法求解所需时间始终是不变的，我们就说这个算法很好，具有O(1)的时间复杂度，也称常数级复杂度。如果数据规模变得有多大，求解时间也同比例变得有多长，比如找n个数中的最大值这个算法的时间复杂度就是O(n)，为线性级复杂度。而像排序等算法，数据扩大2倍，所需时间变4倍的，时间复杂度就是O(n2)，为平方级复杂度。还有一些穷举类的算法，所需时间长度成几何阶数上涨，这就是O(an )的指数级复杂度，在组合问题中，甚至还有O(n!)的阶乘级复杂度。

这样，时间复杂度就可以用来衡量算法与算法之间、甚至是不同计算架构之间的效率了。还是用排序算法来举例，刚才说过简单的排序算法是与排序数据量成平方关系，记作O(n2)，如果算法经过优化，其实能够做到O(log2n）。

不会存在 O(2∗n2) 的复杂度，因为前面的那个"2"是系数，根本不会影响到整个程序的时间增长。同样地，O(n3+n2)的复杂度也就是O(n3)的复杂度。因此，我们会说，一个O(0.01*n3)的程序的复制度要高于比O(100*n2)的复杂度，因为尽管在n很小的时候，前者优于后者，但后者时间随数据规模增长得慢，最终 O(n3)的复杂度将远远超过O(n2)。

再往前一步说，就算再大的多项式n10000，也不能和再小的指数函数1.0001n相比。因为总是存在一个M，当n>M的时候，1.0001n会超过n10000，所以说，O(n10000)的复杂度小于O(1.0001n)的复杂度。

像O(1)，O(ln(n))，O(na)等，我们把它叫做多项式级复杂度，因为它的规模n出现在底数的位置。另一种像O(an)和O(n!)等，它是非多项式级的复杂度，其复杂度用经典计算机往往不能承受。当我们在解决一个问题时，我们选择的算法通常都需要是多项式级的复杂度，非多项式级的复杂度需要的时间太多，使用经典计算机求解往往需要超出实用性的时间。

经典计算中的复杂度分类

1. P类问题（Polynomial-time problem）：能在多项式时间内可解的问题。

2. NP类问题（Nondeterministic polynomial-time problem）：不确定能不能在多项式时间内解决，但能在多项式时间验证的问题。也就是说，不能判定这个问题到底有没有解，而是猜出一个解来在多项式时间内证明这个解是否正确。即该问题的猜测过程是不确定的，而对其某一个解的验证则能够在多项式时间内完成。值得注意的是，P类问题属于NP问题，但是否“NP=P?”，也即“是否所有能在多项式时间内验证得出正确解的问题，都是具有多项式时间求解算法的问题”，至今尚未有定论，是数学界的一个千禧年难题。

3. NPC问题（Non-deterministic Polynomial complete problem ）：存在这样一个NP问题，所有的NP问题都可以约化成它。换句话说，只要解决了这个问题，那么所有的NP问题都解决了。其定义要满足2个条件：①它是一个NP问题；②所有NP问题都能规约到它。

4. NP难问题（Non-deterministic Polynomial hard problem）：NP-Hard问题是这样一种问题，它满足NPC问题定义的第二条但不一定要满足第一条（就是说，NP-Hard问题要比 NPC问题的范围广，NP-Hard问题没有限定属于NP），即所有的NP问题都能约化到它，但是它不一定是一个NP问题。NP-Hard问题同样难以找到多项式的算法，但它不列入我们的研究范围，因为它不一定是NP问题。即使NPC问题发现了多项式级的算法，NP-Hard问题有可能仍然无法得到多项式级的算法。事实上，由于NP-Hard放宽了限定条件，它将有可能比所有的NPC问题的时间复杂度更高从而更难以解决。

引入量子计算后的复杂度分类

量子计算作为一种颠覆性技术已经引起了各界的广泛关注。由于在量子计算中，量子比特的叠加态可以用作计算资源，算力可以随着量子比特的数量呈指数型的增长，也因此对于某些在传统计算机上呈现指数型时间复杂度的问题，理论上可能因为采用量子计算机获得多项式时间复杂度的解决。

以质因数分解问题为例：两个大素数的乘积是很容易计算的，但是如果将这个乘积反过来分解成两个大素数就没有一个简单的方式，它的算法复杂度是O(2n)，是指数增长的，因此这个分解大素数的算法是NP问题，现代密码学的基础——RSA加密算法就是基于此开发出来的。用经典计算机去破解一个256位的RSA密码，需要成千上万年的时间，这就保证了密码的安全性。

但是在1994年，量子计算机的专家肖尔（Peter Shor）提出一个以他的名字命名的算法，宣称能够用多项式算法复杂度解决大素数因式分解问题，在理论上对现代RSA密码体系造成了极大威胁。

由此可见，量子计算设备是与经典的电子计算机完全不同的计算工具，在求解一些“复杂问题”上有着明显优势。所以在界定量子计算和量子算法的应用范围时，量子复杂度理论（Quantum complexity theory）也就应运而生，它主要研究引入量子计算后计算复杂度，以及量子复杂度类与经典复杂度类的关系。

在引入量子计算复杂度性后，不同计算复杂度问题集合机器之间的关系可由下图表述：

 

图1显示了复杂度类及广泛认可的包含关系的示意图。

 

量子复杂度中两个比较重要的复杂度类分别是BQP及QMA，分别对应经典计算中的复杂度P及NP复杂度。值得注意的是，图中的许多复杂类还没有经过数学证明：例如P是否等价于NP。而一些传统认为是NP难的问题，如质因数分解，在引入量子计算后已经证明使用Shor分解算法就能在多项式时间内可解，因此归于BQP类问题。

文：王凯/王衍

编辑：慕一