量子计算或许终将在解决某些复杂问题时超越经典计算机，但"量子优势"何时、如何出现仍未可知。京都大学研究人员将这种优势与密码谜题相关联，证明允许安全保密量子密码学成立的条件，同样决定着量子计算何时能超越经典计算方法。
当量子计算机能够解决当前技术难以解决的问题时，这被称为量子优势。然而，这种优势并不能保证适用于所有计算，这引发了关于该优势存在条件的根本性问题。虽然先前的研究提出了各种量子优势的充分条件，但这些条件的必要性仍不明确。
受此不确定性的启发，京都大学的一个研究团队致力于利用结合量子计算和密码学（安全编码信息的科学）技术的方法，理解量子优势的充分必要条件。
具体而言，该团队专注于一类称为低效验证者量子性证明的交互式协议。这些协议允许没有量子计算机的验证者与量子证明者互动，并验证后者确实拥有量子计算能力。在他们的研究中，团队证明了这些证明的存在依赖于一种称为单向谜题的特定密码学原语的存在。
通过整合这些方法，该团队引入了一个新颖框架，将看似无关的量子优势和密码学安全概念统一起来。其结果，该团队首次能够完整地刻画量子优势的特征。
"我们通过证明量子优势的存在与某些量子密码学原语的安全性之间存在等价关系，从而确定了量子优势的充分必要条件，"通讯作者Yuki Shirakawa表示。
这些结果意味着，当量子优势不存在时，几乎所有密码学原语（先前被认为安全的）其安全性都会被破坏。重要的是，这些原语不仅限于量子密码学，还包括广泛使用的传统密码学原语以及正在快速发展的后量子密码学原语。
所建立的量子计算与密码学之间的等价关系，也为未来量子优势的实验演示以及该领域持续的理论研究提供了更坚实的密码学基础。
"量子优势是一个备受期待且被积极研究的概念，但仍未被完全理解。我们的研究代表了朝着更深入理解这一特性迈出的重要一步，"Shirakawa说道。
该团队期望未来的研究能将这种特征刻画扩展到其他类型的量子优势，并催生更通用的理论框架。