从密码学的角度探讨量子优势的可验证性

《ACM Transactions on Quantum Computing》：A Cryptographic Perspective on the Verifiability of Quantum Advantage

量子优势验证与密码学原语关联性研究。针对NISQ设备量子优势的可验证性难题，从密码学角度建立与高效可采样对（EFI）、伪随机态（PRS）、最小电路大小问题（MCSP）等复杂性原语的强联系，证明量子优势的验证或可构造EFI/PRS，并揭示MCSP算法对验证效率的影响。

　　

摘要

近年来，在NISQ设备上实现可验证的量子优势已成为量子信息领域的一个重要未解决问题。基于采样的量子优势目前尚缺乏高效的验证方法。本文从密码学的角度探讨了量子优势的验证问题。我们建立了量子优势的可验证性与密码学及复杂性原语之间的紧密联系，这些原语包括可高效采样的、在统计上难以区分但在计算上无法区分的（混合）量子态对（EFI）、伪随机态（PRS）以及最小电路尺寸问题的变体（$\text{MCSP}$）。具体来说，我们证明了：a) 基于采样的量子优势要么是可验证的，要么可以用来构建EFI甚至PRS；b) 如果存在针对$\text{MCSP}$的多项式时间算法，那么这将意味着量子优势的高效验证成为可能。我们的研究表明，对可验证量子优势的探索可能会推动量子密码学的应用，而量子原语的构建可以为量子优势的可验证性提供新的见解。