量子科技中心_量科网

该研究建立了自适应场景下容错junta检测问题的首个超多项式量子优势。具体而言，研究证明，在特定参数范围内，高精度容错 \(k\)-junta 检测问题可使用 \(\mathrm{poly}(k)\) 次量子查询解决，而任何经典算法至少需要 \(k^{\Omega(\log k)}\) 次查询。容错 \(k\)-junta 检测问题具体描述如下：给定参数 \((k, \varepsilon_1, \varepsilon_2)\)，满足 \(0 \le \varepsilon_1 < \varepsilon_2 \le 1/2\)，并可通过黑盒访问一个布尔函数 \(f\)（定义在 \(n\) 个变量上），需要区分 \(f\) 是否 \(\varepsilon_1\)-接近某个 \(k\)-junta，或者是否 \(\varepsilon_2\)-远离所有 \(k\)-junta。该研究展示了在接近 \(1/2\) 的参数范围内（例如 \(\varepsilon_1 = 1/2 - 1/k\) 和 \(\varepsilon_2 = 1/2 - 1/(2k^2)\)）的量子优势。研究中使用的（非自适应）量子检测器由Bao、Liu、Yao、Ye和Zhang近期的工作（SOSA 2026）提出。研究对其分析进行了微调，证明该检测器在上述参数范围内依然有效。另一方面，经典下界需要全新的思想。受Chen和Patel（FOCS 2023）的下界技术启发，该研究引入了一种新的“是”实例（即与某个 \(k\)-junta 距离不超过 \(\varepsilon_1\) 的实例）的困难分布，其构造基于植入“近似junta”的方法：随机选择 \(n\) 个坐标中的 \(k\) 个，对于 \(k\) 个坐标的每种固定取值，受限子立方体中的 \(2^{n-k}\) 个值被随机生成，但属于某个纠错码的点集被赋予相同的随机比特。研究证明，该分布比均匀分布更接近 \(k\)-junta，但另一方面，任何进行 \(k^{o(\log k)}\) 次查询的经典算法都无法区分它们。