On Statistical Query Sampling and NMR Quantum Computing

Kearns' statistical query (SQ) oracle (STOC'93) lends a unifying perspective for most classical machine learning algorithms. This ceases to be true in quantum learning, where many settings do not admit, neither an SQ analog nor a quantum statistical query (QSQ) analog. In this work, we take inspiration from Kearns' SQ oracle and Valiant's weak evaluation oracle (TOCT'14) and establish a unified perspective bridging the statistical and parametrized learning paradigms in a nove...

We study the quantum complexity of the static set membership problem: given a subset S (|S| \leq n) of a universe of size m (m \gg n), store it as a table of bits so that queries of the form `Is x \in S?' can be answered. The goal is to use a small table and yet answer queries using few bitprobes. This problem was considered recently by Buhrman, Miltersen, Radhakrishnan and Venkatesh, where lower and upper bounds were shown for this problem in the classical deterministic and ...

Statistical query (SQ) algorithms are algorithms that have access to an {\em SQ oracle} for the input distribution $D$ instead of i.i.d.~ samples from $D$. Given a query function $\phi:X \rightarrow [-1,1]$, the oracle returns an estimate of ${\bf E}_{ x\sim D}[\phi(x)]$ within some tolerance $\tau_\phi$ that roughly corresponds to the number of samples. In this work we demonstrate that the complexity of solving general problems over distributions using SQ algorithms can be...

We discuss the quantum search algorithm using complex queries that has recently been published by Grover (quant-ph/9706005). We recall the algorithm adding some details showing which complex query has to be evaluated. Based on this version of the algorithm we discuss its complexity.

Recent developments in the mathematical foundations of quantum mechanics have brought the theory closer to that of classical probability and statistics. On the other hand, the unique character of quantum physics sets many of the questions addressed apart from those met classically in stochastics. Furthermore, concurrent advances in experimental techniques and in the theory of quantum computation have led to a strong interest in questions of quantum information, in particular ...

Consider a quantum computer in combination with a binary oracle of domain size N. It is shown how N/2+sqrt(N) calls to the oracle are sufficient to guess the whole content of the oracle (being an N bit string) with probability greater than 95%. This contrasts the power of classical computers which would require N calls to achieve the same task. From this result it follows that any function with the N bits of the oracle as input can be calculated using N/2+sqrt(N) queries if w...

Here we study the comparative power of classical and quantum learners for generative modelling within the Probably Approximately Correct (PAC) framework. More specifically we consider the following task: Given samples from some unknown discrete probability distribution, output with high probability an efficient algorithm for generating new samples from a good approximation of the original distribution. Our primary result is the explicit construction of a class of discrete pro...

$ \newcommand{\eps}{\varepsilon} $In learning theory, the VC dimension of a concept class $C$ is the most common way to measure its "richness." In the PAC model $$ \Theta\Big(\frac{d}{\eps} + \frac{\log(1/\delta)}{\eps}\Big) $$ examples are necessary and sufficient for a learner to output, with probability $1-\delta$, a hypothesis $h$ that is $\eps$-close to the target concept $c$. In the related agnostic model, where the samples need not come from a $c\in C$, we know that $$...

Let X = (x_0,...,x_{n-1})$ be a sequence of n numbers. For \epsilon > 0, we say that x_i is an \epsilon-approximate median if the number of elements strictly less than x_i, and the number of elements strictly greater than x_i are each less than (1+\epsilon)n/2. We consider the quantum query complexity of computing an \epsilon-approximate median, given the sequence X as an oracle. We prove a lower bound of \Omega(\min{{1/\epsilon},n}) queries for any quantum algorithm that com...

We investigate the boundary between classical and quantum computational power. This work consists of two parts. First we develop new classical simulation algorithms that are centered on sampling methods. Using these techniques we generate new classes of classically simulatable quantum circuits where standard techniques relying on the exact computation of measurement probabilities fail to provide efficient simulations. For example, we show how various concatenations of matchga...