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

Abstract

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 $\ell$, given samples $u\in {\mathbb{F}}_q^n$ from a special distribution depending on $\ell$: the probability of sampling $u$ is a function of $\ell (u)$ and is non zero for at most $d$ values of $\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.

arXiv comment20 pages, short version to appear in proceedings of ESA 2018

References in corpus (1)

• Quantum algorithms for abelian difference sets and applications to dihedral hidden subgroups