机构名称：
¥ 11.0
在量子计算验证问题中，量子服务器想要让客户端相信，对量子电路 C 进行评估的输出就是它所声称的某个结果。这个问题在量子计算的理论和实践中都非常重要 [32, 1, 47]。客户端的计算能力有限，而其理想特性之一是客户端可以完全是经典的，这就引出了量子计算的经典验证 (CVQC) 问题。就服务器端量子计算的时间复杂度而言（通常决定客户端和服务器的总时间复杂度），迄今为止最快的单服务器 CVQC 协议的复杂度为 O(poly(κ)|C|3)，其中|C|是待验证电路的大小，κ是安全参数，由 Mahadev [41] 给出。这导致许多现有协议（包括多方量子计算、零知识和混淆）也出现类似的立方时间爆炸 [8, 50, 9, 16, 18, 2]。考虑到量子计算资源的珍贵性，这种立方复杂度障碍可能会成为将这些问题的协议付诸实践的一大障碍。在本文中，通过开发新技术，我们给出了一种新的 CVQC 协议，其复杂度为 O ( poly ( κ ) | C | )（就客户端和服务器的总时间复杂度而言），比现有协议快得多。我们的协议在量子随机预言模型 [11] 中是安全的，假设存在有噪声陷门无爪函数 [12]，这两个都是量子密码学中广泛使用的假设。在此过程中，我们还为 {| + θ ⟩ = 1 √
线性时间内量子计算的经典验证
主要关键词
相关文件推荐
