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

Lecture notes in computer science

On the Power of Parity Queries in Boolean Decision Trees

Raghav Kulkarni, Youming Qiao, Xiaoming Sun

Published Jan 1, 2015• 1 citation
Publisher
DOI
10.1007/978-3-319-17142-5_10

Related papers

Parity decision tree in classical–quantum separations for certain classes of Boolean functions

Chandra Sekhar Mukherjee, Subhamoy Maitra

arXiv:2004.12942•Quantum Information Processing•Jun 1, 2021•5 citations

Lower bounds on quantum query complexity for decision trees

Hideaki Fukuhara, Eiji Takimoto

IEICE Technical Report; IEICE Tech. Rep.•Oct 3, 2008•0 citations

Complexity measures and decision tree complexity: a survey

Harry Buhrman, Ronald de Wolf

Theoretical Computer Science•Oct 1, 2002•707 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

Exact Quantum Query Algorithms Outperforming Parity -- Beyond The Symmetric functions

Chandra Sekhar Mukherjee, Subhamoy Maitra

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 ($Q_{algo}(f)$) for a direct sum based class of $Ω\left( 2^{\frac{\sqrt{n}}{2}} \right)$ 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_{\oplus}(f)$) analysing the Walsh Spectrum. Finally, we show that query complexity of $Q_{algo}$ is $\lceil \frac{3n}{4} \rceil$ whereas $D_{\oplus}(f)$ varies between $n-1$ and $\lceil \frac{3n}{4} \rceil+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 $\frac{n}{4}$) class of Maiorana-McFarland type functions, but could only obtain partial results using similar algorithmic techniques.

arXiv:2008.06317•Aug 14, 2020•0 citations

Hybrid Decision Trees: Longer Quantum Time is Strictly More Powerful

Xiaoming Sun, Yufan Zheng

In this paper, we introduce the hybrid query complexity, denoted as $\mathrm{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'\leq q$. We present the following results: $\bullet$ There exists a total Boolean function $f$ such that $\mathrm{Q}(f;1) = \widetilde{\mathcal{O}}(\mathrm{R}(f)^{4/5})$. $\bullet$ $\mathrm{Q}(f;q) = Ω(\mathrm{bs}(f)/q + \sqrt{\mathrm{bs}(f)})$ for any Boolean function $f$; the lower bound is tight when $f$ is the ${\rm O{\small R}}$ function. $\bullet$ $\mathrm{Q}(g \circ {\rm X{\small OR}}_{C \log n};1) = \widetildeΩ(\sqrt{n})$ for some sufficiently large constant $C$, where $g := {\rm B{\small OOL}S{\small IMON}}_n$ is a variant of Simon's problem. Note that $\mathrm{Q}(g\circ {\rm X{\small OR}}_{C \log n}) = \mathcal{O}(\mathrm{polylog}\; n)$. Therefore an exponential separation is established. Furthermore, this open the road to prove the conjecture $\forall k,\,\mathrm{Q}(g \circ {\rm X{\small OR}}_{C \log^{k+1} n};\log^{k} n) = \widetildeΩ(\sqrt{n})$, which would imply the oracle separation $\mathsf{HP}(\mathsf{QSIZE}(n^α))^\mathfrak{O} \subsetneq \mathsf{BQP}^\mathfrak{O}$ for any $α$, where $\mathsf{HP}(\mathsf{QSIZE}(n^α))$ is a complexity class that contains $\mathsf{BQTIME}(n^α)^{\mathsf{BPP}}$ and $\mathsf{BPP}^{\mathsf{BQTIME}(n^α)}$ in any relativized world.

arXiv:1911.13091•Nov 29, 2019•7 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.
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)Q_{algo}(f)Qalgo​(f)) for a direct sum based class of Ω(2n2)Ω\left( 2^{\frac{\sqrt{n}}{2}} \right)Ω(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)D_{\oplus}(f)D⊕​(f)) analysing the Walsh Spectrum. Finally, we show that query complexity of QalgoQ_{algo}Qalgo​ is ⌈3n4⌉\lceil \frac{3n}{4} \rceil⌈43n​⌉ whereas D⊕(f)D_{\oplus}(f)D⊕​(f) varies between n−1n-1n−1 and ⌈3n4⌉+1\lceil \frac{3n}{4} \rceil+1⌈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 n4\frac{n}{4}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)\mathrm{Q}(f;q)Q(f;q), which is the minimal query number needed to compute fff, when a classical decision tree is allowed to call q′q'q′-query quantum subroutines for any q′≤qq'\leq qq′≤q. We present the following results: ∙\bullet∙ There exists a total Boolean function fff such that Q(f;1)=O~(R(f)4/5)\mathrm{Q}(f;1) = \widetilde{\mathcal{O}}(\mathrm{R}(f)^{4/5})Q(f;1)=O(R(f)4/5). ∙\bullet∙ Q(f;q)=Ω(bs(f)/q+bs(f))\mathrm{Q}(f;q) = Ω(\mathrm{bs}(f)/q + \sqrt{\mathrm{bs}(f)})Q(f;q)=Ω(bs(f)/q+bs(f)​) for any Boolean function fff; the lower bound is tight when fff is the OR{\rm O{\small R}}OR function. ∙\bullet∙ Q(g∘XORClog⁡n;1)=Ω~(n)\mathrm{Q}(g \circ {\rm X{\small OR}}_{C \log n};1) = \widetildeΩ(\sqrt{n})Q(g∘XORClogn​;1)=Ω(n​) for some sufficiently large constant CCC, where g:=BOOLSIMONng := {\rm B{\small OOL}S{\small IMON}}_ng:=BOOLSIMONn​ is a variant of Simon's problem. Note that Q(g∘XORClog⁡n)=O(polylog  n)\mathrm{Q}(g\circ {\rm X{\small OR}}_{C \log n}) = \mathcal{O}(\mathrm{polylog}\; n)Q(g∘XORClogn​)=O(polylogn). Therefore an exponential separation is established. Furthermore, this open the road to prove the conjecture ∀k, Q(g∘XORClog⁡k+1n;log⁡kn)=Ω~(n)\forall k,\,\mathrm{Q}(g \circ {\rm X{\small OR}}_{C \log^{k+1} n};\log^{k} n) = \widetildeΩ(\sqrt{n})∀k,Q(g∘XORClogk+1n​;logkn)=Ω(n​), which would imply the oracle separation HP(QSIZE(nα))O⊊BQPO\mathsf{HP}(\mathsf{QSIZE}(n^α))^\mathfrak{O} \subsetneq \mathsf{BQP}^\mathfrak{O}HP(QSIZE(nα))O⊊BQPO for any ααα, where HP(QSIZE(nα))\mathsf{HP}(\mathsf{QSIZE}(n^α))HP(QSIZE(nα)) is a complexity class that contains BQTIME(nα)BPP\mathsf{BQTIME}(n^α)^{\mathsf{BPP}}BQTIME(nα)BPP and BPPBQTIME(nα)\mathsf{BPP}^{\mathsf{BQTIME}(n^α)}BPPBQTIME(nα) in any relativized world.