量子计算机编程：从入门到实践

保持领先：文献指引

｜

249

14.7

　竞赛

：

量子计算机与传统计算机

在讨论各种

QPU

应用时，我们经常饶有兴趣地比较

QPU

算法与传统算法的性能。尽管我

们已经逐个进行了比较，但量子计算机和传统计算机的能力还可以从计算复杂性的角度进

行有趣的比较。笼统地说，一个计算机科学问题的计算复杂性是由运行解决该问题的最高

效算法所需的资源决定的。计算复杂性理论根据问题的计算复杂性来研究难题的分类

4

。例

如，一些问题被分类为

P

，这意味着找到问题的解所需的资源与问题的规模成比例，所需

时间为多项式时间（例如矩阵对角化问题）。

NP

是指一类问题的

正确解

可以在多项式时间

内

检查

，但这些解不一定能在多项式时间内

找到

。这类问题有一个孪生类别，即

co-NP

问

题，它对应的是问题的不正确答案可以在多项式时间内得到验证。例如，我们在第

12

章

中讨论的质因数分解问题既属于

NP

问题，又属于

co-NP

问题——很容易检查一对数字是

（或者不是）质因数，但找出它们很难。不管

P=NP

是不是臭名昭著的待定问题，它都是非

常出名的，这要归功于流行文化的多次提及，以及一个小原因：

100

万美元的奖金在等待

着任何能够解决这个问题的人！基于充分的理由，人们普遍怀疑这两类问题是不相等的。

第

10

章提到的

NP

完全问题在某种意义上就是最难解的一类

NP

问题。

NP

类别中的任何

其他问题都可以归类为这类

NP

完全问题。如果能找到任何

NP

完全问题的多项式时间解，

那么所有

NP

问题也将在多项式时间内解决，类别也将变为

P

。

人们之所以对量子计算感兴趣，主要是因为它似乎能够降低某些问题的计算复杂性。请注 ...