  We study the query complexity of computing a function f:{0,1}^n-->R_+ in
expectation. This requires the algorithm on input x to output a nonnegative
random variable whose expectation equals f(x), using as few queries to the
input x as possible. We exactly characterize both the randomized and the
quantum query complexity by two polynomial degrees, the nonnegative literal
degree and the sum-of-squares degree, respectively. We observe that the quantum
complexity can be unboundedly smaller than the classical complexity for some
functions, but can be at most polynomially smaller for functions with range
{0,1}.
  These query complexities relate to (and are motivated by) the extension
complexity of polytopes. The linear extension complexity of a polytope is
characterized by the randomized communication complexity of computing its slack
matrix in expectation, and the semidefinite (psd) extension complexity is
characterized by the analogous quantum model. Since query complexity can be
used to upper bound communication complexity of related functions, we can
derive some upper bounds on psd extension complexity by constructing efficient
quantum query algorithms. As an example we give an exponentially-close
entrywise approximation of the slack matrix of the perfect matching polytope
with psd-rank only 2^{n^{1/2+epsilon}}. Finally, we show there is a precise
sense in which randomized/quantum query complexity in expectation corresponds
to the Sherali-Adams and Lasserre hierarchies, respectively.
