QIP2021 | Degree vs. Approx.Degree and Q-Implications of Huangs Sensitivity Theorem (Shravs Rao)

Authors: Scott Aaronson, Shalev Ben-David, Robin Kothari, Shravas Rao and Avishay Tal

Affiliations: The University of Texas at Austin | University of Waterloo | Microsoft | Northwestern University | University of California at Berkeley

Abstract
Based on the recent breakthrough of Huang (2019), we show that for any total Boolean function f, deg(f) = O(~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. D(f) = O(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 Q(f)=Omega(n), which is also optimal. We also show that the approximate degree of any read-once formula on n variables is Theta(sqrt{n}).

Get entangled with us!