For any given Boolean formula $\phi(x_1,\dots,x_n)$, one can
efficiently construct (using \emph{arithmetization}) a low-degree
polynomial $p(x_1,\dots,x_n)$ that agrees with $\phi$ over all
points in the Boolean cube $\{0,1\}^n$; the constructed polynomial
$p$ can be interpreted as a polynomial over an arbitrary field
$\mathbb{F}$. The problem $\#SAT$ (of counting the number of
satisfying assignments of $\phi$) thus reduces to the polynomial
summation $\sum_{x\in\{0,1\}^n} p(x)$. Motivated by this connection,
we study the \emph{query complexity} of the polynomial summation
problem: Given (oracle access to) a polynomial $p(x_1,\dots,x_n)$,
compute $\sum_{x\in\{0,1\}^n} p(x)$. Obviously, querying $p$ at all
$2^n$ points in $\{0,1\}^n$ suffices. Is there a field $\mathbb{F}$
such that, for every polynomial $p\in\mathbb{F}[x_1,\dots,x_n]$, the
sum $\sum_{x\in\{0,1\}^n} p(x)$ can be computed using fewer than
$2^n$ queries from $\mathbb{F}^n$? We show that the simple upper
bound $2^n$ is in fact \emph{tight} for \emph{any} field
$\mathbb{F}$ in the \emph{black-box model} where one has only oracle
access to the polynomial $p$. We prove these lower bounds for the
\emph{adaptive} query model where the next query can depend on the
values of $p$ at previously queried points.
Our lower bounds hold even for polynomials that have degree at most
$2$ in each variable. In contrast, for polynomials that have degree
at most $1$ in each variable (i.e., multilinear polynomials), we
observe that a \emph{single} query is sufficient over any field of
characteristic other than $2$. We also give query lower bounds for
certain extensions of the polynomial summation problem.