Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

IEICE Technical Report; IEICE Tech. Rep.

Lower bounds on quantum query complexity for decision trees

Hideaki Fukuhara, Eiji Takimoto

Published Oct 3, 2008• 0 citations
OpenAlex

Related papers

Entropy lower bounds for quantum decision tree complexity

Yaoyun Shi

Information Processing Letters•Jan 1, 2002•11 citations

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

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.

Computing: The Australasian Theory Symposium•Jan 1, 2009•0 citations

Quantum Query Complexity for Some Graph Problems

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

Lecture notes in computer science•Jan 1, 2004•44 citations

Query complexity of matroids.

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.

•Jan 1, 2012•4 citations

Quantum Query Complexity of Some Graph Problems

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

Lecture notes in computer science•Jan 1, 2004•77 citations

Decision Trees and Branching Programs

Thomas Watson

This chapter focuses on query complexity, which measures the minimum number of input bits that need to be read to solve a problem, in other words, the minimum depth of any correct decision tree (or branching program). Techniques for upper and lower bounds for deterministic and randomized query complexities are covered. The close relationships between query complexity and other measures known as certificate complexity and sensitivity are also covered. The chapter concludes with techniques for proving lower bounds on the size (as opposed to depth) of decision trees and branching programs.

Cambridge University Press eBooks•Oct 9, 2026•0 citations
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.
Let M\mathcal{M}M be a bridgeless matroid on ground set {1,...,n} and fM:{0,1}n→{0,1}f_{\mathcal{M}}: \{0,1\}^n \to \{0, 1\}fM​:{0,1}n→{0,1} be the indicator function of its independent sets. A folklore fact is that fMf_\mathcal{M}fM​ is evasive, i.e., D(fM)=nD(f_\mathcal{M}) = nD(fM​)=n where D(f) denotes the deterministic decision tree complexity of f. Here we prove query complexity lower bounds for fMf_\mathcal{M}fM​ in three stronger query models: (a) D⊕(fM)=Ω(n),D_\oplus(f_\mathcal{M}) = \Omega(n),D⊕​(fM​)=Ω(n), where D ⊕ (f) denotes the parity decision tree complexity of f; (b) R(fM)=Ω(n/log⁡n),R(f_\mathcal{M}) = \Omega(n / \log n),R(fM​)=Ω(n/logn), where R(f) denotes the bounded error randomized decision tree complexity of f; and (c) Q(fM)=Ω(n),Q(f_\mathcal{M}) = \Omega(\sqrt n),Q(fM​)=Ω(n​), where Q(f) denotes the bounded error quantum query complexity of f.
This chapter focuses on query complexity, which measures the minimum number of input bits that need to be read to solve a problem, in other words, the minimum depth of any correct decision tree (or branching program). Techniques for upper and lower bounds for deterministic and randomized query complexities are covered. The close relationships between query complexity and other measures known as certificate complexity and sensitivity are also covered. The chapter concludes with techniques for proving lower bounds on the size (as opposed to depth) of decision trees and branching programs.