Paper Info
Title
Quantum algorithms for learning the algebraic normal form of quadratic Boolean functions
Abstract
Quantum algorithms for the analysis of Boolean functions have received a lot of attention over the last few years. The algebraic normal form (ANF) of a linear Boolean function can be recovered by using the Bernstein-Vazirani (BV) algorithm. No research has been carried out on quantum algorithms for learning the ANF of general Boolean functions. In this paper, quantum algorithms for learning the ANF of quadratic Boolean functions are studied. We draw a conclusion about the influences of variables on quadratic functions, so that the BV algorithm can be run on them. We study the functions obtained by inversion and zero-setting of some variables in the quadratic function and show the construction of their quantum oracle. We introduce the concept of "club" to group variables that appear in quadratic terms and study the properties of clubs. Furthermore, we propose a bunch of algorithms for learning the full ANF of quadratic Boolean functions. The most efficient algorithm, among those we propose, provides anO(n) speedup over the classical one, and the number of queries is independent of the degenerate variables.
Year
DOI
Venue
2020
10.1007/s11128-020-02778-3
QUANTUM INFORMATION PROCESSING
Keywords
DocType
Volume
Bernstein-Vazirani algorithm,Boolean function,Quantum cryptanalysis,Quantum computation
Journal
19
Issue
ISSN
Citations 
8
1570-0755
0
PageRank 
References 
Authors
0.34
0
4
Name
Order
Citations
PageRank
Xuexuan Hao100.68
Fengrong Zhang24111.72
Shixiong Xia310213.28
Yong Zhou46112.72