量子科技中心_量科网

该研究团队首次开展关于相位态的量子不可知学习研究（针对函数类𝒞⊆{c:{0,1}ⁿ→{0,1}}）：给定未知n量子比特态|ψ⟩的若干副本（该态与相位态|ϕᶜ⟩=1/√2ⁿ∑ₓ∈{0,1}ⁿ(-1)ᶜ⁽ˣ⁾|x⟩对于某c∈𝒞具有最优保真度opt），输出满足|⟨ϕ|ψ⟩|²≥opt−ε的|ϕ⟩。为此，研究团队提出以下两类不可知学习协议： 1. 规模为t的决策树学习协议，运行时间为poly(n,t,1/ε)。该结果同时表明k-juntas可在poly(n,2ᵏ,1/ε)时间内实现不可知学习。 2. s项DNF公式的拟多项式时间学习协议poly(n,(s/ε)^(loglog(s/ε)))。 核心技术创新在于量子不可知增强协议——该协议将“弱”不可知学习器（输出满足|⟨ϕ|ψ⟩|²≥opt/poly(n)的奇偶态|ϕ⟩）转化为“强”学习器（输出满足|⟨ϕ'|ψ⟩|²≥opt−ε的奇偶态叠加态|ϕ'⟩）。 通过运用量子不可知增强技术，研究人员首次在均匀量子PAC模型中利用量子样本，针对由AND/OR/NOT门构成的poly(n)规模深度-3电路，提出具有n^O(loglogn)时间复杂度“拟”多项式学习算法。经典计算学习理论中，深度-3电路（甚至深度-2电路）在均匀PAC模型中的高效学习问题长期悬而未决。该工作在使用量子样本的条件下近乎解决了这一难题。