论文标题
程度与黄金敏感性定理的近似程度和量子意义
Degree vs. Approximate Degree and Quantum Implications of Huang's Sensitivity Theorem
论文作者
论文摘要
根据Huang（2019年）的最近突破，我们表明，对于任何总布尔函数$ f $， $ \ bullet \ quad \ mathrm {deg}（f）= o（\ widetilde {\ mathrm {deg}}}}（f）^2）$：$ f $的度数最多在$ f $的近似度上是Quadratic的。这是最佳选择，如或功能所见。 $ \ bullet \ quad \ mathrm {d}（f）= o（\ mathrm {q}（f）^4）$：$ f $的确定性查询复杂性最多在$ f $的量子查询复杂性中最Quartic。由于Ambainis，Balodis，Belovs，Lee，Santha和Smotrovs（2017年），这与已知的分离（最多到原木因子）相匹配。 我们将这些结果应用于Aanderaa-karp--Rosenberg猜想的量子类似物。我们表明，如果$ f $是其邻接矩阵指定的$ n $ vertex图的非平凡单调图属性，则是$ \ mathrm {q}（f）（f）=ω（n）$，这也是最佳的。我们还表明，$ n $变量上任何读取公式的近似度为$θ（\ sqrt {n}）$。
Based on the recent breakthrough of Huang (2019), we show that for any total Boolean function $f$, $\bullet \quad \mathrm{deg}(f) = O(\widetilde{\mathrm{deg}}(f)^2)$: The degree of $f$ is at most quadratic in the approximate degree of $f$. This is optimal as witnessed by the OR function. $\bullet \quad \mathrm{D}(f) = O(\mathrm{Q}(f)^4)$: The deterministic query complexity of $f$ is at most quartic in the quantum query complexity of $f$. This matches the known separation (up to log factors) due to Ambainis, Balodis, Belovs, Lee, Santha, and Smotrovs (2017). We apply these results to resolve the quantum analogue of the Aanderaa--Karp--Rosenberg conjecture. We show that if $f$ is a nontrivial monotone graph property of an $n$-vertex graph specified by its adjacency matrix, then $\mathrm{Q}(f)=Ω(n)$, which is also optimal. We also show that the approximate degree of any read-once formula on $n$ variables is $Θ(\sqrt{n})$.
