Lower Bounds on Quantum Query Complexity for Read-Once Decision Trees with Parity Nodes

Fukuhara, H. and Takimoto, E.

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. Note that some of equations in this abstract may have been omitted or may be displayed incorrectly.

Cite as: Fukuhara, H. and Takimoto, E. (2009). Lower Bounds on Quantum Query Complexity for Read-Once Decision Trees with Parity Nodes. In Proc. Fifteenth Computing: The Australasian Theory Symposium (CATS 2009), Wellington, New Zealand. CRPIT, 94. Downey, R. and Manyem, P., Eds. ACS. 89-98.

(from crpit.com) (local if available)