Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR03-014 | 28th February 2003 00:00

On Statistical Query Sampling and NMR Quantum Computing


Authors: Avrim Blum, Ke Yang
Publication: 13th March 2003 18:30
Downloads: 2801


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

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

ISSN 1433-8092 | Imprint