量子科技中心_量科网

涉及交互式证明类的复杂性类包含关系以非相对化特性著称：尽管𝖨𝖯=𝖯𝖲𝖯𝖠𝖢𝖤已被证明，但Fortnow和Sipser揭示了存在一个相对预言机使得𝖼𝗈𝖭𝖯⊈𝖨𝖯。与此形成鲜明对比的是，𝖡𝖰𝖯⊆𝖨𝖯这一包含关系是否具有相对化特性的问题至今悬而未决。本研究通过证明𝖡𝖰𝖯⊆𝖬𝖨𝖯对所有经典预言机均成立，为解决该问题取得重要进展。该成果的获得源于研究者为任意经典预言机𝒪构建了一个𝖯𝖢𝖯证明系统：验证者在对指数级长度的证明和预言机𝒪进行多项式次经典查询的条件下，该系统可验证𝖡𝖰𝖯𝒪类问题。该构建方法受Grover与Rudolph的态合成算法启发，同时与Aharonov、Arad及Vidick构建的"指数级PCP"形成互补——后者虽实现类似参数但基于不同理念且不具备相对化特性。研究团队提出将相对化特性作为证明者效率的代理指标，并期待在预言机世界中针对𝖡𝖰𝖯的𝖨𝖯研究进展，最终能催生出非加密的交互协议，使得经典怀疑论者在非相对化世界中可验证任意量子计算——这始终是量子复杂性理论中长期悬而未决的难题。