Affordable Access

Access to the full text

Quantum algorithms for learning the algebraic normal form of quadratic Boolean functions

Authors
  • Hao, Xuexuan1, 2, 1
  • Zhang, Fengrong1, 2, 1
  • Xia, Shixiong1, 1
  • Zhou, Yong1, 1
  • 1 China University of Mining and Technology, Xuzhou, 221116, People’s Republic of China , Xuzhou (China)
  • 2 Guilin University of Electronic Technology, Guilin, 541004, People’s Republic of China , Guilin (China)
Type
Published Article
Journal
Quantum Information Processing
Publisher
Springer-Verlag
Publication Date
Jul 30, 2020
Volume
19
Issue
8
Identifiers
DOI: 10.1007/s11128-020-02778-3
Source
Springer Nature
Keywords
License
Yellow

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 an O(n) speedup over the classical one, and the number of queries is independent of the degenerate variables.

Report this publication

Statistics

Seen <100 times