论文标题
黄的灵敏度定理的量子含义
Quantum Implications of Huang's Sensitivity Theorem
论文作者
论文摘要
根据Huang（2019）的最新突破，我们表明，对于任何总布尔函数$ f $，确定性查询复杂性，$ d（f）$，最多在量子查询复杂性中是Quartic的，$ q（f）$：$ d（$ d（$ d）= o（q（q（q（f）^4）^4）$。由于Ambainis，Balodis，Belovs，Lee，Santha和Smotrovs（2017年），这与已知的分离（最多到原木因子）相匹配。我们还使用结果来解决Aanderaa-Karp-Rosenberg猜想的量子类似物。我们表明，如果$ f $是其邻接矩阵指定的$ n $ vertex图的非平凡单调图属性，则是$ q（f）=ω（n）$，这也是最佳的。
Based on the recent breakthrough of Huang (2019), we show that for any total Boolean function $f$, the deterministic query complexity, $D(f)$, is at most quartic in the quantum query complexity, $Q(f)$: $D(f) = O(Q(f)^4)$. This matches the known separation (up to log factors) due to Ambainis, Balodis, Belovs, Lee, Santha, and Smotrovs (2017). We also use the result 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 $Q(f) = Ω(n)$, which is also optimal.
