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.
This paper explores a fine-grained version of the Watrous conjecture, including the randomized and quantum algorithms with success probabilities arbitrarily close to
1/2. Our contributions include the following: i) An analysis of the optimal success probability of quantum and randomized query algorithms of two fundamental partial symmetric Boolean functions given a fixed number of queries. We prove that for any quantum algorithm computing these two functions using
T queries, there exist randomized algorithms using
poly(T) queries that achieve the same success probability as the quantum algorithm, even if the success probability is arbitrarily close to 1/2. ii) We establish that for any total symmetric Boolean function
f, if a quantum algorithm uses
T queries to compute
f with success probability
1/2+β, then there exists a randomized algorithm using
O(T2) queries to compute
f with success probability
1/2+Ω(δβ2) on a
1−δ fraction of inputs, where
β,δ can be arbitrarily small positive values. As a corollary, we prove a randomized version of Aaronson-Ambainis Conjecture for total symmetric Boolean functions in the regime where the success probability of algorithms can be arbitrarily close to 1/2. iii) We present polynomial equivalences for several fundamental complexity measures of partial symmetric Boolean functions. Specifically, we first prove that for certain partial symmetric Boolean functions, quantum query complexity is at most quadratic in approximate degree for any error arbitrarily close to 1/2. Next, we show exact quantum query complexity is at most quadratic in degree. Additionally, we give the tight bounds of several complexity measures, indicating their polynomial equivalence.