__
TR03-014 | 28th February 2003 00:00
__

#### On Statistical Query Sampling and NMR Quantum Computing

**Abstract:**
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.