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.
We give and prove an optimal exact quantum query algorithm with complexity
k+1 for computing the promise problem (i.e., symmetric and partial Boolean function)
DJnk defined as:
DJnk(x)=1 for
∣x∣=n/2,
DJnk(x)=0 for
∣x∣ in the set
{0,1,…,k,n−k,n−k+1,…,n}, and it is undefined for the rest cases, where
n is even,
∣x∣ is the Hamming weight of
x. The case of
k=0 is the well-known Deutsch-Jozsa problem. We outline all symmetric (and partial) Boolean functions with degrees 1 and 2, and prove their exact quantum query complexity. Then we prove that any symmetrical (and partial) Boolean function
f has exact quantum 1-query complexity if and only if
f can be computed by the Deutsch-Jozsa algorithm. We also discover the optimal exact quantum 2-query complexity for distinguishing between inputs of Hamming weight
{⌊n/2⌋,⌈n/2⌉} and Hamming weight in the set
{0,n} for all odd
n. In addition, a method is provided to determine the degree of any symmetrical (and partial) Boolean function.
We investigate efficient algorithms for computing Boolean function properties relevant to query complexity. Such properties include, for example, deterministic, randomized, and quantum query complexities; block sensitivity; certificate complexity; and degree as a real polynomial. The algorithms compute the properties, given an n-variable function's truth table (of size N=2 n ) as input. Our main results are the following: O(N log 2 3 log N) algorithms for many common properties, an O(N log 2 5 log N) algorithm for block sensitivity, an O(N) algorithm for testing "quasi symmetry," a notion of a "tree decomposition" of a Boolean function, proof that the decomposition is unique, and an O(N log 2 3 log N) algorithm for finding it, a subexponential-time approximation algorithm for space-bounded quantum query complexity. To develop this algorithm, we give a new way to search systematically through unitary matrices using finite-precision arithmetic. The algorithms discussed have been implemented in a linkable library.