Linear approximation of a vectorial Boolean function using quantum computing. (30th December 2020)

• Record Type: Journal Article
• Authors: Malviya, A. K.; Tiwari, N.
• Is Part Of: Europhysics letters. Volume 132:Number 4(2020)
• Publication Date: 2020-12-30
• Subjects: 03.67.Lx -- 03.67.-a -- 03.65.-w; Physics -- Periodicals; Electronic journals; 530.05
• DOI: 10.1209/0295-5075/132/40001
• Languages: English
• ISSNs: 0295-5075

Abstract

Abstract: A vectorial Boolean function takes multi-bit input and produces a multi-bit output. According to the input parameters, a vectorial Boolean function can be linear or non-linear. Non-linear vectorial Boolean functions have high importance in information theory and cryptology. Finding a linear approximation of a non-linear vectorial Boolean function is of high significance in these areas. Assuming that the quantum access to a vectorial Boolean function is provided, we present a quantum computing approach which can find the best linear approximation of the non-linear vectorial Boolean functions. The presented quantum approach is exponentially better than any known solution on the factors of querying the function, quantum circuit depth and memory requirements.