On learning linear functions from subset and its applications in quantum computing
share
Let F_q be the finite field of size q and let ℓ: F_q^n →F_q be a linear function. We introduce the Learning From Subset problem LFS(q,n,d) of learning ℓ, given samples u ∈F_q^n from a special distribution depending on ℓ: the probability of sampling u is a function of ℓ(u) and is non zero for at most d values of ℓ(u). We provide a randomized algorithm for LFS(q,n,d) with sample complexity (n+d)^O(d) and running time polynomial in q and (n+d)^O(d). Our algorithm generalizes and improves upon previous results 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 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: Z_q^n →{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 CD07, Friedl for HMS(q,n,r) with these parameters require exponential time.
READ FULL TEXT