量子科技中心_量科网

Mahadev [SIAM J. Comput. 2022] 首次提出了基于学习伴随错误（LWE）假设的量子计算经典验证协议，实现了4轮交互方案。这一突破性成果自然引出了一个问题：在纯模型下是否可能实现更少的交互轮次？尽管该问题具有重要意义，但至今仍未得到解决。该工作证明，对于𝖰𝖬𝖠类问题的非交互式经典量子计算验证，不存在基于任何可证伪假设的量子黑盒归约。这里的“非交互式”指在实例无关的初始设置后，协议仅需单轮通信即可完成。鉴于可证伪假设涵盖了密码学中几乎所有标准假设（包括LWE），这一结果构成了强有力的否定性结论。该分离性结果建立在𝖰𝖬𝖠-𝖰𝖢𝖬𝖠间隙问题存在的前提下——这类问题本质上要求比𝖰𝖬𝖠≠𝖰𝖢𝖬𝖠稍强的假设。为佐证此类问题的存在性，该研究团队还给出了相对于量子酉算符预言机的具体构造方案。