# 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 '19**Published on: **02 May '19**Published in: **Quantum Information Processing**

Join Sparrho today to stay on top of science

Discover, organise and share research that matters to you

Join Sparrho today to stay on top of science

Discover, organise and share research that matters to you

Join for free

#### 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.