# Quantum algorithms for learning Walsh spectra of multi-output Boolean functions

Research paper by Jingyi Cui, Jiansheng Guo, Linhong Xu, Mingming Li

Indexed on: 03 May '19Published on: 02 May '19Published in: Quantum Information Processing

#### Abstract

In classical cryptography, many cryptographic primitives could be treated as multi-output Boolean functions. The analysis of such functions is of great interest for cryptologists owing to their wide ranges of applications. Since each multi-output Boolean function can be uniquely determined by its Walsh transform, the Walsh spectra could reveal the properties of multi-output Boolean functions. In this paper, several quantum algorithms for learning Walsh spectra of multi-output Boolean functions are proposed. Firstly, with the usage of the amplitude estimation algorithm based on the Monte Carlo method, we present a quantum algorithm that allows one to estimate the Walsh coefficient of a multi-output Boolean function at a specified point with an additive error $$\epsilon$$ and probability at least $$1-\delta$$. The corresponding query complexity is $${\mathrm O}( {{\epsilon }^{-1}}\log {{\delta }^{-1}} )$$. There is an almost quadratic speedup over the classical algorithm. Secondly, we propose a generalized phase kick-back technique for multi-output Boolean functions to encode multiple Walsh coefficients on the amplitudes of states. Based on this generalized technique, a quantum Goldreich–Levin algorithm for arbitrary multi-output Boolean function $$F:{{\{ 0,1 \}}^{n}}\rightarrow {{\{ 0,1 \}}^{m}}$$ where $$m,n\in \mathbb {Z}$$ is proposed to find those Walsh coefficients satisfying the threshold boundary condition $$\tau$$ with probability at least $$1-\delta$$. The whole query complexity is $${\mathrm O}\left( \frac{{{2}^{m+5+n/2}}}{{{\tau }^{3}}}\log \frac{{{2}^{m+5}}n}{\delta {{\tau }^{2}}} \right)$$. Finally, by using the same idea of the swap-test circuit, the query complexity of the modified quantum Goldreich–Levin algorithm could be lowered to $${\mathrm O}\left( \frac{{{2}^{m+9}}n\pi }{{{\tau }^{4}}}\log \frac{{{2}^{m+3}}n}{\delta {{\tau }^{2}}} \right)$$ achieving a further speedup when $$\tau$$ is no less than $${\mathrm O}( {{2}^{-n/2+6}}n)$$. Those two quantum Goldreich–Levin algorithms have their own advantages in implementation and query complexity.