Aaronson-Ambainis Conjecture Is True For Random Restrictions

Abstract

In an attempt to show that the acceptance probability of a quantum query algorithm making $q$ queries can be well-approximated almost everywhere by a classical decision tree of depth $\le \text{poly}(q)$, Aaronson and Ambainis proposed the following conjecture: let $f:\{\pm 1{\}}^n\to [0,1]$ be a degree $d$ polynomial with variance $\ge \epsilon$. Then, there exists a coordinate of $f$ with influence $\ge \text{poly}(\epsilon ,1/d)$. We show that for any polynomial $f:\{\pm 1{\}}^n\to [0,1]$ of degree $d$ $(d\ge 2)$ and variance $\text{Var}[f]\ge 1/d$, if $\rho$ denotes a random restriction with survival probability $\frac{\log (d)}{C_{1}d}$, $$\text{Pr}\left[f_{\rho }\text{ has a coordinate with influence}\ge \frac{\text{Var}[f{]}^2}{d^{C_2}}\right]\ge \frac{\text{Var}[f]\log (d)}{50C_{1}d}$$ where $C_1,C_2>0$ are universal constants. Thus, Aaronson-Ambainis conjecture is true for a non-negligible fraction of random restrictions of the given polynomial assuming its variance is not too low.

Accepted at ITCS 2025