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.
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.
In this paper, we introduce the hybrid query complexity, denoted as Q(f;q), which is the minimal query number needed to compute f, when a classical decision tree is allowed to call q′-query quantum subroutines for any q′≤q. We present the following results: ∙ There exists a total Boolean function f such that Q(f;1)=O(R(f)4/5). ∙Q(f;q)=Ω(bs(f)/q+bs(f)) for any Boolean function f; the lower bound is tight when f is the OR function. ∙Q(g∘XORClogn;1)=Ω(n) for some sufficiently large constant C, where g:=BOOLSIMONn is a variant of Simon's problem. Note that Q(g∘XORClogn)=O(polylogn). Therefore an exponential separation is established. Furthermore, this open the road to prove the conjecture ∀k,Q(g∘XORClogk+1n;logkn)=Ω(n), which would imply the oracle separation HP(QSIZE(nα))O⊊BQPO for any α, where HP(QSIZE(nα)) is a complexity class that contains BQTIME(nα)BPP and BPPBQTIME(nα) in any relativized world.