量子科技中心_量科网

该研究团队展示了一个无条件的经典预言机分离结果，用于区分可通过量子证明验证的语言类（𝖰𝖬𝖠）与可通过经典证明验证的语言类（𝖰𝖢𝖬𝖠）。相较于Bostanci、Haferkamp、Nirkhe和Zhandry（STOC 2026）的最新研究，该工作的证明在概念和技术层面更为简洁，并能直接推广至其他预言机分离场景。尤其值得注意的是，该团队的技术首次实现了量子建议语言类（𝖡𝖰𝖯/𝗊𝗉𝗈𝗅𝗒）与经典建议语言类（𝖡𝖰𝖯/𝗉𝗈𝗅𝗒）之间的无条件经典预言机分离，改进了Aaronson和Kuperberg（CCC 2007）的量子预言机分离方案，以及Li、Liu、Pelecanos和Yamakawa（ITCS 2024）提出的经典可访问预言机分离结果。该工作所采用的预言机基于Yamakawa和Zhandry（FOCS 2022）提出的代码交集问题，并结合了具有极优列表恢复特性的编码方案。