Quantum algorithms for the Goldreich-Levin learning problem

Abstract

The Goldreich-Levin algorithm was originally proposed for a cryptographic purpose and then applied to learning. The algorithm is to find some larger Walsh coefficients of an $n$ variable Boolean function. Roughly speaking, it takes a $poly(n,\frac{1}{\hat{I}}\mu \log \frac{1}{\hat{I}}´)$ time to output the vectors $w$ with Walsh coefficients $S(w)\ge \hat{I}\mu$ with probability at least $1-\hat{I}´$. However, in this paper, a quantum algorithm for this problem is given with query complexity $O(\frac{\log \frac{1}{\hat{I}}´}{\hat{I}{\mu }^4})$, which is independent of $n$. Furthermore, the quantum algorithm is generalized to apply for an $n$ variable $m$ output Boolean function $F$ with query complexity $O(2^m\frac{\log \frac{1}{\hat{I}}´}{\hat{I}{\mu }^4})$.

9 pages