On learning linear functions from subset and its applications in quantum computing

Let ${\mathbb{F}}_q$ be the finite field of size $q$ and let $\ell: $\mathbb{F}$_q^n \to $\mathbb{F}$_q$ be a linear function. We introduce the {\em Learning From Subset} problem LFS$(q,n,d)$ of learning $\mathrm{\ell }$, given samples $u \in $\mathbb{F}$_q^n$fromaspecialdistributiondependingon$\ell$: the probability of sampling $u$ is a function of $\mathrm{\ell }(u)$ and is non zero for at most $d$ values of $\mathrm{\ell }(u)$. We provide a randomized algorithm for LFS$(q,n,d)$ with sample complexity $(n+d{)}^{O(d)}$ and running time polynomial in $\log q$ and $(n+d{)}^{O(d)}$. Our algorithm generalizes and improves upon previous results \cite{Friedl, Ivanyos} that had provided algorithms for LFS$(q,n,q-1)$ with running time $(n+q{)}^{O(q)}$. We further present applications of our result to the {\em Hidden Multiple Shift} problem HMS$(q,n,r)$ in quantum computation where the goal is to determine the hidden shift $s$ given oracle access to $r$ shifted copies of an injective function $f:{\mathbb{Z}}_q^n\to \{0,1{\}}^l$, that is we can make queries of the form $f_s(x,h)=f(x-hs)$ where $h$ can assume $r$ possible values. We reduce HMS$(q,n,r)$ to LFS$(q,n,q-r+1)$ to obtain a polynomial time algorithm for HMS$(q,n,r)$ when $q=n^{O(1)}$ is prime and $q-r=O(1)$. The best known algorithms \cite{CD07, Friedl} for HMS$(q,n,r)$ with these parameters require exponential time.