Let $f \in \mathbb{Z}_2[x_1, ..., x_n]$ be arbitrary. We define $gap(f) = |f^{-1}(0)| - |f^{-1}(1)|$. I want to understand, as a function of any properties of $f$ you find relevant (number of terms, sparsity of variable occurrence, etc.), upper bounds on the the quantity

$\mathbb{E}_{i \in [n]} |gap(f) - gap(f + x_i)|.$

Doing a little bit of manipulation, I can do at least something, but it isn't as strong as I'd like. We define $X^{(i)}_{a, b} = \{ x \mid f(x) = a \wedge x_i = b \}.$ Note then that

$f^{-1}(a) = X^{(i)}_{a, 0} \oplus X^{(i)}_{a, 1} $

$(f + x_i)^{-1}(0) = X^{(i)}_{0, 0} \oplus X^{(i)}_{1, 1}$

$(f + x_i)^{-1}(1) = X^{(i)}_{1, 0} \oplus X^{(i)}_{0, 1}$

and thus that

$gap(f) - gap(f + x_i) = |X^{(i)}_{0, 0}| + |X^{(i)}_{0, 1}| - |X^{(i)}_{1, 0}| - |X^{(i)}_{1, 1}| -|X^{(i)}_{0, 0}| - |X^{(i)}_{1, 1}| +|X^{(i)}_{1, 0}| + |X^{(i)}_{0, 1}| = 2|X^{(i)}_{0, 1}| - 2|X^{(i)}_{1, 1}|$

which is two times the gap of $f$ restricted to inputs where $x_i = 1$. Rewriting this further in terms of the number of zeroes of this restricted $f$, one can use Schwartz-Zippel to get a bound, but it is hardly informative. This problem is a toy version of something which would yield interesting results in quantum circuits: it is a step towards computing the average sensitivity of quantum circuits. As such, if one can find an infinite family of polynomials which bounds this quantity above, say, $\sqrt{s}$, where $s$ is the number of terms in the polynomial, this would be a very interesting result in this respect. For more information on how this relates to quantum circuits, see this paper.


Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.