Here we revisit the quantum algorithms for obtaining Forrelation [Aaronson et al, 2015] values to evaluate some of the well-known cryptographically significant spectra of Boolean functions, namely the Walsh spectrum, the cross-correlation spectrum and the autocorrelation spectrum. We introduce the existing 2-fold Forrelation formulation with bent duality based promise problems as desirable instantiations. Next we concentrate on the $3$-fold version through two approaches. First, we judiciously set-up some of the functions in $3$-fold Forrelation, so that given an oracle access, one can sample from the Walsh Spectrum of $f$. Using this, we obtain improved results than what we obtain from the Deutsch-Jozsa algorithm, and in turn it has implications in resiliency checking. Furthermore, we use similar idea to obtain a technique in estimating the cross-correlation (and thus autocorrelation) value at any point, improving upon the existing algorithms. Finally, we tweak the quantum algorithm with superposition of linear functions to obtain a cross-correlation sampling technique. To the best of our knowledge, this is the first cross-correlation sampling algorithm with constant query complexity. This also provides a strategy to check if two functions are uncorrelated of degree $m$. We further modify this using Dicke states so that the time complexity reduces, particularly for constant values of $m$.
翻译:我们在这里重新审视获取 Forresulation [Aaronson 等人, 2015] 值的量子算法, 以评价一些已知的、 具有加密意义的布林函数光谱, 即 Walsh 频谱、 交叉关系频谱 和 自动关系频谱。 我们在此介绍现有的二倍关系配方, 以弯曲的双性承诺问题为理想的即时推移。 接下来我们通过两种方法, 集中关注 3 美元 的版本。 首先, 我们明智地设置了 3 美元 倍关系中的一些函数 。 因此, 有了 鼠标访问, 就可以从 Walsh Spectrum 中提取一些已知的、 具有地谱意义的、 Walshol- Jozsa 函数的样本。 我们用这个比分法取得了更好的结果, 反过来, 我们用一个类似的想法来获得一种技术来估计 交叉关系( 自动关系), 任何时间关系中的 美元 价值, 改进现有的算法。 最后, 我们用 量算算算法的 和直线函数的超级定位,, 也提供这种不断的校算法 的 。