终于，科学家们找到了只有量子计算机才能解决的问题(2)

理论计算机研究中的一个基本项目就是将问题根据复杂程度进行分类，也称复杂度分级（Complexity Classes），即根据解决问题所需资源（如时间和内存）的多少进行分类。

其中最着名的两个分类是“P”和“NP”，，P 是传统计算可以快速解决的所有问题。 （“这个数字是否是质数？”属于 P）NP 是传统计算机并不能迅速解决，但如果存在一个已知答案能够快速验证的问题（如“这个数的质因数有哪些？”属于 NP）。计算机科学家认为 P 和 NP 是不同的类别，但证明 P 与 NP 不同却是该领域最难以及最重要的问题之一。

[好文分享：www.11jj.com]

1993 年，计算机科学家 Ethan Bernstein 和 Umesh Vazirani 为复杂度分类创造了一个新的类别，“有限错误量子多项式时间”类（bounded-error quantum polynomial time）”，即上文中所提到过的 BQP 问题。该定义类中包含量子计算机可以高效解决的所有决策问题，即答案为是或否的问题。两位科学家同时还证明了量子计算机可以解决传统计算机可以解决的所有问题，也就是证明了 BQP 分类中包含了 P 分类（这里分类看为数学中集合的概念）。

但 Ethan 和 Umesh 无法确定 BQP 中是否也包含“多项式层次结构（Polynomial Hierarchy）”类问题，也称 PH 类问题。PH 是 NP 的拓展，包含所有由 NP 类延伸出的问题，如通过添加“对于所有...来说是否存在...”。 当今的传统计算机无法解决 PH 中的大多数问题，但如果 P 等于 NP，则可以将 PH 看作是传统计算机可以解决的所有问题。换句话说，比较 BQP 和 PH 这两种问题分类，便是为了确定量子计算机是否真的较传统计算机具有优势。

关于不同复杂度类别的问题可以参考“旅行推销员问题（TSP）”。“是否存在通过若干个城市的一些路径比另一些路径更短”是一个 NP 问题。而一个 PH 问题则是“是否通过这几个城市的最短路径就是某个特定距离”。

德克萨斯大学的计算机科学家 Scott Aaronson 说：“PH 是最基本的古典复杂度分类之一。而我们想知道，量子计算在古典复杂度分类的标准中处于什么样的位置。”

区分出两个复杂类别的最好方法是，找到一个可被证明为仅属于其中一类的问题。 然而，由于基础研究上的不足以及技术上的障碍，一直没人能找到符合这种要求的问题。

Aaronson 说，如果你想找到一个仅属于 BQP 而不属于 PH 的问题，你必须找到一个从定义上传统计算机不能有效证明答案的问题，这样的问题“传统计算机甚至不能有效地验证答案，更别说找到它了。这就排除了我们在计算机科学中所考虑的许多问题。”

BQP 和 PH