NTT Research昨日宣布，其密码学和信息安全(CIS)实验室的科学家和NTT社会信息学实验室(SIL)的同事合作撰写了一篇关于量子优势的开创性论文。该论文已被选中在2022年IEEE计算机科学基础研讨会(FOCS)上发表。这篇题为“非结构化的可验证量子优势”的论文的共同作者是NTT SIL的杰出研究员Takashi Yamakawa博士和NTT Research CIS实验室的高级科学家Mark Zhandry博士。

量子优势的主题涉及量子计算机可以比经典计算机解决相同问题的速度有多快。所讨论的问题通常为非确定性多项式时间(NP)类问题。能获得多少优势可能会有很大程度的不同。量子计算机可能能在一分钟或一秒钟内解决一个特定问题，而经典计算机需要一周时间，或者也可能是深不可测的指数时间。在本文中，作者解决了如何验证这种优势的挑战，并有效地做到了这一点。迄今为止，量子优势的演示大多涉及重要的“结构”，或者两方或多方之间的来回通信。

德克萨斯大学奥斯汀分校计算机科学教授Scott Aaronson博士说：“这是我们第一次看到NP搜索问题的指数级量子加速，它只需要一个随机预言机(random oracle)。”Yamakawa和Zhandry博士只需要一个随机预言机，即能对每个查询生成随机响应的理论黑盒，并将他们的问题建立在非结构化的计算假设上。因此，他们的问题更接近于单向函数(例如在公钥密码学中用到的那些)而不是结构化函数。这种单向对齐有助于进行有效的验证。

Yamakawa和Zhandry设计的NP搜索问题是一个二合一问题。它需要找到1)一个n符号字符串，它是给定纠错码的代码字，以及2)一个n符号字符串，其中每个符号在随机预言机下被映射为零。每个问题单独来看都很简单，但是要找到一个既是代码字又映射到零的符号串要困难得多，至少在传统计算机上是这样。Zhandry博士说：“如果你的方法是量子的，你可以在多项式时间内解决这个问题。但如果你的方法是经典的，如果你在这个黑盒模型中，你将需要指数级时间。”

另一方面，如果有一个潜在的解决方案，通过检查它是否分别解决了两个问题中的每个问题来验证它是很简单的。作为一篇在FOCS上发表的论文，这项工作是一项基础性研究。正如Aaronson博士在美国Simons研究所的演讲中所指出的那样。Yamakawa-Zhandry论点属于一类可以很容易地在数学上验证的加速。但它在短时间内还不能用真正的量子计算机进行实际验证。除了其开创性的验证方案之外，该论文还指出了有关量子加速程度的一些新问题。

Zhandry博士说：“在我们的工作之前，我们确实已有NP问题获得量子优势的例子，比如因式分解，或者在黑盒设置下进行周期查找。但事实证明，所有这些例子背后的量子算法基本上都是周期查找算法——尽管演示如何将周期查找算法应用于这些例子通常并非易事。我们的论文显示至少还有第二种情况。你可以乐观地解释为，量子优势可能比我们以前想象的要更加普遍。”（编译:Qtech）