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,1ϵlog1δ)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$poly(n,\frac{1}{\epsilon }\log \frac{1}{\delta })$$\end{document} time to output the vectors w with Walsh coefficients S(w)≥ϵ\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$S(w)\ge \epsilon $$\end{document} with probability at least 1-δ\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$1-\delta $$\end{document}. However, in this paper, a quantum algorithm for this problem is given with query complexity O(log1δϵ4)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O(\frac{\log \frac{1}{\delta }}{\epsilon ^4})$$\end{document}, 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(2mlog1δϵ4)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O(2^m\frac{\log \frac{1}{\delta }}{\epsilon ^4})$$\end{document}.