Aaronson–Ambainis influence conjecture

Consider a rule that outputs 1 only when two on/off switches are both on, and outputs 0 otherwise. Its four equally likely settings give 0, 0, 0, 1. Flipping the first switch changes the output only when the second is on, so the average squared change is one half. This measures the first switch’s influence. More generally, a polynomial rule adds product terms, using each switch at most once in a term; its output must stay between 0 and 1. Degree counts the most switches multiplied together in a term. The conjecture asks whether every such rule whose output varies must have at least one sufficiently influential switch, with a guarantee depending on degree and overall variation, rather than the number of switches.[1] [2]

Can output variation of a bounded low-degree rule always be traced to at least one substantially influential input bit, independently of how many bits there are? Let $X$ range uniformly over all $n$-bit settings, and let $X^{\oplus i}$ denote the same setting with bit $i$ flipped. For the example $f(x,y)=xy$, the four outputs are $0,0,0,1$, with mean $1/4$, variance $3/16$, and influence $1/2$ for either bit. These are illustrative calculations, not a proof of the general guarantee. Variance and squared flip influence mean$$\operatorname{Var}(f)=\mathbb E[(f(X)-\mathbb E f(X))^2],\qquad \operatorname{Inf}_i(f)=\mathbb E[(f(X)-f(X^{\oplus i}))^2].$$The function is multilinear: each variable has exponent at most one in every product term. Degree $d$ is the largest number of variables multiplied in any product term. For every such $f:\{0,1\}^n\to[0,1]$ with $d\ge1$ and positive variance, the conjecture asks for constants $c,C>0$ that work universally:$$\max_i\operatorname{Inf}_i(f)\ge c\left(\frac{\operatorname{Var}(f)}d\right)^C.$$Those constants cannot depend on $n$, $d$, or the particular rule.[1] [2]

The proposed guarantee is still unproved for all bounded low-degree polynomials.[1] [2]

Distributional equivalences in the September preprint preserve the core conjecture rather than remove its universal quantifier.[1] [2]

The question asks whether a rule can spread meaningful output variation among many inputs so thinly that none is useful to inspect. Finding an influential input suggests a way to learn more by querying that input first. The connection to quantum computing is specific: quantum query acceptance probabilities are bounded polynomial rules. The conjecture would support classical approximations of those probabilities on most uniformly chosen inputs, with only polynomially more input queries; it would not guarantee a fast classical simulation of every quantum computation.[1] [2]

A quantum algorithm using $T$ input queries has an acceptance probability represented by a bounded multilinear polynomial of degree at most $2T$. Under the influence conjecture, for any desired additive error $\varepsilon$ and exceptional fraction $\delta$, a deterministic classical procedure could approximate that probability to within $\varepsilon$ on at least a $1-\delta$ fraction of uniformly chosen inputs, using $\operatorname{poly}(T,1/\varepsilon,1/\delta)$ queries. This links an analytic statement about one influential coordinate to limits on typical-input quantum query advantages. Query count does not bound total computational time, and the influence statement is stronger than the average-input simulation conjecture it implies.[1] [2]