机构名称：
¥ 1.0
量子性证明是一种可证明的方法（向经典验证者证明），量子设备可以执行具有同等资源的经典设备无法执行的计算任务。提供量子性证明是构建有用的量子计算机的第一步。目前有三种方法可以展示量子性证明：（i）反转经典困难的单向函数（例如使用 Shor 算法）。这在技术上似乎遥不可及。（ii）从经典难以采样的分布中采样（例如 BosonSampling）。这可能在近期实验的范围内，但对于所有这些已知验证任务，都需要指数时间。（iii）基于加密假设的交互式协议。使用陷门方案可以实现有效的验证，并且实现所需的资源似乎比（i）少得多，但仍比（ii）多。在这项工作中，我们提出了一种显著简化方法 (iii) 的方法，即采用随机预言启发式方法。（我们注意到，我们不应用 Fiat-Shamir 范式。）我们基于任何无爪陷门函数给出了量子性的双消息（质询-响应）证明。与早期的提议相比，我们不需要自适应硬核位属性。这允许使用更小的安全参数和更多样化的计算假设（例如带错误的环学习），从而显著减少成功演示所需的量子计算工作量。
更简单的量子性证明 - DROPS
主要关键词
相关文件推荐
