From the sum-of-squares representation of a Boolean function to an optimal exact quantum query algorithm

Abstract

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 multilinear polynomials, in this paper a primary algorithm framework is proposed with three basic steps: The first basic step is to find sum-of-squares representations of the Boolean function and its negation function; the second basic step is to construct a state which is assumed to be the final state of an optimal exact quantum query algorithm; the third basic step is to find each unitary operator in the undetermined algorithm. However, there still exist some intractable problems such that the algorithm framework may not be feasible in some cases, but it can be used to investigate the quantum query model with low complexity, such as Deutsch’s problem, a five-bit symmetric Boolean function and the characterization of Boolean functions with exact quantum 2-query complexity.