加利福尼亚州桑尼维尔 - 26 年 2022 月 XNUMX 日 - NTT Research 宣布，其科学家 密码学和信息安全 (CIS) 实验室 和一位同事 NTT 社会信息学实验室 (SIL) 撰写了一篇关于量子优势的开创性论文。 该论文被选中在 31 月 3 日至 XNUMX 月举行的年度 IEEE 计算机科学基础研讨会 (FOCS) 上发表。 XNUMX 在丹佛。
该论文的共同作者，标题为“无结构可验证的量子优势，”是 NTT SIL 的杰出研究员 Takashi Yamakawa 博士和该研究的高级科学家 Mark Zhandry 博士 NTT研究 独联体实验室。 这项工作部分是在普林斯顿大学完成的，山川博士是该大学的访问研究学者，詹德利博士也是计算机科学的助理教授。
量子优势（或量子加速）的主题涉及量子计算机可以比经典或非量子计算机更快地解决的问题类型以及它们的速度有多快。 所讨论的问题通常被描述为非确定性多项式时间（NP）类。 多少优势可能在很大程度上有所不同。 量子计算机可能能够在一分钟或一秒钟内解决一个特定问题，而经典计算机需要一周时间，或者可能是深不可测的指数时间。 在本文中，作者解决了验证这种优势的挑战，并有效地做到了这一点。 迄今为止，量子优势的展示涉及重要的“结构”，或两方或多方之间的来回通信。 Yamakawa 和 Zhandry 论文的突破是展示了一个 NP 难题，即无需结构即可验证。
“这是我们第一次看到 NP 搜索问题的指数量子加速，它只需要一个随机预言机，”德克萨斯大学奥斯汀分校计算机科学教授 Scott Aaronson 博士说，他评论了早期版本该论文于 13 年 2022 月 XNUMX 日在西蒙斯计算理论研究所的一次研讨会上发表。 Yamakawa 和 Zhandry 只需要一个随机预言机，即对每个查询生成随机响应的理论黑盒，将他们的问题建立在非结构化计算假设上。 因此，他们的问题更接近于单向函数而不是结构化函数，例如在公钥密码学中发现的那些。 这种单向对齐有助于有效的验证。
“很高兴看到 NTT 下属的密码学家合作开展再次获得‘突破’标签的研究，特别是在一篇丰富我们对量子计算的理解的论文中，这是我们 NTT Research 关注的另一个领域，”Kazuhiro Gomi 说, NTT Research 总裁兼首席执行官。 “祝贺这次享有盛誉的 IEEE 会议的所有参与者并致以最良好的祝愿。”
Yamakawa 和 Zhandry 设计的 NP 搜索问题是一个二合一问题，需要找到 1）一个 n 符号字符串，它是给定纠错码的代码字，以及 2）一个 n 符号字符串，其中每个在随机预言下，符号被映射为零。 单独的每个问题都很容易。 但是要找到一个既是代码字又映射到零的符号串要困难得多，至少在传统上是这样。 “如果你是量子的，你可以在多项式时间内解决这个问题，”Zhandry 博士说，“但如果你是经典的，至少如果你在这个黑盒模型中，你需要指数时间。” 另一方面，给定一个潜在的解决方案，通过检查它是否分别解决了两个问题中的每一个来验证它很简单。 请注意，作为 FOCS 的论文，这项工作是基本的或基础的。 正如 Aaronson 博士在西蒙斯研究所的演讲中所指出的那样（在本 NTT 研究中讨论过） 博客文章)，Yamakawa-Zhandry 论点属于一类加速，可以很容易地在数学上检查，但不会很快被实际的量子计算机实际证明。 然而，除了其开创性的验证方案之外，该论文还指出了有关量子加速程度的一些新问题。
“在我们的工作之前，我们确实有 NP 问题的量子优势的例子，比如因式分解，或者在黑盒设置中，周期发现。 但事实证明，所有这些例子背后的量子算法基本上都是周期发现——尽管展示如何将周期发现应用于这些例子通常并非易事，”Zhandry 博士说。 “我们的论文显示至少还有第二种情况。 你可以乐观地解释为，量子优势可能比我们以前想象的更普遍。”
FOCS 由 IEEE 计算机学会计算数学基础技术委员会 (TCMF) 赞助，是理论计算机科学领域的领先会议。 FOCS 2022 的论文征集是第 63 届此类年度聚会，将量子计算列为 17 个普遍感兴趣的领域之一。 Yamakawa-Zhandry 论文计划于 31 年 2022 月 10 日上午 15:XNUMX 提交。 要了解有关此活动的更多信息并注册，请访问 福克斯 2022 网站。
