Generalisations of the bent property of a Boolean function are presented, by proposing spectral analysis of the Boolean function with respect to a well-chosen set of local unitary transforms. Quadratic Boolean functions are related to simple graphs and it is shown that the orbit generated by some graph transforms can be found within the spectra of certain unitary transform sets. The flat spectra of a quadratic Boolean function with respect to those transforms are related to modified versions of its associated adjacency matrix. The flat spectra of concrete recursive structures are found using this method. We derive a spectral interpretation of the interlace polynomials (in one or two variables) of a graph and we relate to one of them a quantum measure of entanglement of the associated quantum state. We characterise the values of the spectra of a quadratic Boolean function. We give a formula for the weight hierarchy for a binary linear code in terms of a modified interlace polynomial. We derive as well a spectral interpretation of the pivot operation on a graph and generalise this operation to hypergraphs. We enumerate the number of inequivalent pivot orbits for small numbers of vertices. We also construct a family of Boolean functions of degree higher than two with a large number of flat spectra with respect to the {I,H}n set of transforms, and compute a lower bound on this number. We show how to change the degree of a Boolean function via pivot operation. Finally, we give concrete formulae for the spectra of a wide range of vectors with respect to well-chosen transforms sets.Generalisations of the bent property of a Boolean function are presented, by proposing spectral analysis of the Boolean function with respect to a well-chosen set of local unitary transforms. Quadratic Boolean functions are related to simple graphs and it is shown that the orbit generated by some graph transforms can be found within the spectra of certain unitary transform sets. The flat spectra of a quadratic Boolean function with respect to those transforms are related to modified versions of its associated adjacency matrix. The flat spectra of concrete recursive structures are found using this method. We derive a spectral interpretation of the interlace polynomials (in one or two variables) of a graph and we relate to one of them a quantum measure of entanglement of the associated quantum state. We characterise the values of the spectra of a quadratic Boolean function. We give a formula for the weight hierarchy for a binary linear code in terms of a modified interlace polynomial. We derive as well a spectral interpretation of the pivot operation on a graph and generalise this operation to hypergraphs. We enumerate the number of inequivalent pivot orbits for small numbers of vertices. We also construct a family of Boolean functions of degree higher than two with a large number of flat spectra with respect to the {I,H}n set of transforms, and compute a lower bound on this number. We show how to change the degree of a Boolean function via pivot operation. Finally, we give concrete formulae for the spectra of a wide range of vectors with respect to well-chosen transforms sets.

Jan 1, 20055 citations

Polynomial Representation of General Partial Boolean Functions with a Single Quantum Query

Guoliang Xu, Daowen Qiu

Early in 1992, Deutsch-Jozsa algorithm computed a symmetric partial Boolean function with a single quantum query, and thus achieved the best separation between classical deterministic and exact quantum query complexity. Recently, it was clarified that all symmetric partial Boolean functions with a single quantum query can be computed exactly by Deutsch-Jozsa algorithm. For the general partial Boolean functions with a single quantum query, the latest characterizations is complex and not very satisfactory. Based on this, this paper proves and discovers three new results: (1) Under a new equivalence, each partial Boolean function with a single quantum query can be transformed to a simple partial Boolean function whose polynomial degree is just one; (2) For partial Boolean functions up to four bits, there are only 10 non-trivial partial Boolean functions with a single quantum query; (3) For each quantum 1-query algorithm with undefined measurement, there exists a constructive method for finding out all partial Boolean functions that can be computed exactly by the algorithm.Early in 1992, Deutsch-Jozsa algorithm computed a symmetric partial Boolean function with a single quantum query, and thus achieved the best separation between classical deterministic and exact quantum query complexity. Recently, it was clarified that all symmetric partial Boolean functions with a single quantum query can be computed exactly by Deutsch-Jozsa algorithm. For the general partial Boolean functions with a single quantum query, the latest characterizations is complex and not very satisfactory. Based on this, this paper proves and discovers three new results: (1) Under a new equivalence, each partial Boolean function with a single quantum query can be transformed to a simple partial Boolean function whose polynomial degree is just one; (2) For partial Boolean functions up to four bits, there are only 10 non-trivial partial Boolean functions with a single quantum query; (3) For each quantum 1-query algorithm with undefined measurement, there exists a constructive method for finding out all partial Boolean functions that can be computed exactly by the algorithm.

arXiv:2112.12416International Journal of Foundations of Computer ScienceJan 30, 20260 citations

A quantum algorithm for approximating the influences of Boolean functions and its applications

Hongwei Li, Li Yang

arXiv:1409.1416Quantum Information ProcessingMar 4, 201531 citations

Quantum Networks and Quantum Algorithms

Vlatko Vedral

Springer eBooksJan 1, 19990 citations

HHL Algorithm for Tensor-Decomposable Matrices

Cezary Pilaszewicz, Marian Margraf

We use the HHL algorithm to retrieve a quantum state holding the algebraic normal form (ANF) of a Boolean function. Unlike the standard HHL applications, we do not describe the cipher as an exponentially big system of equations. Rather, we perform a set of small matrix inversions which correspond to the Boolean Möbius transform. This creates a superposition holding information about the ANF in the form |Af⟩=1C∑I=02n−1cI|I⟩, where cI is the coefficient of the ANF and C is a scaling factor. The procedure has a time complexity of O~(n) for a Boolean function with n-bit input. We also propose two approaches by which some information about the ANF can be extracted from such a state. Next, we use a similar approach, the Dual Boolean Möbius transform, to compute the preimage under the algebraic transition matrix. We show that such a matrix is well-suited for the HHL algorithm when the attacker gets oracle access in the Q2 setting to the Boolean function.We use the HHL algorithm to retrieve a quantum state holding the algebraic normal form (ANF) of a Boolean function. Unlike the standard HHL applications, we do not describe the cipher as an exponentially big system of equations. Rather, we perform a set of small matrix inversions which correspond to the Boolean Möbius transform. This creates a superposition holding information about the ANF in the form |Af⟩=1C∑I=02n−1cI|I⟩, where cI is the coefficient of the ANF and C is a scaling factor. The procedure has a time complexity of O~(n) for a Boolean function with n-bit input. We also propose two approaches by which some information about the ANF can be extracted from such a state. Next, we use a similar approach, the Dual Boolean Möbius transform, to compute the preimage under the algebraic transition matrix. We show that such a matrix is well-suited for the HHL algorithm when the attacker gets oracle access in the Q2 setting to the Boolean function.

Quantum ReportsAug 19, 20251 citation

Quantum Algorithms Related to

\textit{HN}

-Transforms of Boolean Functions