In this paper we study the separation between the deterministic (classical) query complexity (D) and the exact quantum query complexity (QE) of several Boolean function classes using the parity decision tree method. We first define the Query Friendly (QF) functions on n variables as the ones with minimum deterministic query complexity (D(f)). We observe that for each n, there exists a non-separable class of QF functions such that D(f)=QE(f). Further, we show that for some values of n, all the QF functions are non-separable. Then we present QF functions for certain other values of n where separation can be demonstrated, in particular, QE(f)=D(f)−1. In a related effort, we also study the Maiorana McFarland (M-M) type Bent functions. We show that while for any M-M Bent function f on n variables D(f)=n, separation can be achieved as 2n≤QE(f)≤⌈43n⌉. Our results highlight how different classes of Boolean functions can be analyzed for classical-quantum separation exploiting the parity decision tree method.
In Exact Quantum Query model, almost all of the Boolean functions for which non-trivial query algorithms exist are symmetric in nature. The most well known techniques in this domain exploit parity decision trees, in which the parity of two bits can be obtained by a single query. Thus, exact quantum query algorithms outperforming parity decision trees are rare. In this paper we first obtain optimal exact quantum query algorithms (Qalgo(f)) for a direct sum based class of Ω(22n) non-symmetric functions. We construct these algorithms by analyzing the algebraic normal form together with a novel untangling strategy. Next we obtain the generalized parity decision tree complexity (D⊕(f)) analysing the Walsh Spectrum. Finally, we show that query complexity of Qalgo is ⌈43n⌉ whereas D⊕(f) varies between n−1 and ⌈43n⌉+1 for different classes, underlining linear separation between the two measures in many cases. To the best of our knowledge, this is the first family of algorithms beyond generalized parity (and thus parity) for a large class of non-symmetric functions. We also implement these techniques for a larger (doubly exponential in 4n) class of Maiorana-McFarland type functions, but could only obtain partial results using similar algorithmic techniques.
We introduce a complexity measure for decision trees called the soft rank, which measures how well-balanced a given tree is. The soft rank is a somehow relaxed variant of the rank. Among all decision trees of depth d, the complete binary decision tree (the most balanced tree) has maximum soft rank d, the decision list (the most unbalanced tree) has minimum soft rank √d, and any other trees have soft rank between √d and d. We show that, for any decision tree T in some class G of decision trees which includes all read-once decision trees, the soft rank of T is a lower bound on the quantum query complexity of the Boolean function that T represents. This implies that for any Boolean function f that is represented by a decision tree in G, the deterministic query complexity of f is only quadratically larger than the quantum query complexity of f.