Published in Quantum Information Processing
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 ...
In this paper we address the question "How many properties of Boolean functions can be defined by means of linear equations?" It follows from a result by Sparks that there are countably many such linearly definable classes of Boolean functions. In this paper, we refine this result by completely describing these classes. This work is tightly related...
Published in Mathematical Notes
Abstract For the monotone symmetric threshold Boolean functions \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$ f^n_2(\widetilde x\mspace{2mu})=\bigvee_{1\le i
Published in Doklady Mathematics
AbstractWe introduce the concept of the uniform width of a contact circuit. For each Boolean function, we find the minimal possible value of the uniform width of a contact circuit implementing this function. We prove constructively that this value does not exceed 3. We also establish that, for almost all Boolean functions on n variables, it equals ...
Published in Quantum Information Processing
In quantum computation, designing an optimal exact quantum query algorithm (i.e., a quantum decision tree algorithm) for any small input Boolean function is a fundamental and abstract problem. As we are aware, there is not a general method for this problem. Due to the fact that every Boolean function can be represented by a sum-of-squares of some m...
Published in Journal of Applied and Industrial Mathematics
Abstract The well-known lower bound for the maximum number of prime implicants of a Boolean function (the length of the reduced DNF) differs by \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-...
