Counting Zeros of (Boolean) Polynomials

One of the features included in the Quantum Dictionary construct introduced in our recently released paper is finding the number of times a value appears in the dictionary. We use the zero sum subset problem as an example. We also show how to efficiently (in terms of the number of CNOT gates) encode quadratic boolean polynomials, used to solve QUBO problems. Even though more CNOT gates are needed, the same is true about all boolean polynomials (polynomials of multiple variables with the degree of every variable at most 1). We can then count the number of zeros of such polynomials using a Quantum Dictionary.

Why is this important? As the abstract of this paper states, "The investigation of properties of Boolean polynomials is an important topic of discrete mathematics and combinatorial analysis. Theoretical results in this field have wide practical applications. For example, a number of popular public-key cryptosystems are based on Reed-Muller codes, and the representation of these codes, as well as encryption and decryption algorithms are based on Boolean polynomials. The spectral properties of such codes are determined by the number of zeros of Boolean polynomials and are analyzed using the randomization lemma. Since the problem of determining the number of zeros Z_g of the Boolean polynomial g(x) is NP-hard, the algorithms taking into account the "combinatorial structure of the polynomial" (even though they are search algorithms) are of practical interest."

It is also worth noting that any polynomial on integers, not necessarily boolean, can be converted to a boolean polynomial by replacing each variable to its binary expansion, so the digits representing a variable become boolean variables. This way we can minimize, find roots, or count roots using the Quantum Dictionary pattern.

It is also interesting to note that the state of a quantum system itself can be thought of as a boolean polynomial over the field of complex numbers: final states are the monomials of the polynomial, translated to binary strings representing the degrees of all variables, and the amplitudes are the coefficients of those monomials.

Bringing the machinery of Algebraic Geometry into Quantum Computing will probably accelerate going forward, e.g. I saw some papers that reference applications of Grobner bases. There is also a connection to Geometric Algebra which I mentioned before. Interesting times ahead.