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

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.