We introduce a ``Statistical Query Sampling'' model, in which
the goal of an algorithm is to produce an element in a hidden set
$S\subseteq\bit^n$ with reasonable probability. The algorithm
gains information about $S$ through oracle calls (statistical
queries), where the algorithm submits a query function $g(\cdot)$
and receives an approximation to $\Pr_{x \in S}[g(x)=1]$. We
show how this model is related to NMR quantum computing, in which only
statistical properties of an ensemble of quantum systems can be
measured, and in particular to the question of whether one can
translate standard quantum algorithms to the NMR setting without
putting all of their classical post-processing into the quantum
system. Using Fourier analysis techniques developed in the related
context of {\em statistical query learning},
we prove a number of lower bounds (both information-theoretic and
cryptographic) on the ability of algorithms to produces an $x\in S$,
even when the set $S$ is fairly simple. These lower bounds point
out a difficulty in efficiently applying NMR quantum computing to
algorithms such as Shor's and Simon's algorithm that involve
significant classical post-processing. We also explicitly relate the
notion of statistical query sampling to that of statistical query
learning.

An extended abstract to appear in the 18th Aunnual IEEE Conference
of Computational Complexity (CCC 2003), 2003.