2020/10/23 by Scott Aaronson, Aaronson, Scott, Shalev Ben-David +7 · 4 citations
Computer Science · #Machine Learning and Algorithms #Quantum Computing Algorithms and Architecture #Complexity and Algorithms in Graphs
paper · pdf · doi:10.48550/arxiv.2010.12629
Based on the recent breakthrough of Huang (2019), we show that for any total\nBoolean function f,\n bullet deg(f) = O( widetildedeg(f)2): The\ndegree of f is at most quadratic in the approximate degree of f. This is\noptimal as witnessed by the OR function.\n bullet \D(f) = O(\Q(f)4): The deterministic query\ncomplexity of f is at most quartic in the quantum query complexity of f.\nThis matches the known separation (up to log factors) due to Ambainis, Balodis,\nBelovs, Lee, Santha, and Smotrovs (2017).\n We apply these results to resolve the quantum analogue of the\nAanderaa--Karp--Rosenberg conjecture. We show that if f is a nontrivial\nmonotone graph property of an n-vertex graph specified by its adjacency\nmatrix, then \Q(f)=\Ω(n), which is also optimal. We also show\nthat the approximate degree of any read-once formula on n variables is\n\Θ(\√(n)).\n