论文标题
Goldreich-Levin学习问题的量子算法
Quantum algorithms for the Goldreich-Levin learning problem
论文作者
论文摘要
Goldreich-Levin算法最初是出于加密目的而提出的，然后应用于学习。该算法是要找到一些$ n $ darable boolean函数的较大的沃尔什系数。粗略地说，需要一个$ poly（n，\ frac {1}ε\ log \ frac {1}δ）$时间才能使用walsh系数$ s（w）\geqε$输出vectors $ w $，概率至少为$ 1-δ$。但是，在本文中，使用查询复杂性$ o（\ frac {\ log \ frac {1}δ} {ε^4}）$给出了此问题的量子算法，该算法独立于$ n $。此外，量子算法被概括为申请$ n $ a $ $ m $ umput boolean函数$ f $，带有查询复杂性$ o（2^m \ frac {\ log \ frac \ frac {1}δ}Δ} {ε^4}）$。
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}ε\log\frac{1}δ)$ time to output the vectors $w$ with Walsh coefficients $S(w)\geqε$ with probability at least $1-δ$. However, in this paper, a quantum algorithm for this problem is given with query complexity $O(\frac{\log\frac{1}δ}{ε^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}δ}{ε^4})$.
