Lower bounds on quantum query complexity for decision trees

Yaoyun Shi

Hideaki Fukuhara, Eiji Takimoto

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.

Raghav Kulkarni, Miklós Sántha

Let \(\mathcal{M}\) be a bridgeless matroid on ground set {1,...,n} and \(f_{\mathcal{M}}: \{0,1\}^n \to \{0, 1\}\) be the indicator function of its independent sets. A folklore fact is that \(f_\mathcal{M}\) is evasive, i.e., \(D(f_\mathcal{M}) = n\) where D(f) denotes the deterministic decision tree complexity of f. Here we prove query complexity lower bounds for \(f_\mathcal{M}\) in three stronger query models: (a) \(D_\oplus(f_\mathcal{M}) = \Omega(n),\) where D ⊕ (f) denotes the parity decision tree complexity of f; (b) \(R(f_\mathcal{M}) = \Omega(n / \log n),\) where R(f) denotes the bounded error randomized decision tree complexity of f; and (c) \(Q(f_\mathcal{M}) = \Omega(\sqrt n),\) where Q(f) denotes the bounded error quantum query complexity of f.

Aija Bērziņa, Andrej Dubrovsky, Rūsiņš Freivalds +2 more

Christoph Dürr, Mark Heiligman, Peter Høyer +1 more

Nikos Leonardos

Abstract: In this work we prove lower bounds on the randomized decision tree complexity of several read-once threshold functions. A read-once threshold formula can be defined by a rooted tree, in which every internal node is labeled by a threshold function (with output 1 only when at least out of input bits are 1) and each leaf by a variable. We consider the randomized decision tree complexity of such functions, when the underlying tree is a uniform and balanced tree with all its internal nodes labeled by the same threshold function. We prove lower bounds of the form , where is the depth of the tree, for certain values of and. The value of each parameter depends on the solution of a linear program, which is provided by computational methods. Keywords: Decision trees, query complexity, randomized computation, lower bounds, read-once functions. Title: Computer-assisted proof of lower bounds on the randomized query complexity of certain read-once threshold functions Author: Nikos Leonardos International Journal of Recent Research in Mathematics Computer Science and Information Technology ISSN 2350-1022 Vol. 9, Issue 2, October 2022 - March 2023 Page No: 11-17 Paper Publications Website: www.paperpublications.org Published Date: 10-December-2022 DOI: https://doi.org/10.5281/zenodo.7421269 Paper Download Link (Source) https://www.paperpublications.org/upload/book/Computer-assisted%20proof%20of%20lower-10122022-1.pdf