Algorithms for determining predicates on polynomial degrees of Boolean functions

This work deals with determining certain properties of polynomial degree of Boolean functions. These properties are connected with complexity of quantum algorithms. Thus the work has a potential of application in quantum computing – a relatively new field with great potential of application, since many problems can be solved much more efficiently in this model of computation.
Two algorithms are given for solving a problem and its generalization proposed in this paper. A full classification of non-equivalent Boolean functions of 5 variables based on polynomial degree is given. Such a classification hasn’t been made in literature before.

Scientific field





Reinis Cirpons

Share this Post