Lower bounds on quantum query complexity for read-once decision trees with parity nodes

We introduce a complexity measure for decision trees called the soft rank, which measures how wellbalanced 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.