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

假如你现在有两个随机数字序列生成器，而你需要解决这样一个问题：这两组序列是完全独立的，还是以某种隐藏的形式相关联的（比如一组是另一组序列的“傅里叶变换”）。Aaronson 在 2009 年首次提出了这种“关系（forrelation）”问题，并证明它属于 BQP。但解决该问题的第二步将更为困难，因为你需要证明该关系不属于 PH 类的集合。

Raz 和 Tal 这篇论文的成就便是实现了一种名为“Oracle（也称“黑匣子”）”的 BQP 与 PH 的区分方式。 区分 BQP 和 PH 的最佳方式是测量解决每个问题所需的计算时间。但多伦多大学的计算机科学家 Henry Yuen 认为，目前我们对计算所需时间的认识还不足以让人们得出某一问题所需的计算时间。

图 | 普林斯顿大学理论计算机科学家 Ran Raz

正如 Yuen 所说的那样，计算机科学家一般会测量一些其他的量来衡量计算所需的时间，比如计算出计算机在解决问题的过程中询问“oracle”的次数。oracle 就像是一个提示，你不知道它是怎样产生的，但你知道它是可靠的。

回到解决两组数列是否相关的问题上，你可以先询问 oracle 类似“每个发生器的第六个数字是什么？”的问题，然后，根据每种计算机所需的提示数量来比较计算能力（需要更多提示的计算机计算速度较慢）。

Tal 说：“从某种意义上来说，我们更好地理解了这个模型。 模型更多涉及到的是信息而不是计算。”

图 | 斯坦福大学理论计算机科学家 Avishay Tal

Raz 和 Tal 的这篇论文证明了量子计算机在解决 forrelation 问题时较传统计算机所需的提示更少。 事实上，量子计算机只仅要一个提示就能解决问题，而即使有无限个提示，PH 中也没有可以解决问题的算法。Raz 说： “这意味着有一个非常有效的量子算法能够解决这类问题，即那些传统算法无法解决的问题。这说明了 forrelation 问题在分类上属于 BQP 而不是 PH。”

Raz 和 Tal 在四年前就已接近证明出这一结论，但他们无法完成证明中的重要一步。 然后就在论文发表的一个月前，Tal 看到一篇关于伪随机数列产生器的论文，意识到这篇论文中的技术正是他和Raz的证明所需要的，于是才有了这篇论文的发表。